Paying for the Tuning: End-to-End Cost of Optimal High-Order Methods

Optimization theory promises that methods using second- and third-order derivative information can reach an accurate solution in far fewer steps than gradient methods. On smooth convex problems, accelerated gradient descent needs on the order of $\epsilon^{-1/2}$ iterations to reach accuracy $\epsilon$, while the best second-order methods need $\epsilon^{-2/7}$ and third-order "tensor" methods need $\epsilon^{-1/5}$. These rates count only outer iterations. They leave out three costs. Each step is expensive. Many methods run an internal search to adapt their step parameters. And a user must tune hyperparameters before the method works at all. On the other side, the evidence that high-order methods beat gradient methods in practice comes from small studies in which first-order baselines were not tuned with a budget comparable to the one spent on the proposed method. The benchmarking literature has shown repeatedly that this kind of gap produces illusory gains.

This note proposes to measure the cost that a practitioner actually pays: total computational work to reach a target accuracy, including every hyperparameter-search trial and every internal line-search or parameter-search evaluation. The measurement is restricted to problem classes where the theoretical rates apply. The central question is whether a theory-derived crossover accuracy $\epsilon^*$ exists: the accuracy beyond which high-order methods win once all costs are counted. A second question is whether that crossover can be predicted in advance from the rates plus measured per-step costs. A secondary question is whether "self-tuning" high-order methods, which adapt their parameters internally, pay for their internal search. The alternative is externally tuning a fixed schedule.

Core Claim

We claim that the comparison between high-order and first-order methods is currently uninterpretable for two reasons. It mixes iteration counts with unequal tuning budgets, and it ignores internal adaptation overhead. A benchmark that charges methods for tuning and internal search will show two things. First, there will be a problem-dependent crossover accuracy. Above it, tuned first-order or quasi-Newton methods win. Below it, adaptive high-order methods win. Second, the location of this crossover can be predicted to within roughly an order of magnitude by equating the theoretical iteration bounds weighted by measured per-iteration cost. The second part is the risky, falsifiable claim. If it holds, practitioners get a rule for choosing a method class before running anything. If it fails, the failure itself is informative. It would show that worst-case rates carry little information about where methods actually rank.

The work sits across three literatures in unequal roles. Optimal iteration complexity supplies the methods and the predicted crossover. Hyperparameter optimization supplies the accounting: tuning is charged as cost, and the metrics come from sensitivity studies. Standardized benchmarking supplies the protocol discipline: multiple seeds, equal budgets, and held-out evaluation.

Research Program

Method sources. The high-order methods come from existing work. The first source is OPTAMI: Global Superlinear Convergence of High-order Methods. It introduces NATA, an accelerated tensor method that searches at every step for the largest acceleration parameter that still satisfies its convergence condition. It also provides a PyTorch library with cubic-regularized Newton, basic tensor methods, and a third-order subproblem solver. The second source is Newton Method Revisited. It gives Root Newton, a stepsized Newton method with global rates up to $O(k^{-3})$. It also gives two adaptive procedures, Universal Backtracking and Gradient-Regulated Line Search, that remove the need to know smoothness constants.

The gap these papers leave. Both papers report convergence curves on logistic regression with the a9a and w8a datasets, Poisson regression, and Rosenbrock-type problems. Neither charges the internal search to the method. Neither gives first-order baselines a matched tuning budget. The research file records no numerical results from either paper, only curves.

Why we suspect the gap matters. DeepOBS showed that optimizer rankings depend on tuning protocol and seed. It also found that Adam's practical edge was its tunability rather than its peak speed. Fantastic Pretraining Optimizers found that tuning AdamW's learning rate alone gave a 2x speedup on a 100M-parameter model. After all eleven optimizers were tuned, no alternative exceeded 1.4x, and the advantage shrank to about 1.1x at 1.2B parameters. On the State of the Art of Evaluation in Neural Language Models showed that a tuned LSTM beat newer architectures on Penn Treebank. That paper also warns that tuning on a small validation split overfits it. We adopt that warning as a design constraint.

