Gradient descent

Gradient Descent and Optimization Methods

These notes cover Lecture 12, slides 1-21 of CSE 6740 (Fall 2026).

Motivation for Gradient Descent

Gradient descent is an essential tool in machine learning because it allows us to optimize complex loss functions in a computationally efficient manner. To intuitively understand this, let us examine a simplified neural network.

Example 1. Consider a single neuron with one trainable weight $\theta\in\mathbb{R}$ and no bias:

Say we have two data points:

Let $\ell(\widehat y,y)$ denote the binary cross-entropy loss for one example. We use the average loss as our objective, matching the averaging convention used later for full gradients and batches:

Our problem then becomes finding $\theta^\star=\arg\min_{\theta\in\mathbb{R}}f(\theta)$. How would you solve for $\theta$ directly?

Your first instinct might be to try the method you learned in Calculus 1: set $f’(\theta)=0$ and solve for $\theta$. Differentiating $f(\theta)$ gives

Let $q=e^\theta>0$ and we get $5q^6+4q^5-1 = 0$. This equation does not give us a simple expression for the optimal weight, so we can turn to a nonlinear root-finding algorithm to get a numerical solution. The point of all of this is to show how solving the stationarity equations directly becomes cumbersome even in this trivial problem. In practice, neural networks often have millions or billions of parameters, making these equations much harder to solve. Their loss functions are generally non-convex, so a stationary point need not be a global minimum.

What Are Descent Methods?

Gradient descent is one method in the family of descent methods. In general, let $\theta\in\mathbb{R}^d$ be the parameter vector and $f:\mathbb{R}^d\to\mathbb{R}$ the objective we want to minimize. Throughout these notes, $k$ indexes iterations, $i$ indexes parameter coordinates, and $j$ indexes training examples. We write $\theta_k$ for the parameter vector at iteration $k$ and $\theta_{k,i}$ for its $i$th coordinate. The exact gradient is $g_k=\nabla f(\theta_k)$.

Descent methods solve $\min_{\theta\in\mathbb{R}^d} f(\theta)$. Starting from an initial point $\theta_0$, they generate a sequence of points using the update

where $p_k\in\mathbb{R}^d$ is the search direction and $\eta_k>0$ is the learning rate (step-size multiplier). The actual displacement is $\eta_kp_k$. For a fixed learning rate, we write $\eta_k=\eta$ for every $k$. These are called descent methods because we require the function evaluations to “descend”:

A negative directional derivative is a sufficient condition for decrease with sufficiently small positive steps. We therefore choose search directions $p_k$ satisfying

General descent method

Given a differentiable objective $f$, starting point $\theta_0$, and stopping tolerance $\varepsilon_{\mathrm{stop}}>0$:

1. Initialize $k=0$ and $g_0=\nabla f(\theta_0)$.
2. While $\lVert g_k \rVert_2 > \varepsilon_{\mathrm{stop}}$:
   • Choose a direction $p_k$ satisfying $g_k^\top p_k<0$.
   • Choose $\eta_k>0$ so the update decreases $f$.
   • Update $\theta_{k+1}=\theta_k+\eta_kp_k$.
   • Increase $k$ by one and compute $g_k=\nabla f(\theta_k)$.
3. Return $\theta_k$.

Gradient Descent (First-Order Steepest Descent)

Recall our goal is to find the minimum of the objective, while also being computationally efficient. Choosing the best possible displacement $s\in\mathbb{R}^d$ by directly minimizing $f(\theta_k+s)$ would simply give us another version of the original optimization problem.

Instead, we replace the objective near our current point with a simpler function. A first-order Taylor approximation is useful because it describes the objective’s local change using only its gradient:

This approximation is accurate for sufficiently small displacements and is inexpensive to work with. Using this approximation, in which direction do we get the largest descent of our objective? Fixing a radius $r>0$, this question can be written as

We drop $f(\theta_k)$ since it is constant and restrict $|s|_2$ to keep the candidate displacement local. By Cauchy–Schwarz (the dot product is bounded by the product of norms),

Thus, $-r|g_k|_2$ is a lower bound on the linearized change. To show that this bound is the minimum, we now show that it is achievable. Assuming $g_k\neq0$, choose

This displacement satisfies the constraint because $|s^\star|_2=r$. Substituting it into the objective gives

Since $s^\star$ achieves the lower bound exactly, it must minimize the first-order approximation. Absorbing the positive scaling factor into the learning rate, we choose the search direction $p_k=-g_k$. The gradient descent update is therefore

where $\eta_k>0$ is chosen sufficiently small to decrease the objective. This simple update rule is termed gradient descent because we move in the negative-gradient direction.

