Momentum Optimization: Comprehensive Background

1. Background Knowledge

Momentum is a fundamental optimization technique that accelerates gradient descent by maintaining a velocity vector that accumulates gradients over time. Rather than updating parameters directly with the current gradient, momentum uses an exponentially weighted moving average of past gradients, which provides two key benefits:

• Acceleration: Momentum builds up speed in consistent directions, allowing faster convergence toward minima
• Noise dampening: Oscillations caused by noisy gradients are reduced, creating smoother optimization trajectories

Core Concept: Exponential Moving Average

The velocity update uses an exponential moving average (EMA), where older gradients decay exponentially. The parameter $\beta$ (typically 0.9) controls this decay:

• Higher $\beta$ values (e.g., 0.95) give more weight to historical gradients
• Lower $\beta$ values (e.g., 0.5) make the algorithm more responsive to recent gradients

Historical Context

Momentum methods include several variants:

• Heavy-ball momentum: Classical approach using a constant momentum coefficient
• Nesterov's Accelerated Gradient (NAG): Looks ahead before computing gradients
• Quasi-hyperbolic momentum (QHM): Interpolates between current and momentum-based updates

2. Algorithm Approach

The momentum update follows a two-step process:

Step 1: Update Velocity (Exponential Moving Average) $v_t = \beta \cdot v_{t-1} + (1 - \beta) \cdot dW_t$

This combines the previous velocity (scaled by \beta) with the current gradient (scaled by 1-\beta).

Step 2: Update Parameters $W_t = W_{t-1} - \alpha \cdot v_t$

The parameter update uses the accumulated velocity, not the raw gradient.

Why This Works

The velocity acts as a low-pass filter that smooths gradient noise. When gradients consistently point in one direction, velocity accumulates. When gradients oscillate, the averaging effect cancels out noise.

3. Step-by-Step Strategy

Implementation Steps

1. Compute new velocity using the EMA formula:

• Multiply previous velocity by $\beta$
• Multiply current gradient by $(1 -$\beta$)$
• Sum these two terms

2. Update weight using the new velocity:

• Multiply velocity by learning rate $\alpha$
• Subtract from current weight

3. Round results to 4 decimal places for output

Walkthrough with Sample Input

Given: weight=0.0, grad=1.0, velocity=0.0, beta=0.9, learning_rate=0.1

Step 1: v_new = 0.9 * 0.0 + (1 - 0.9) * 1.0
 v_new = 0.0 + 0.1 * 1.0 = 0.1

Step 2: w_new = 0.0 - 0.1 * 0.1
 w_new = 0.0 - 0.01 = -0.01

Result: (-0.01, 0.1)

4. Common Pitfalls

5. Time & Space Complexity

• Time Complexity: $O(1)$ — Each momentum step performs a constant number of arithmetic operations regardless of problem size
• Space Complexity: $O(1)$ — Only stores scalar values (weight, velocity, gradient) per parameter

Practical Considerations

In practice, momentum is applied to all parameters in a neural network simultaneously, so total complexity scales with the number of parameters. However, each individual update remains constant-time.

---

Implementation Template

def momentum_step(weight, grad, velocity, beta, learning_rate):
 # Step 1: Update velocity (exponential moving average)
 new_velocity = beta * velocity + (1 - beta) * grad

 # Step 2: Update weight using new velocity
 new_weight = weight - learning_rate * new_velocity

 # Step 3: Round to 4 decimal places
 return (round(new_weight, 4), round(new_velocity, 4))

This implementation directly translates the mathematical formulas into code, maintaining clarity and correctness.