Gradient Descent Variants and Constrained Optimization

The update rule. Standard gradient descent. also called vanilla gradient descent. is the simplest iterative optimization algorithm. You use it to find the minimum of a loss function by taking steps proportional to the negative gradient.

$${\theta }_{t+1}={\theta }_t-\eta \nabla J({\theta }_t)$$

Here is what every symbol means:

Why subtract the gradient? The gradient $\nabla J({\theta }_t)$ points in the direction of steepest increase. To go downhill. which is what you want when minimizing. you move in the opposite direction. So you subtract $\eta \nabla J({\theta }_t)$ from the current point.

The algorithm moves by only two things: the learning rate and the gradient. It has no memory of where it came from. It does not know whether it is at the global minimum, a local minimum, or a flat plateau. It only knows the current position and the current slope.

Momentum fixes gradient descent's slow convergence by adding a velocity term. The velocity accumulates past gradients. A heavy ball keeps rolling even when the slope momentarily flattens.

The momentum update has two equations:

$$v_t=\beta v_{t-1}+\eta \nabla J({\theta }_t)$$

$${\theta }_{t+1}={\theta }_t-v_t$$

Here is what every symbol means:

Why two equations? The first equation builds the velocity. a running blend of old velocity and new gradient. The second equation uses that velocity to update the parameters. This split is what gives momentum its memory: the velocity persists across steps.

When $\beta =0$, momentum collapses to standard gradient descent because $v_t=\eta \nabla J({\theta }_t)$. When $\beta$ is high (say $0.9$), the velocity carries forward most of its previous value, adding only a small fraction of the current gradient.

Expand the velocity recurrence to see what it really does. Write $g_t=\nabla J({\theta }_t)$ for brevity.

$$v_t=\beta v_{t-1}+\eta g_t$$

Substitute $v_{t-1}=\beta v_{t-2}+\eta g_{t-1}$:

$$\begin{array}{r}{v}_t\&=\eta g_t+\beta (\beta v_{t-2}+\eta g_{t-1})\\ <ul><li>\&=\eta g_t+\beta \eta g_{t-1}+{\beta }^2{v}_{t-2}</li></ul><p>\end{array}$$

Keep expanding:

$$v_t=\eta g_t+\beta \eta g_{t-1}+{\beta }^2\eta g_{t-2}+{\beta }^3\eta g_{t-3}+\cdots$$

This is a weighted sum of past gradients with exponentially decaying weights. The current gradient gets weight $\eta$. The previous one gets $\beta \eta$. The one before that gets ${\beta }^2\eta$, and so on. For $\beta =0.9$, the weights are $1,.0.9,.0.81,.0.729,.\dots$

The ball gets "heavier" because of the accumulated past gradient contributions. That is why it is called momentum. The heavy ball does not stop exactly at the minimum. it overshoots, rolls up the opposite side, comes back, oscillates a bit, and settles.

In standard gradient descent, the learning rate is the same for every parameter and every step. But the loss landscape is not uniform. some directions are steep, others nearly flat. A single learning rate cannot serve both well.

All adaptive algorithms follow this template:

$${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{A_t}}\odot \nabla J({\theta }_t)$$

where $A_t$ is an accumulation factor. a running statistic of squared gradients. and $\odot$ denotes element-wise (Hadamard) multiplication. The core idea: divide the learning rate by a factor that tracks gradient magnitude per parameter.

• When the gradient is very high (steep slope) → large denominator → small effective step → no overshoot.
• When the gradient is very small (flat region) → small denominator → large effective step → faster movement.

The algorithms differ only in how they compute $A_t$.

Adagrad accumulates all past squared gradients with equal weight. No decay. every gradient in the entire history counts equally.

Accumulation factor:

$$G_t=G_{t-1}+(\nabla J({\theta }_t){)}^2$$

Update rule:

$${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{G_t}}\odot \nabla J({\theta }_t)$$

The square root is taken element-wise. The operator $\odot$ means element-wise multiplication: multiply the first element of $\eta /\sqrt{G_t}$ by the first element of the gradient, the second by the second, and so on.

Why it adapts. When the terrain has been steep, $G_t$ is large, so $\eta /\sqrt{G_t}$ is small. The effective learning rate shrinks. When the terrain is flat, $G_t$ stays small, so the effective learning rate stays large.

