Full search page →

OPT 06 · Gradient Descent, Newton Steps and Numerical Reliability

OptimizationAdvanced19 minUpdated Oct 4, 2026

Needs: OPT 05 · Approximation, Statistical Estimation and Experiment Design

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

See why a step size that works on a round bowl can diverge on a narrow one.

What you’ll learn

  • Separate a search direction from the step length chosen along it.
  • Derive a safe gradient step under a Lipschitz-gradient assumption.
  • Implement Armijo backtracking with domain and iteration safeguards.
  • Explain conditioning, norm-dependent steepest descent and Newton curvature.
  • Interpret a Newton decrement and the assumptions behind rapid local convergence.
  • Verify derivatives, linear solves and stopping evidence in a CPU example.

The big picture

Convexity tells us which answers are globally optimal. An algorithm tells us how to move toward one using information that can be computed. Those are complementary questions: a convex problem can still be badly scaled, expensive or numerically delicate.

Boyd and Vandenberghe’s Chapter 9 [1] develops unconstrained descent methods, gradient descent, steepest descent, Newton’s method, self-concordance and implementation. This chapter follows that progression, keeping the cost of each step and the meaning of a stopping test visible.

The examples solve deterministic convex objectives. Their guarantees should not be silently transferred to a neural network’s nonconvex training objective, a noisy derivative or a nonsmooth penalty. Useful ideas can transfer, but the proof assumptions must be checked again.

We first use a quadratic with an exact solution, then implement a smooth regularized logistic objective from scratch. Both run on a CPU with locally generated data and no solver package beyond NumPy.

A direction and a distance

Plain version. A descent iteration chooses where to point, then how far to travel. Combining those choices too early hides why a step is safe.

Write an iteration as

xk+1=xk+tkdk.x_{k+1}=x_k+t_kd_k.

xkx_k is the current decision vector, dkd_k a search direction and tk>0t_k>0 the step length. For a differentiable objective ff, a strict descent direction satisfies ∇f(xk)⊤dk<0\nabla f(x_k)^\top d_k<0.

The inner product is the directional derivative at zero step. By differentiability, a sufficiently small positive step lowers the objective and remains in an open domain around the current point. A large step can still increase it or leave the domain.

The direction may depend on a gradient, a Hessian, a metric or other structure. The line search evaluates candidate distances. Counting only accepted iterations can hide many rejected objective evaluations.

If the gradient is zero for a differentiable convex objective on an open convex domain, the supporting-plane inequality certifies a global minimizer. With constraints, zero unconstrained gradient is generally not the correct optimality condition; the next chapter uses constrained systems.

Exact and inexact line searches

An exact line search minimizes f(x+td)f(x+td) over allowed positive distances. That auxiliary one-dimensional problem can be costly or unnecessary.

An inexact search accepts sufficient decrease rather than solving the line problem precisely. It should also preserve the objective’s domain. For a logarithmic term, testing a candidate with an invalid argument is a failed domain test, not evidence about its objective.

Floating-point evaluation adds another distinction: a mathematically decreasing step can become indistinguishable from the current value at machine precision. Repeatedly shrinking until a comparison happens to pass is not a robust termination rule.

Gradient descent and its assumptions

Plain version. Gradient descent points opposite the gradient. A curvature bound tells us how small a fixed step must be.

The update is

xk+1=xk−η∇f(xk).x_{k+1}=x_k-\eta\nabla f(x_k).

η>0\eta>0 is the step size. Assume the gradient is Lipschitz with constant LL on the relevant region:

∥∇f(y)−∇f(x)∥2≤L∥y−x∥2.\|\nabla f(y)-\nabla f(x)\|_2\leq L\|y-x\|_2.

x,yx,y are points whose connecting segment stays in that region. LL measures how rapidly the gradient changes; it is not a regularization coefficient or a loss value.

The smoothness inequality is

f(x+d)≤f(x)+∇f(x)⊤d+L2∥d∥22.f(x+d)\leq f(x)+\nabla f(x)^\top d+\frac L2\|d\|_2^2.

dd is a trial displacement. Substituting d=−∇f(x)/Ld=-\nabla f(x)/L gives

