Gradient Descent Flashcards
What is Gradient Descent?
Gradient Descent is an iterative optimization algorithm used to minimize a loss/cost function by adjusting model parameters in the direction of the negative gradient. It is foundational in machine learning for training models like linear regression and neural networks.
What is the general update rule for Gradient Descent?
For parameters θ and learning rate α:
θ = θ - α ⋅ ∇J(θ),
where ∇J(θ) is the gradient of the cost function J(θ).
What is Batch Gradient Descent (BGD)?
BGD computes the gradient using the entire training dataset and updates parameters once per epoch. It is stable but computationally expensive.
What is the cost function for BGD in linear regression (MSE)?
J(θ) = (1/2m) Σ(hθ(xⁱ) - yⁱ)²,
where m = number of training examples, hθ(x) = θᵀx.
What is the gradient of MSE for BGD?
∇J(θ) = (1/m) Σ(hθ(xⁱ) - yⁱ) ⋅ xⁱ.
For parameter θ_j: ∂J/∂θ_j = (1/m) Σ(hθ(xⁱ) - yⁱ) ⋅ x_jⁱ.
What are the pros and cons of BGD?
Pros: Stable convergence, accurate gradients. Cons: Slow for large datasets, high memory usage.
What is Stochastic Gradient Descent (SGD)?
SGD updates parameters per training example (one example at a time). It is faster but noisier than BGD.
What is the update rule for SGD?
For a single example (xⁱ, yⁱ):
θ = θ - α ⋅ (hθ(xⁱ) - yⁱ) ⋅ xⁱ.
Why does SGD have noisy updates?
Because it uses a single example’s gradient, which may not represent the true gradient of the entire dataset.
What is Mini-Batch Gradient Descent?
A compromise between BGD and SGD. It uses small batches (e.g., 32, 64 examples) to compute gradients. Balances speed and stability.
What is the update rule for Mini-Batch GD?
For a batch size b:
θ = θ - α ⋅ (1/b) Σ(hθ(xⁱ) - yⁱ) ⋅ xⁱ
for i=1 to b.
Why is Mini-Batch GD widely used in deep learning?
It leverages vectorized operations for efficiency, avoids SGD’s noise, and scales well to large datasets.
What is the role of the learning rate (α)?
α controls the step size of parameter updates. Too small: slow convergence. Too large: oscillations/divergence.
How does learning rate decay improve convergence?
Reducing α over time (e.g., α = α₀ / (1 + decay_rate * epoch)) helps fine-tune parameters near the minimum.
What is the difference between BGD, SGD, and Mini-Batch GD in terms of updates?
- BGD: 1 update/epoch.
- SGD: m updates/epoch (m = dataset size).
- Mini-Batch: m/b updates/epoch (b = batch size).
What is an ‘epoch’?
One full pass through the entire training dataset.
What is a ‘local minimum’? How does SGD escape it?
A point where J(θ) is lower than nearby points but not the global minimum. SGD’s noisy updates can ‘jump’ out of local minima.
What is a saddle point? Why is it problematic?
A point where gradients are zero but not a minimum (common in high-dimensional spaces). SGD’s noise helps escape it.
Why is feature scaling important for Gradient Descent?
Scaling features (e.g., normalization) ensures all parameters update at the same rate, speeding up convergence.
What is the convergence criterion for Gradient Descent?
Stop when ||∇J(θ)|| < ε (small threshold) or when J(θ) changes minimally between epochs.
How does BGD guarantee convergence for convex functions?
For convex J(θ), BGD converges to the global minimum with a sufficiently small α.
What is the time complexity of BGD vs. SGD?
- BGD: O(m) per epoch.
- SGD: O(1) per update (total O(m) per epoch).
What is the ‘vanishing gradient’ problem?
In deep networks, gradients become extremely small, slowing down updates in early layers. Not directly related to GD variants.
What is momentum in Gradient Descent?
Momentum (e.g., v = γv + α∇J(θ); θ = θ - v) accelerates updates in consistent gradient directions, reducing oscillations.
What is AdaGrad?
An adaptive learning rate method: α is scaled per parameter using past squared gradients. Works well for sparse data.
What is RMSProp?
Improves AdaGrad by using an exponentially weighted average of squared gradients to handle non-convex problems.
What is Adam?
Combines momentum and RMSProp:
m_t = β₁m_{t-1} + (1-β₁)g_t
v_t = β₂v_{t-1} + (1-β₂)g_t²
θ = θ - α ⋅ m_t / (√v_t + ε).
Why is Mini-Batch GD preferred over SGD in practice?
Mini-Batch GD uses hardware parallelism (e.g., GPUs) for batch computations, reducing noise compared to SGD.
How do you choose the batch size in Mini-Batch GD?
Common choices: 32, 64, 128. Small batches add noise (regularization), large batches mimic BGD’s stability.
What is online learning? How does it relate to SGD?
Online learning updates models incrementally as data arrives (e.g., streaming). SGD is a form of online learning.
What is early stopping?
Halting training when validation error starts increasing to prevent overfitting. Used with all GD variants.
How does regularization (e.g., L2) affect GD updates?
Adds a penalty term (e.g., λ||θ||²) to the loss. Gradients become ∇J(θ) + 2λθ.
What is the difference between GD and Newton’s method?
Newton’s method uses the Hessian (second derivatives) for faster convergence but is computationally expensive.
Why is SGD used for non-convex loss functions (e.g., neural networks)?
Its noisy updates help escape local minima, making it suitable for complex, non-convex optimization.
What is a learning rate schedule? Example?
A plan to adjust α during training. Example: α = α₀ * e^(-kt), where t is the iteration number.
How does parallelization improve Mini-Batch GD?
Batch computations can be split across multiple cores/GPUs, speeding up training.
What is gradient clipping?
Limiting gradient values to a maximum threshold to prevent exploding gradients in deep networks.
What is the Polyak-Learning Rate?
α = (J(θ) - J) / ||∇J(θ)||², where J is the optimal loss. Rarely used practically but theoretically optimal.
What is the disadvantage of using a fixed learning rate?
It may cause slow convergence (if too small) or oscillations (if too large). Adaptive methods (Adam) mitigate this.
What is the role of bias correction in Adam?
Corrects initial estimates of m_t and v_t to account for zero initialization (m_t / (1 - β₁^t)).
How does SGD handle redundant training examples?
Redundant examples may bias gradients, but shuffling the dataset mitigates this.
What is the effect of batch size on generalization?
Small batches (e.g., SGD) act as a regularizer, often improving generalization by adding noise.
What is the difference between GD and genetic algorithms?
GD is deterministic and gradient-based. Genetic algorithms are stochastic and inspired by evolution.
How does GD handle non-differentiable loss functions?
Subgradient methods or proximal GD are used (e.g., for L1 regularization).
What is coordinate descent? How is it different from GD?
Updates one parameter at a time instead of all parameters. Useful for high-dimensional problems.
What is the Hessian matrix? Why is it not used in GD?
The Hessian contains second-order partial derivatives. GD uses first-order gradients; Newton’s method uses Hessians.
What is the stochastic variance reduced gradient (SVRG)?
A variant of SGD that reduces variance by combining current and historical gradients.
What is the disadvantage of AdaGrad?
The learning rate can become infinitesimally small over time, halting updates.
What is the difference between GD and backpropagation?
GD is the optimization algorithm. Backpropagation computes gradients efficiently in neural networks.
What is Nesterov Accelerated Gradient (NAG)?
A momentum variant that ‘looks ahead’ to the future gradient for smoother updates.
What is the Fletcher-Reeves method?
A conjugate gradient method that avoids computing the Hessian, using past gradients for direction.
What is the Wolfe condition?
A set of criteria to ensure sufficient decrease in the loss when choosing a step size in line search methods.
What is the Armijo rule?
A condition to guarantee a sufficient decrease in the loss during line search.
How does GD perform in high-dimensional spaces?
It can struggle with saddle points and flat regions. Adaptive methods (Adam) help navigate such landscapes.
What is the relationship between GD and the Normal Equation?
The Normal Equation (θ = (XᵀX)⁻¹Xᵀy) solves linear regression in one step, while GD iteratively approaches the solution.
How does GD handle multicollinearity in data?
GD will still converge, but the learning rate may need tuning. Regularization (e.g., L2) is often added.
What is the disadvantage of using BGD for online learning?
BGD requires the entire dataset, making it incompatible with streaming/online data.
What is the regret in online learning? How does SGD minimize it?
Regret measures the difference between the learner’s loss and the best fixed parameter’s loss. SGD has sublinear regret.
What is the difference between GD and Expectation-Maximization (EM)?
EM is used for latent variable models (e.g., GMMs), while GD is a general-purpose optimizer.
What is the ELBO in variational inference? How is GD used?
The Evidence Lower BOund is maximized using GD to train variational autoencoders (VAEs).
What is the role of GD in reinforcement learning?
GD optimizes policy or value function parameters (e.g., in policy gradient methods).
How does GD relate to the Karush-Kuhn-Tucker (KKT) conditions?
KKT conditions generalize gradients to constrained optimization. GD is used in unconstrained settings.
What is the difference between GD and Frank-Wolfe?
Frank-Wolfe solves constrained problems by iteratively moving toward the steepest feasible direction.
What is mirror descent?
A generalization of GD using Bregman divergences for non-Euclidean geometry.
What is the role of GD in meta-learning?
GD is used to optimize hyperparameters or learn initialization parameters for fast adaptation.