Why it breaks. The accumulation never forgets. If you start on a steep cliff and later enter a flat valley, $G_t$ remains large from the cliff memory. Your effective learning rate stays small forever. Even though the current gradient is tiny, you cannot speed up. The denominator grows monotonically, and eventually learning grinds to a halt.

RMSprop fixes Adagrad's monotonically growing denominator by adding a decay factor. Instead of accumulating all squared gradients equally, RMSprop applies an exponentially weighted moving average.

Accumulation factor:

$$S_t=\beta S_{t-1}+(1-\beta )(\nabla J({\theta }_t){)}^2$$

Update rule:

$${\theta }_{t+1}={\theta }_t-\frac{\eta }{\sqrt{S_t}}\odot \nabla J({\theta }_t)$$

The structure is identical to Adagrad. The only difference is $S_t$. it uses a moving average, so it can increase or decrease based on current gradients.

$\beta$ is typically high, around $0.9$. A high $\beta$ biases the accumulation toward past squared gradients. The current gradient gets only a small weight, $(1-\beta )$. Think about it this way: "We would put more weightage to the past gradients than what your current gradient is. We keep track of my history and are more biased towards history than the present."

Why RMSprop is faster than Adagrad. Because $S_t$ is a moving average, old large gradients are gradually forgotten. If you leave a steep region and enter a flat valley, $S_t$ will decay, lowering the denominator and allowing larger steps again. Adagrad would be permanently penalized by old steep gradients.

Adam combines momentum and RMSprop. It maintains two running averages:

1. $m_t$. a momentum-like running average of gradients (first moment).
2. $v_t$. an RMSprop-like running average of squared gradients (second moment).

Momentum term (first moment):

$$m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)\nabla J({\theta }_t)$$

Velocity term (second moment):

$$v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)(\nabla J({\theta }_t){)}^2$$

${\beta }_1$ controls momentum decay (typically $0.9$). ${\beta }_2$ controls the squared-gradient moving average (typically $0.999$ in implementations, though the text used $0.8$ for hand calculations). Both are close to 1, meaning the optimizer is heavily biased toward its history.

Expanded interpretation. Expand the recurrences the same way as momentum:

$$m_t=(1-{\beta }_1)\sum _{k=0}^t{\beta }_1^{t-k}\nabla J({\theta }_k),v_t=(1-{\beta }_2)\sum _{k=0}^t{\beta }_2^{t-k}(\nabla J({\theta }_k){)}^2$$

So $m_t$ is a weighted sum of past gradients, and $v_t$ is a weighted sum of past squared gradients.

Bias correction. Both $m_t$ and $v_t$ start at zero ($m_0=0,v_0=0$). This biases early iterations toward zero. the cold start problem. Adam compensates with bias correction:

$${\hat{m}}_t=\frac{m_t}{1-{\beta }_1},{\hat{v}}_t=\frac{v_t}{1-{\beta }_2}$$

Adam uses this simplified form where you divide by $(1-\beta )$ once. The original Adam paper (Kingma &. Ba, 2014) uses ${\hat{m}}_t=m_t/(1-{\beta }_1^t)$ and ${\hat{v}}_t=v_t/(1-{\beta }_2^t)$, where $t$ is the iteration index. This provides a per-step correction that gradually disappears as $t$ grows. For the first iteration ($t=1$), the two forms give the same result since ${\beta }_1^1={\beta }_1$. For later iterations, this simplified form somewhat over-corrects. But it works reasonably and is what you will see on the exam.

Update rule:

$${\theta }_{t+1}={\theta }_t-\eta .{\hat{m}}_t\oslash \sqrt{{\hat{v}}_t}$$

where $\oslash$ denotes element-wise division. The update uses both corrected factors: the momentum term divided by the square root of the velocity term.

Why take the square root of $v_t$? Because $v_t$ tracks squared gradients. Taking the square root brings it back to the same order as the gradient, making the ratio ${\hat{m}}_t/\sqrt{{\hat{v}}_t}$ unit-consistent. It is like root mean squared (RMS): square the values, average them, take the square root to return to the original scale.

Gradient-based methods need the loss function to be smooth and continuous. The gradient. being a derivative. is only defined where the function has no sharp edges, corners, or walls. If the function has breaks, you cannot compute the gradient at those points.

In constrained optimization, the constraints themselves introduce hard boundaries. The feasible region. the set of points that satisfy all constraints. has edges. The optimum often lies on one of those edges, exactly where the gradient is not defined. Think of a ball rolling and hitting a wall: the trajectory is broken.

