Stochastic Gradient and Coordinate Descent
Stub. Two ways to make each iteration of descent cheaper than a full gradient step: stochastic gradient (noisy gradients, the incremental gradient method, the perceptron, empirical risk minimization, the randomized Kaczmarz method, convergence analysis under several noise models, and implementation details like epochs/minibatching/momentum), and coordinate descent (updating one coordinate — or a block — at a time, with randomized, cyclic, and random-permutation sampling orders and their different convergence guarantees).
Corresponds to Chapters 5–6. Both methods trade exactness for speed per iteration. Stochastic gradient replaces the true gradient (a sum over a whole dataset, e.g. in empirical risk minimization) with a cheap, unbiased estimate from one or a few samples — the randomness this introduces is analyzed rigorously as exactly the kind of random dynamical system covered elsewhere in this vault, under several different noise models (bounded gradients, the randomized Kaczmarz method for linear systems, additive Gaussian noise, incremental gradient), with practical implementation choices (epochs, minibatching, combining with momentum) covered alongside the theory. Coordinate descent instead keeps the gradient exact but only updates one coordinate (or a block of coordinates) per step, which is cheap when each coordinate’s update has a simple closed form; covers the Lipschitz-constant bookkeeping this needs and how the convergence guarantee depends on whether coordinates are chosen randomly (with or without replacement), cyclically, or in a random permutation each pass.
Outline (TODO — flesh out each)
- Examples and motivation — noisy gradients, incremental gradient, the perceptron, empirical risk minimization
- Randomness and steplength — computing a mean, the randomized Kaczmarz method
- Key assumptions for convergence analysis (bounded gradients, Kaczmarz, additive Gaussian noise, incremental gradient)
- Convergence analysis under each assumption
- Implementation — epochs, minibatching, momentum
- Coordinate descent in machine learning
- Coordinate descent for smooth convex functions — Lipschitz constants
- Randomized CD (with replacement), cyclic CD, random-permutations CD
- Block-coordinate descent