Optimization Theory quiz

Question 1

What is a convex function and why does convexity guarantee that local minima are global minima?

Accepted Answer

Any local minimum of a convex function is a global minimum

Answer

Convex functions can have multiple local minima

Answer

Convexity requires the Hessian to be zero

Answer

Non-convex functions cannot be minimized

Question 2

Derive the gradient descent update rule and explain the role of the learning rate.

Accepted Answer

Too large a learning rate can cause divergence

Answer

Large learning rate always speeds convergence

Answer

Gradient descent requires computing the Hessian

Answer

Gradient descent converges in O(1) steps for convex functions

Question 3

Explain momentum in optimization and why it accelerates convergence in ill-conditioned problems.

Accepted Answer

Momentum reduces convergence cost from O(κ) to O(√κ)

Answer

Momentum makes convergence slower

Answer

Momentum β must equal 1.0

Answer

Momentum requires computing the Hessian

Question 4

Describe the AdaGrad optimizer and its main limitation.

Accepted Answer

AdaGrad's accumulated squared gradients grow monotonically

Answer

AdaGrad increases learning rate over time

Answer

AdaGrad is optimal for dense gradient problems

Answer

AdaGrad uses exponential moving averages

Question 5

What is AdamW and why is it preferred over L2-regularized Adam for weight decay?

Accepted Answer

AdamW applies weight decay directly to parameters, decoupled from adaptive scaling

Answer

AdamW adds weight decay to the gradient like L2

Answer

AdamW is slower than Adam

Answer

L2 regularization in Adam is equivalent to AdamW

Question 6

What are the Karush-Kuhn-Tucker (KKT) conditions for constrained optimization?

Accepted Answer

Complementary slackness: λ_i·g_i(x*)=0

Answer

KKT requires all inequality constraints to be active

Answer

Dual multipliers λ_i can be negative

Answer

KKT conditions are only for equality constraints

Question 7

What is the difference between weak duality and strong duality in optimization?

Accepted Answer

Strong duality: dual = primal under Slater's condition for convex problems

Answer

Weak duality: dual ≥ primal always

Answer

Strong duality holds for all optimization problems

Answer

Slater's condition requires all constraints to be equality constraints

Question 8

Describe Newton's method for optimization and its convergence rate.

Accepted Answer

Newton's method has quadratic convergence near the optimum

Answer

Newton's method has linear convergence

Answer

Newton's method requires only gradient computation

Answer

Newton's method is unaffected by the learning rate

Question 9

What is a line search and what are the Wolfe conditions?

Accepted Answer

Armijo condition ensures sufficient decrease in function value

Answer

Armijo condition ensures the step is not too small

Answer

Wolfe conditions require exact minimization along the line

Answer

Strong Wolfe conditions are weaker than standard Wolfe

Question 10

Describe the proximal gradient method and when is it used instead of gradient descent.

Accepted Answer

Proximal gradient handles non-smooth g via a proximal operator

Answer

Proximal gradient requires the full function to be smooth

Answer

ISTA achieves O(1/T²) convergence

Answer

Soft-thresholding is the proximal operator for L2 norm

Question 11

What is gradient clipping and why is it necessary for RNN training?

Accepted Answer

Gradient clipping addresses exploding gradients in RNNs

Answer

Gradient clipping addresses vanishing gradients

Answer

Gradient clipping increases the gradient norm

Answer

Gradient clipping is not needed with LSTM

Question 12

What is the condition number of a matrix and how does it affect optimization convergence?

Accepted Answer

High condition number slows gradient descent convergence

Answer

High condition number speeds gradient descent

Answer

Condition number is always 1 for orthogonal matrices

Answer

Condition number equals the matrix rank

Question 13

What is coordinate descent and when is it preferred over gradient descent?

Accepted Answer

Coordinate descent cycles through coordinates one at a time

Answer

Coordinate descent updates all coordinates simultaneously

Answer

Coordinate descent is slower than gradient descent for all problems

Answer

Coordinate descent cannot handle L1 regularization

Question 14

What is the subgradient method and when is it needed?

Accepted Answer

Subgradient iterates may increase f; best iterate is tracked

Answer

Subgradient method guarantees decrease at every step

Answer

Subgradient method achieves O(1/T) convergence

Answer

Subgradient equals gradient for all convex functions

Question 15

What is the online learning setting and what does regret measure?

Accepted Answer

Regret = total loss minus best fixed strategy loss in hindsight

Answer

Regret measures performance vs. a random baseline

Answer

Online gradient descent achieves O(T) regret

Answer

Sublinear regret means R_T/T goes to a constant

Question 16

What is SVRG (Stochastic Variance Reduced Gradient) and how does it improve over SGD?

Accepted Answer

SVRG achieves linear convergence for strongly convex functions

Answer

SVRG achieves O(1/T) convergence like SGD

Answer

SVRG requires computing the full Hessian

Answer

SVRG only works for non-convex problems

Question 17

What is Polyak-Ruppert averaging and how does it improve SGD's final iterate?

Accepted Answer

Polyak averaging of SGD iterates achieves minimax optimal convergence

Answer

Iterate averaging worsens SGD convergence

Answer

SWA uses the first iterate rather than the average

Answer

Averaging only works for convex problems

Question 18

What is the regret bound for online gradient descent on convex functions?

Accepted Answer

O(√T) regret is achievable for convex losses

Answer

O(1) regret is achievable for convex losses

Answer

O(T) regret is the best possible

Answer

O(log T) regret is achievable for all convex losses

Question 19

What is the saddle-free Newton method and why are saddle points problematic in deep learning?

Accepted Answer

Saddle points are common in high-dimensional non-convex optimization

Answer

Saddle points are rare in high-dimensional optimization

Answer

SGD cannot escape saddle points due to zero gradient

Answer

Adam has no advantage over SGD near saddle points

Question 20

How does mixed precision training use FP16 and FP32 to speed up optimization?

Accepted Answer

FP32 master weights are maintained to avoid precision loss in updates

Answer

Mixed precision stores gradients in FP16 for the optimizer step

Answer

Loss scaling prevents FP16 overflow, not underflow

Answer

Mixed precision offers no speed benefit over FP32

Question 21

What is the concept of a global optimum in non-convex optimization and what heuristics help avoid poor local optima?

Accepted Answer

SGD noise helps escape sharp local minima

Answer

Non-convex optimization always converges to the global minimum

Answer

Flat minima generalize worse than sharp minima

Answer

Random restarts are ineffective for large neural networks

Question 22

What is the difference between first-order and second-order optimization methods?

Accepted Answer

First-order methods use only gradient information

Answer

First-order methods use the Hessian

Answer

Second-order methods are always faster for deep learning

Answer

Adam is a second-order method

Question 23

What is the Sharpness-Aware Minimization (SAM) optimizer and how does it improve generalization?

Accepted Answer

SAM minimizes worst-case loss over an L2 ball

Answer

SAM requires one forward pass per step

Answer

SAM requires two forward-backward passes per step

Answer

SAM and standard SGD find the same minima

Question 24

What is Adafactor and why is it preferred over Adam for very large models?

Accepted Answer

Adafactor reduces second-moment memory via factorization

Answer

Adafactor uses more memory than Adam

Answer

Adafactor requires a manually set learning rate always

Answer

Adafactor stores the full second moment matrix

Test yourself