The key idea: "Gradient is a derivative. It is only defined for a smooth, continuous function. If the function has edges, you cannot compute the gradient at a point like this."

Consider an optimization problem with box constraints:

Objective: Minimize $J(x,y)=x^2+y^2$

Subject to: $0\le x\le 4$, $0\le y\le 2$

The constraints carve out a rectangular feasible region. all points with $x$ between 0 and 4, $y$ between 0 and 2. You are only allowed to search within this rectangle.

Consider a linear programming problem:

A fundamental result from linear programming: the optimum of a linear objective with linear constraints always lies at a corner point. It is never in the interior. This is why the simplex method only checks vertices.

Visual intuition. Plot the $x$-$y$ plane. Shade the three constraint regions. The feasible polygon has vertices at $(0,0)$, $(2,0)$, $(1,4)$, and $(0,4)$. The objective $2x+4y$ is a plane tilted upward. its minimum over this polygon sits at the origin $(0,0)$.

Rather than working with hard constraints directly, we convert the constrained problem into an unconstrained one using the Lagrangian. This is done by adding penalty terms for constraint violations.

Step 1: Write constraints in standard form ($\le 0$).

Every constraint must be rewritten as $g(x,y)\le 0$. If a constraint says $x\ge 0$, multiply by $-1$ to get $-x\le 0$. If a constraint says $y\le 2$, rewrite as $y-2\le 0$.

The rule: "Wherever you have greater-than-or-equal-to constraints, you multiply by minus one and convert it into less-than-or-equal-to."

For the box-constraint problem $J(x,y)=x^2+y^2$ with $0\le x\le 4$, $0\le y\le 2$:

The Lagrangian converts a constrained problem into an unconstrained one that depends on both the original variables $(x,y)$ and the multipliers $\lambda$. This creates a minimax game. a zero-sum contest between two players:

• Player 1 (Minimizer): chooses $(x,y)$ to minimize $\mathcal{L}$.
• Player 2 (Maximizer): chooses $\lambda \ge 0$ to maximize $\mathcal{L}$. effectively punishing constraint violations.

The order of play matters enormously.

The primal problem ${\min }_x{\max }_{\lambda }\mathcal{L}(x,\lambda )$: you pick the variables first, then the adversary picks penalties. Since you moved first without knowing the penalties, you might wander into forbidden regions. The penalty explodes. You lose.

The dual problem ${\max }_{\lambda }{\min }_x\mathcal{L}(x,\lambda )$: the penalties are set first, then you optimize the variables knowing what is forbidden. You stay safely inside. Going second gives you an advantage. you see what the first player did and can react.

The analogy: "When you know there is a gate and a danger mark, you will not enter. If there is no sign and dynamite in the ground, you step on it. Then you realize the mistake."

T-shirt bargaining analogy. You go to a shop. If the price is set (penalties fixed), you. the buyer. choose the best T-shirt your budget allows. If the seller sets the price after seeing you want it, they can charge more. The one who moves second has the advantage.

Machine learning interpretation. Let $x$ be model parameters and $\lambda$ be noise. If you know the noise level ($\lambda$ set first), you can choose the best model. that is the dual. If you choose a model first without knowing the noise, you risk a bad fit. that is the primal.

The min-max inequality formalizes the idea that planning second is never worse than planning first:

$$\underset{x}{\min }\underset{\lambda }{\max }\mathcal{L}(x,\lambda )\ge .\underset{\lambda }{\max }\underset{x}{\min }\mathcal{L}(x,\lambda )$$

• Left side (primal): first minimize over variables, then maximize over penalties. Think: pick model first, then face the data.
• Right side (dual): first maximize over penalties, then minimize over variables. Think: know the noise first, then pick the model.

The inequality says the dual value is always at least as large as the primal value. When equality holds. ${\min }_x{\max }_{\lambda }={\max }_{\lambda }{\min }_x$. we call it strong duality. For convex problems (like the ones in this lecture), strong duality holds. The dual gives the same answer as the primal, and the dual is often much easier to solve.

Why the inequality? The minimizer on the left has to protect against any penalty the maximizer could choose. a worst-case mindset. The minimizer on the right gets to see the penalties first. an informed choice. Information cannot hurt you, so the informed minimum is never worse (i.e., never larger) than the uninformed one.