Simulate gradient accumulation over multiple micro-batches.
In gradient accumulation, we sum gradients over K micro-batches before performing one optimizer step. The effective gradient is the average:
geff=K1∑i=1Kgi
Given a parameter vector, micro-batch gradients, and a learning rate, simulate one full optimization step with gradient accumulation.
Input:
Line 1: K lr (accumulation steps, learning rate)
Line 2: space-separated floats (initial parameter vector)
Next K lines: gradient vectors for each micro-batch
Output: Updated parameter vector after one step: θ' = θ - lr * g_eff, rounded to 4 decimal places.
Example
Input
2 0.1
1.0 2.0
0.5 1.0
1.5 3.0
Output
0.9000 1.8000
Reasoning
We calculate the effective gradient geff by summing the micro-batch gradients and dividing by the number of micro-batches K: geff=21⋅([0.5,1.0]+[1.5,3.0])=21⋅[2.0,4.0]=[1.0,2.0]
Then, we update the parameter vector θ using the formula θ′=θ−lr⋅geff: θ′=[1.0,2.0]−0.1⋅[1.0,2.0]=[1.0,2.0]−[0.1,0.2]=[0.9,1.8]
The final output is the updated parameter vector θ′ rounded to 4 decimal places: [0.9000,1.8000]
Constraints
1 <= K <= 10
Parameter and gradient vectors have same dimension
The problem revolves around gradient accumulation, a technique used in deep learning to simulate large batch sizes by accumulating gradients over multiple micro-batches. This is particularly useful when working with limited computational resources or when the model is too large to fit a full batch in memory. The core concept here is the effective gradient, which is the average of the gradients computed over each micro-batch. This average gradient is then used to update the model's parameters.
In the context of optimization, gradient accumulation is a strategy to improve the stability and efficiency of the training process. By averaging gradients over multiple micro-batches, the model can better capture the overall direction of the gradient, leading to more stable updates. The learning rate plays a crucial role in this process, as it controls how large each update step is. A high learning rate can lead to rapid convergence but also increases the risk of overshooting, while a low learning rate may result in slower convergence.
Understanding vector operations is also essential for this problem. The parameter vector and gradient vectors are all represented as vectors, and operations such as summation and scalar multiplication are performed on these vectors. The effective gradient is computed by summing the gradients over all micro-batches and then dividing by the number of micro-batches, which is a simple yet powerful operation that helps in stabilizing the training process.
Algorithm/Approach
The general approach to solving this problem involves the following pattern:
Read the input parameters, including the number of accumulation steps (K), the learning rate (lr), and the initial parameter vector.
Iterate over each micro-batch, computing the gradient vector for that batch.
Accumulate these gradient vectors to compute the effective gradient.
Use the effective gradient and the learning rate to update the parameter vector.
PRO
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
PRO
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.