Convex optimization

Notes:

• Duality (BV Ch. 5)
  • SDP duality
• Convex problems
• First-order methods
  • Gradient descent (BV Ch. 9)
  • Mirror descent
  • AGD by coupling
  • AGD, intuition by Chebyshev - actually covers conjugate gradients.
• Second-order methods
  • Newton’s method (BV Ch. 9)
• Constrained optimization (BV Ch. 10)
• Interior point methods (BV Ch. 11)
• Ellipsoid method
• Stochastic and online methods
  • SGD
  • SGD variance reduction (SAGA, SVRG)
• Bandit convex optimization (OCO Ch. 6)

To learn about:

• Accelerated gradient descent (see Bubeck, Moritz, Nesterov) (? see also: a universal catalyst, 4-12-16, S15 in alg-ml)
• AH15 Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier paper (see also: 2 cultures)
• Review online/bandit methods
• Bandit algorithms—recent progress by Bubeck.
• Ellipsoid method
  • Yin-Tat Lee’s improvements.
• Sampling methods
  • Two cultures
  • CV16 Gaussian cooling paper and followup. See Karan’s talk in alg-ml S4.
• Allen-Zhu’s work. Posts from Minimizing regret
  • ICML 2016 papers.
  • Improvements since SGD
  • OCO
  • Classification and regression
  • Reductions
  • LiSSA
• Recht on SGD
• ? Belief propagation
• Optimization on manifolds—write up notes.