Choosing the Learning Rate: Ensuring Descent

A descent direction, $g_k^\top p_k<0$, guarantees decrease only for sufficiently small positive steps. The learning rate controls whether the finite update actually decreases $f$: too small means slow progress, while too large can cause overshooting or divergence (Figure 1).

Figure 1. Effect of the learning rate on the optimization path and loss.

A safe learning rate.

If the gradient is $L$-Lipschitz continuous for $L>0$,

the descent lemma applied to GD gives

Thus $0<\eta_k<2/L$ guarantees strict decrease when $g_k\neq0$; $0<\eta_k\leq1/L$ is a common sufficient choice. This requires Lipschitz continuity of the gradient, and does not require convexity or guarantee a global minimum.

Backtracking line search.

When $L$ is unknown, choose $c,\rho\in(0,1)$ and shrink a trial $\eta>0$ by $\eta\gets\rho\eta$ until

Accept $\eta_k=\eta$. This condition enforces decrease because $g_k^\top p_k<0$. For a differentiable objective and a descent direction, sufficiently small steps pass the test; the cost is extra objective evaluations.

Newton’s Method (Second-Order Optimization)

Gradient descent uses only a linear approximation of $f$ near $\theta_k$ at each iteration, and this approximation is quite good so long as the step is small enough. But, what if we wanted a better approximation near $\theta_k$? We could decrease the step size to reduce the approximation error, or use a higher-order Taylor expansion as our stand-in for $f$.

Newton’s method does the latter, using a second-order approximation that accounts for curvature. Assume $f$ is twice continuously differentiable, and let

Using the same gradient $g_k=\nabla f(\theta_k)$ as before, the second-order approximation for a displacement $s$ is

We can again write this as an optimization problem:

If $H_k$ is positive definite, this quadratic model has a unique minimizer. Taking the derivative with respect to $s$ and setting it equal to zero gives

Choose $p_k=s^\star$ as the search direction. The update rule becomes

A full Newton step uses $\eta_k=1$, which minimizes the quadratic model. Since the model is only an approximation, this may lead to $f(\theta_{k+1})>f(\theta_k)$. When $H_k$ is positive definite and $g_k\neq0$, the Newton direction is a descent direction, so the backtracking line search in the learning-rate section above can select a smaller learning rate that decreases the actual objective.

Gradient Descent versus Newton’s Method.

The tradeoff is the cost of each iteration versus the number of iterations needed. Gradient descent uses only the gradient, making each iteration inexpensive. Newton’s method also uses curvature, which can produce more effective updates but is more expensive to compute.

Let $d$ be the number of parameters, and let $C_g$ and $C_H$ denote the costs of evaluating the gradient and Hessian, respectively. For a dense Hessian, excluding line-search evaluations:

The $O(d^3)$ cost comes from solving $H_kp_k=-g_k$.

For smooth, strongly convex objectives, gradient descent with an appropriate learning rate converges linearly. Newton’s method converges quadratically sufficiently close to a minimizer with a positive-definite Hessian, assuming the Hessian is locally Lipschitz continuous and full steps are taken. Thus, Newton can require far fewer iterations, while gradient descent is usually more practical when $d$ is very large because it avoids storing and solving with the Hessian.

Other Optimization Methods

Throughout this section, $\delta>0$ is a small numerical stabilizer.

AdaGrad (Adaptive Gradient).

GD uses one learning rate for every direction. In an elongated valley, a rate that is safe in the steep direction can be slow along the shallow direction. Newton adjusts the geometry using the Hessian. AdaGrad instead rescales the gradient using its history, without computing second derivatives. Initialize $G_0=0\in\mathbb{R}^{d\times d}$:

Here $I_d$ is the identity matrix and $\tau$ indexes past iterations. The outer products retain gradient magnitudes and directional relationships. The inverse square root damps directions with large accumulated gradient projections more strongly, balancing different scales. The term $\delta I_d$ ensures invertibility. Full-matrix AdaGrad still requires matrix storage and computation, and its accumulating history can also make steps too small.

Momentum.

Momentum accumulates exponentially discounted gradients. Initialize $z_0=0\in\mathbb{R}^d$ and update

Consistent gradient components reinforce each other, building speed. Components that repeatedly change sign tend to cancel, reducing oscillation. Larger $\beta$ retains more history but can cause overshooting.

Adam (Adaptive Moment Estimation).

Adam combines momentum with adaptive coordinatewise scaling. Initialize $m_0=v_0=0\in\mathbb{R}^d$ and maintain moving averages of gradients and squared gradients:

