Gradient-Based Methods

a class of optimization algorithms that use the gradient (first derivative) of the objective function to guide the search for an optimal solution. These methods rely on the intuition that the negative gradient points in the direction of steepest descent.

Mathematical Foundation

For an objective function $L(\theta )$ where $\theta \in {\mathbb{R}}^D$, gradient-based methods utilize the gradient vector:

$\nabla L(\theta )={\left[\frac{\partial L}{\partial {\theta }_1},\frac{\partial L}{\partial {\theta }_2},\dots ,\frac{\partial L}{\partial {\theta }_D}\right]}^T$

The negative gradient $-\nabla L(\theta )$ points in the direction of steepest descent of the function at the current point.

General Update Rule

The general form of gradient-based methods follows the update rule:

${\theta }_{k+1}={\theta }_k-{\alpha }_k\nabla L({\theta }_k)$

where:

• ${\theta }_k$ is the parameter vector at iteration $k$
• ${\alpha }_k$ is the step size (or learning rate)
• $\nabla L({\theta }_k)$ is the gradient at ${\theta }_k$

Key Gradient-Based Methods

Gradient Descent (Steepest Descent)

The most basic gradient-based method, which directly follows the negative gradient direction:

1. Initialize ${\theta }_0$
2. For each iteration $k$:
   • Compute gradient $\nabla L({\theta }_k)$
   • Determine step size ${\alpha }_k$
   • Update: ${\theta }_{k+1}={\theta }_k-{\alpha }_k\nabla L({\theta }_k)$
3. Repeat until convergence criteria are met

Variants of Gradient Descent

• Batch Gradient Descent: Uses the entire dataset to compute the gradient
• Stochastic Gradient Descent (SGD): Uses a single sample to approximate the gradient
• Mini-batch Gradient Descent: Uses a small subset of samples to approximate the gradient

Momentum Method

Accelerates convergence by incorporating past gradients:

$v_{k+1}=\beta v_k+\nabla L({\theta }_k)$ ${\theta }_{k+1}={\theta }_k-{\alpha }_k{v}_{k+1}$

where $\beta \in [0,1)$ is the momentum parameter that determines how much past gradients influence the current update.

Conjugate Gradient Method

Utilizes conjugate directions to achieve faster convergence:

1. Initialize ${\theta }_0$, ${\mathbf{g}}_0=\nabla L({\theta }_0)$, ${\mathbf{p}}_0=-{\mathbf{g}}_0$
2. For each iteration $k$:
   • Determine step size ${\alpha }_k$ via line search
   • Update: ${\theta }_{k+1}={\theta }_k+{\alpha }_k{\mathbf{p}}_k$
   • Compute new gradient: ${\mathbf{g}}_{k+1}=\nabla L({\theta }_{k+1})$
   • Compute scaling factor (Fletcher-Reeves formula): ${\beta }_k=\frac{{\mathbf{g}}_{k+1}^T{\mathbf{g}}_{k+1}}{{\mathbf{g}}_k^T{\mathbf{g}}_k}$
   • Update direction: ${\mathbf{p}}_{k+1}=-{\mathbf{g}}_{k+1}+{\beta }_k{\mathbf{p}}_k$
3. Repeat until convergence

Adaptive Gradient Methods

Adapt the learning rate for each parameter based on historical gradients:

• AdaGrad: Divides the learning rate by the square root of the sum of squared past gradients
• RMSProp: Uses an exponentially weighted average of squared gradients
• Adam: Combines momentum with RMSProp

Step Size Determination

The performance of gradient-based methods heavily depends on the choice of step size ${\alpha }_k$:

Fixed Step Size

Using a constant ${\alpha }_k=\alpha$ for all iterations. Simple but often inefficient, requiring careful tuning.

Line Search Methods

Determine the optimal step size by solving a one-dimensional optimization problem at each iteration:

${\alpha }_k=\arg {\min }_{\alpha \ge 0}L({\theta }_k-\alpha \nabla L({\theta }_k))$

