Optimization - Advanced Techniques

calendar_today May 8, 2025 schedule 11 min read

1. Welcome and Icebreaker:

Fun Question: If Gradient Descent is like carefully walking down a hill, what would an advanced optimization technique be like? (e.g., having a map, a sled, a jetpack?)
Share: Has anyone used a tool or technique that significantly sped up a repetitive task or helped find a better solution more quickly?

2. Outline the Session:

Agenda:
1. Welcome & Icebreaker (5 min)
2. Limitations of Standard Gradient Descent (15 min)
3. Momentum (20 min)
4. AdaGrad (Adaptive Gradient Algorithm) (15 min)
5. RMSprop (Root Mean Square Propagation) (15 min)
6. Adam (Adaptive Moment Estimation) (20 min)
7. Brief Mention: Other techniques (L-BFGS, Newton’s Method) (5 min)
8. Live Coding: Comparing Optimizers (Conceptual or using a library like Keras/PyTorch) (15 min)
9. Task: Conceptual Understanding (15 min)
10. Q&A and Wrap-up (5 min)
Learning Outcomes: By the end of this session, you will be able to:
- Identify common challenges with standard Gradient Descent.
- Explain the intuition behind Momentum and its benefits.
- Describe how AdaGrad, RMSprop, and Adam adapt learning rates.
- Understand why Adam is a popular default optimizer.
- Recognize that other optimization families exist.
Structure: We’ll review GD’s issues, then introduce several popular algorithms that address these, culminating in Adam. A high-level coding example will show their impact.
Interactivity: These concepts build upon each other. Please ask for clarification as we go. We’ll discuss the pros and cons of each method.

3. Concept Explanation:

Limitations of Standard Gradient Descent

While Gradient Descent (Batch, Mini-batch, SGD) is a workhorse, it has several challenges:

Slow Convergence in Ravines: If the cost function landscape has long, narrow valleys (ravines) leading to the minimum, GD can oscillate back and forth across the narrow part and make slow progress along the valley floor. This happens when gradients are steep in one direction but shallow in another.
Getting Stuck in Local Minima or Saddle Points: For non-convex functions (common in deep learning), GD can converge to a local minimum that isn’t the global best. It can also get stuck on saddle points, which are flat in some dimensions and look like a minimum but are actually a maximum in others.
Learning Rate Choice: The learning rate α needs careful tuning. A single learning rate for all parameters and all stages of training might not be optimal.
- Some parameters might need larger updates, others smaller.
- The learning rate might need to decrease as we approach a minimum (learning rate scheduling).
Sensitivity to Feature Scaling: As mentioned before, GD is sensitive to the scale of input features.

Advanced optimization algorithms aim to address these issues, often by adapting the learning rate per parameter or by incorporating information from past gradients.

Momentum

The Momentum method helps accelerate SGD in the relevant direction and dampens oscillations. It adds a fraction γ (gamma, the momentum term, typically around 0.9) of the previous update vector to the current update vector.

Imagine a ball rolling down a hill. It accumulates momentum, so it doesn’t just stop if the slope flattens momentarily; it continues moving in the same general direction. Similarly, in GD with momentum, the updates tend to continue in directions where gradients have been consistently pointing, and oscillations in directions where gradients frequently change sign are dampened.

Update Rule:

v_t = γ * v_{t-1} + α * ∇J(θ_{t-1})
θ_t = θ_{t-1} - v_t

Where:

v_t is the update vector (velocity) at time t.
γ is the momentum coefficient (e.g., 0.9). It controls how much of the previous velocity is retained.
α is the learning rate.
∇J(θ_{t-1}) is the gradient at the previous parameters.

Benefits:

Faster convergence, especially in ravines, as it builds up speed in consistent gradient directions.
Helps escape shallow local minima and navigate saddle points more effectively due to the accumulated momentum.

Nesterov Accelerated Gradient (NAG): A slight variation of momentum that often works better. Instead of calculating the gradient at the current position θ_{t-1}, NAG calculates the gradient at an approximated future position θ_{t-1} - γ * v_{t-1} (where it would be after applying the previous velocity). This “lookahead” helps it correct its course more effectively. Update for NAG (simplified):

v_t = γ * v_{t-1} + α * ∇J(θ_{t-1} - γ * v_{t-1})
θ_t = θ_{t-1} - v_t

AdaGrad (Adaptive Gradient Algorithm)

AdaGrad adapts the learning rate for each parameter individually. It performs larger updates for infrequent parameters and smaller updates for frequent parameters.

It does this by keeping a running sum of the squares of the gradients for each parameter. The learning rate for each parameter is then divided by the square root of this sum.

Update Rule (for parameter θ_i):

Accumulate squared gradients: G_{t,ii} = G_{t-1,ii} + (g_{t,i})^2 (where g_{t,i} = ∂J/∂θ_i at time t)
Update parameter: θ_{t+1,i} = θ_{t,i} - (α / (sqrt(G_{t,ii}) + ε)) * g_{t,i}

Where:

