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