f(x−1L∇f(x))≤f(x)−12L∥∇f(x)∥22.f\left(x-\frac1L\nabla f(x)\right) \leq f(x)-\frac1{2L}\|\nabla f(x)\|_2^2.

The step 1/L1/L therefore supplies descent whenever the assumptions and domain requirement hold. For a twice-differentiable objective, an upper Hessian eigenvalue bound can establish such an LL [1, Section 9.3].

When only convexity and smoothness are assumed, objective convergence is typically sublinear under the standard fixed-step analysis. Strong convexity adds a positive lower curvature bound and permits linear geometric convergence. Those words describe mathematical rates, not a promise that every implementation will be fast.

From one-step decrease to a convergence rate

Descent proves that the objective improves; a convergence rate quantifies how much work reaches a target error. For a convex differentiable function on Rn\mathbb R^n with LL-Lipschitz gradient and an attained minimizer x∗x^*, use x+=x−∇f(x)/Lx^+=x-\nabla f(x)/L. The gradient supporting bound gives

f(x)−f(x∗)≤∇f(x)⊤(x−x∗).f(x)-f(x^*)\leq\nabla f(x)^\top(x-x^*).

Here xx is the current point, x+x^+ its next iterate and x∗x^* any minimizer. Expanding the squared distance after the update gives

∥x+−x∗∥22=∥x−x∗∥22−2L∇f(x)⊤(x−x∗)+1L2∥∇f(x)∥22.\|x^+-x^*\|_2^2 =\|x-x^*\|_2^2-\frac2L\nabla f(x)^\top(x-x^*) +\frac1{L^2}\|\nabla f(x)\|_2^2.

All symbols retain their definitions above. Combine the first inequality with the earlier smoothness decrease bound to obtain

f(x+)−f(x∗)≤L2(∥x−x∗∥22−∥x+−x∗∥22).f(x^+)-f(x^*)\leq\frac L2 \left(\|x-x^*\|_2^2-\|x^+-x^*\|_2^2\right).

Summing this inequality over the first kk updates cancels the intermediate distances. Since objective values decrease, the last error is no larger than the average of those kk errors:

f(xk)−f(x∗)≤L∥x0−x∗∥222k,k≥1.f(x_k)-f(x^*)\leq\frac{L\|x_0-x^*\|_2^2}{2k},\qquad k\geq1.

Here x0x_0 is the start and xkx_k the point after kk updates. This is the concrete meaning of an O(1/k)O(1/k) objective rate: halving the guaranteed error generally requires twice as many iterations under this bound. It is a worst-case guarantee with these assumptions, not a claim about every observed trace [1].

Strong convexity and a stopping bound

If ff is μ\mu-strongly convex, its supporting model includes μ2∥y−x∥22\frac\mu2\|y-x\|_2^2. Minimizing that lower model yields

f(x)−f∗≤∥∇f(x)∥222μ.f(x)-f^*\leq\frac{\|\nabla f(x)\|_2^2}{2\mu}.

f∗f^* is the global minimum and μ>0\mu>0 a valid strong-convexity constant. A small gradient then gives an objective-gap bound with known units.

Without a verified positive μ\mu, the same formula is not a certificate. A small gradient can coexist with a large distance to the solution on a very flat objective. A small parameter update can instead reflect an excessively small step.

Avoid stopping solely because several printed objective values look identical. Check a suitable residual, the model’s scale, the progress trend and an iteration or time limit.

Conditioning changes the path

Plain version. An elongated bowl has steep and flat directions. A step safe for the steep direction can make progress painfully slow along the flat one.

For a positive-definite quadratic,

f(x)=12x⊤Qx+c⊤x,∇f(x)=Qx+c.f(x)=\frac12x^\top Qx+c^\top x,\qquad \nabla f(x)=Qx+c.

QQ is symmetric positive definite and cc fixed. The Hessian is QQ. Its smallest and largest eigenvalues supply μ\mu and LL.

The ratio κ=L/μ\kappa=L/\mu describes this Euclidean curvature conditioning. A large ratio means a single scalar step size must accommodate very different directional scales. Coordinate units can therefore change the behavior of gradient descent substantially.