G_{t,ii} is the sum of squares of past gradients for parameter θ_i up to time t.
α is a global learning rate.
ε (epsilon, e.g., 1e-8) is a small smoothing term to prevent division by zero.

Benefits:

Good for sparse data (e.g., in NLP or recommender systems) where some features appear infrequently but might be very informative. These features get larger effective learning rates.
Eliminates the need to manually tune the learning rate as much (though the global α still needs setting).

Drawback:

The learning rate monotonically decreases and can become too small prematurely, effectively stopping learning before convergence. This is because the sum of squared gradients G_{t,ii} in the denominator keeps growing.

RMSprop (Root Mean Square Propagation)

RMSprop addresses AdaGrad’s issue of a rapidly diminishing learning rate. Instead of accumulating all past squared gradients, RMSprop uses an exponentially decaying average of squared gradients.

Update Rule (for parameter θ_i):

Accumulate squared gradients (decaying average): E[g^2]_{t,i} = β * E[g^2]_{t-1,i} + (1 - β) * (g_{t,i})^2 (where g_{t,i} = ∂J/∂θ_i at time t, and β is a decay rate, e.g., 0.9)
Update parameter: θ_{t+1,i} = θ_{t,i} - (α / (sqrt(E[g^2]_{t,i}) + ε)) * g_{t,i}

Where:

E[g^2]_{t,i} is the decaying average of squared gradients for parameter θ_i.
β is the decay rate (hyperparameter, often 0.9 or 0.99).
α is a global learning rate.
ε is a smoothing term.

Benefits:

The learning rate adapts per parameter but doesn’t shrink too fast, allowing for continued learning.
Works well in practice, especially for recurrent neural networks.

RMSprop was an unpublished, adaptive learning rate method proposed by Geoff Hinton in one of his Coursera lectures.

Adam (Adaptive Moment Estimation)

Adam is arguably the most popular and often default optimization algorithm today. It combines the ideas of Momentum and RMSprop.

Momentum-like part: It keeps an exponentially decaying average of past gradients (first moments), similar to momentum. m_t = β1 * m_{t-1} + (1 - β1) * g_t
RMSprop-like part: It keeps an exponentially decaying average of past squared gradients (second moments), similar to RMSprop. v_t = β2 * v_{t-1} + (1 - β2) * (g_t)^2

Where g_t is the gradient at time t, and β1 (e.g., 0.9) and β2 (e.g., 0.999) are decay rates.

Since m_t and v_t are initialized as zeros, they are biased towards zero, especially during the initial steps. Adam performs bias correction to counteract this:

m_hat_t = m_t / (1 - β1^t)
v_hat_t = v_t / (1 - β2^t) (where t is the iteration number)

Final Adam Update Rule: θ_{t+1} = θ_t - (α / (sqrt(v_hat_t) + ε)) * m_hat_t

Where:

α is the learning rate (e.g., 0.001).
ε is a small smoothing term (e.g., 1e-7 or 1e-8).

Benefits:

Combines the advantages of AdaGrad/RMSprop (adaptive learning rates per parameter) and Momentum (helps with ravines and saddle points).
Relatively robust to the choice of hyperparameters (though α, β1, β2, ε can still be tuned).
Often works well out-of-the-box for a wide range of problems, especially in deep learning.

Brief Mention: Other Techniques

While the above are very common in deep learning, other families of optimization algorithms exist:

Second-Order Methods: These methods use the second derivative (Hessian matrix) in addition to the first derivative (gradient) to make updates. They can converge much faster but are computationally very expensive for high-dimensional problems (like training large neural networks) because calculating and inverting the Hessian is costly.
- Newton’s Method: θ := θ - H^(-1) * ∇J(θ) where H is the Hessian.
- Quasi-Newton Methods (e.g., L-BFGS): Approximate the inverse Hessian to reduce computational cost. L-BFGS is effective for smaller to medium-sized problems and can be an option when you can afford to compute gradients over larger batches or the full dataset.
Specialized Solvers: For certain types of problems (e.g., linear programming, quadratic programming), highly specialized and efficient solvers exist.

When to use which?

Adam is often a good starting point and default choice for deep learning tasks.
SGD with Nesterov Momentum can sometimes outperform Adam with careful tuning, especially for some computer vision tasks.
RMSprop is also a strong contender, particularly if Adam isn’t performing as expected.
AdaGrad might be useful for very sparse data if its aggressive learning rate decay isn’t an issue.
L-BFGS and other quasi-Newton methods are more common in classical ML or smaller-scale problems where full batch gradients are feasible and second-order information is beneficial.

4. Live Coding Demonstration: Comparing Optimizers

Actually implementing all these from scratch is extensive. Instead, we’ll show how to use them with a high-level library like Keras (TensorFlow) or PyTorch when defining a simple model. This demonstrates their practical application.

We’ll define a simple neural network and train it on some dummy data using different optimizers to observe potential differences in convergence speed or final performance. (Focus on the how to use rather than a rigorous benchmark).

import numpy as np
import tensorflow as tf
from tensorflow import keras
from tensorflow.keras import layers
import matplotlib.pyplot as plt

