Unconstrained optimization finds minima of \(f(\theta)\). Convex problems \(f(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda)f(\mathbf{y})\) have no local minima that aren't global—gradient descent is guaranteed to converge. Strongly convex functions satisfy \(\mathcal{L}(\theta_2) \geq \mathcal{L}(\theta_1) + \nabla\mathcal{L}(\theta_1)^\top(\theta_2-\theta_1) + \frac{m}{2}\|\theta_2-\theta_1\|^2\) with constant \(m > 0\), yielding a unique global minimum and linear convergence rate \(\|\theta_t-\theta^*\|^2 \leq (1-m/L)^t\|\theta_0-\theta^*\|^2\). For L-smooth convex functions, GD achieves \(\mathcal{L}(\theta_T) - \mathcal{L}(\theta^*) \leq L\|\theta_0-\theta^*\|^2/(2T)\) (sublinear \(O(1/T)\) rate). Jensen's inequality \(f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]\) for convex \(f\) underpins many information-theoretic bounds. Constrained optimization adds equality (\(g_i(\theta) = 0\)) and inequality (\(h_j(\theta) \leq 0\)) constraints. Lagrange multipliers satisfy \(\nabla f = \lambda \nabla g\) at the optimum, with the Lagrangian \(\mathcal{L}(\mathbf{x},\lambda) = f(\mathbf{x}) + \lambda g(\mathbf{x})\). The KKT conditions extend this with complementary slackness \(\mu_i h_i(\mathbf{x}^*) = 0\): either the constraint is active (\(h_i = 0\)) or the multiplier is zero (\(\mu_i = 0\)). The Lagrangian dual function \(d(\lambda,\mu) = \min_\theta \mathcal{L}(\theta,\lambda,\mu)\) provides lower bounds; strong duality holds under Slater's condition.
Gradient descent \(\theta_{t+1} = \theta_t - \eta\nabla\mathcal{L}(\theta_t)\) takes steps opposite the gradient. The learning rate \(\eta\) is critical: too large diverges, too small is slow; optimal \(\eta \approx 1/L\). Each step decreases the loss proportional to \(\eta\|\nabla\mathcal{L}\|^2\) for small \(\eta\) by the first-order Taylor approximation. Stochastic Gradient Descent (SGD) uses single random examples—much cheaper per step but noisy. Mini-batch SGD averages B examples: \(\theta_{t+1} = \theta_t - (\eta/B)\sum_{i\in\mathcal{B}} \nabla\ell_i\). Gradient noise (variance \(\sigma^2_{\mathrm{grad}}/B\)) acts as implicit regularization, helping escape sharp minima and saddle points. For convergence, SGD requires Robbins-Monro conditions \(\sum_t \eta_t = \infty\) (enough progress) and \(\sum_t \eta_t^2 < \infty\) (steps decrease). Momentum accelerates convergence in narrow valleys: \(v_{t+1} = \beta v_t + \nabla\mathcal{L}\) with \(\beta \approx 0.9\)—consistent gradient directions accumulate, with effective learning rate \(\approx \eta/(1-\beta)\). Nesterov momentum evaluates the gradient at the look-ahead position \(\theta_t - \beta\eta v_t\) for slightly faster convergence. The subgradient method extends to non-smooth objectives using \(\mathbf{g}_t \in \partial\mathcal{L}(\theta_t)\) with diminishing step sizes.
Adaptive methods scale learning rates per parameter. AdaGrad accumulates squared gradients \(G_t = \sum g_k^2\) and divides \(\eta\) by \(\sqrt{G_t}\)—great for sparse features but LR eventually vanishes to zero. RMSprop uses exponential moving average \(v_t = \rho v_{t-1} + (1-\rho)g_t^2\) with \(\rho \approx 0.9\), fixing AdaGrad's decay issue; effective learning rate \(\eta/\sqrt{v_t}\) normalizes by recent gradient scale. Adam combines first moment \(m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t\) (momentum) with second moment \(v_t = \beta_2 v_{t-1} + (1-\beta_2)g_t^2\) (RMSprop), applies bias correction \(\hat{m}_t = m_t/(1-\beta_1^t)\), and updates \(\theta_{t+1} = \theta_t - \eta\hat{m}_t/(\sqrt{\hat{v}_t}+\epsilon)\) with \(\epsilon \approx 10^{-8}\) for numerical stability. AdamW applies decoupled weight decay \(\lambda\theta\) directly, improving generalization. LAMB adds per-layer trust ratios for large-batch distributed training. Learning rate schedules include cosine annealing \(\eta_t = \eta_{\min} + \frac{1}{2}(\eta_{\max}-\eta_{\min})(1+\cos(\pi t/T))\), linear warmup, step decay, and the 1-cycle policy.
Second-order methods use curvature. Newton's method \(\theta_{t+1} = \theta_t - H^{-1}\nabla\mathcal{L}\) achieves quadratic convergence but costs \(O(n^2)\) memory and \(O(n^3)\) inversion—impractical for large networks. L-BFGS approximates \(H^{-1}\) using the last m gradient differences (\(s_k = \theta_k-\theta_{k-1}\), \(y_k = \nabla\mathcal{L}_k - \nabla\mathcal{L}_{k-1}\)), reducing to \(O(mn)\) memory. The natural gradient \(\tilde\nabla_\theta \mathcal{L} = \mathcal{I}(\theta)^{-1}\nabla_\theta \mathcal{L}\) accounts for parameterization geometry via the Fisher information matrix \(\mathcal{I}(\theta) = \mathbb{E}[\nabla\log p \cdot (\nabla\log p)^\top]\) (TRPO, natural policy gradient); K-FAC approximates this with Kronecker-factored terms \(A_{l-1} \otimes G_l\). Projected gradient descent handles simple constraints via \(\theta_{t+1} = \Pi_C(\theta_t - \eta\nabla f(\theta_t))\). Proximal methods use \(\mathrm{prox}_{\eta g}(\theta) = \arg\min_u \frac{1}{2}\|u-\theta\|^2 + \eta g(u)\)—for L1 this is soft-thresholding \(\mathrm{sign}(\theta_j)\max(|\theta_j|-\eta\lambda, 0)\). Gradient clipping \(\mathbf{g} \leftarrow \tau\mathbf{g}/\max(\|\mathbf{g}\|,\tau)\) prevents exploding gradients. Stochastic gradient Langevin dynamics adds Langevin noise \(\sqrt{2\eta}\,\boldsymbol{\epsilon}_t\) to SGD for Bayesian sampling. Gradient accumulation simulates large batches; the linear scaling rule multiplies \(\eta\) by \(B'/B\) when batch size changes. The implicit bias of GD on linear networks finds minimum nuclear-norm solutions among zero-error solutions.