Blog · Collection
Machine learning theory
The statistics and optimization behind machine learning: gradient methods and convexity, learning theory with VC dimension and covering numbers, and sparse high-dimensional estimation.
Machine learning theory looks at the subject from two angles: how to fit models efficiently, which is optimization, and why fitted models generalize, which is statistics.
Optimization
Least squares has a closed-form solution, but forming and solving the normal equations costs operations, so large problems call for iterative methods. For a smooth convex loss, gradient descent reaches accuracy in iterations, and strong convexity improves this to a linear rate. Stochastic gradient descent uses one random example per step, trading noise for much cheaper iterations, which is the right trade when is huge. Newton’s method converges quadratically near the optimum and is unaffected by linear changes of variables. Nonsmooth problems such as support vector machines need subgradients, coordinate descent or proximal methods.
Learning theory
The central question is how far a learned predictor’s test error can be from its training error. For a finite class of hypotheses , a union bound gives a gap of order . For infinite classes, the VC dimension takes the place of . The Sauer lemma shows that a class with VC dimension can label points in at most ways, which leads to generalization bounds of order . Covering numbers extend the argument to real-valued function classes, including balls in a reproducing kernel Hilbert space.
Sparse high-dimensional learning
When but only coefficients are nonzero, the lasso estimates the coefficient vector with squared error of order , provided the design satisfies a restricted eigenvalue condition. A minimax lower bound shows that no method can do fundamentally better. Proximal gradient methods with Nesterov acceleration solve the lasso efficiently, and nonconvex penalties can reduce its bias while remaining computationally tractable under the right conditions.
Deep and unsupervised learning
Neural networks raise the puzzle of why their nonconvex training works so well in practice, and unsupervised methods such as -means clustering ask what can be learned without labels.