Examples

Contents:

• 1. Unconstrained convex minimization
  • 1.1. Gradient descent
  • 1.2. Subgradient method
  • 1.3. Subgradient method under restricted secant inequality and error bound
  • 1.4. Gradient descent with exact line search
  • 1.5. Conjugate gradient
  • 1.6. Heavy Ball momentum
  • 1.7. Accelerated gradient for convex objective
  • 1.8. Simplified accelerated gradient for convex objective
  • 1.9. Accelerated gradient for strongly convex objective
  • 1.10. Optimized gradient
  • 1.11. Optimized gradient for gradient
  • 1.12. Robust momentum
  • 1.13. Triple momentum
  • 1.14. Information theoretic exact method
  • 1.15. Cyclic coordinate descent
  • 1.16. Proximal point
  • 1.17. Accelerated proximal point
  • 1.18. Inexact gradient descent
  • 1.19. Inexact gradient descent with exact line search
  • 1.20. Inexact accelerated gradient
  • 1.21. Epsilon-subgradient method
  • 1.22. Gradient descent for quadratically upper bounded convex objective
  • 1.23. Gradient descent with decreasing step sizes for quadratically upper bounded convex objective
  • 1.24. Conjugate gradient for quadratically upper bounded convex objective
  • 1.25. Heavy Ball momentum for quadratically upper bounded convex objective
  • 1.26. Gradient descent for smooth strongly convex quadratic objective
  • 1.27. Gradient descent for smooth strongly convex objective with linear mapping
  • 1.28. Gradient descent with silver step-size for convex objective
  • 1.29. Gradient descent with silver step-size for strongly convex objective
• 2. Composite convex minimization
  • 2.1. Proximal gradient
  • 2.2. Proximal gradient on quadratics
  • 2.3. Accelerated proximal gradient (a.k.a., FISTA)
  • 2.4. Simplified accelerated proximal gradient
  • 2.5. Bregman proximal point
  • 2.6. Douglas Rachford splitting
  • 2.7. Douglas Rachford splitting contraction
  • 2.8. Accelerated Douglas Rachford splitting
  • 2.9. Frank Wolfe
  • 2.10. Improved interior method
  • 2.11. No Lips in function value
  • 2.12. No Lips in Bregman divergence
  • 2.13. Three operator splitting
• 3. Non-convex optimization
  • 3.1. Gradient Descent
  • 3.2. No Lips 1
  • 3.3. No Lips 2
  • 3.4. Gradient descent on smooth function satisfying quadratic Lojasiewicz inequality (naive version)
  • 3.5. Gradient descent on smooth function satisfying quadratic Lojasiewicz inequality (intermediate)
  • 3.6. Gradient descent on smooth function satisfying quadratic Lojasiewicz inequality (expensive version)
  • 3.7. Difference-of-convex algorithm (DCA)
• 4. Stochastic and randomized convex minimization
  • 4.1. Stochastic gradient descent
  • 4.2. Stochastic gradient descent in overparametrized setting
  • 4.3. SAGA
  • 4.4. Point SAGA
  • 4.5. Randomized coordinate descent for smooth strongly convex functions
  • 4.6. Randomized coordinate descent for smooth convex functions
• 5. Monotone inclusions and variational inequalities
  • 5.1. Proximal point
  • 5.2. Accelerated proximal point
  • 5.3. Optimal Strongly-monotone Proximal Point
  • 5.4. Douglas Rachford Splitting
  • 5.5. Douglas Rachford Splitting 2
  • 5.6. Three operator splitting
  • 5.7. Optimistic gradient
  • 5.8. Optimistic gradient (more expensive/less conservative version)
  • 5.9. Optimistic gradient, cocoercive problem (more expensive/less conservative version)
  • 5.10. Past extragradient
• 6. Fixed point
  • 6.1. Halpern iteration
  • 6.2. Optimal Contractive Halpern iteration
  • 6.3. Krasnoselskii-Mann with constant step-sizes
  • 6.4. Krasnoselskii-Mann with increasing step-sizes
  • 6.5. Inconsistent Halpern iteration
• 7. Potential functions
  • 7.1. Gradient descent Lyapunov 1
  • 7.2. Gradient descent Lyapunov 2
  • 7.3. Accelerated gradient method
• 8. Inexact proximal methods
  • 8.1. Accelerated inexact forward backward
  • 8.2. Partially inexact Douglas Rachford splitting
  • 8.3. Relatively inexact proximal point
• 9. Adaptive methods
  • 9.1. Polyak steps in distance to optimum
  • 9.2. Polyak steps in function value
• 10. Continuous-time models
  • 10.1. Gradient flow for strongly convex functions
  • 10.2. Gradient flow for convex functions
  • 10.3. Accelerated gradient flow for strongly convex functions
  • 10.4. Accelerated gradient flow for convex functions
• 11. Online learning and convex optimization
  • 11.1. Online gradient descent (OGD)
  • 11.2. Online Frank-Wolfe (OFW)
  • 11.3. Follow-the-leader (FTL)
  • 11.4. Follow-the-regularized-leader (FTRL)
• 12. Low dimensional worst-cases scenarios
  • 12.1. Inexact gradient
  • 12.2. Non-convex gradient descent
  • 12.3. Optimized gradient
  • 12.4. Frank Wolfe
  • 12.5. Proximal point
  • 12.6. Halpern iteration
  • 12.7. Alternate projections
  • 12.8. Averaged projections
  • 12.9. Dykstra
• 13. Tutorials
  • 13.1. Contraction rate of gradient descent