# Generate some synthetic data for a simple regression problem
np.random.seed(42)
X_train = np.random.rand(100, 1) * 10 - 5 # Features between -5 and 5
y_train = 0.5 * X_train**2 + X_train + 2 + np.random.randn(100, 1) * 2 # A quadratic relationship with noise

# Function to build a simple Keras model
def build_model():
    model = keras.Sequential([
        layers.Dense(20, activation='relu', input_shape=(1,)),
        layers.Dense(10, activation='relu'),
        layers.Dense(1) # Output layer for regression
    ])
    return model

# Optimizers to compare
optimizers_to_test = {
    'SGD': keras.optimizers.SGD(learning_rate=0.01),
    'MomentumSGD': keras.optimizers.SGD(learning_rate=0.01, momentum=0.9),
    'NesterovSGD': keras.optimizers.SGD(learning_rate=0.01, momentum=0.9, nesterov=True),
    'AdaGrad': keras.optimizers.Adagrad(learning_rate=0.01),
    'RMSprop': keras.optimizers.RMSprop(learning_rate=0.001), # RMSprop often needs smaller LR
    'Adam': keras.optimizers.Adam(learning_rate=0.001)      # Adam often needs smaller LR
}

history_dict = {}
epochs = 100

plt.figure(figsize=(12, 8))

for opt_name, optimizer_instance in optimizers_to_test.items():
    print(f"Training with {opt_name}...")
    model = build_model()
    model.compile(optimizer=optimizer_instance, loss='mse')
    
    history = model.fit(
        X_train,
        y_train,
        epochs=epochs,
        batch_size=32,
        verbose=0 # Suppress verbose output for cleaner comparison
    )
    
    history_dict[opt_name] = history.history['loss']
    plt.plot(history.history['loss'], label=opt_name)

plt.title("Comparison of Optimizers (Training Loss)")
plt.xlabel("Epochs")
plt.ylabel("Mean Squared Error (Loss)")
plt.legend()
plt.grid(True)
plt.ylim(0, 20) # Adjust ylim based on typical loss values for better visualization
plt.show()

# Print final losses for comparison
print("\nFinal losses after {} epochs:".format(epochs))
for opt_name, losses in history_dict.items():
    print(f"- {opt_name}: {losses[-1]:.4f}")

Explanation of Code:

Data: We generate synthetic data for a non-linear regression task.
build_model(): A simple Keras sequential model with a couple of dense layers.
optimizers_to_test: A dictionary mapping optimizer names to their Keras instances. We initialize them with some common learning rates (these might need tuning for a fair comparison, but serve for demonstration).
Training Loop:
- For each optimizer, we build a fresh model (to avoid interference).
- model.compile(optimizer=optimizer_instance, loss='mse'): This is where we tell Keras which optimizer and loss function to use.
- model.fit(...): Trains the model.
- We store the loss history for each optimizer.
Plotting: We plot the training loss (MSE) over epochs for each optimizer on the same graph to visually compare their convergence behavior.

Expected Observations (General Trends, may vary with data/model/LRs):

SGD can make noisy progress and may converge more slowly for a particular learning rate, but the outcome depends on the data and tuning.
Momentum/Nesterov can reduce oscillation or speed progress in some problems; they are tendencies, not guarantees of faster convergence or a lower final loss.
AdaGrad might start strong but could slow down significantly later.
RMSprop and Adam are often useful starting points, but their performance and final loss still depend on the problem and hyperparameter choices.

This code provides an illustration, not a controlled benchmark. For a fair comparison, tune each optimizer using the same validation protocol and run multiple trials with different random seeds.

5. Tasks:

Conceptual Understanding:

If your training loss is oscillating wildly and not decreasing when using SGD, what could be a primary cause related to the learning rate? How might Momentum help with this oscillation even if the learning rate is a bit high?
Why does AdaGrad’s learning rate for a specific parameter decrease over time? What is the potential downside of this behavior?
How does RMSprop try to fix the main problem of AdaGrad?
Adam combines ideas from which two other optimization algorithms? What are these two main ideas?
If you have a very large dataset with sparse features (many features are zero for most samples), which of the discussed adaptive methods (AdaGrad, RMSprop, Adam) might be particularly well-suited and why?

Thought Experiment (No Coding Required): Imagine you are training a very deep neural network. You notice that the loss decreases for a while but then plateaus at a value that is still too high. You suspect you might be stuck in a saddle point or a poor local minimum.

Which of the advanced optimization techniques discussed would you consider switching to or trying first, and why?
Besides changing the optimizer, what other simple strategy related to the optimization process could you try (e.g., related to initialization or learning rate)?

6. Q&A and Wrap-up:

Open floor for questions about any of the advanced optimizers or their practical usage.
Key takeaway: Adam is a strong default, but understanding other methods helps in troubleshooting and when Adam doesn’t perform optimally.
The choice of optimizer is a hyperparameter itself and can significantly impact training speed and model performance.
Preview: We’ve covered how to find the best parameters. Next, we’ll look into how to evaluate how good our model actually is (Model Evaluation).