---
id: FOUND-010
title: "Optimization and Gradient Descent"
alternative_names:
  - "Numerical Optimization for Machine Learning"
  - "Stochastic Gradient Descent"
category: "Foundations → Mathematics"
volume: I
chapter: 3
entry_type: "Standard Article"
level: 3
status: "Draft"
last_reviewed: 2026-10-15
version: "0.1.0"
prerequisites:
  - "FOUND-008"
related_entries:
  - "FOUND-007"
  - "FOUND-009"
  - "TECH-BACKPROP-001"
  - "TECH-DL-001"
  - "HIST-008"
---

# Optimization and Gradient Descent

## 1. Concise Definition
**Optimization** is the problem of finding parameters that minimize (or maximize) an objective function, possibly subject to constraints. **Gradient descent** is an iterative first-order method that repeatedly moves the parameters in the direction of the negative gradient of the objective; its stochastic variants, which estimate the gradient from small random subsets of data, are the standard means of training neural networks.

## 2. Overview & Significance
Most machine learning is framed as minimizing a loss $L(\theta)$ over parameters $\theta$ ([[FOUND-007] Learning, Reasoning and Generalization](FOUND-007_learning_reasoning_and_generalization.md)). Whether a model learns well depends on its architecture and data, and also on how the optimizer navigates the loss landscape. In deep learning the parameter count can be very large and the loss is non-convex, so exact minimization is infeasible and the relevant questions become: how fast does the method make progress, where does it end up, and how does the end point generalize?

Gradient-based training became practical through backpropagation, which computes gradients of a network's loss efficiently (Rumelhart et al., 1986; see [[TECH-BACKPROP-001] Backpropagation](../vol03_technical/TECH-BACKPROP-001_backpropagation.md)). Optimization is thus the link between a model specification and a trained system, and choices such as learning rate, batch size and optimizer are significant engineering decisions in large-scale training ([[TECH-DL-001] Deep Learning](../vol03_technical/TECH-DL-001_deep_learning.md)).

## 3. Historical Development
Gradient descent is usually attributed to Cauchy in the nineteenth century. This article does not cite the primary source and treats the attribution as conventional. [VERIFICATION NEEDED: primary source for the Cauchy attribution] Robbins and Monro (1951) introduced stochastic approximation, the basis of stochastic gradient descent (SGD): iterating with noisy gradient estimates and decreasing step sizes converges under conditions. Polyak (1964) introduced the heavy-ball momentum method to speed convergence on ill-conditioned problems.

Rumelhart, Hinton and Williams (1986) showed that gradient descent with backpropagated gradients could train multi-layer networks to learn useful internal representations, a milestone in the connectionist revival ([[HIST-008] Backpropagation and the Connectionist Revival](../vol02_history/HIST-008_backpropagation_and_the_connectionist_revival.md)). Adaptive per-parameter methods followed, including Adam (Kingma & Ba, 2015), and Loshchilov and Hutter (2019) proposed decoupling weight decay from the gradient update (AdamW). Bottou, Curtis and Nocedal (2018) provide a comprehensive review of optimization methods for large-scale machine learning. Standard theoretical background in convex optimization is in Boyd and Vandenberghe (2004), and a deep-learning-oriented treatment is in Goodfellow, Bengio and Courville (2016).

## 4. Technical / Conceptual Explanation

### 4.1 Gradient descent
For a differentiable objective $L(\theta)$, gradient descent iterates
$$\theta_{t+1} = \theta_t - \eta\,\nabla L(\theta_t),$$
where $\eta > 0$ is the **learning rate**. The negative gradient is the direction of steepest local decrease. For a convex function whose gradient is $\beta$-Lipschitz ($\beta$-smooth), the choice $\eta = 1/\beta$ gives $L(\theta_k) - L(\theta^*) = O(1/k)$, a standard result (Boyd & Vandenberghe, 2004; Bottou et al., 2018). For strongly convex functions the convergence is linear (geometric). Neither guarantee applies directly to neural-network losses, which are non-convex.

