Bird
Raised Fist0

Implement Mini-Batch SGD with Momentum and Adam

CODINGadvancedInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🎯
Implement Mini-Batch SGD with Momentum and Adam
30 min · senior
senior

You are tasked with implementing a mini-batch stochastic gradient descent (SGD) optimizer with momentum and Adam for a deep learning model. The model will be trained on a dataset with 1 million samples and 1000 features. The implementation must handle edge cases such as zero gradients and numerical stability. The optimizer should be efficient enough to handle large-scale data and converge within a reasonable number of epochs.

Given Info
  • Dataset size: 1 million samples, 1000 features
  • Must handle zero gradients and numerical stability
  • Efficient convergence required
  • Implementation should be in Python using NumPy
  • No use of external libraries like TensorFlow or PyTorch for the optimizer
📋
Guided Steps
1/4
Step 1
Understanding Mini-Batch SGD
What are the key components of mini-batch SGD and how do they affect convergence?
💡 Hint
Consider how batch size impacts the variance of the gradient estimate and the convergence rate.
Key Decision
Choosing an appropriate batch size because it balances gradient variance and computational efficiency.
Interviewer Expectation
Mid: Understands the trade-off between batch size and convergence. Senior: Quantifies the impact of batch size on convergence speed and computational cost.
⚠️Common Wrong Answer
Choosing a very small batch size without considering the increased noise in gradient estimates.
Step 2
Implementing Momentum
How does momentum improve the convergence of SGD, and how should it be implemented?
💡 Hint
Think about how momentum helps in navigating ravines in the loss landscape.
Key Decision
Using momentum to accelerate SGD in the relevant direction and dampen oscillations.
Interviewer Expectation
Mid: Implements basic momentum. Senior: Explains how momentum helps in faster convergence and reduces oscillations in narrow valleys.
⚠️Common Wrong Answer
Ignoring the momentum term, leading to slower convergence in certain loss landscapes.
Step 3
Implementing Adam Optimizer
What are the key differences between Adam and SGD with momentum, and how do they affect implementation?
💡 Hint
Consider how Adam adapts learning rates for each parameter.
Key Decision
Implementing adaptive learning rates because they help in faster convergence and better handling of sparse gradients.
Interviewer Expectation
Mid: Implements Adam with default parameters. Senior: Adjusts hyperparameters based on dataset characteristics and explains the rationale.
⚠️Common Wrong Answer
Using default hyperparameters without considering their impact on convergence for the specific dataset.
Step 4
Handling Edge Cases
How will you ensure your implementation handles edge cases like zero gradients and numerical stability?
💡 Hint
Think about how small values can lead to division by zero or overflow.
Key Decision
Incorporating epsilon to prevent division by zero because it ensures numerical stability.
Interviewer Expectation
Mid: Adds epsilon to prevent division by zero. Senior: Explains the choice of epsilon value and its impact on stability.
⚠️Common Wrong Answer
Neglecting to add epsilon, leading to potential numerical instability.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Correct implementation of mini-batch SGD with momentum
  • Correct implementation of Adam optimizer
  • Handling of zero gradients and numerical stability
  • Efficient handling of large-scale data
  • Use of NumPy for all computations
Good to Have - 30%
  • Explanation of the impact of batch size on convergence
  • Adjustment of Adam hyperparameters based on dataset
  • Quantification of convergence speed improvements with momentum
  • Consideration of computational cost in implementation
Bonus - 10%
  • Discussion of alternative optimizers and their trade-offs
  • Implementation of learning rate scheduling
  • Analysis of convergence behavior on different types of datasets
✅
Model Answer
▼ Reveal

The ideal solution involves implementing mini-batch SGD with momentum and Adam optimizers using NumPy. The implementation should handle edge cases like zero gradients and ensure numerical stability. The candidate should demonstrate an understanding of how batch size, momentum, and adaptive learning rates affect convergence and computational efficiency.

Key Decisions
  • Choosing a batch size that balances gradient variance and computational efficiency.
  • Implementing momentum to accelerate convergence and reduce oscillations.
  • Using adaptive learning rates in Adam to handle sparse gradients effectively.
  • Incorporating epsilon to ensure numerical stability and prevent division by zero.