Standardizing variables or choosing a suitable metric can improve a path, but must transform constraints, coefficients and stopping norms consistently. A rescaled algorithm is not judged fairly by an untransformed parameter-distance threshold.

Gradient and Newton paths on an elongated positive-definite quadratic, with separate horizontal scales for readability.
Figure 1 — Original analytical quadratic f(x) = (x₁² + 40x₂²)/2. The gradient path uses step 1/40; Newton reaches the exact quadratic minimizer in one full step. This example isolates conditioning and does not compare total runtime on general problems.

Code: compare a fixed gradient step and a Newton step

The objective is minimized at zero. We compare objective decrease and verify the Newton linear system rather than using an explicit matrix inverse.

Code · Python · 16 lines
import numpy as np

Q = np.diag([1., 40.])
x = np.array([3., 3.])
start = x.copy()
values = [0.5*x @ Q @ x]
for _ in range(200):
    x = x - (Q @ x)/40
    values.append(0.5*x @ Q @ x)
direction = np.linalg.solve(Q, -(Q @ start))
newton = start + direction
assert np.all(np.diff(values) <= 1e-12)
assert np.allclose(Q @ direction + Q @ start, 0)
assert np.linalg.norm(newton) < 1e-12
print("gradient objective after 200 steps:", round(values[-1], 8))
print("Newton objective after one step:", 0.5*newton @ Q @ newton)

A one-step Newton solution is special to an exact positive-definite quadratic with an accurate linear solve. On a general smooth function, curvature changes as we move and a full step may fail.

Read the quadratic path one eigenvector at a time

A quadratic makes the effect of the step size exact. Let ek=xk−x∗e_k=x_k-x^* be the error for a positive-definite quadratic with curvature QQ. Gradient descent gives ek+1=(I−ηQ)eke_{k+1}=(I-\eta Q)e_k. In an eigenvector of QQ with eigenvalue qiq_i, the error coefficient is multiplied by 1−ηqi1-\eta q_i.

Here η\eta is the fixed step, II the identity, and qi>0q_i>0 the directional curvature. All coefficients contract precisely when 0<η<2/L0\lt \eta\lt 2/L, where LL is the largest eigenvalue. If η>2/L\eta>2/L, the steepest-direction error grows in magnitude even though the objective is convex.

For the chapter’s Q=diag⁡(1,40)Q=\operatorname{diag}(1,40) and η=1/40\eta=1/40, the steep coordinate disappears after one update, while the flat coordinate is multiplied by 39/4039/40 each time. Starting from (3,3)(3,3) therefore leaves first-coordinate error 3(39/40)k3(39/40)^k after kk updates. The gradual path is a consequence of directional curvature, not random numerical failure.

For a quadratic with smallest eigenvalue μ\mu, choosing η=2/(L+μ)\eta=2/(L+\mu) balances the magnitudes of the extreme contraction factors. Their worst value is (L−μ)/(L+μ)(L-\mu)/(L+\mu). This choice improves the bound relative to a conservative step, but relies on known spectral endpoints and does not replace a line search for arbitrary nonquadratic functions [1].

Armijo backtracking

Plain version. Start with a candidate distance and shrink it until the decrease is large enough relative to the local slope.

The sufficient-decrease condition is

f(x+td)≤f(x)+αt∇f(x)⊤d.f(x+td)\leq f(x)+\alpha t\nabla f(x)^\top d.

dd is a descent direction, t>0t>0 the tested distance, and α∈(0,1)\alpha\in(0,1) a fixed decrease fraction. Backtracking repeatedly multiplies tt by β∈(0,1)\beta\in(0,1) until the domain and decrease tests pass [1, Section 9.2].

For Newton methods, a usual choice keeps α<1/2\alpha<1/2 so full steps are accepted near a regular optimum under the standard local analysis. This is an assumption-aware choice, not a universal optimal parameter.

An implementation needs a maximum number of trials, a minimum meaningful step, finite-value checks and a clear failure report. Otherwise an invalid direction or an incorrect gradient can produce an endless shrinking loop.

What a rejected step tells us

A rejection can mean the initial distance was too ambitious, the curvature model was inaccurate far from the solution, the domain was crossed or the derivatives were wrong. It does not by itself identify which reason applies.