The accounting. We charge each method a cost in gradient-equivalents. A gradient counts as one. A Hessian-vector product counts as a measured constant. A full Hessian formation and solve counts at its measured multiple. Wall-clock time on fixed hardware is reported separately, because DeepOBS notes that implementation quality confounds timing.

The tuning-inclusive cost after $k$ random hyperparameter trials is

$$C_k(\epsilon) = \sum_{j=1}^{k} c_j(\epsilon) \quad \text{with success judged by } \min_{j \le k} \text{gap}_j .$$

Here:

  • $c_j(\epsilon)$ is the cost of trial $j$, run until it either reaches suboptimality $\epsilon$ or exhausts its per-run cap;
  • $\text{gap}_j$ is that trial's final suboptimality, measured on a validation objective separate from the reporting objective.

Averaging $C_k$ over random draws of trials gives an expected cost-versus-budget curve. This is the optimizer analogue of the relative-performance-at-$k$ sensitivity measure from Quantifying the Hyperparameter Sensitivity of Neural Networks. That paper defined such measures for comparing architectures; we apply them to the internal knobs of optimizers. These knobs include:

  • the regularization constant $M$;
  • subproblem tolerances;
  • line-search contraction factors;
  • learning rates.

The prediction. For each problem we estimate the smoothness constants: the gradient Lipschitz constant $L_1$, the Hessian Lipschitz constant $L_2$, and a distance-to-solution scale $R$. The prediction then comes from the standard bounds. Tuned accelerated gradient descent needs about $\sqrt{L_1 R^2/\epsilon}$ steps, which is the $p=1$ case of the lower bound in Lower Bounds for Higher-Order Convex Optimization. Optimal second-order methods need about $(L_2 R^3/\epsilon)^{2/7}$. Writing $c_1$ and $c_2$ for the measured per-step costs of the two method classes, the predicted crossover solves

$$c_1 \sqrt{L_1 R^2/\epsilon^*} = c_2 \, (L_2 R^3/\epsilon^*)^{2/7} .$$

We then compare this $\epsilon^*$ with the empirical crossover of the tuning-inclusive cost curves. There is a known reason the prediction may fail. NATA exists precisely because theoretical schedules are pessimistic. OPTAMI also proves global superlinear convergence on strongly star-convex problems, which can move the crossover to much looser accuracies than the worst-case formula implies. Measuring how far the prediction is off is part of the result.

Baselines

Naive reference. The do-nothing reference is plain gradient descent with its step size set from the estimated Lipschitz constant, with no tuning cost charged. It marks the floor and the cost of doing nothing clever.

Parameter-free first-order methods. The zero-tuning first-order reference is AdaGrad-norm stepsizes. Attia & Koren prove these adapt to unknown smoothness and noise. Rodomanov et al. prove they are universal across smooth, nonsmooth, and Hölder-smooth problems. They are the fairest comparison for self-tuning high-order methods, because neither side pays external tuning cost.

Strongest baselines. The strongest competitors are two methods, each tuned with the same budget of $k$ random trials drawn from log-uniform ranges:

  • Nesterov accelerated gradient and AdamW, where the learning rate and momentum are tuned;
  • L-BFGS with a Wolfe line search, where the memory size and initial scaling are tuned.

L-BFGS is the most dangerous competitor on logistic regression. It captures curvature at nearly first-order per-step cost. The research file records no reported result on Lacuna for tuned L-BFGS or tuned AdamW on a9a or w8a suboptimality. The closest reported figures are the 1.4x and 1.1x ceilings from Wen et al. on C4-EN pretraining. Those come from a different regime and serve only as context for how large tuned-baseline gaps typically are. We therefore report the baseline cost curves ourselves.

Beating a baseline. A high-order method "beats" a baseline at accuracy $\epsilon$ if its median tuning-inclusive cost is lower at matched budget $k$. The median is taken across ten seeds. The seeds vary three things: initialization, a bootstrap resample of the training set, and the hyperparameter draw. The confidence intervals of the two methods must not overlap.

