Chapter 4

Foundations — Stochastic Compositional Optimization

Moving average is all you need!

In this chapter, we introduce stochastic compositional optimization problems and their optimization algorithms, including stochastic gradient descent and stochastic compositional gradient descent, and stochastic compositional momentum methods. We also consider extensions of these techniques to structured optimization including min-max optimization, min-min optimization and bilevel optimization. We focus on the complexity of these methods for non-convex optimization.

---

Contents

• 4.1 Stochastic Compositional Optimization
• 4.2 Stochastic Compositional Gradient Descent
• 4.3 Stochastic Compositional Momentum Methods
• 4.4 Non-smooth (Non-convex) Regularized Problems
• 4.5 Structured Optimization with Compositional Gradient
• 4.6 Notes and Discussion