Bird
Raised Fist0

Implement Mini-Batch SGD with Momentum and Adam

CODINGadvancedInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
▶
Execution Trace
Step 1/6
Initial parameter and gradient

Initial param = 0.5, grad = 0.1

🎯 Understanding initial conditions is crucial for debugging.
param = 0.5
grad = 0.1
Momentum update

v = 0.9 * 0 - 0.01 * 0.1 = -0.001

🎯 Momentum helps in accelerating gradients vectors in the right directions.
v = 0.9 * v - 0.01 * grad
Parameter update with momentum

Updated param = 0.5 + (-0.001) = 0.499

🎯 Parameter update step is crucial for convergence.
param += v
Adam first moment estimate

m = 0.9 * 0 + 0.1 * 0.1 = 0.01

🎯 First moment estimate smooths the gradient.
m = 0.9 * m + 0.1 * grad
Adam second moment estimate

v = 0.999 * 0 + 0.001 * 0.01 = 0.000001

🎯 Second moment estimate helps in scaling the learning rate.
v = 0.999 * v + 0.001 * (grad ** 2)
Parameter update with Adam

Updated param = 0.499 - 0.01 * (0.01 / (sqrt(0.000001) + 1e-8)) = 0.489

🎯 Adam combines momentum and adaptive learning rates for efficient updates.
param -= 0.01 * (m / (sqrt(v) + 1e-8))
📊
Diagram
Diagram
┌───────────────────────────────┐
│ Mini-Batch SGD with Momentum │
├───────────────────────────────┤
│ t = 1                         │
│ v = 0.9 * v - lr * grad       │
│ param += v                    │
├───────────────────────────────┤
│ Adam Optimizer               │
├───────────────────────────────┤
│ t = 1                         │
│ m = β1 * m + (1-β1) * grad    │
│ v = β2 * v + (1-β2) * grad^2  │
│ m_hat = m / (1-β1^t)          │
│ v_hat = v / (1-β2^t)          │
│ param -= lr * m_hat / (sqrt(v_hat) + ε) │
└───────────────────────────────┘
Labels
  • Mini-Batch SGD: Update rule with momentum
  • Adam Optimizer: Adaptive learning rate with bias correction
  • v: Velocity term in momentum
  • m, v: First and second moment estimates in Adam
  • param: Model parameters being updated
🔑
Key Moments
▲
Q: Why does momentum help in gradient descent?
A: Momentum helps by accelerating gradients vectors in the right directions, thus leading to faster convergence.
Q: How does Adam adjust the learning rate?
A: Adam adjusts the learning rate by using first and second moment estimates to scale the learning rate adaptively.
Q: What is the role of bias correction in Adam?
A: Bias correction in Adam ensures that the moment estimates are unbiased, especially in the initial steps.
Trace Summary

This diagram and trace illustrate the implementation of Mini-Batch SGD with Momentum and the Adam optimizer. The diagram shows the update rules for both methods, highlighting the role of momentum and adaptive learning rates. The trace steps through the algorithm, showing how parameters are updated using momentum and Adam's moment estimates. Key insights include the acceleration of gradient descent with momentum and the adaptive learning rate adjustments in Adam, which are crucial for efficient optimization.

Primary Focus

✓ Implementing optimization algorithms with momentum and adaptive learning rates

Practice

(1/5)
1. What is the time complexity of computing a confusion matrix for a binary classification problem with n predictions?
easy
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(1)

Solution

  1. Step 1: Analyze the operation

    Computing a confusion matrix involves iterating over predictions once.

  2. Step 2: Determine complexity

    Each prediction is checked once, leading to O(n) complexity.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Confusion matrix computation is linear in predictions. [OK]
Hint: Confusion matrix computation is linear in predictions. [OK]
Common Mistakes:
2. What is the time complexity of calculating the entropy for a dataset with n samples?
easy
A. O(log n)
B. O(n log n)
C. O(n^2)
D. O(n)

Solution

  1. Step 1: Analyze entropy calculation

    Entropy calculation involves counting occurrences and computing probabilities, both O(n).

  2. Step 2: Eliminate wrong options

    O(n^2) and O(n log n) are incorrect as they overestimate the operations needed.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Entropy calculation is linear in n [OK]
Hint: Entropy calculation is linear in n [OK]
Common Mistakes:
3. What does the following Python code snippet output when implementing sinusoidal positional encoding?
import numpy as np

def positional_encoding(position, d_model):
    angle_rads = np.arange(position)[:, np.newaxis] / np.power(10000, (2 * (np.arange(d_model)[np.newaxis, :] // 2)) / np.float32(d_model))
    angle_rads[:, 0::2] = np.sin(angle_rads[:, 0::2])
    angle_rads[:, 1::2] = np.cos(angle_rads[:, 1::2])
    return angle_rads

pe = positional_encoding(4, 4)
print(pe)
easy
A. A 4x4 matrix with alternating sine and cosine values
B. A 4x4 matrix with random values
C. A 4x4 identity matrix
D. A 4x4 matrix with all zeros

Solution

  1. Step 1: Understand the code logic

    The code generates a matrix where each row corresponds to a position and each column to a dimension, filled with sinusoidal values.

  2. Step 2: Eliminate wrong options

    A 4x4 matrix with all zeros is incorrect because the matrix is not filled with zeros. A 4x4 identity matrix is incorrect because the matrix is not an identity matrix. A 4x4 matrix with random values is incorrect because the values are not random but deterministic sinusoidal values.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Sinusoidal encoding alternates sine/cosine. [OK]
Hint: Sinusoidal encoding alternates sine/cosine. [OK]
Common Mistakes:
4. What is the time complexity of computing the scaled dot-product attention for a single query with n keys?
easy
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(1)

Solution

  1. Step 1: Identify operations

    For a single query, the main operations are dot product and softmax, both O(n).

  2. Step 2: Eliminate incorrect complexities

    O(n^2) and O(n log n) are incorrect as they imply more complex operations than present.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Single query, n keys -> O(n) [OK]
Hint: Single query, n keys -> O(n) [OK]
Common Mistakes:
5. In a recommendation system, why might you choose NDCG over precision at k?
medium
A. NDCG is easier to compute.
B. NDCG considers the position of relevant items.
C. NDCG is less sensitive to irrelevant items.
D. NDCG is more interpretable than precision.

Solution

  1. Step 1: Understand NDCG vs Precision

    NDCG accounts for the position of relevant items, giving higher scores to relevant items at higher ranks.

  2. Step 2: Evaluate Options

    Precision at k does not consider the order of items, only their presence.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    NDCG values position. [OK]
Hint: NDCG values position. [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