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
Optimize neural networks using advanced gradient descent techniques.
codingadvancedFreq: very_highDeep Learning Coding
Prerequisites:Optimizers - SGDAdamAdaGradBackpropagation implementation
📝
Problem Statement

Implement Mini-Batch Stochastic Gradient Descent (SGD) with Momentum and Adam optimizer from scratch using NumPy. The function should update the weights of a neural network given gradients, learning rate, and other hyperparameters.

I/O Specification
Input:  [object Object]
Output: [object Object]
Example
{
  "input": {
    "weights": "[[0.5, 0.3], [0.2, 0.8]]",
    "gradients": "[[0.1, 0.2], [0.3, 0.4]]",
    "learning_rate": "0.01",
    "momentum": "0.9",
    "beta1": "0.9",
    "beta2": "0.999",
    "epsilon": "1e-8",
    "t": "1"
  },
  "expected_output": "[[0.499, 0.298], [0.197, 0.796]]"
}
🎯
Interview Angles
  • Understanding of momentum in gradient descent and its impact on convergence.
  • Ability to implement adaptive learning rate methods like Adam from scratch.
  • Handling numerical stability issues in optimization algorithms.
  • Comparison of different optimization techniques and their use cases.
🔵
Naive Approach

The naive approach is to implement basic SGD without any enhancements. This involves updating the weights directly using the gradients and learning rate.

Time: O(n * d) - n weights, each updated in O(1), Space: O(n * d) - space for updated weights
Why Insufficient
This approach does not account for momentum or adaptive learning rates, which can lead to slow convergence and poor performance on complex loss surfaces.
🐍
Naive Code
Python
import numpy as np

def naive_sgd(weights, gradients, learning_rate):
    return weights - learning_rate * gradients

# Driver example
weights = np.array([[0.5, 0.3], [0.2, 0.8]])
gradients = np.array([[0.1, 0.2], [0.3, 0.4]])
learning_rate = 0.01
updated_weights = naive_sgd(weights, gradients, learning_rate)
print(updated_weights)
💡
Key Insight
Use momentum to accelerate SGD in the relevant direction and dampen oscillations. For Adam, maintain running averages of both the gradients and their squares to adaptively adjust the learning rate for each parameter.
🐍
Optimized Code
Python
import numpy as np

def sgd_with_momentum(weights, gradients, learning_rate, momentum, velocity):
    velocity = momentum * velocity - learning_rate * gradients
    return weights + velocity, velocity

def adam(weights, gradients, learning_rate, beta1, beta2, epsilon, m, v, t):
    m = beta1 * m + (1 - beta1) * gradients
    v = beta2 * v + (1 - beta2) * (gradients ** 2)
    m_hat = m / (1 - beta1 ** t)
    v_hat = v / (1 - beta2 ** t)
    weights_update = learning_rate * m_hat / (np.sqrt(v_hat) + epsilon)
    return weights - weights_update, m, v

# Driver example for SGD with Momentum
weights = np.array([[0.5, 0.3], [0.2, 0.8]])
gradients = np.array([[0.1, 0.2], [0.3, 0.4]])
learning_rate = 0.01
momentum = 0.9
velocity = np.zeros_like(weights)
updated_weights, velocity = sgd_with_momentum(weights, gradients, learning_rate, momentum, velocity)
print(updated_weights)

# Driver example for Adam
weights = np.array([[0.5, 0.3], [0.2, 0.8]])
gradients = np.array([[0.1, 0.2], [0.3, 0.4]])
learning_rate = 0.01
beta1 = 0.9
beta2 = 0.999
epsilon = 1e-8
m = np.zeros_like(weights)
v = np.zeros_like(weights)
t = 1
updated_weights, m, v = adam(weights, gradients, learning_rate, beta1, beta2, epsilon, m, v, t)
print(updated_weights)
🔍
Line-by-Line
velocity = momentum * velocity - learning_rate * gradients
Update velocity with momentum term and gradient descent step.
return weights + velocity, velocity
Update weights using the velocity and return the new velocity.
m = beta1 * m + (1 - beta1) * gradients
Compute the biased first moment estimate.
v = beta2 * v + (1 - beta2) * (gradients ** 2)
Compute the biased second raw moment estimate.
m_hat = m / (1 - beta1 ** t)
Correct bias in first moment estimate.
v_hat = v / (1 - beta2 ** t)
Correct bias in second moment estimate.
weights_update = learning_rate * m_hat / (np.sqrt(v_hat) + epsilon)
Compute the parameter update using the corrected moments.
⚡
Complexity
Time: O(n * d) - n weights, each updated in O(1), Space: O(n * d) - space for velocity, m, and v
Output
[[0.499, 0.298], [0.197, 0.796]]
🔲
Edge Cases
Zero Gradients
Weights remain unchanged as the update step is zero.
velocity = momentum * velocity - learning_rate * gradients
High Momentum
Can lead to overshooting if not dampened by learning rate.
velocity = momentum * velocity - learning_rate * gradients
Small Epsilon in Adam
Prevents division by zero in the update step.
weights_update = learning_rate * m_hat / (np.sqrt(v_hat) + epsilon)
⚠️
Common Mistakes
Forgetting to initialize velocity, m, or v to zero arrays.
Symptom: Uninitialized variables lead to incorrect weight updates.
Incorrect bias correction in Adam.
Symptom: Leads to slower convergence or divergence.
Using incorrect shapes for gradients or weights.
Symptom: Shape mismatch errors during computation.
Not updating the time step t in Adam.
Symptom: Bias correction does not work properly, affecting convergence.