### 4.2 Stochastic and mini-batch gradients
With a training objective $L(\theta) = \frac{1}{N}\sum_{i=1}^N \ell_i(\theta)$, computing the full gradient costs $O(N)$ per step. SGD replaces it with an unbiased estimate from a random mini-batch $B$:
$$\theta_{t+1} = \theta_t - \eta_t\,\frac{1}{|B|}\sum_{i \in B}\nabla \ell_i(\theta_t).$$
Each step is cheap, and the noise can help escape poor regions. Convergence analyses require step sizes that decay or are small enough to control variance (Robbins & Monro, 1951; Bottou et al., 2018). Larger batches reduce gradient variance but increase cost per step.

### 4.3 Momentum
Momentum accumulates a velocity:
$$v_{t+1} = \mu v_t - \eta\,\nabla L(\theta_t), \qquad \theta_{t+1} = \theta_t + v_{t+1},$$
with $\mu \in [0,1)$. It damps oscillations in directions of high curvature and accelerates progress along consistent directions (Polyak, 1964).

### 4.4 Adaptive methods
Adam maintains exponential moving averages of the gradient $g_t$ and its square:
$$m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t, \qquad v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2,$$
and updates $\theta_{t+1} = \theta_t - \eta\,\hat m_t / (\sqrt{\hat v_t} + \epsilon)$, where $\hat m_t$ and $\hat v_t$ are bias-corrected (Kingma & Ba, 2015). Each parameter thus has its own effective step size. AdamW applies weight decay directly to the parameters, separately from the adaptive gradient scaling (Loshchilov & Hutter, 2019).

### 4.5 Learning-rate schedules and practicalities
Learning rate is typically varied over training (warm-up, decay). Gradient clipping, normalization layers and mixed-precision arithmetic address numerical stability. The choices are largely empirical; no single schedule is optimal across problems.

### 4.6 The loss landscape
Neural-network losses have many parameters, saddle points and flat regions. Dauphin et al. (2014) argued, using ideas from statistical physics and empirical evidence, that in high dimensions saddle points rather than poor local minima are the principal obstacle to optimization. Choromanska et al. (2015) analysed the loss surfaces of multilayer networks under simplifying assumptions and related the structure of critical points to network size. These analyses rely on assumptions that do not fully match practical networks, and they are best regarded as suggestive.

### 4.7 Regularization as optimization
Explicit penalties (for example, $L_2$ weight decay) change the objective; optimizer choice and early stopping act as implicit regularizers. Which solutions SGD-like methods select among the many that fit the training data, and why those solutions generalize, is a research question.

## 5. Types, Components & Classifications
- **First-order methods**: gradient descent, SGD, momentum, Nesterov-type acceleration, adaptive methods (AdaGrad, RMSProp, Adam, AdamW).
- **Second-order and quasi-Newton methods**: use curvature information (Hessian approximations); costly for models with very many parameters, so used mainly at smaller scale or through approximations.
- **Derivative-free and evolutionary methods**: used where gradients are unavailable (black-box tuning, some reinforcement learning settings).
- **Convex versus non-convex problems**: convex problems have global-optimality guarantees (Boyd & Vandenberghe, 2004); neural-network training is non-convex.
- **Constrained and discrete optimization**: relevant to planning, scheduling and combinatorial search ([[FOUND-004] Computational Complexity in AI](FOUND-004_computational_complexity.md)).

## 6. Applications & Concrete Examples
- **Training neural networks** with SGD or Adam-family optimizers is the standard practice in deep learning (Kingma & Ba, 2015; Goodfellow et al., 2016). The AdamW variant is widely used for transformer training; because training recipes change, current practice should be checked against recent technical reports and the relevant Living Reference entries.
- **Linear and logistic regression, support vector machines**: convex problems solved by gradient or quasi-Newton methods (Bishop, 2006).
- **Large-batch training.** Keskar et al. (2017) reported that large-batch methods tended to converge to sharper minima and showed a generalization gap in their experiments. Subsequent work has examined whether the gap is intrinsic or can be mitigated with tuning; the conclusion in the original paper is therefore **Contested** in general.
- **Adaptive versus non-adaptive generalization.** Wilson et al. (2017) reported cases in which adaptive methods generalized worse than SGD with momentum when tuned comparably; this does not imply that adaptive methods are inferior in general.

