Optimization Difficulty: Intermediate

Gradient Descent

Gradient descent iteratively moves in the direction of the negative gradient to minimize a function. It is the workhorse of modern machine learning optimization.

Key Points

  • For convex Lipschitz-smooth functions, gradient descent converges at rate $O(1/k)$.
  • Step size (learning rate) selection strongly affects convergence.
  • Momentum, AdaGrad, and Adam adapt the update direction or step size.

Formulas

Gradient descent update
$$x_{k+1} = x_k - \eta \nabla f(x_k)$$
Convergence rate (convex, L-smooth)
$$f(x_k) - f^* \le \frac{2L\|x_0 - x^*\|^2}{k}$$
Momentum
$$v_{k+1} = \beta v_k + \nabla f(x_k), \quad x_{k+1} = x_k - \eta v_{k+1}$$

Code Example

import numpy as np

def grad_f(x):
    return 2*x + 4  # f(x) = x^2 + 4x

x = 0.0
eta = 0.1
for _ in range(50):
    x -= eta * grad_f(x)
print(x)  # ~ -2

Applications

Tags

  • first-order-methods
  • iterative

References

  • Convex Optimization
    Stephen Boyd and Lieven Vandenberghe · Cambridge University Press · source
  • Optimization Methods for Large-Scale Machine Learning
    Léon Bottou, Frank E. Curtis, and Jorge Nocedal · SIAM Review · source

Knowledge Graph