Check the directional derivative first. If it is nonnegative, ordinary descent backtracking lacks its intended justification. A modified direction may be needed, or the candidate may already meet an optimality test.

Repeated rejection near an optimum can come from floating-point cancellation. Compare objective and derivative scales before demanding an improvement below representable precision. Termination should explain which numerical condition was met.

Steepest descent depends on a norm

Plain version. “Steepest” requires a definition of one unit of movement. Different norms choose different directions.

The normalized steepest direction solves

min⁡∥d∥≤1∇f(x)⊤d.\min_{\|d\|\leq1}\nabla f(x)^\top d.

dd is the direction, ∥⋅∥\|\cdot\| the chosen movement norm, and xx the current point. Under the Euclidean norm, a nonzero gradient gives direction −∇f(x)/∥∇f(x)∥2-\nabla f(x)/\|\nabla f(x)\|_2.

For a positive-definite metric matrix PP, define ∥d∥P=d⊤Pd\|d\|_P=\sqrt{d^\top Pd}. A corresponding unnormalized descent direction is

d=−P−1∇f(x).d=-P^{-1}\nabla f(x).

PP determines directional cost. The directional derivative is −∇f(x)⊤P−1∇f(x)-\nabla f(x)^\top P^{-1}\nabla f(x), strictly negative for a nonzero gradient.

Choosing PP resembles preconditioning: we account for known scale or curvature without necessarily forming the true Hessian. The usefulness depends on how cheaply the metric system can be solved and how well it represents the problem.

With a coordinate-based movement norm, steepest directions may select a coordinate or distribute movement differently. The book’s treatment [1, Section 9.4] explains why steepest descent is a family rather than one coordinate-independent procedure.

Newton’s local quadratic model

Plain version. Newton uses a quadratic approximation of the objective, then solves for the minimizer of that approximation.

At the current point, the model is

m(d)=f(x)+g⊤d+12d⊤Hd,g=∇f(x), H=∇2f(x).m(d)=f(x)+g^\top d+\frac12d^\top Hd,\qquad g=\nabla f(x),\ H=\nabla^2f(x).

dd is the displacement, gg the gradient and HH the Hessian. When HH is positive definite, the model’s unique minimizing displacement solves

Hd=−g.Hd=-g.

This is the Newton direction. Compute it through a linear solve or factorization, not by forming an inverse. Positive definiteness ensures a descent direction whenever g≠0g\ne0.

Convexity gives a positive-semidefinite Hessian, which may be singular. A full Newton step is not automatically defined. A regularized Hessian, restricted subspace or another direction can be appropriate, but each changes the stated numerical procedure.

The Newton decrement

Define

λN(x)2=g⊤H−1g=−g⊤d.\lambda_N(x)^2=g^\top H^{-1}g=-g^\top d.

λN\lambda_N is the Newton decrement and HH is assumed positive definite. The quadratic model predicts a decrease of λN2/2\lambda_N^2/2 at its minimizing step.

For an exact quadratic, that prediction equals the objective gap. For a general function, it is a local model quantity; a rigorous gap interpretation needs additional assumptions. Do not label the predicted decrease an unconditional global error certificate.

The direction and decrement transform coherently under an invertible affine change of coordinates when derivatives and solves are exact. This is one reason Newton behaves differently from Euclidean gradient descent. Floating-point conditioning and implementation still matter.

Local convergence is conditional

With suitable smoothness, a nonsingular positive-definite Hessian near the minimizer and an appropriate line search, Newton eventually accepts full steps and can converge quadratically [1, Section 9.5].

Quadratic convergence describes error shrinking approximately as the square of the previous error in a sufficiently small neighborhood. It does not imply that the first few steps from any initial point exhibit that behavior.

Errors in gradients, Hessians and linear solves can limit the rate. Far from the solution, safeguards may be essential. Near the solution, requesting a residual below derivative accuracy can waste work or trigger misleading failures.

Why Newton respects a change of coordinates

Newton adjusts direction using curvature, so changing variable units does not change its ideal physical step. Let x=Tz+bx=Tz+b with invertible matrix TT and fixed offset bb, and define f~(z)=f(Tz+b)\widetilde f(z)=f(Tz+b). At corresponding points, the chain rule gives

