📘

Gradient Descent Step

MediumOptimization 📚 CV: Mathematical Foundations

Implement a single step of gradient descent for a 2D function, a fundamental optimization technique in machine learning. This process involves iteratively updating parameters to minimize a function.

Gradient descent is based on the concept of minimizing a function $f(x, y)$ by moving in the direction of the negative gradient, which is a vector of partial derivatives $\nabla f = [\partial f/\partial x, \partial f/\partial y]$ . The update rule for gradient descent can be broken down into steps:

Compute the gradient of the function at the current point.
Scale the gradient by the learning rate $\alpha$ .
Subtract the scaled gradient from the current point to obtain the new point.

\mathbf{x}_{new} = \mathbf{x}_{old} - \alpha \nabla f(\mathbf{x}_{old})

This technique is widely used in machine learning for training models.

Example:

Input:

f(x) = x²
f'(x) = 2x
x₀ = 5.0
learning_rate = 0.1
iterations = 50

Output:

x = 0.0 (minimum found)

Reasoning:

Gradient descent update rule:

$x_{\text{new}} = x_{\text{old}} - \eta \cdot \nabla f(x_{\text{old}})$

where $\eta$ is the learning rate.

Initial state: $x_0 = 5.0$
Iteration 1:
- Gradient: $f'(5.0) = 2 \times 5.0 = 10.0$
- Update: $x_1 = 5.0 - 0.1 \times 10.0 = 4.0$
Iteration 2:
- Gradient: $f'(4.0) = 2 \times 4.0 = 8.0$
- Update: $x_2 = 4.0 - 0.1 \times 8.0 = 3.2$
Pattern: Each step reduces $x$ by 20% $x \rightarrow x - 0.1 \times 2x = x \times (1 - 0.2) = 0.8x$
After many iterations: $x \rightarrow 0$ (the minimum of $x^2$ )
Result: $x \approx 0.0$

The function $f(x) = x^2$ has its minimum at $x = 0$ where $f'(x) = 0$ .

Constraints:

Starting point is [x, y]
Learning rate α > 0
Return new point [x', y'] rounded to 4 decimal places

More from CV: Mathematical Foundations

Adam Optimizer StepHard Power Iteration for Dominant EigenvectorHard SVD Image CompressionHard Batch Affine Transform with PyTorchMedium Covariance Matrix from Image PatchesHard

Gradient Descent Step: Background & Implementation Guide

Background Knowledge

Gradient Descent Fundamentals

Gradient descent is a first-order optimization algorithm used to minimize functions by iteratively moving in the direction of steepest descent. The core intuition is that the gradient $\nabla f($ \mathbf{x} $)$ at any point indicates the direction of greatest increase of the function. By moving in the opposite direction (hence the minus sign), we descend toward lower function values. For a 2D function $f(x, y)$ , the gradient is a vector $[$ \partial $f/$ \partial $x,$ \partial $f/$ \partial $y]$ where each component represents the rate of change along that dimension.

The Learning Rate Parameter

The learning rate $\alpha$ (also called step size) controls how far we move along the negative gradient direction in each iteration. This is a critical hyperparameter: too small a learning rate leads to slow convergence, while too large a learning rate can cause the algorithm to overshoot the minimum or diverge entirely. The update rule $\mathbf{x}_{new} =$ \mathbf{x} $_{old} -$ \alpha\nabla $f($ \mathbf{x} $_{old})$ is a linear approximation based on the first-order Taylor expansion of $f$ around $\mathbf{x}_{old}$ .

Single-Step vs. Iterative Process

This problem focuses on implementing a single gradient descent step—one iteration of the update rule. In practice, gradient descent repeats this process many times until convergence. Understanding how to correctly implement one step is foundational, as the entire algorithm is just this step applied repeatedly.

Algorithm/Approach

The gradient descent step follows a straightforward pattern:

Receive inputs: Current point $\mathbf{x}_{old}$ (coordinates), gradient vector $\nabla f$ , and learning rate $\alpha$
Compute the update: Multiply the gradient by the learning rate: $\alpha$ \nabla $f($ \mathbf{x} $_{old})$
Apply the update: Subtract this scaled gradient from the current point
Return the new point: $\mathbf{x}_{new}$

This is a direct application of the update formula—no iteration loops or convergence checks are needed for a single step.

Step-by-Step Strategy

Step 1: Parse the Input

Extract the current coordinates $(x_{old}, y_{old})$ from $\mathbf{x}_{old}$
Extract the gradient components $($ \partial $f/$ \partial $x,$ \partial $f/$ \partial $y)$ from $\nabla f$
Identify the learning rate $\alpha$

Step 2: Scale the Gradient

Multiply each component of the gradient by the learning rate:
$\Delta x =$ \alpha $\cdot$ \partial $f/$ \partial $x$
$\Delta y =$ \alpha $\cdot$ \partial $f/$ \partial $y$

Step 3: Update Each Coordinate

Subtract the scaled gradient from each coordinate:
$x_{new} = x_{old} - \Delta x$
$y_{new} = y_{old} - \Delta y$

Step 4: Return the Result

Return the new point as a tuple, list, or appropriate data structure matching the expected output format

Common Pitfalls

Sign Error: The most common mistake is adding the gradient instead of subtracting it. Remember: we move opposite to the gradient direction to minimize the function.
Incorrect Scaling: Forgetting to multiply the gradient by the learning rate, or applying the learning rate incorrectly (e.g., dividing instead of multiplying).
Data Type Mismatch: Ensure the output format (tuple, list, array, etc.) matches what the problem expects.
Floating-Point Precision: Be aware that floating-point arithmetic may introduce small rounding errors; avoid overly strict equality comparisons in tests.
Misunderstanding the Gradient: Confusing the gradient (a vector of partial derivatives) with the function value itself. The gradient tells you the direction, not how much the function changes.

Time & Space Complexity

Time Complexity: $\mathcal{O}(1)$ for a 2D function. The update involves a constant number of arithmetic operations (two multiplications and two subtractions), independent of input size.
Space Complexity: $\mathcal{O}(1)$ . You only need to store the current point and gradient vector, both of fixed size (2 elements each for 2D).

For higher-dimensional problems, both complexities scale linearly with the number of dimensions, but for this 2D case, they remain constant.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.