where $0\leq\beta_1,\beta_2<1$ and $\odot$ denotes elementwise multiplication. Correcting for zero initialization gives

The coordinate update is

The numerator smooths the direction using momentum and the denominator adapts each coordinate’s scale. Unlike AdaGrad’s cumulative history, Adam discounts old squared gradients. Momentum and Adam need not produce descent directions, so their objectives can increase on individual updates even with exact gradients.

Example 2. Figure 2 shows the different paths and progress on a common objective. GD zigzags, momentum can reduce zigzagging but overshoot, and AdaGrad and Adam adapt the scaling. Newton uses curvature but needs several steps because the objective is nonquadratic.

Figure 2. Original Python simulation of the update rules above, for

Each method takes 80 updates. Fixed learning rates: GD $0.09$, Newton $1$, AdaGrad $0.7$, momentum $0.06$, and Adam $0.15$. Momentum uses $\beta=0.8$; Adam uses $(\beta_1,\beta_2)=(0.9,0.99)$. Adaptive states start at zero with $\delta=10^{-8}$. The log plot has a display floor of $10^{-12}$. Settings are illustrative, and costs per update differ.

The optimizer comparison on slide 21

The lecture also compares optimizer trajectories and training cost for an MNIST multilayer neural network with dropout. Its plots include Nesterov momentum (NAG, which evaluates a lookahead gradient), RMSprop, and AdaDelta. RMSprop and AdaDelta use adaptive scaling that discounts older squared gradients, in contrast to AdaGrad’s cumulative history. Adam has the lowest plotted training cost after about 200 passes through the dataset in that experiment, while AdaGrad remains higher. This illustrates the benefit of combining adaptation and momentum there; it is not a universal ranking, and lower training cost alone does not establish better test performance. Lecture 12, slide 21

Batching: Full-batch, Mini-batch, and Stochastic Updates

Batching determines how we estimate gradients and can be combined with different optimizers. For training data $\mathcal D_{\mathrm{train}} = \lbrace (x_j, y_j) \rbrace_{j=1}^N$, let $\ell_j(\theta) = \ell(h_\theta(x_j), y_j)$ be the loss of the model’s prediction on example $j$. The objective is

Computing the full gradient requires all $N$ examples. Instead, sample indices $B_k\subseteq{1,\ldots,N}$ with $b=\lvert B_k\rvert$:

All gradients in a batch are evaluated at the same $\theta_k$, then averaged before making one parameter update. For a fresh uniformly sampled batch, $\mathbb E[\widetilde g_k\mid\theta_k]=g_k$, so the batch average is an unbiased estimate of the full gradient. Using $\widetilde g_k$ in GD gives $\theta_{k+1}=\theta_k-\eta_k\widetilde g_k$. Stochastic gradient descent (SGD) uses $b=1$: each update uses the gradient of one randomly chosen training example. Mini-batch gradient descent uses $1<b<N$: each update uses the average gradient of a small group of training examples. The parameters are updated once per batch, rather than after each example within that batch. Under the slide’s simplified $O(d)$ gradient cost per example:

Smaller batches give cheaper, more frequent updates but noisier directions. Larger batches reduce noise at the cost of more computation and usually more working memory. Mini-batches balance these tradeoffs and suit parallel computation; total gradient work still scales with $b$. Noise can help leave shallow local minima, but can also cause oscillation near a solution and increase the objective on individual steps. The same batch estimates can replace $g_k$ in momentum, AdaGrad, or Adam, keeping their states across batches.

Sources and acknowledgments

• Kai Wang, CSE 6740 Lecture 12: Gradient Descent, slides 1-21. Primary lecture source and source of Figure 1. Slide 21 credits Oren Milman for its trajectory illustration; the comparison is discussed here in words.
• John Duchi, Elad Hazan, and Yoram Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR, 2011. Reference for AdaGrad’s use of gradient history to adapt the geometry.
• Diederik P. Kingma and Jimmy Ba, Adam: A Method for Stochastic Optimization, ICLR, 2015. Reference for Adam’s moment estimates, bias corrections, and update.
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Chapter 9, 2004. Reference for descent directions, backtracking, and the GD/Newton comparison.

AI assistance: Used AI for assistance with editing, notation checks, Markdown conversion, and the Python simulation. The equations, derivatives, and simulation were checked against the lecture and the cited references.

Assignment pending

Develop the assigned part of the lecture’s core course materials.

The course team will assign this section through a GitHub issue.

Assignment pending

Develop an optional extension, application, or related topic assigned for this lecture.

The course team will assign this section through a GitHub issue.

Assignment pending

Develop an optional extension, application, or related topic assigned for this lecture.

The course team will assign this section through a GitHub issue.