Cited By
View all- Linial NShraibman A(2009)Learning complexity vs communication complexityCombinatorics, Probability and Computing10.1017/S096354830800965618:1-2(227-245)Online publication date: 1-Mar-2009
On the limitations of embedding methods
Pages 353 - 365
Abstract
We show that for any class of functions H which has a reasonable combinatorial dimension, the vast majority of small subsets of the combinatorial cube can not be represented as a Lipschitz image of a subset of H, unless the Lipschitz constant is very large. We apply this result to the case when H consists of linear functionals of norm at most one on a Hilbert space, and thus show that “most” classification problems can not be represented as a reasonable Lipschitz loss of a kernel class.
References
[1]
F. Barthe, O. Guédon, S. Mendelson, A. Naor, A probabilistic approach to the geometry of the lp p ball, Annals of Probability, 33 (2) 480-513, 2005.
[2]
S. Ben-David, N. Eiron, H.U. Simon, Limitations of learning via embeddings in Euclidean half spaces, Journal of Machine Learning Research 3, 441-461, 2002.
[3]
B. Bollobás, Extremal graph theory, Academic Press, 1978.
[4]
J. Forster, N. Schmitt, and H.U. Simon, Estimating the optimal margins of embeddings in Euclidean halfspaces, in Proceedings of the 14th Annual Conference on Computational Learning Theory, 2001, LNCS volume 2111, 402-415. Springer, Berlin, 2001.
[5]
M. Ledoux, M. Talagrand, Probability in Banach spaces, Springer, 1991.
[6]
N. Linial, S. Mendelson, G. Schechtman, A. Shraibman, Complexity measures of sign matrices, preprint.
[7]
S. Mendelson, R. Vershynin, Entropy and the combinatorial dimension, Inventiones Mathematicae, 152(1), 37-55, 2003.
[8]
S. Mendelson, G. Schechtman, The shattering dimension of sets of linear functionals, Annals of Probability, 32 (3A), 1746-1770, 2004.
[9]
S. Mendelson, Embedding with a Lipschitz function, Random Structures and Algorithms, to appear (available on the journal's web-page).
[10]
V.D. Milman, G. Schechtman, Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Mathematics 1200, Springer, 1986.
[11]
A. Pajor, Sous espaces l1 n des espaces de Banach, Hermann, Paris, 1985.
[12]
G. Pisier, The volume of convex bodies and Banach space geometry, Cambridge University Press, 1989.
[13]
A.W. Van der Vaart, J.A. Wellner, Weak convergence and Empirical Processes, Springer-Verlag, 1996.
Recommendations
On the semilocal convergence of inexact Newton methods in Banach spaces
We provide two types of semilocal convergence theorems for approximating a solution of an equation in a Banach space setting using an inexact Newton method [I.K. Argyros, Relation between forcing sequences and inexact Newton iterates in Banach spaces, ...
Superlinearly convergent approximate Newton methods for LC1 optimization problems
In the literature, the proof of superlinear convergence of approximate Newton or SQP methods for solving nonlinear programming problems requires twice smoothness of the objective and constraint functions. Sometimes, the second-order derivatives of those ...
On the convergence of Newton-type methods using recurrent functions
We introduce the new idea of recurrent functions to provide a new semilocal convergence analysis for Newton-type methods. It turns out that our sufficient convergence conditions are weaker, and the error bounds are tighter than in earlier studies in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Pascal
- Google Inc.
- Machine Learning Journal/Springer
- BiCi
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 27 June 2005
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
Cited By
View all- Linial NShraibman A(2009)Learning complexity vs communication complexityCombinatorics, Probability and Computing10.1017/S096354830800965618:1-2(227-245)Online publication date: 1-Mar-2009