Practice

(1/5)
1. What is the time complexity of calculating the Euclidean distance between two vectors of length n?
easy
A. O(n^2)
B. O(1)
C. O(n log n)
D. O(n)

Solution

  1. Step 1: Understand Euclidean distance calculation

    Euclidean distance involves element-wise operations and a square root.

  2. Step 2: Analyze operations

    Each element is processed once, leading to O(n) complexity.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Element-wise operations imply O(n). [OK]
Hint: Element-wise operations imply O(n). [OK]
Common Mistakes:
2. What does the following Python code snippet output when implementing the Skip-Gram model with negative sampling? 
import numpy as np

vocab_size = 5
embedding_dim = 3

# Initialize random embeddings
embeddings = np.random.rand(vocab_size, embedding_dim)

# Select a word index
word_index = 2

# Get the embedding for the word
word_embedding = embeddings[word_index]

print(word_embedding.shape)
easy
A. (3, 5)
B. (5, 3)
C. (3,)
D. (1, 3)

Solution

  1. Step 1: Understand the code

    The code initializes a random embedding matrix of shape (vocab_size, embedding_dim) and retrieves the embedding for a specific word index.

  2. Step 2: Determine the shape of the retrieved embedding

    The embedding for a single word is a 1D array with length equal to embedding_dim, hence the shape is (3,).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Single word embedding shape is (embedding_dim,) [OK]
Hint: Single word embedding shape is (embedding_dim,) [OK]
Common Mistakes:
3. In a multi-class classification problem, how would you modify the softmax function to handle very large input values?
medium
A. Subtract the maximum input value before applying softmax.
B. Subtract the mean of the input values before applying softmax.
C. Use a sigmoid function instead of softmax.
D. Apply a logarithmic transformation to the inputs before softmax.

Solution

  1. Step 1: Address numerical stability

    Subtracting the max input value prevents overflow in exponentials.

  2. Step 2: Ensure correct probabilities

    This adjustment maintains the relative differences between inputs.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Subtract max for stability in softmax [OK]
Hint: Subtract max for stability in softmax [OK]
Common Mistakes:
4. You implemented a train-test split with stratification, but the test set has a different class distribution than expected. What is the most likely cause?
medium
A. Incorrect test_size parameter
B. Stratify parameter not set correctly
C. Data leakage between train and test sets
D. Random state not fixed

Solution

  1. Step 1: Identify the role of stratification

    Stratification ensures class distribution is maintained across splits.

  2. Step 2: Diagnose the issue

    If the stratify parameter is not set correctly, class distribution will not be maintained.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Check stratify parameter for distribution issues. [OK]
Hint: Check stratify parameter for distribution issues. [OK]
Common Mistakes:
5. How can you optimize the mAP calculation for a large dataset with thousands of images and bounding boxes?
hard
A. Use parallel processing to compute IoU for each image
B. Reduce the number of bounding boxes by increasing the confidence threshold
C. Precompute IoU values for all possible box pairs
D. Use a more efficient data structure for storing bounding boxes

Solution

  1. Step 1: Identify the Bottleneck

    Calculating IoU for many boxes is computationally expensive.

  2. Step 2: Evaluate Optimization Strategies

    Use parallel processing to compute IoU for each image: Parallel processing can significantly speed up IoU calculations. Reduce the number of bounding boxes by increasing the confidence threshold: Reducing boxes might miss important detections. Precompute IoU values for all possible box pairs: Precomputing is infeasible due to combinatorial explosion. Use a more efficient data structure for storing bounding boxes: Efficient data structures help but don't address computation directly.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Parallelize IoU for large datasets [OK]
Hint: Parallelize IoU for large datasets [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