Chapter 3

Basics — Stochastic Optimization

Stochastic optimization is classical wisdom in motion!

In this chapter, we introduce standard stochastic optimization problems and present key stochastic optimization algorithms along with their complexity analysis. While many important stochastic algorithms have been proposed for solving stochastic optimization and empirical risk minimization problems, we focus on seven foundational methods that gained prominence before the deep learning era. These algorithms have had a profound impact on machine learning and provide essential insights for understanding more advanced methods presented in later chapters. The selected algorithms include stochastic gradient descent (SGD), stochastic proximal gradient descent, stochastic mirror descent, adaptive gradient methods, stochastic coordinate descent, stochastic gradient descent-ascent, and stochastic optimistic mirror prox. Except for SGD, we concentrate on the complexity analysis in the convex setting.

---

Contents

• 3.1 Stochastic Gradient Descent
• 3.2 Stochastic Proximal Gradient Descent
• 3.3 Stochastic Coordinate Descent
• 3.4 Stochastic Mirror Descent
• 3.5 Adaptive Gradient Method (AdaGrad)
• 3.6 Stochastic Gradient Descent Ascent
• 3.7 Stochastic Optimistic Mirror Prox
• 3.8 Notes and Discussion