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 O(np2+p3)O(np^2 + p^3) operations, so large problems call for iterative methods. For a smooth convex loss, gradient descent reaches accuracy ε\varepsilon in O(1/ε)O(1/\varepsilon) 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 nn 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 H\mathcal{H}, a union bound gives a gap of order log⁡∣H∣/n\sqrt{\log|\mathcal{H}|/n}. For infinite classes, the VC dimension takes the place of log⁡∣H∣\log|\mathcal{H}|. The Sauer lemma shows that a class with VC dimension dd can label nn points in at most O(nd)O(n^d) ways, which leads to generalization bounds of order dlog⁡n/n\sqrt{d \log n / n}. Covering numbers extend the argument to real-valued function classes, including balls in a reproducing kernel Hilbert space.

Sparse high-dimensional learning

When p≫np \gg n but only ss coefficients are nonzero, the lasso estimates the coefficient vector with squared error of order slog⁡p/ns \log p / n, 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 kk-means clustering ask what can be learned without labels.

← All collections