## 7. Advantages, Limitations & Unresolved Questions
**Strengths.** Gradient methods are simple, scale to billions of parameters when combined with data and model parallelism, and work with any differentiable model.

**Limitations.**
- No global-optimality guarantee for non-convex losses.
- Sensitivity to hyperparameters (learning rate, batch size, schedule); instability and divergence are common failure modes.
- Vanishing and exploding gradients in deep or recurrent architectures.
- Optimizing a proxy loss does not guarantee that the downstream objective is met; a model can minimize its training loss while failing on goals the loss does not capture (relevant to [[SAFE-ALIGN-001] AI Alignment](../vol08_safety_governance/SAFE-ALIGN-001_ai_alignment.md)).

**Open questions.** Why simple first-order methods find solutions that generalize in over-parameterized networks; the relationship between flat minima and generalization (Keskar et al., 2017, and critics); whether the saddle-point picture of Dauphin et al. (2014) fully accounts for training dynamics; and optimizer behaviour at frontier scale.

## 8. Current State of Knowledge
As of 2026-10-15:
- Convergence results for convex smooth objectives and for SGD under standard assumptions are **Established** (Boyd & Vandenberghe, 2004; Bottou et al., 2018).
- SGD and Adam-family optimizers are the dominant practical choice for training neural networks (Goodfellow et al., 2016; Kingma & Ba, 2015); specific hyperparameters used by named frontier models are mostly undisclosed or change quickly and are not tabulated here.
- The relative generalization of adaptive and non-adaptive methods, and the role of batch size and sharpness, are **Contested** (Wilson et al., 2017; Keskar et al., 2017).
- The picture that saddle points rather than local minima dominate difficulty in high dimensions is **Preliminary** to **Well Supported**, depending on the model class (Dauphin et al., 2014; Choromanska et al., 2015).

## 9. Future Trajectory & Strategic Outlook
No registered forecast is made. Observed research directions include second-order and preconditioned methods that remain tractable at scale, optimizers designed for very large batch sizes and low-precision arithmetic, and theory of implicit regularization. Near-term change is likely to be incremental refinements of existing optimizers rather than replacement of gradient-based training. Claims that a particular new optimizer will supersede Adam-family methods should be evaluated against independent, well-tuned baselines.

## 10. Related Entries & Knowledge Graph
- **Foundational Concepts**:
  - [[FOUND-008] Probability, Statistics and Bayesian Inference](FOUND-008_probability_statistics_and_bayesian_inference.md): likelihood objectives that are optimized.
  - [[FOUND-007] Learning, Reasoning and Generalization](FOUND-007_learning_reasoning_and_generalization.md): empirical risk minimization and generalization.
  - [[FOUND-009] Information Theory](FOUND-009_information_theory.md): cross-entropy losses.
- **Related Methods & Technologies**:
  - [[TECH-BACKPROP-001] Backpropagation](../vol03_technical/TECH-BACKPROP-001_backpropagation.md): computing the gradients.
  - [[TECH-DL-001] Deep Learning](../vol03_technical/TECH-DL-001_deep_learning.md): the main application setting.
  - [[TECH-RL-001] Reinforcement Learning](../vol03_technical/TECH-RL-001_reinforcement_learning.md): policy-gradient optimization.
  - [[HIST-008] Backpropagation and the Connectionist Revival](../vol02_history/HIST-008_backpropagation_and_the_connectionist_revival.md): the historical context.
- **Advanced Implications & Future Trajectories**:
  - [[TECH-SCALE-001] Scaling Laws](../vol03_technical/TECH-SCALE-001_scaling_laws.md): how loss behaves under optimization at scale.
  - [[SAFE-ALIGN-001] AI Alignment](../vol08_safety_governance/SAFE-ALIGN-001_ai_alignment.md): optimization of proxy objectives.

