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. Accelerated gradient for strongly convex objective
  • 1.9. Optimized gradient
  • 1.10. Optimized gradient for gradient
  • 1.11. Robust momentum
  • 1.12. Triple momentum
  • 1.13. Information theoretic exact method
  • 1.14. Cyclic coordinate descent
  • 1.15. Proximal point
  • 1.16. Accelerated proximal point
  • 1.17. Inexact gradient descent
  • 1.18. Inexact gradient descent with exact line search
  • 1.19. Inexact accelerated gradient
  • 1.20. Epsilon-subgradient method
  • 1.21. Gradient descent for quadratically upper bounded convex objective
  • 1.22. Gradient descent with decreasing step sizes for quadratically upper bounded convex objective
  • 1.23. Conjugate gradient for quadratically upper bounded convex objective
  • 1.24. Heavy Ball momentum for quadratically upper bounded convex objective
  • 1.25. Gradient descent for smooth strongly convex quadratic objective
  • 1.26. Gradient descent for smooth strongly convex objective with linear mapping
• 2. Composite convex minimization
  • 2.1. Proximal gradient
  • 2.2. Accelerated proximal gradient
  • 2.3. Bregman proximal point
  • 2.4. Douglas Rachford splitting
  • 2.5. Douglas Rachford splitting contraction
  • 2.6. Accelerated Douglas Rachford splitting
  • 2.7. Frank Wolfe
  • 2.8. Improved interior method
  • 2.9. No Lips in function value
  • 2.10. No Lips in Bregman divergence
  • 2.11. Three operator splitting
• 3. Non-convex optimization
  • 3.1. Gradient Descent
  • 3.2. No Lips 1
  • 3.3. No Lips 2
• 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. Three operator splitting
  • 5.6. Optimistic gradient
  • 5.7. 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. Low dimensional worst-cases scenarios
  • 10.1. Inexact gradient
  • 10.2. Non-convex gradient descent
  • 10.3. Optimized gradient
  • 10.4. Frank Wolfe
  • 10.5. Proximal point
  • 10.6. Halpern iteration
  • 10.7. Alternate projections
  • 10.8. Averaged projections
  • 10.9. Dykstra
• 11. Continuous-time models
  • 11.1. Gradient flow for strongly convex functions
  • 11.2. Gradient flow for convex functions
  • 11.3. Accelerated gradient flow for strongly convex functions
  • 11.4. Accelerated gradient flow for convex functions
• 12. Tutorials
  • 12.1. Contraction rate of gradient descent