← All Cracked Math projects
PM-B10NOT STARTEDBEGINNERMATHPYTHONIMPACT ★★☆☆☆

Optimizer golf on nasty functions

Predict gradient descent's convergence rate from the Hessian's eigenvalues, then race it against Adam and Newton.

EST.7 h
REWARD+200 XP
AFTERGabriel Goh

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Function+gradient evaluations to reach f - f* < 1e-8; predicted vs measured linear rates (the factor by which the error shrinks each step)
GOAL · Measured rates on the quadratic within 10% of theory ((k-1)/(k+1) for GD and (sqrt k - 1)/(sqrt k + 1) for heavy-ball, with k the condition number); damped Newton uses fewer evaluations than BFGS on all 4 functions
scipy.optimize.minimize (BFGS) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Derive gradients and Hessians by hand (the Hessian is the matrix of second derivatives, which describes curvature). Do this for Rosenbrock, Beale and Himmelblau (classic hard test functions with curved valleys or several minima) and for an ill-conditioned quadratic with kappa = 1e4 (kappa, the condition number, is the ratio of the largest to the smallest curvature). Check them with your B04 finite differences. Implement GD, heavy-ball (gradient descent with momentum), Nesterov (momentum with a look-ahead step), Adam and damped Newton (Newton's method with a shortened step for safety). Before running, predict the GD and heavy-ball rates from the Hessian spectrum (its eigenvalues). Keep a golf leaderboard of evaluations-to-target: as in golf, fewer is better.

VICTORY CONDITIONS

  1. Measured rates on the quadratic within 10% of theory ((k-1)/(k+1) for GD and (sqrt k - 1)/(sqrt k + 1) for heavy-ball, with k the condition number); damped Newton uses fewer evaluations than BFGS on all 4 functions (Function+gradient evaluations to reach f - f* < 1e-8; predicted vs measured linear rates (the factor by which the error shrinks each step)).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Hessian
The matrix of second partial derivatives; its eigenvalues tell you how sharply the function curves in each direction.
Condition number (kappa)
The ratio of the largest to the smallest Hessian eigenvalue; a large kappa means a long narrow valley that slows gradient descent.
Heavy-ball momentum
Gradient descent that also adds a fraction of the previous step, which speeds up progress along narrow valleys.
Damped Newton
Newton's method (step = inverse Hessian times gradient) with the step shortened when a full step would increase the function.
BFGS
A quasi-Newton method that builds an approximate Hessian from successive gradients instead of computing it.

Why it rates ★★☆☆☆

Standard optimisation coursework. The discipline of predicting from theory before measuring is what lifts it above a notebook.