Classical second-order baseline. Damped Newton with Armijo backtracking is the classical second-order baseline. Hanzely et al. report that Gradient-Regulated Line Search was more robust than Armijo on Rosenbrock, but give no numbers in the file.

Ablation. The ablation that isolates our key ingredient is to replace NATA's per-step search with the best fixed acceleration schedule found by external tuning. We do the same for Root Newton, replacing Universal Backtracking with an externally tuned fixed step. This tells us whether internal adaptation is cheaper than buying the same effect through tuning trials.

Why not just…?

Why not just add high-order methods to DeepOBS? DeepOBS problems are nonconvex neural networks with many parameters. Exact Hessians there are infeasible, and the theoretical rates do not apply. Such a run could not test the crossover prediction. It would mostly measure how well Hessian approximations are engineered. We borrow the DeepOBS protocol, not its problems. Its ill-conditioned quadratic and Rosenbrock problems enter only as a convex control and a nonconvex control.

Why not just tune L-BFGS well and declare victory? This is a real threat. On moderately sized logistic regression, tuned L-BFGS may dominate at every accuracy we test. OPTAMI notes that global superlinear guarantees for quasi-Newton methods are open. Agafonov et al. show that inexact curvature must be controlled carefully to keep rates. Neither result proves L-BFGS loses in practice. If L-BFGS wins throughout, we will report that no crossover exists within the tested accuracy range. That finding would narrow the practical claims for exact high-order methods. It is an acceptable outcome, and the experiments are designed so it can be seen.

Why not just report wall-clock time? Wall-clock is confounded by kernels and library maturity, as DeepOBS observed. That makes it unsuitable for testing a prediction derived from theory. We report it alongside the operation-count cost. We flag any case where the two orderings disagree.

Why not just use parameter-free AdaGrad and skip tuning entirely? Its guarantees stop at first-order rates, so it cannot exploit Hessian smoothness at tight accuracies. Whether that matters at the accuracies people actually need is exactly what the cost curves show. It appears as a baseline for that reason.

Proposed Experiments

Problems. The testbed covers four settings.

  • Logistic regression. The OPTAMI and Root Newton problems: logistic regression on a9a and w8a. We sweep the L2 regularization over several values to vary the conditioning.
  • Other convex problems. Poisson regression, and Nesterov's lower-bound function, where worst-case rates are tight.
  • Dimension sweep. Random-feature expansions of a9a at increasing dimension, to locate where the cubic cost of dense Hessian solves erases the iteration advantage.
  • Nonconvex controls. DeepOBS Rosenbrock and the ill-conditioned quadratic.

Metrics. The primary metric is expected tuning-inclusive cost $C_k(\epsilon)$ over a grid of $\epsilon$ from $10^{-2}$ to $10^{-10}$ and $k$ from 1 to 50. Secondary metrics are:

  • Wiemerslage-style sensitivity summaries over each method's hyperparameter space;
  • held-out test loss on bootstrap splits, to check whether driving training suboptimality very low changes generalization.

Decisive checks. There are four.

  1. For each problem, does an empirical crossover $\epsilon^*$ exist between tuned L-BFGS/accelerated gradient and the best adaptive high-order method? Does the rate-based prediction land within a factor of ten of it?
  2. Does the fixed-schedule ablation of NATA and Root Newton, once charged for its tuning trials, cost more than the self-adaptive version? If it costs less, internal search is overhead and not a benefit.
  3. At $k=1$, does any high-order method's cost beat AdaGrad-norm? This settles whether "tuning-free" high-order methods are actually tuning-free in practice.
  4. Does the crossover move predictably along the dimension sweep, following the ratio $c_2/c_1$?

A clear pass on the first and fourth checks would give the field a usable rule linking theory to method choice. A clear failure would show that worst-case iteration complexity should not be cited as evidence of practical speed.