a quasi-Newton method
/ KWAY-zye NOO-tun /
Newton's method is fast because it knows the curvature — the Hessian — but computing and inverting that big matrix every step is expensive or impossible for large problems. Quasi-Newton methods are the clever compromise: keep Newton's curvature-aware speed, but never compute the Hessian. Instead, LEARN an approximation of the curvature on the fly, purely from the gradients you are already calculating, the way you might infer how a road bends just by noting how its slope changes between two points.
The key observation is the secant idea: if you know the gradient at two nearby points x_k and x_{k+1}, then the change in gradient tells you about curvature in the direction you moved. Let s_k = x_{k+1} - x_k (the step) and y_k = grad f(x_{k+1}) - grad f(x_k) (the gradient change). The true Hessian H roughly satisfies H s_k = y_k (the secant equation). A quasi-Newton method keeps a matrix B_k (or its inverse) approximating the Hessian, and at each step UPDATES it with a cheap formula so the new matrix satisfies the secant equation, then takes a Newton-like step p = -B_k^{-1} grad f(x_k). Each update is a low-rank change, costing only O(n^2) work — far less than the O(n^3) of forming and factoring a true Hessian — and uses only gradients, no second derivatives at all.
Quasi-Newton methods (BFGS being the famous one, and L-BFGS its low-memory cousin) are the practical workhorses of medium-to-large smooth optimization, hitting SUPERLINEAR convergence — faster than gradient descent's linear rate, just short of Newton's quadratic rate — without ever touching a Hessian. The honest limits: the convergence is only superlinear, not quadratic; the approximation needs the curvature condition (y_k^T s_k > 0) to stay positive definite, which is why these methods are paired with a Wolfe line search; and for truly huge problems even the O(n^2) matrix is too big, which is exactly the gap that limited-memory L-BFGS fills by storing only a few recent (s_k, y_k) pairs instead of the whole matrix.
On a long thin valley where steepest descent zig-zags for thousands of steps, BFGS starts from the identity as its Hessian guess and, after just a few steps of watching how the gradient changes, has learned the valley's elongation well enough to step almost straight to the floor — superlinear, using only gradients it already computed.
Build curvature from gradient changes — Newton-like speed, no Hessian.
Quasi-Newton converges SUPERLINEARLY, not quadratically — it approximates the Hessian, so it cannot match true Newton's digit-doubling near a solution. It also keeps an n-by-n matrix (O(n^2) memory), too much for very large models; that is where limited-memory L-BFGS takes over by storing only a few recent gradient-difference vectors.