Bird
Raised Fist0

Implement Mini-Batch SGD with Momentum and Adam

CODINGadvancedInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
Mini-Batch SGD with Momentum vs Adam

In a deep learning model training scenario with limited compute resources, would you choose Mini-Batch SGD with Momentum or Adam? Justify your choice.

📊
Comparison
DimensionMini-Batch SGD with MomentumAdam
Convergence SpeedMediumHigh
Memory UsageLowHigh
Parameter SensitivityHighMedium
Stability on Convex ProblemsHighMedium
Adaptability to Non-Convex ProblemsLowHigh
✅
Verdict
Default to Adam for non-convex problems with sufficient compute resources and a short training time budget. Switch to Mini-Batch SGD with Momentum for convex problems with large datasets and limited compute resources.
💡
Key Insight
The choice between Mini-Batch SGD with Momentum and Adam hinges on problem convexity and resource availability.
⚠️
Interview Trap
❌ Wrong: Always use Adam because it converges faster.
This ignores the stability and memory efficiency of Mini-Batch SGD with Momentum in convex problems.
✅ Consider the problem's convexity and resource constraints; use Adam for non-convex problems with ample resources, and Mini-Batch SGD with Momentum for convex problems with limited resources.
Mini-Batch SGD with Momentum
"Stability in convergence for convex problems"
Weaknesses
  • Requires careful tuning of learning rate and momentum parameters
  • Slower convergence on non-convex problems compared to adaptive methods
  • Sensitive to initial parameter settings
Ideal When
  • n > 100K and data is convex
  • limited compute resources
  • training time > 24h
Google uses Mini-Batch SGD with Momentum for training large-scale linear models where convexity is guaranteed.
Adam
"Fast convergence on non-convex problems"
Weaknesses
  • Higher memory usage due to additional parameters
  • Can lead to suboptimal convergence in some convex problems
  • Sensitive to hyperparameter settings like beta1 and beta2
Ideal When
  • n < 100K and data is non-convex
  • sufficient compute resources
  • training time < 12h
OpenAI uses Adam for training deep neural networks where fast convergence is critical.
🐍
Mini-Batch SGD with Momentum - Example
▼ Show
Python
import numpy as np

# Initialize parameters
params = np.random.randn(10)
velocity = np.zeros_like(params)
learning_rate = 0.01
momentum = 0.9

# Update rule
for i in range(100):
    grad = compute_gradient(params)
    velocity = momentum * velocity - learning_rate * grad  # Apply momentum
    params += velocity  # Update parameters
🐍
Adam - Example
▼ Show
Python
import numpy as np

# Initialize parameters
params = np.random.randn(10)
m = np.zeros_like(params)
v = np.zeros_like(params)
learning_rate = 0.001
beta1 = 0.9
beta2 = 0.999
epsilon = 1e-8

# Update rule
for i in range(100):
    grad = compute_gradient(params)
    m = beta1 * m + (1 - beta1) * grad  # Update biased first moment estimate
    v = beta2 * v + (1 - beta2) * (grad ** 2)  # Update biased second raw moment estimate
    m_hat = m / (1 - beta1 ** (i + 1))  # Compute bias-corrected first moment estimate
    v_hat = v / (1 - beta2 ** (i + 1))  # Compute bias-corrected second raw moment estimate
    params -= learning_rate * m_hat / (np.sqrt(v_hat) + epsilon)  # Update parameters
✅
Use Mini-Batch SGD with Momentum When
  • •n > 100K and data is convex
  • •limited compute resources
  • •training time > 24h
✅
Use Adam When
  • •n < 100K and data is non-convex
  • •sufficient compute resources
  • •training time < 12h
↳
Nuances
  • For very large datasets with convex loss functions, Mini-Batch SGD with Momentum can outperform Adam due to its stability.
  • In scenarios where memory is a constraint, Mini-Batch SGD with Momentum is preferable due to its lower memory footprint.
  • Adam's fast convergence can lead to overfitting if not properly regularized, especially in small datasets.

Practice

(1/5)
1. What is the time complexity of the forward pass of batch normalization for a dataset with n samples and d features?
easy
A. O(n + d)
B. O(n^2)
C. O(d^2)
D. O(n * d)

Solution

  1. Step 1: Analyze the operations

    Batch normalization involves computing mean and variance, both O(n * d) operations.

  2. Step 2: Consider the normalization step

    Normalizing each feature is also O(n * d).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Batch norm: O(n * d) for mean/variance [OK]
Hint: Batch norm: O(n * d) for mean/variance [OK]
Common Mistakes:
2. What is the time complexity of computing the ROC curve using the sklearn library?
easy
A. O(n log n)
B. O(n^2)
C. O(n)
D. O(log n)

Solution

  1. Step 1: Understand ROC computation

    ROC curve computation involves sorting the scores, which is O(n log n).

  2. Step 2: Eliminate wrong options

    O(n^2) is incorrect as it suggests quadratic complexity, O(n) suggests linear complexity which ignores sorting, and O(log n) is too low.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    ROC curve involves sorting, hence O(n log n) [OK]
Hint: ROC curve involves sorting, hence O(n log n) [OK]
Common Mistakes:
3. You implemented a KNN classifier using a KD-Tree, but it returns incorrect classifications. What is the most likely cause?
medium
A. The distance metric used is incorrect.
B. The KD-Tree is not balanced.
C. The KD-Tree was built with insufficient data.
D. The KD-Tree does not support high-dimensional data well.

Solution

  1. Step 1: Identify potential issues

    Incorrect classifications often stem from using an inappropriate distance metric.

  2. Step 2: Eliminate other options

    A: Balancing affects efficiency, not correctness. C: Insufficient data affects accuracy, not correctness. D: High-dimensionality affects efficiency, not correctness.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check distance metric for KD-Tree issues [OK]
Hint: Check distance metric for KD-Tree issues [OK]
Common Mistakes:
4. In a text classification task using Multinomial Naive Bayes, which preprocessing step is crucial for improving model performance?
medium
A. Normalizing feature values
B. Scaling features to [0, 1]
C. Removing stop words
D. Applying PCA for dimensionality reduction

Solution

  1. Step 1: Understand text preprocessing needs

    In text classification, irrelevant words can add noise.

  2. Step 2: Evaluate preprocessing steps

    Removing stop words (Removing stop words) reduces noise and improves performance. Options A and C are less relevant as MultinomialNB doesn't require normalized or scaled features. Applying PCA for dimensionality reduction is unnecessary as PCA isn't typically used for text data.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Remove stop words to reduce noise in text data. [OK]
Hint: Remove stop words to reduce noise in text data. [OK]
Common Mistakes:
5. How can you optimize a naive 2D convolution implementation for large images and kernels?
hard
A. Use a larger stride to reduce computation.
B. Use a smaller kernel to decrease computation.
C. Implement convolution using FFT (Fast Fourier Transform).
D. Increase the kernel size to cover more area.

Solution

  1. Step 1: Identify optimization techniques

    Using FFT can significantly reduce the computational complexity of convolution from O(N^2 * K^2) to O(N^2 log N) for large images and kernels.

  2. Step 2: Eliminate wrong options

    Use a larger stride to reduce computation. reduces output size, not computation. Increase the kernel size to cover more area. increases computation. Use a smaller kernel to decrease computation. limits kernel effectiveness.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    FFT reduces convolution complexity. [OK]
Hint: FFT reduces convolution complexity. [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