Gradient Descent

Definition and Purpose

What is Gradient Descent?

Gradient descent: iterative optimization algorithm. Purpose: minimize differentiable objective functions. Core idea: use gradient to find direction of steepest descent. Widely used in machine learning: optimize model parameters by minimizing loss functions.

Historical Context

Origin: 1847 by Cauchy. Popularized in machine learning since 1950s. Key to training neural networks, regression models, and other parametric methods.

Role in Optimization

Optimization: find minimum of function f(θ). Gradient descent: update parameters θ iteratively in negative gradient direction. Applicable to convex and non-convex problems.

"Gradient descent is the backbone of modern machine learning optimization." -- Yann LeCun

Mathematical Formulation

Objective Function

Given function f: ℝⁿ → ℝ, goal: find θ* = argmin_θ f(θ). Assumption: f is differentiable. Gradient ∇f(θ) indicates local slope.

Update Rule

Parameters θ updated iteratively: move opposite to gradient scaled by learning rate α.

θₖ₊₁ = θₖ - α ∇f(θₖ)

Gradient Vector

Gradient ∇f(θ) = [∂f/∂θ₁, ∂f/∂θ₂, ..., ∂f/∂θₙ]ᵀ. Direction of steepest ascent. Negative gradient: steepest descent.

Algorithm Variants

Batch Gradient Descent

Uses entire dataset to compute gradient per iteration. Stable updates but computationally expensive for large data.

Stochastic Gradient Descent (SGD)

Updates parameters per single data point. Faster iterations, noisier updates, can escape shallow local minima.

Mini-batch Gradient Descent

Compromise: compute gradient on small data batches. Balances speed and stability.

Comparison Table

Learning Rate and Its Impact

Definition

Learning rate α: positive scalar controlling step size per iteration. Critical hyperparameter for convergence speed and accuracy.

Too Large α

Can cause divergence or oscillations. Overshooting minima. Instability in updates.

Too Small α

Slow convergence. Excessive computation time. Risk of getting stuck in local minima.

Adaptive Learning Rates

Techniques: decay schedules, adaptive optimizers (Adam, RMSProp). Adjust α dynamically for efficiency and stability.

Convergence Analysis

Convex Functions

Gradient descent guarantees convergence to global minimum. Rate depends on smoothness and strong convexity.

Non-Convex Functions

May converge to local minima or saddle points. SGD can help escape shallow traps.

Convergence Rate

Typically linear for strongly convex functions. Sublinear for convex but not strongly convex.

Mathematical Bounds

If f is L-smooth and μ-strongly convex:||θₖ - θ*|| ≤ (1 - αμ)^k ||θ₀ - θ*|| 

Cost Functions and Gradient Computation

Common Cost Functions

Mean Squared Error (MSE), Cross-Entropy, Hinge Loss, Log Loss. Differentiability required for gradient computation.

Gradient Calculation

Analytical gradients: explicit formulas. Numeric gradients: finite differences (less efficient). Automatic differentiation: widely used in frameworks.

Example: Linear Regression

Cost: J(θ) = (1/2m) Σ (h_θ(xᵢ) - yᵢ)²Gradient: ∇J(θ) = (1/m) Xᵀ(Xθ - y) 

Batch vs Stochastic Gradient Descent

Batch GD Characteristics

Stable convergence. Requires entire dataset in memory. Slow for large datasets.

Stochastic GD Characteristics

Fast updates. High variance in gradient estimates. Useful for online learning.

Mini-batch Advantages

Improves computational efficiency. Reduces variance compared to SGD. Enables parallelism.

Practical Considerations

Batch size selection impacts performance and memory usage. Typical mini-batch sizes: 32–256.

Momentum and Advanced Optimizers

Momentum

Acceleration technique: incorporates past gradients to smooth updates. Formula:

vₖ = βvₖ₋₁ + (1 - β)∇f(θₖ)θₖ₊₁ = θₖ - α vₖ 

Adaptive Methods

Adam, RMSProp, Adagrad: adapt learning rate per parameter using historical gradients. Improve convergence on complex problems.

Comparison Table

Applications in Machine Learning

Supervised Learning

Training linear models, logistic regression, support vector machines. Optimize parameters to minimize prediction error.

Neural Networks

Backpropagation uses gradient descent to update weights. Essential for deep learning architectures.

Unsupervised Learning

Clustering, dimensionality reduction (e.g., autoencoders). Optimization of reconstruction or similarity loss.

Reinforcement Learning

Policy gradient methods: optimize expected rewards using gradient ascent/descent techniques.

Limitations and Challenges

Local Minima and Saddle Points

Non-convex functions: may converge to local minima or get stuck at saddle points. SGD variants mitigate this.

Choice of Hyperparameters

Learning rate, batch size, momentum require tuning. Poor selection degrades performance.

Computational Cost

Large datasets and complex models demand significant resources. Approximate methods and hardware acceleration help.

Gradient Vanishing and Exploding

Particularly in deep networks. Causes slow or unstable training. Techniques like normalization and careful initialization address this.

Practical Implementation Tips

Feature Scaling

Normalize or standardize features. Improves convergence speed and stability.

Initialization

Random but controlled parameter initialization. Avoids symmetry and poor local minima.

Learning Rate Scheduling

Decay learning rate over time or use adaptive optimizers. Prevent overshooting and improve fine tuning.

Early Stopping

Monitor validation loss. Stop training to prevent overfitting.

Gradient Checking

Verify analytical gradients with numerical approximations. Detect bugs in implementation.

Case Studies and Examples

Linear Regression Example

Dataset: housing prices. Objective: minimize MSE. Batch gradient descent iteratively updates weights until convergence.

Initialize θ randomlyRepeat until convergence: θ := θ - α * (1/m) * Xᵀ(Xθ - y) 

Training a Neural Network

Use mini-batch SGD with momentum. Backpropagation computes gradients. Adam optimizer enhances convergence.

Logistic Regression for Classification

Optimize cross-entropy loss using stochastic gradient descent. Regularization added to prevent overfitting.

Empirical Results

References

• Ruder, S. "An overview of gradient descent optimization algorithms." arXiv preprint arXiv:1609.04747, 2016.
• Kiefer, J., and Wolfowitz, J. "Stochastic estimation of the gradient of a regression function." The Annals of Mathematical Statistics, vol. 23, no. 3, 1952, pp. 462–466.
• Bottou, L. "Large-Scale Machine Learning with Stochastic Gradient Descent." Proceedings of COMPSTAT, 2010, pp. 177–186.
• Nocedal, J., and Wright, S. J. "Numerical Optimization." Springer Science & Business Media, 2006.
• Kingma, D. P., and Ba, J. "Adam: A method for stochastic optimization." International Conference on Learning Representations (ICLR), 2015.