## 11. References & Foundational Literature
1. Robbins, H., & Monro, S. (1951). A stochastic approximation method. *The Annals of Mathematical Statistics*, 22(3), 400-407. https://doi.org/10.1214/aoms/1177729586. [Foundation of stochastic gradient methods. Checked against Crossref.]
2. Polyak, B. T. (1964). Some methods of speeding up the convergence of iteration methods. *USSR Computational Mathematics and Mathematical Physics*, 4(5), 1-17. https://doi.org/10.1016/0041-5553(64)90137-5. [Heavy-ball momentum. Checked against Crossref.]
3. Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. *Nature*, 323(6088), 533-536. https://doi.org/10.1038/323533a0. [Gradient descent with backpropagation for multi-layer networks. Checked against Crossref.]
4. Kingma, D. P., & Ba, J. (2015). Adam: A method for stochastic optimization. *International Conference on Learning Representations (ICLR 2015)*. arXiv:1412.6980. [Adam optimizer. Authors and title checked against arXiv page; venue from author knowledge.]
5. Loshchilov, I., & Hutter, F. (2019). Decoupled weight decay regularization. *International Conference on Learning Representations (ICLR 2019)*. arXiv:1711.05101. [AdamW. Authors and title checked against arXiv page; venue from author knowledge.]
6. Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization methods for large-scale machine learning. *SIAM Review*, 60(2), 223-311. https://doi.org/10.1137/16M1080173. [Review and convergence analysis of SGD-type methods. Checked against Crossref.]
7. Boyd, S., & Vandenberghe, L. (2004). *Convex Optimization*. Cambridge University Press. ISBN 978-0521833783. [Convex optimization theory and convergence results. ISBN checked against Open Library (Open Library lists first author Boyd).]
8. Goodfellow, I., Bengio, Y., & Courville, A. (2016). *Deep Learning*. MIT Press. ISBN 978-0262035613. [Textbook source for optimization in deep learning. Checked against Open Library.]
9. Bishop, C. M. (2006). *Pattern Recognition and Machine Learning*. Springer. ISBN 978-0387310732. [Convex learning problems such as logistic regression. Checked against Open Library.]
10. Dauphin, Y., et al. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. *Advances in Neural Information Processing Systems (NeurIPS 2014)*. arXiv:1406.2572. [Argues that saddle points are a principal obstacle in high dimensions. Six authors confirmed on arXiv; venue from author knowledge.]
11. Choromanska, A., et al. (2015). The loss surfaces of multilayer networks. *Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS 2015)*. arXiv:1412.0233. [Analysis of critical points of neural-network loss surfaces under simplifying assumptions. Five authors confirmed on arXiv; venue from author knowledge.]
12. Keskar, N. S., et al. (2017). On large-batch training for deep learning: Generalization gap and sharp minima. *International Conference on Learning Representations (ICLR 2017)*. arXiv:1609.04836. [Reports a generalization gap for large-batch training associated with sharp minima. Five authors confirmed on arXiv; venue from author knowledge.]
13. Wilson, A. C., et al. (2017). The marginal value of adaptive gradient methods in machine learning. *Advances in Neural Information Processing Systems (NeurIPS 2017)*. arXiv:1705.08292. [Reports cases in which adaptive methods generalized worse than SGD. Five authors confirmed on arXiv; venue from author knowledge.]

## 12. Evidential Classification Matrix
| Section / Claim | Evidence Category | Supporting Source | Confidence / Status |
| :--- | :--- | :--- | :--- |
| Gradient descent update and convex convergence rates | Established | Boyd & Vandenberghe (2004); Bottou et al. (2018) | High |
| SGD with decaying step sizes converges (stochastic approximation) | Established | Robbins & Monro (1951) | High |
| Momentum and Adam update rules | Established (as definitions) | Polyak (1964); Kingma & Ba (2015) | High |
| Backpropagation supplies gradients for multi-layer networks | Established | Rumelhart et al. (1986) | High |
| Saddle points dominate difficulty in high-dimensional loss landscapes | Preliminary to Well Supported | Dauphin et al. (2014); Choromanska et al. (2015) | Moderate |
| Large batches converge to sharp minima that generalize worse | Contested | Keskar et al. (2017) | Moderate |
| Adaptive methods generalize worse than tuned SGD | Contested | Wilson et al. (2017) | Moderate; setting-dependent |

## 13. Revision History
- **v0.1.0** (2026-10-15): Initial draft. Citations checked against arXiv/Crossref/publisher pages where marked; not independently fact-checked.