Optimization Theory for Machine Learning: Convex & Non-Convex Methods
Module: AI/ML Premium | Difficulty: PhD Level | Prerequisites: Linear Algebra, Real Analysis
1. Convex Optimization Foundations
1.1 Convex Sets and Functions
2. Gradient Descent Analysis
2.1 Basic Gradient Descent
2.2 Convergence Analysis
3. Stochastic Gradient Descent
3.1 SGD with Momentum
3.2 Adaptive Learning Rate Methods
4. Second-Order Methods
4.1 Newton's Method
4.2 Quasi-Newton Methods
5. Non-Convex Optimization
5.1 Landscape Analysis
5.2 Escaping Saddle Points
6. Learning Rate Schedules
7. Distributed Optimization
7.1 Data Parallelism
7.2 Communication Efficiency
| Method | Communication | Compression |
|---|---|---|
| AllReduce | per worker | None |
| Gradient Compression | Top-k, Random-k | |
| Local SGD | Periodic sync | None |
| Federated Averaging | per round | Differential Privacy |
8. Convergence Proofs
8.1 Proof Sketch for SGD
Summary
| Method | Per-iteration Cost | Convergence | Best For |
|---|---|---|---|
| Gradient Descent | Convex | ||
| SGD | Large-scale | ||
| SGD+Momentum | Deep learning | ||
| Adam | Sparse/NLP | ||
| Newton | Small-scale | ||
| L-BFGS | Superlinear | Medium-scale |
Research Frontier: Adaptive methods with provable generalization guarantees remain an open problem. Recent work on Sharpness-Aware Minimization (SAM) connects optimization geometry to generalization.