g~=T⊤g,H~=T⊤HT.\widetilde g=T^\top g,\qquad \widetilde H=T^\top HT.

Here g,Hg,H are the gradient and positive-definite Hessian in xx coordinates, while tildes denote the same derivatives in zz coordinates. The transformed Newton equation is

T⊤HT Δz=−T⊤g⟹H(TΔz)=−g.T^\top HT\,\Delta z=-T^\top g \quad\Longrightarrow\quad H(T\Delta z)=-g.

Here Δz\Delta z is the displacement in new coordinates. Uniqueness of the solve gives TΔz=ΔxT\Delta z=\Delta x, the original Newton displacement. Its predicted decrease is invariant too: g~⊤H~−1g~=g⊤H−1g\widetilde g^\top\widetilde H^{-1}\widetilde g=g^\top H^{-1}g.

Ordinary gradient descent instead maps its transformed step to −ηTT⊤g-\eta TT^\top g, generally a different direction from −ηg-\eta g. This connects coordinate scaling to the metric in steepest descent. Newton’s invariance assumes exact derivatives and solves; an ill-conditioned coordinate transformation can still harm a floating-point implementation [1, Section 9.5].

Self-concordance and controlled curvature

Plain version. Some convex functions control how quickly curvature changes through their own local curvature. This gives a special route to analyzing Newton steps.

For a standard self-concordant one-dimensional function,