Anti-patterns
Ignoring the need for numerical stability measures.
Using default hyperparameters without considering dataset characteristics.
Failing to leverage NumPy's vectorized operations for efficiency.
Neglecting the impact of batch size on the variance of gradient estimates.

Practice

(1/5)
1. 
import numpy as np

def numerical_gradient(f, x):
    h = 1e-4
    grad = np.zeros_like(x)
    for i in range(x.size):
        x[i] += h
        fxh1 = f(x)
        x[i] -= 2 * h
        fxh2 = f(x)
        grad[i] = (fxh1 - fxh2) / (2 * h)
        x[i] += h
    return grad

# Test function
f = lambda x: x[0]**2 + x[1]**2
x = np.array([3.0, 4.0])
print(numerical_gradient(f, x))
easy
A. [6.0, 8.0]
B. [6.0001, 8.0001]
C. [5.9999, 7.9999]
D. [0.0, 0.0]

Solution

  1. Step 1: Understand the numerical gradient calculation

    The function calculates the gradient using central difference approximation.

  2. Step 2: Calculate the gradient for each element

    For x = [3.0, 4.0], the gradient is [6.0, 8.0] because the derivative of x^2 is 2x.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Central difference gives exact gradient for quadratic. [OK]
Hint: Central difference gives exact gradient for quadratic. [OK]
Common Mistakes:
2. In the context of implementing backpropagation using NumPy, which of the following is a correct approach to handle vanishing gradients?
medium
A. Use a smaller learning rate.
B. Switch to a sigmoid activation function.
C. Implement gradient clipping.
D. Increase the number of layers in the network.

Solution

  1. Step 1: Identify vanishing gradient issue

    Vanishing gradients occur when gradients become too small to update weights effectively.

  2. Step 2: Correct approach

    Gradient clipping prevents gradients from becoming too small or too large.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Clip gradients to prevent vanishing [OK]
Hint: Clip gradients to prevent vanishing [OK]
Common Mistakes:
3. In the following implementation of scaled dot-product attention, the output is incorrect. What is the likely cause? 
import torch
import torch.nn.functional as F

queries = torch.randn(2, 3)
keys = torch.randn(2, 3)
values = torch.randn(2, 3)

scores = torch.matmul(queries, keys.T) / torch.sqrt(torch.tensor(3.0))
attention_weights = F.softmax(scores, dim=0)
output = torch.matmul(attention_weights, values)
medium
A. Incorrect scaling factor used.
B. Softmax applied on the wrong dimension.
C. Values tensor has incorrect shape.
D. Scores tensor is not normalized.

Solution

  1. Step 1: Identify the issue

    Softmax should be applied on the last dimension, not the first.

  2. Step 2: Eliminate other causes

    Scaling factor and tensor shapes are correct; normalization is handled by softmax.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Softmax on last dim for attention [OK]
Hint: Softmax on last dim for attention [OK]
Common Mistakes:
4. How can you optimize the backward pass of batch normalization to improve computational efficiency?
hard
A. Fuse batch normalization with preceding linear layers.
B. Pre-compute gradients for all layers.
C. Use a smaller batch size to reduce computation.
D. Use a higher learning rate to speed up convergence.

Solution

  1. Step 1: Identify optimization techniques

    Fusing operations can reduce computational overhead.

  2. Step 2: Evaluate each option

    Fusing batch normalization with linear layers reduces redundant computations.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Fuse layers to optimize batch norm [OK]
Hint: Fuse layers to optimize batch norm [OK]
Common Mistakes:
5. How can you optimize the implementation of a learning rate scheduler to reduce computational overhead in a large-scale training setup?
hard
A. Use a scheduler that updates every batch instead of every epoch.
B. Increase the step size in StepLR.
C. Switch to a constant learning rate.
D. Use a custom scheduler with fewer updates.

Solution

  1. Step 1: Identify computational overhead sources

    Frequent updates can increase overhead, especially in large-scale setups.

  2. Step 2: Optimize scheduler updates

    Creating a custom scheduler that reduces the frequency of updates can minimize computational costs while maintaining performance.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Custom schedulers can reduce update frequency. [OK]
Hint: Custom schedulers can reduce update frequency. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard