Spectral Norm in Learning Theory: Some Selected Topics
Abstract
In this paper, we review some known results that relate the statistical query complexity of a concept class to the spectral norm of its correlation matrix. Since spectral norms are widely used in various other areas, we are then able to put statistical query complexity in a broader context. We briefly describe some non-trivial connections to (seemingly) different topics in learning theory, complexity theory, and cryptography. A connection to the so-called Hidden Number Problem, which plays an important role for proving bit-security of cryptographic functions, will be discussed in somewhat more detail.
Cite
Text
Simon. "Spectral Norm in Learning Theory: Some Selected Topics." International Conference on Algorithmic Learning Theory, 2006. doi:10.1007/11894841_4Markdown
[Simon. "Spectral Norm in Learning Theory: Some Selected Topics." International Conference on Algorithmic Learning Theory, 2006.](https://mlanthology.org/alt/2006/simon2006alt-spectral/) doi:10.1007/11894841_4BibTeX
@inproceedings{simon2006alt-spectral,
title = {{Spectral Norm in Learning Theory: Some Selected Topics}},
author = {Simon, Hans Ulrich},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2006},
pages = {13-27},
doi = {10.1007/11894841_4},
url = {https://mlanthology.org/alt/2006/simon2006alt-spectral/}
}