∣f′′′(t)∣≤2(f′′(t))3/2.|f'''(t)|\leq2\bigl(f''(t)\bigr)^{3/2}.

tt is the scalar input and primes are derivatives, with nonnegative second derivative. In multiple dimensions, this condition is applied along lines in the domain [1, Section 9.6].

The logarithmic barrier −log⁡t-\log t on t>0t>0 satisfies the scalar relation. This links unconstrained Newton analysis to the interior-point methods in the next chapter.

Self-concordance is more specific than ordinary smooth convexity. Its usefulness is that local norms can control changes without a single global Euclidean Hessian-Lipschitz constant. The theory includes precise decrement-based regions and complexity statements; those require the proper normalization and barrier assumptions.

A function containing logarithms is not automatically a valid barrier for every constraint representation. Its domain, boundary behavior and scaling must match the optimization problem. Distinguish a smooth likelihood term from a constraint barrier even if both contain a logarithm.

A stable convex logistic solver

Plain version. A complete implementation should evaluate the objective stably, verify its derivatives and stop using an optimality quantity.

For fixed rows ai⊤a_i^\top and binary outcomes yi∈{0,1}y_i\in\{0,1\}, use

f(w)=1N∑i=1N[log⁡(1+exp⁡(ai⊤w))−yiai⊤w]+ρ2∥w∥22.f(w)=\frac1N\sum_{i=1}^N \bigl[\log(1+\exp(a_i^\top w))-y_i a_i^\top w\bigr] +\frac\rho2\|w\|_2^2.

ww is the parameter vector, NN the observation count and ρ>0\rho>0 a regularization coefficient. Every coordinate is regularized in this example. The fixed-design logistic likelihood follows the convex-estimation reasoning in [1, Chapter 7].

Let pi=1/(1+exp⁡(−ai⊤w))p_i=1/(1+\exp(-a_i^\top w)). The derivatives are

g=1NA⊤(p−y)+ρw,H=1NA⊤diag⁡(pi(1−pi))A+ρI.g=\frac1N A^\top(p-y)+\rho w,\qquad H=\frac1N A^\top\operatorname{diag}(p_i(1-p_i))A+\rho I.

AA stacks the rows, p,yp,y are observation vectors, and II is the identity. The positive ρI\rho I gives a valid global strong-convexity constant μ=ρ\mu=\rho.

Use a stable softplus evaluation instead of taking the logarithm of a potentially overflowed exponential. The following bounded synthetic scores permit a direct sigmoid; for unrestricted extreme scores, use a numerically stable sigmoid implementation as well.

Derive the logistic curvature bounds

A stable objective is also easier to optimize when its curvature constants are known. For one score s=ai⊤ws=a_i^\top w, the derivative of log⁡(1+es)\log(1+e^s) is pip_i, and its second derivative is pi(1−pi)p_i(1-p_i). Thus subtracting the linear term yisy_i s gives gradient (pi−yi)ai(p_i-y_i)a_i and Hessian pi(1−pi)aiai⊤p_i(1-p_i)a_i a_i^\top.

Here aia_i is a fixed feature vector, ww the parameter vector, yi∈{0,1}y_i\in\{0,1\} the observed label and pip_i the sigmoid probability. Average over observations and add the quadratic penalty to obtain the derivatives displayed above. Since 0≤pi(1−pi)≤1/40\leq p_i(1-p_i)\leq1/4,

ρI⪯∇2f(w)⪯(ρ+∥A∥224N)I.\rho I\preceq\nabla^2 f(w) \preceq\left(\rho+\frac{\|A\|_2^2}{4N}\right)I.

Here ff is the regularized average logistic objective, AA the feature matrix, NN the observation count, ρ>0\rho>0 the penalty, and ∥A∥2\|A\|_2 its largest singular value. The lower bound follows from full-coordinate regularization; the upper bound follows by testing v⊤A⊤diag⁡(pi(1−pi))Avv^\top A^\top\operatorname{diag}(p_i(1-p_i))Av for arbitrary direction vv.

Consequently μ=ρ\mu=\rho and L=ρ+∥A∥22/(4N)L=\rho+\|A\|_2^2/(4N) are valid global constants. They provide a safe gradient step and an objective-gap stopping bound for this specific model. If the intercept is left unpenalized, the same positive lower bound for every coordinate no longer follows. The mathematical formula, the penalty implementation and the stopping test must agree [1].

Code: Newton with derivative and stopping checks

This is an optimization demonstration, not a classification benchmark. It checks a directional derivative before solving and verifies the final gradient, decrease sequence and strong-convexity gap bound.

Code · Python · 54 lines
import numpy as np

rng = np.random.default_rng(16)
A = rng.normal(size=(160, 5))
truth = np.array([0.8, -0.5, 0.3, 0., 0.4])
prob = 1/(1+np.exp(-(A @ truth)))
y = (rng.random(len(A)) < prob).astype(float)
rho = 0.1

def evaluate(w):
    z = A @ w
    p = 1/(1+np.exp(-z))
    value = np.mean(np.logaddexp(0, z)-y*z) + rho*(w @ w)/2
    gradient = A.T @ (p-y)/len(y) + rho*w
    Hessian = (A.T * (p*(1-p))) @ A/len(y) + rho*np.eye(A.shape[1])
    return value, gradient, Hessian

w = np.zeros(A.shape[1])
direction = rng.normal(size=len(w))
eps = 1e-5
finite_difference = (evaluate(w+eps*direction)[0] -
                     evaluate(w-eps*direction)[0])/(2*eps)
assert np.isclose(finite_difference, evaluate(w)[1] @ direction,
                  atol=1e-8)
history = []
for iteration in range(30):
    value, g, H = evaluate(w)
    history.append(value)
    if np.linalg.norm(g) < 1e-9:
        break
    step_direction = np.linalg.solve(H, -g)
    slope = g @ step_direction
    assert slope < 0
    step = 1.0
    for trial in range(50):
        candidate = w + step*step_direction
        candidate_value = evaluate(candidate)[0]
        if np.isfinite(candidate_value) and candidate_value <= value+0.1*step*slope:
            w = candidate
            break
        step *= 0.5
    else:
        raise RuntimeError("backtracking did not accept a step")
else:
    raise RuntimeError("iteration limit reached")

value, g, H = evaluate(w)
assert np.linalg.norm(g) < 1e-9
assert np.all(np.diff(history) <= 1e-12)
assert np.linalg.eigvalsh(H).min() >= rho-1e-12
print("accepted Newton steps:", len(history)-1)
print("objective:", round(value, 8))
print("gradient norm:", np.linalg.norm(g))
print("objective-gap upper bound:", (g @ g)/(2*rho))

The derivative check tests one direction and one point; it cannot prove every derivative correct. Add checks at representative nonzero points when changing the model. Hessian symmetry, eigenvalue expectations and solve residuals provide additional independent evidence.

Objective convergence for the illustrative quadratic gradient method and synthetic regularized logistic Newton solver.
Figure 2 — Original computed convergence traces. The left panel has a known zero quadratic optimum; the right panel shows a gradient norm for a synthetic logistic objective. Accepted steps are not a runtime or cross-problem benchmark.

Implementation and stopping reports

Plain version. A solver result should describe why it stopped, what it verified and what computational work it performed.

Dense Newton stores a matrix whose size grows quadratically with the number of variables. Factorization can dominate the cost. Gradient methods often need only matrix-vector products, making many cheap iterations attractive for large problems.

Sparse matrices, low-rank terms and block structure can alter that comparison substantially. Exploit structure only after checking that the transformed system remains equivalent and that factorization fill-in is manageable [1, Section 9.7 and Appendix C].

A Hessian-vector product can support an iterative linear solve without explicitly storing the Hessian. Then the inner solve has its own residual and tolerance. A loosely solved Newton system need not reproduce the exact Newton direction or convergence rate.

Report objective values, a suitable gradient or stationarity residual, domain checks, iteration count and the stated stopping condition. Where timing matters, include derivative evaluations and line-search trials rather than only accepted steps.

Scaling the objective changes gradient magnitudes. A fixed absolute gradient tolerance is therefore not comparable across arbitrary loss normalization. Relative criteria need a documented scale and should remain meaningful near zero.

An iteration limit is a resource stop, not an optimality certificate. A line-search failure is an algorithmic diagnosis, not proof of nonexistence. Retain the final candidate and residual evidence so that the result can be assessed.

Exact quadratic line searches reveal a tradeoff

For the positive-definite quadratic above and a nonzero descent direction dd, the objective along the line is a scalar quadratic. Differentiating with respect to distance gives

t∗=−g⊤dd⊤Qd.t^*=-\frac{g^\top d}{d^\top Qd}.

g=Qx+cg=Qx+c is the current gradient, QQ the positive-definite curvature and t∗>0t^*>0 the minimizing line distance. This formula is an exact line search for this particular quadratic, not a general smooth objective.

For the negative gradient direction, the numerator becomes g⊤gg^\top g and the denominator is g⊤Qgg^\top Qg. The chosen distance accounts for curvature along that direction. It can outperform a conservative fixed step without correcting the underlying elongated geometry.

Successive directions can still zigzag. Exact minimization along one line does not imply that the line points directly toward the global minimizer. This makes the roles of direction and distance particularly clear: better distance selection cannot fully replace better directional geometry.

A Newton direction uses the whole quadratic curvature system, reaching the minimizer with distance one in exact arithmetic. A metric approximation may reduce the system cost while giving a less accurate route. The fair comparison includes how the metric is built and reused, not just the length of the visible path.

If a matrix factorization is reusable across many right-hand sides, its initial cost can be amortized. If the matrix changes at each iteration, that advantage may shrink. Likewise, an objective evaluation can be cheap in a tiny tutorial but expensive in an application with a simulation inside it. State the actual computational primitives before making a speed claim.

Derivative checks need a scale

A central finite difference divides the difference of two nearby objective values by twice the perturbation. Making the perturbation smaller reduces the ideal truncation error at first, but eventually amplifies floating-point cancellation.

Use several perturbation sizes and compare relative as well as absolute discrepancies. Scale the direction sensibly, choose test points away from a domain boundary, and inspect whether the result stabilizes over a useful interval. One failed tiny-step comparison may indicate numerical resolution rather than an incorrect derivative.

For a Hessian, compare a gradient difference with a Hessian-vector product. This tests a different layer of the implementation from checking objective differences alone. Also verify symmetry when the objective is twice continuously differentiable and the intended Hessian should be symmetric.

An automatic derivative system can remove much manual algebra but still differentiate the implemented expression rather than the intended model. Incorrect broadcasting, a misplaced reduction or an accidentally regularized intercept can yield a perfectly consistent derivative of the wrong objective.

Record these checks beside the formulation. The goal is to connect symbols to arrays, not merely to produce a green test. Once the implementation matches the model, numerical tolerances and algorithm assumptions can be assessed meaningfully.

A reproducible comparison also needs a starting point, objective normalization, stopping rule and numerical precision. Changing any of these can alter apparent convergence. Store the parameters and random seed with a synthetic experiment so that a later figure can be regenerated from the same stated problem.

For deterministic algorithms, small platform differences may still affect the final few digits or a marginal line-search comparison. Verify properties with justified tolerances instead of asserting one exact decimal trajectory. The examples here check descent, linear-system consistency and gradient evidence, which are the quantities tied to the formulation.

Modern view

Plain version. Modern convex algorithms trade curvature information, projections, proximal operations and communication costs. The right choice depends on structure and required accuracy.

Dvurechensky, Shtern and Staudigl’s first-order survey [2] provides a broad foundation, including non-Euclidean proximal methods, acceleration and projection-free approaches. It was published in 2021; it is a background map rather than a new 2026 result.

Condat and colleagues’ 2023 SIAM Review survey [3] unifies proximal splitting for high-dimensional nonsmooth convex problems through primal–dual product spaces and chosen metrics. It explains why adding an absolute-value penalty changes the appropriate primitive: an ordinary smooth Newton formula cannot simply differentiate through the kink.

Pokutta’s 2024 Frank–Wolfe survey [4] focuses on linear minimization over constrained sets and its convergence and certificate structure. It complements the gradient/Newton comparison by asking whether a projection or expensive system solve can be avoided.

Together these reviews give a practical taxonomy: smooth versus nonsmooth objectives, inexpensive versus expensive feasible-set operations, Euclidean versus structured geometry, and local curvature versus cheap first-order steps. Recent variants do not remove those modeling distinctions.

Current issues include adaptive methods with reliable certificates, precision limits in large linear systems, communication in distributed problems and differentiating through solver outputs. Match the algorithm to the model, the hardware and the requested error measure; compare total work at a comparable accuracy.

Key takeaways

  • A descent direction and a step length are separate choices.
  • Fixed gradient steps require a valid curvature and domain argument.
  • Poor conditioning slows a scalar-step gradient method.
  • Backtracking needs safeguards and correct derivative signs.
  • Newton uses a linear solve and has conditional local convergence.
  • A decrement is a model quantity unless its gap assumptions are established.
  • Reliable reports include stopping evidence and the cost of rejected work.

Exercises

  1. Derive the smoothness decrease inequality for a step of size 1/L1/L.
Hint

Substitute the negative scaled gradient into the upper quadratic model.

  1. Replace the quadratic eigenvalue 40 by 400. Predict and test how fixed-step gradient progress changes.
Hint

The flat-direction contraction depends on the eigenvalue ratio.

  1. Implement backtracking for −log⁡x+x2-\log x+x^2 on x>0x>0, checking the domain before every objective evaluation.
Hint

Reject nonpositive candidates immediately.

  1. Verify the logistic gradient in three random directions at a nonzero parameter vector.
Hint

Compare central differences and inner products using several finite-difference scales.

  1. Show why a singular positive-semidefinite Hessian does not always define a unique Newton direction.
Hint

Inspect the linear system’s nullspace and consistency.

  1. Rescale the logistic objective by one hundred. Determine which stopping quantity and tolerance changes preserve the original requested objective accuracy.
Hint

Transform the gradient, strong-convexity constant and desired gap together.

References

  1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004. Reading: Chapter 9, Sections 9.1–9.7; Appendix C for linear systems; Chapter 7 for the logistic likelihood connection. Official book, free PDF.
  2. Pavel Dvurechensky, Shimrit Shtern and Mathias Staudigl, “First-Order Methods for Convex Optimization,” EURO Journal on Computational Optimization, 9, 100015, 2021. Verified open manuscript, published article.
  3. Laurent Condat, Daichi Kitahara, Andrés Contreras and Akira Hirabayashi, “Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists,” SIAM Review, 65(2), 375–435, 2023. Published survey, open manuscript.
  4. Sebastian Pokutta, “The Frank-Wolfe Algorithm: A Short Introduction,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 126, 2024. Open-access survey.

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next OPT 07 · Equality Constraints and Interior-Point Methods · 21 min