mathematics//optimization//gradient descent
Gradient descent is an iterative optimization algorithm that lowers a cost by repeatedly stepping against its gradient, the direction in which the cost rises fastest, and it is how neural networks learn and how logistic regression, boosting, adaptive controllers and many fits without a closed form find their parameters. It needs only the cost and its gradient at the current point: a hiker in fog who feels the slope under the boots and nothing else.
Gradient descent is an iterative optimization algorithm that lowers a cost by repeatedly stepping against its gradient, the direction in which the cost rises fastest, and it is how neural networks learn and how logistic regression, boosting, adaptive controllers and many fits without a closed form find their parameters. It needs only the cost and its gradient at the current point: a hiker in fog who feels the slope under the boots and nothing else.
θk+1=θk−η ∇L(θk)\theta_{k+1} = \theta_k - \eta\,\nabla L(\theta_k)θk+1=θk−η∇L(θk)
θk\theta_kθk are the parameters at step kkk and η\etaη is the step size, the learning rate. In a neural network one step is three moves.
1Compute how wrong the model isloss function2Compute which direction to adjust each weightbackpropagation3Nudge the weights in that direction
Near a minimum every smooth cost looks like a bowl L≈12θ⊤HθL\approx\frac12\theta^{\top}H\thetaL≈21θ⊤Hθ, with HHH the Hessian, and the update becomes the linear map θk+1=(I−ηH)θk\theta_{k+1}=(I-\eta H)\theta_kθk+1=(I−ηH)θk. It converges only if ∣1−ηλi∣<1|1-\eta\lambda_i|<1∣1−ηλi∣<1 for every eigenvalue λi\lambda_iλi of HHH, that is if η<2/λmax\eta<2/\lambda_{\max}η<2/λmax. The steepest direction caps the step and the flattest, λmin\lambda_{\min}λmin, sets the pace; with a large condition number λmax/λmin\lambda_{\max}/\lambda_{\min}λmax/λmin the valley is a long narrow bathtub and the optimizer bounces from wall to wall while it crawls along the floor.
outcomeconverged steps218 loss9.7e−7 learning rate0.035 On an ill-conditioned quadratic valley (κ = 50), plain gradient descent with learning rate 0.035 converges in 218 steps. The stability limit is 2/λmax = 0.04: above it the zigzag across the steep direction grows instead of dying out.
On the quadratic with plain gradient, raise the rate from 0.035 to 0.041: past 2/λmax=0.042/\lambda_{\max}=0.042/λmax=0.04 the zigzag stops dying out and blows up. Then try momentum, Adam and the curved banana valley of the Rosenbrock function, and tap to start elsewhere.
Gradient descent is explicit Euler on the gradient flow θ˙=−∇L(θ)\dot\theta=-\nabla L(\theta)θ˙=−∇L(θ) with step η\etaη, and η<2/λmax\eta<2/\lambda_{\max}η<2/λmax is Euler's stability limit. Bad conditioning slows it and an excessive rate destabilizes it: an ill-conditioned loss is a stiff system (stiffness), and a diverging training run is an unstable loop to be diagnosed like one.
The cure for conditioning is to reshape the valley. Standardizing features (zero mean, unit variance) brings the condition number toward 1, which is why it is never cosmetic (variable scaling); rescaling each axis without computing the Hessian is preconditioning, which Adam does cheaply per parameter, and using the curvature outright is Newton's method.
Using all the data for every step is impractical at scale, so the gradient is estimated on a random minibatch (stochastic gradient descent), and a running velocity of past gradients crosses narrow valleys faster (momentum). Adam combines both and is the default optimizer for networks.
On a non-convex loss there are many minima, and in large networks most are roughly equally good; flat regions such as saddle points slow descent more than bad minima. On a convex cost any minimum it reaches is the global one.
Deep networks add their own failures: gradients that shrink layer after layer (vanishing gradient), which residual connections relieve, and the engineering of splitting each step across many GPUs (distributed training), whose return follows power laws in data, parameters and compute (scaling laws).