Exact line search is often computationally expensive, so approximate methods are used:

Backtracking Line Search

1. Start with initial step size $\alpha =\bar{\alpha }$
2. If $L({\theta }_k-\alpha \nabla L({\theta }_k))>L({\theta }_k)-c\alpha |\nabla L({\theta }_k){|}^2$, then reduce $\alpha =\rho \alpha$ and repeat
3. Where $c\in (0,1)$ and $\rho \in (0,1)$ are parameters

Strong Wolfe Conditions

Ensures sufficient decrease and gradient magnitude reduction:

1. $L({\theta }_k+{\alpha }_k{\mathbf{p}}_k)\le L({\theta }_k)+c_1{\alpha }_k\nabla L({\theta }_k{)}^T{\mathbf{p}}_k$ (Armijo condition)
2. $|\nabla L({\theta }_k+{\alpha }_k{\mathbf{p}}_k{)}^T{\mathbf{p}}_k|\le c_2|\nabla L({\theta }_k{)}^T{\mathbf{p}}_k|$ (curvature condition)

where $0<c_1<c_2<1$

Adaptive Step Sizes

Methods like AdaGrad, RMSProp, and Adam automatically adjust step sizes for each parameter based on the history of gradients.

Convergence Properties

Convergence Rate

For convex functions with Lipschitz continuous gradients:

• Gradient descent with fixed step size: $O(1/k)$ sublinear convergence
• Gradient descent with optimal step size: $O(1/k)$ sublinear convergence
• Accelerated methods (e.g., momentum): $O(1/k^2)$ sublinear convergence
• Conjugate gradient: Linear convergence, guaranteed to converge in $n$ steps for quadratic functions in ${\mathbb{R}}^n$

Convergence Guarantees

• For convex functions: Convergence to global minimum
• For non-convex functions: Convergence to local minimum or saddle point
• For strongly convex functions with appropriate step size: Linear convergence rate

Challenges and Limitations

Zig-Zagging

Gradient descent can exhibit zig-zagging behavior in narrow valleys, where the negative gradient points across the valley rather than along it.

Ill-Conditioning

When the Hessian has a high condition number (ratio of largest to smallest eigenvalue), gradient descent converges very slowly. The contours of the objective function become elongated ellipses rather than circles.

Saddle Points

In high-dimensional non-convex problems, saddle points (where the gradient is zero but not a minimum) can significantly slow down gradient-based methods.

Local Minima

Gradient-based methods can get trapped in local minima, missing the global optimum in non-convex problems.

Implementation Considerations

Gradient Evaluation

• Analytical gradients: Most accurate but may be complex to derive
• Numerical gradients: Approximated using finite differences, less accurate but universal
• Automatic differentiation: Combines accuracy of analytical with convenience of numerical methods

Preconditioning

Transforming the optimization problem to improve conditioning:

${\theta }_{k+1}={\theta }_k-{\alpha }_k{\mathbf{P}}_k\nabla L({\theta }_k)$

where ${\mathbf{P}}_k$ is a preconditioning matrix that approximates the inverse Hessian.

Mini-Batch Processing

For large datasets, using mini-batches to approximate gradients can significantly speed up computation:

$\nabla L(\theta )\approx \frac{1}{|B|}{\sum }_{i\in B}\nabla L_i(\theta )$

where $B$ is a mini-batch of samples.

Applications

Gradient-based methods are widely used in:

• Machine Learning: Training neural networks and other parametric models
• Image and Signal Processing: Image reconstruction, signal enhancement
• Control Theory: Optimal control strategies
• Economics: Portfolio optimization, utility maximization
• Engineering Design: Parameter tuning, shape optimization

Related Pages

• Numerical Methods
• Stochastic Gradient Descent
• Conjugate Gradient Method
• Line Search Methods
• Adaptive Gradient Methods
• Newton-Raphson Method
• Quasi-Newton Methods