Dissertation · 2016 · Open access

The complexity of algorithmic hypothesis class

Tongliang Liu

UTS ePRESS (University of Technology Sydney) · Published 1 January 2016

Open full textCite this paper

In brief

“The complexity of algorithmic hypothesis class” is a 2016 dissertation by Tongliang Liu, published in UTS ePRESS (University of Technology Sydney). OpenAlex counts 0 citations as of 18 November 2026. It is open access: the full text is free to read at UTS ePRESS (University of Technology Sydney).

Citations
0
References
110
Authors
1

Abstract

Statistical learning theory provides the mathematical and theoretical foundations for statistical learning algorithms and inspires the development of more efficient methods. It is observed that learning algorithms may not output some hypotheses in the predefined hypothesis class. Therefore, in this thesis, we focus on statistical learning theory and study how to measure the complexity of the algorithmic hypothesis class, which is a subset of the predefined hypothesis class that a learning algorithm will (or is likely to) output. By designing complexity measures for the algorithmic hypothesis class, we provide new generalization bounds for k-dimensional coding schemes and multi-task learning and propose two frameworks to derive tighter generalization bounds than the current state-of-the-art. \nWe take k-dimensional coding schemes, a set of unsupervised learning algorithms, and multi-task learning, a set of supervised learning algorithms, as examples to demonstrate that learning algorithm outputs may have special properties and are therefore included in a subset of the predefined hypothesis class. By analyzing the subsets (or the algorithmic hypothesis classes), we shed new light on learning problems and derive tighter generalization bounds than the current state-of-the-art. Specifically, for k-dimensional coding schemes, we show that the induced algorithmic loss function classes are sets of Lipschitz-continuous hypotheses and that a dimensionality-dependent complexity measure helps to derive small Lipschitz constants and thus improve the generalization bounds. For multi-task learning, we prove that tasks can act as regularizer and that feature structures can contribute to a small algorithmic hypothesis class and also help to improve the generalization bounds. \nTo more precisely exploit algorithmic hypothesis class complexity by considering the hypothesis and feature structure properties, we extend algorithmic robustness and stability to complexity measures for the hypothesis class. \nInspired by the idea of algorithmic robustness, we propose the complexity measure of uniform robustness. Compared to the Rademacher complexity, our measure more finely considers the geometric information of data. For example, when the sample space is covered by a small number of small radius and widely separated balls, the uniform robustness can be very small while the Rademacher complexity can be very large. Moreover, based on the definition of uniform robustness, we also provide a framework to derive generalization bounds for a very general class of learning algorithms. \nWe exploit the algorithmic hypothesis class of stable algorithms by studying the definition of algorithmic stability. Stable learning algorithms have the property that their outputs will not change much when one training example is changed. This implies that their outputs will not be sufficiently far apart, even though the training sample is completely…

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Liu, T. (2016). The complexity of algorithmic hypothesis class. UTS ePRESS (University of Technology Sydney). http://hdl.handle.net/10453/52375

MLA 9

Liu, Tongliang. “The complexity of algorithmic hypothesis class.” UTS ePRESS (University of Technology Sydney), 2016. http://hdl.handle.net/10453/52375.

Chicago

Liu, Tongliang. 2016. “The complexity of algorithmic hypothesis class.” UTS ePRESS (University of Technology Sydney). http://hdl.handle.net/10453/52375.

Harvard

Liu, T. (2016) ‘The complexity of algorithmic hypothesis class’, UTS ePRESS (University of Technology Sydney). Available at: http://hdl.handle.net/10453/52375.

IEEE

T. Liu, “The complexity of algorithmic hypothesis class,” UTS ePRESS (University of Technology Sydney), 2016.

BibTeX

@phdthesis{liu2016complexity,
  title     = {{The complexity of algorithmic hypothesis class}},
  author    = {Liu, Tongliang},
  year      = {2016},
  url       = {http://hdl.handle.net/10453/52375}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Topic and keywords

Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms

  • generalization bounds
  • multi-task learning
  • Rademacher complexity
  • algorithm stability
  • algorithmic robustness
  • feature structures
  • unsupervised learning
  • supervised learning

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Liu, T. (2016). The complexity of algorithmic hypothesis class. UTS ePRESS (University of Technology Sydney). http://hdl.handle.net/10453/52375

How many times has this paper been cited?

0 times, according to OpenAlex on 18 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at UTS ePRESS (University of Technology Sydney): sign in and open the full text from this page.

Who wrote this paper?

Tongliang Liu.

Bibliographic data from OpenAlex (CC0), last checked 18 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.