SGD Parameter Update

1. Background Knowledge

Stochastic Gradient Descent (SGD) is a foundational optimization algorithm in machine learning for minimizing loss functions $L($\mathbf{w}$)$ where $\mathbf{w}$ represents model parameters (weights). The core update rule is:

$\mathbf{w} \leftarrow \mathbf{w} - \alpha \nabla L(\mathbf{w})$

Here, $\alpha$ is the learning rate (step size), and $\nabla L($\mathbf{w}$)$ is the gradient. In full-batch GD, the gradient uses all data; in SGD, it uses a single (or mini-batch) example, making it stochastic but computationally efficient for large datasets.

Key prerequisites:

• Vectors/matrices: Weights $\mathbf{w} \in \mathbb{R}^n$, gradients $\mathbf{dw} \in \mathbb{R}^n$
• Element-wise operations: Update applies independently per parameter: $w_i \leftarrow w_i -$\alpha$\cdot dw_i$
• Numerical stability: Round to 4 decimals as specified to handle floating-point precision.

2. Algorithm Approach

The problem requires vanilla SGD (no momentum, adaptive rates like Adam, or variance reduction). Standard techniques:

• Element-wise vector subtraction: Use NumPy broadcasting for efficiency.
• Simultaneous update: Compute all new weights before overwriting (avoids using updated values prematurely).
• Common libraries: numpy for vectorized operations (assumed available).

Pseudocode:

for each i in 0 to n-1:
 new_weights[i] = weights[i] - learning_rate * gradients[i]
return round(new_weights, 4)

3. Step-by-Step Strategy

1. Validate inputs: Ensure weights and gradients have identical length (1-100 elements per constraints).
2. Initialize output list: Create new list same size as input.
3. Compute updates: For each index $i$, calculate $w_i' = w_i -$\alpha$\cdot dw_i$.
4. Apply rounding: Round each $w_i'$ to 4 decimal places using round(value, 4).
5. Return result: Output as Python list.

Sample Implementation:

def sgd_update(weights, gradients, learning_rate):
 if len(weights) != len(gradients):
 raise ValueError("Weights and gradients must have same length")
 updated = []
 for w, dw in zip(weights, gradients):
 new_w = w - learning_rate * dw
 updated.append(round(new_w, 4))
 return updated

Vectorized (NumPy) version:

import numpy as np
def sgd_update(weights, gradients, learning_rate):
 w = np.array(weights)
 dw = np.array(gradients)
 return np.round(w - learning_rate * dw, 4).tolist()

Verification: [1.0] - 0.1 * [0.5] = [0.95] ✓

4. Common Pitfalls

• In-place updates: weights[i] -= alpha * gradients[i] uses partially updated values, causing errors in multi-parameter cases.
• No rounding: Output [0.949999999] instead of [0.95] fails tests.
• Integer division: Use float inputs/operations (Python 3 handles this).
• Empty lists: Constraints guarantee 1+ elements, but edge case $n=1$ needs testing.
• Sign error: Remember subtract gradient (negative direction reduces loss).
• List vs. NumPy: Return Python list, not array.

5. Time & Space Complexity

• Time: $O(n)$ where $n =$ list length (1-100). Single pass with constant-time operations per element.
• Space: $O(n)$ for output list + $O(n)$ temporary storage. In-place impossible without errors.

LaTeX notation: $\mathcal{O}(n)$ time, $\mathcal{O}(n)$ space.

This covers vanilla SGD parameter update completely—simple but fundamental to all deep learning optimizers!