PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex Optimization Is Free When Accuracy Is Expensive

Arthur Paing, Arthur Jacot

arXiv:2609.35418v1math.OCcs.LGstat.ML

TL;DR

When gradients are available only through costly approximations, existing inexact-gradient theory needs adapting in the HTMC regime. The paper randomizes a multilevel oracle to price bias and variance independently, and shows that plain inexact gradient descent reaches loss ε at compute ε^-γ rather than ε^-(γ+1) for fixed-accuracy descent.

  • Problem

    In the HTMC regime, inexact gradient descent with costly gradient approximations requires an adaptation of existing theory, while prior oracles expose only one accuracy choice.

    Source: §1 · p. 1

  • Method

    The paper randomizes a hierarchy of gradient approximations into a weakly biased oracle whose bias and variance are priced independently, then uses plain inexact gradient descent.

    Source: §2.1 · p. 2, §5 · p. 10

  • Results

    For γ>2, plain inexact gradient descent reaches loss ε at compute ε^-γ, versus ε^-(γ+1) for the same method at fixed accuracy.

    Source: §5 · p. 10

  • Takeaways & Limitations

    The compute bound is independent of the step size and smoothness constant, and depends on the underlying gradient flow rather than its discretization.

    Source: §5 · p. 10

    Extending the strongly convex analysis would require describing convergence to a multilevel Poisson jump process as η approaches zero and adapting the proofs to subgradients.

    Source: Strongly convex case · p. 6

Abstract

from arXiv · show

This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like $\delta^{-\gamma}$ in the accuracy $\delta$. When $\gamma>2$, falling into the Harder-Than-Monte-Carlo (HTMC) regime, the price of accuracy outruns the variance reduction that Monte Carlo would buy and we show that minimizing a loss function costs no more, up to a factor depending only on $\gamma$, than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy $\delta$ by an unbiased estimator of it, whose variance $\sigma^2$ becomes a second, independently priced dial: the cost of one call drops from $\delta^{-\gamma}$ to $\delta^{2-\gamma}\sigma^{-2}$. Plain inexact gradient descent driven by that oracle reaches loss $\varepsilon$ at expected compute $\Theta(\varepsilon^{-\gamma})$ in the convex case, against $\Theta(\varepsilon^{-(\gamma+1)})$ for the same method run at a fixed accuracy: randomization buys a full power of $\varepsilon$. Under $\mu$-strong convexity the exponent halves, to $\varepsilon^{-\gamma/2}$, because the iterates settle at a noise floor and the bias budget relaxes accordingly. Both bounds are independent of the step size, and hence of the smoothness constant, and we show that the cost is a functional of the underlying gradient flow rather than of any discretization of it.

1 Introduction

The paper studies convex optimization when gradients are available only through increasingly accurate, increasingly costly approximations. It introduces an oracle with independently priced bias and variance, so iteration count no longer determines the compute bill in the HTMC regime.

Motivation

  • Discretized PDEs, nested simulations, and neural networks approximating scores or drifts are examples where gradients are available only through costly approximations.The paper adapts inexact-gradient theory to the HTMC regime, where minimizing the function can cost no more than one gradient evaluation at the required accuracy.Source: §1 · p. 1

Contribution

  • Earlier approaches expose a single accuracy knob, whereas this paper’s oracle separately prices bias and variance.The introduction contrasts this design with Van Dessel & Glineur (2024) and Dvurechensky & Gasnikov (2016).Source: §1 · p. 1

Related work

  • The paper adapts existing inexact-gradient theory to the HTMC regime, building on randomized multilevel estimators studied by Hu et al. (2024).Hu et al. (2024) obtain the same cost exponents under assumptions about a hierarchy of approximating functions.Source: §1 · p. 1

2 Setup

The setup models a convex loss whose gradient is available through a hierarchy of increasingly accurate, increasingly costly algorithms. Randomization turns the hierarchy’s single accuracy choice into separately priced bias and variance, with the resulting oracle behaving differently across compute regimes.

2.1 The approximate gradient oracle

  • The dyadic hierarchy assumes algorithms A_k approximate the gradient within 2^-k at compute growing exponentially in k.The paper states that its bounds apply to any hierarchy of this shape.Source: §2.1 · p. 2
  • Randomizing the hierarchy’s algorithms creates separate bias and variance choices from the single accuracy dial of a fixed-level evaluation.The paper describes these two quantities as being priced at unrelated exponents.Source: §2.1 · p. 2
  • For γ>2, plain gradient descent with the randomized oracle has the smallest bound, while acceleration has the smallest bound below the threshold.Table 1 identifies the smallest bound in each regime; its expected-compute entries omit a factor c^γ and constants depending only on γ.Source: §2.1 · p. 2, Table 1 · p. 2

2.2 Upgrading to a weakly biased oracle through randomization

  • The randomized estimator keeps bias at most δ and can be tuned to variance at most σ^2, with no other choice of level probabilities improving its compute by more than a factor depending on γ.Source: §2.2 · p. 3
  • In the HTMC and ETMC regimes, the multilevel oracle matches the least-biased cost rate; in the MC regime, it falls short by a logarithmic factor.The stated rates are h(r)=r^min{γ,2} for the least-biased oracle and h(r)=r^2 log^2(1/r) for the multilevel oracle in the MC regime.Source: §2.2 · pp. 3–4
  • Above γ=2, the oracle’s bias and variance are bought separately and a cruder estimator is cheaper; below it, bias is free but multilevel randomization no longer cancels the iteration horizon.At the threshold, bias is free only up to a log2(σ/δ) factor.Source: §2.2 · p. 4

3 Multilevel stochastic gradient descent

The section analyzes plain inexact gradient descent driven by a randomized multilevel oracle, which separates bias and variance. It establishes the optimization cost and its optimality, then explains how strong convexity and acceleration affect the rates.

3 Multilevel stochastic gradient descent

  • Plain inexact gradient descent uses independent randomized-oracle draws across steps, with total compute measured as iterations times expected per-call compute.The oracle separates bias and variance; above the threshold, a cruder estimator is cheaper, so the bias is chosen as large as the geometry permits.Source: §3 · p. 4

Strongly convex case.

  • The strongly convex weighted average focuses on iterates near a noise floor, relaxing the bias budget and halving the exponent.The stated strongly convex bound applies when ε ≤ µd0^2; the continuous-time time-varying-accuracy result removes the logarithmic factor.Source: Strongly convex case · pp. 5–6
  • In the HTMC regime, the cost is independent of β and is described as a functional of the gradient flow rather than its discretization.The authors note that removing the smoothness assumption for nonsmooth losses would require a Poisson-process limit and proofs for subgradients.Source: Strongly convex case · p. 6

3.2 The cost exponent is optimal

  • Randomization changes the convex complexity exponent from ε^-(γ+1) for the deterministic baseline to ε^-γ; under strong convexity, the exponent γ/2 is optimal.The strongly convex randomized bound avoids the baseline’s conditioning factor κ, up to a logarithm.Source: §3.1 · p. 5, §3.2 · p. 7
  • The lower bound applies to worst-case instances in the oracle model, while the paper notes that some instances, including its Section 4 design, are easier.The optimality argument uses a hierarchy in which distinguishing two instances requires querying below a specified accuracy.Source: §3.2 · p. 7

3.3 A word on acceleration

  • Acceleration helps if and only if γ < 2, taking part of the gap there without closing it; at and above the threshold it is neutral or strictly worse.Above the threshold, the lower bound already restricts accelerated methods, leaving no exponent improvement to gain.Source: §3.3 · p. 8

4 Least squares with truncated features

The least-squares instance makes the approximation-cost exponent measurable from feature geometry, then tests the predicted separation between multilevel and fixed-level optimization. The multilevel method has the smaller compute exponent on every seed, with its advantage widening at tighter targets.

4.1 The design and its rate

  • For columns with norms proportional to i^-1/φ, the truncation hierarchy has γ = 2φ/(2 − φ), placing the instance in HTMC precisely when φ > 1.At φ = 1, feature importance decays harmonically; HTMC corresponds to slower decay.Source: §4.1 · pp. 8–9

4.2.1 Protocol

  • The experiment uses φ = 1.2 and γ = 3, with levels {1, 8, 64, 512}; each level retains eight times as many features, costs eight times as much, and halves bias.The target is flat, discarded features carry energy, and b = AX∗ makes the full problem interpolate.Source: §4.2.1 · p. 9

4.2.2 Results

  • The fixed-level comparator uses the same oracle and optimizer, is tuned over its available parameters, and is not restricted to the multilevel method’s probability ladder.Reported compute is the minimum reaching each target, summarized as a median over ten seeds with interquartile bands.Source: §4.2.2 · p. 9
  • On every seed, level bias follows a power law with R2 ≥ 0.999; the exact-residual fit gives 2.04 ± 0.26 for truncated residuals versus 2.92–2.99 for exact residuals.The remaining 1.2% discrepancy closes as the design tail is lengthened.Source: §4.2.2 · pp. 9–10
  • 2.76 ± 0.12 (multilevel) vs 3.44 ± 0.09 (fixed level); exact-residual multilevel reaches 2.18 ± 0.10 and 46× at the tightest shared target.Figure 1 compares compute to target loss; the exact-residual implementation is cheaper in the same run.Source: §4.2.2 · p. 9, Figure 1 · p. 10
  • The multilevel advantage appears only at tighter targets: the fixed-level baseline is cheaper at loose targets, where the telescope overhead is not yet repaid.The dashed loss floor marks where the strongly convex bound becomes binding.Source: §4.2.2 · p. 10, Figure 1 · p. 10

4 Least squares with truncated features

  • This least-squares example is diagnostic rather than a solver contest: truncation restricts to a subspace, and a Krylov method beats both plotted curves on the quadratic.Its value here is that the rate γ is available in closed form and can be measured rather than assumed.Source: §4 · p. 8, §4.2.2 · p. 10

5 Conclusion

The paper shows that in the HTMC regime, randomized multilevel estimation lets plain inexact gradient descent reach loss ε at compute ε^-γ rather than ε^-(γ+1) for fixed-accuracy descent. The authors leave non-convex optimization as an open question.

5 Conclusion

  • For convex objectives with γ > 2, reaching loss ε costs ε^-γ with the randomized multilevel oracle, versus ε^-(γ+1) for fixed-accuracy gradient descent.The rate is optimal in the same oracle model and also binds accelerated methods.Source: §5 · p. 10
  • The method randomizes a deterministic approximation hierarchy into a weakly biased estimator whose bias and variance are priced independently, then runs plain inexact gradient descent.The resulting bound is independent of step size and smoothness, making cost a functional of the gradient flow rather than its discretization.Source: §5 · p. 10
  • Whether the method’s advantages extend to non-convex optimization remains an open question.The paper notes potential relevance to costly DNN gradient evaluations, citing evidence that DNNs lie in HTMC, but says their gradients likely do as well.Source: §5 · pp. 10–11

AI use statement

The paper reports AI assistance in writing and experiment implementation, while stating that the research questions, claims, and proofs were not AI-generated. Its related-work discussion distinguishes its deterministic approximation hierarchy from prior random-oracle frameworks.

AI use statement

  • Authors used AI assistance for prose revision, figure and table preparation, experiment code, and locating related work, with references checked against sources.They state that research questions, claims, and proofs were not produced with generative AI, and describe independent numerical checks of estimator unbiasedness, flop accounting, and scaling.Source: AI use statement · p. 13

Ethics statement

  • The work is theoretical and its experiment uses synthetic data; it includes no human subjects, sensitive data, or released dataset.The authors report no specific ethical concern beyond those generally associated with optimization methods.Source: Ethics statement · p. 13

A Related work

  • Unlike Hu et al. (2024), this paper starts from deterministic oracles and upgrades them to random oracles without assumptions about correlations between levels.The cited framework starts with random oracles and proposes four multilevel estimators.Source: A Related work · p. 14
  • In HTMC, prior estimators described here cannot expose the ETMC variance-accuracy tradeoff; the paper contrasts their rates with faster guarantees available in ETMC.The related-work passage reports no rates faster than ε^-1 in the strictly convex case or exponent 2 in the convex case for that framework.Source: A Related work · p. 14

B.1.1 A sufficient choice of probabilities pk

  • The sufficient probability choice clamps p_k at one; this clamp becomes binding for γ ≤ 2, where the sum is dominated by k_min.The unclamped shape is p_k proportional to 2^-(1+γ/2)k.Source: §B.1.1 · p. 16

B.1.2 The optimal probabilities, and the other two branches

The appendix optimizes multilevel sampling probabilities and derives distinct cost branches across γ regimes, then uses a biased-and-noisy oracle decomposition to prove the convex-case bound. It also compares that analysis with deterministic fixed-accuracy descent.

B.1.2 The optimal probabilities, and the other two branches

  • The optimal unconstrained sampling probabilities scale as p_k ∝ 2^-(1+γ/2)k; enforcing p_k ≤ 1 makes an initial segment deterministic up to a cut accuracy δ∗.Above the cut, probabilities are interior; optimizing the cut yields the cost expression referenced as equation 3.Source: §B.1.2 · p. 16
  • For γ > 2, the finest randomized level dominates and the optimal construction takes no deterministic prefix; for γ < 2, the prefix and randomized costs balance.Below the threshold, accuracy is bought deterministically down to the tolerated noise level, and the multilevel construction buys nothing.Source: §B.1.2 · pp. 16–17
  • At γ = 2, the cost includes log2(σ/δ); across the three branches, variance costs scale as σ^-2, σ^-2 log2, or σ^-γ.The passage attributes the threshold logarithm to the sum counting its levels.Source: §B.1.2 · p. 17

B.2 Proof of Theorem 4

  • The proof decomposes each oracle call into exact gradient, deterministic bias bounded by δ, and centered noise with conditional second moment at most σ2.A one-step bound is stated for η ≤ 1/(4β), followed by a master recursion in expectation.Source: §B.2 · pp. 17–18

B.2.1 Convex case

  • For deterministic fixed-level descent, the proof uses T = ⌈16βd0^2/ε⌉ steps, each costing (16cd0/ε)^γ; the resulting exponent is γ + 1.In this case the step size does not cancel and β remains in the bound.Source: §B.2.1 · p. 19

B.2.2 Strongly convex case

In the strongly convex case, the contraction noise floor replaces the initial distance in the bias budget, yielding an exponent of γ/2. The appendix also relates the bounds to continuous-time flow and gives an intrinsic-rate optimality argument.

B.2.2 Strongly convex case

  • The iterates contract to a noise floor V, making the typical distance V rather than d0 and relaxing the bias budget to δ ≍ √(με).Choosing V = ε/μ gives the stated bias budget and accounts for the γ/2 exponent.Source: §B.2.2 · pp. 20–21
  • Strong convexity halves the exponent to γ/2; randomization instead removes the condition-number factor paid by the fixed-accuracy baseline.The comparison is for ε ≤ μd0^2, where the floor lies below the starting point.Source: §B.2.2 · p. 21

B.3 Proof of Proposition 6

  • Per unit of flow time, 1/η calls accumulate drift b and variance ησ²; the diffusion rate remains finite as η → 0.The continuous-time proof weights and integrates the contraction and oracle-noise injection; its schedule must avoid endpoint choices that reintroduce a logarithm or worsen the error bound.Source: §B.3 · pp. 21–23

C The exponent is optimal

  • Theorem 7 establishes that nothing in the iteration can improve the exponent below γ, while strong convexity forces its exponent through stability under Legendre conjugation.Appendix C.1 counts compute inside oracle calls; the randomized telescope's level increment uses two queries.Source: C The exponent is optimal · p. 23, §C.1 · p. 23

C.2 Two instances that no coarse query separates

This section establishes lower bounds from indistinguishable instances and duality, identifies where they are tight, and analyzes how acceleration affects cost-relevant error and restart budgets. In the strongly convex case, it shows that the compute exponent in ε is γ/2 with or without acceleration, while conditioning amplification remains bounded rather than growing with the horizon, and horizon tightening scales the bias and variance budgets by the same multiplier across all three regimes.

C.2 Two instances that no coarse query separates

  • At least 3/4 probability of a fine query is necessary: below the threshold, two instances give identical answers, yet no shared output can be ε-accurate for both.The base problem starts at its minimizer and makes the hard pair’s rate legitimate, since the adjoined coordinate alone has an exactly computable gradient.Source: §C.2 · pp. 24–25

C.3 Duality forces the exponent, without any construction

  • At intrinsic rate g = γmin(∇L), any solver for every strongly convex instance needs loss-cost exponent t ≥ g/2, and the paper’s upper bound attains (g + η)/2 for every η > 0.The intrinsic rate is invariant under conjugation; the proposition requires strong convexity, and establishing its hypothesis for a concrete family remains open.Source: §C.3 · pp. 25–26

C.4 Tightness, and where it stops

  • The lower bound holds at every rate but is tight only for γ ≥ 2; below that threshold, iteration count dominates, so a matching bound must force many iterations to use fine levels.The upper-bound multiplier diverges as γ decreases below 2, reflecting where compute is spent rather than a defect in the construction.Source: §C.4 · p. 26

D Acceleration

  • Gradient error δ converts to linear-in-δ function-oracle error on a bounded convex set, but to quadratic-in-δ error under strong convexity without a domain; this determines which acceleration bound is cheaper.Because per-call compute scales as δ^(2−γ)σ^−2, the conversion that permits larger δ is cheaper.Source: D Acceleration · p. 27

D.1 The convex case

  • In the convex HTMC regime, acceleration degrades the bound: momentum accumulates bias over iterations, the smoothness constant reappears, and its potential improvement vanishes as γ approaches 2.Source: §D.1 · p. 28

D.2 The strongly convex case

  • Under strong convexity, restarting accelerated runs whenever expected squared distance halves yields shrinking losses; stage length is fixed, while the δ and σ budgets bind at the final stage.Strong convexity makes restarts useful by converting a small loss into a small distance, so each stage starts closer to the optimum.Source: §D.2 · pp. 28–29
  • Shrinking the horizon by κ^-1/2 tightens the bias and variance budgets, multiplying δ^(2−γ) by κ^((γ−2)/4) and σ^-2 by κ^1/2; the same multiplier holds in all three regimes.The paper checks the shared multiplier in Appendix D.3.Source: §D.2 · p. 29
  • The strongly convex ε exponent is γ/2 either way: acceleration does not change accuracy costs, which above γ = 2 include a power of the conditioning.Source: §D.2 · p. 29
  • Unlike in the convex case, amplification is bounded by a power of the conditioning rather than the horizon; acceleration could still win a logarithm, which Proposition 6 already gains by scheduling accuracies.Source: §D.2 · p. 29

D.3 Below and at the threshold

Acceleration helps below the γ = 2 threshold and is neutral at it; the numerical study measures the design's oracle-cost rate and uses correlated columns to make the HTMC regime measurable across the ladder.

D.3 Below and at the threshold

  • For γ < 2, acceleration helps; at γ = 2 it is neutral, while the strongly convex comparison has multiplier κ^((γ−2)/4).The convex-case multiplier is T^((γ−2)/2) below the threshold and 1 at the threshold.Source: §D.3 · pp. 29–30

E.1 The instance, and the rate it is designed to have

  • γ = 2φ/(2 − φ) is the design-predicted rate for truncated least squares, and it exceeds 2 exactly when φ > 1.The feature-tail bound gives cost Θ(mk) for accuracy δ, with k ≍ (M/δ)^(2φ/(2−φ)).Source: E The numerical experiment in detail · p. 30

E The numerical experiment in detail

  • The experiment measures the design's rate at fixed points before descent, separating oracle-cost scaling from optimizer behavior.The authors note that the absolute exponents cannot be measured exactly and report deficits from the theorem-allowed values.Source: §E.1 · p. 30

E.1.1 Configuration, and the constraints that fix it

  • The configuration uses φ = 1.2, γ = 3 and 10 seeds; C is swept because the theory's closed-form choice uses conservative constants.The sweep ranges over C ∈ {1, 2, 4, 8, 16, 32}.Source: §E.1.1 · pp. 30–31

E.1.2 Correlated columns, and why they are necessary

  • At m = 2048, a shared direction removes the independent-column damping; ρ = 0.6 yields an R² = 0.995 fit across the ladder.ρ shifts the crossing below which the signal-dominated profile appears, but does not change γ, which is fixed by φ.Source: §E.1.2 · pp. 31–32

E.2.1 What happens with an exact residual

With an exact residual, the two truncations have the same rate but different prefactors; the residual-based form is the reliable instrument for measuring the hierarchy exponent. The appendix reads that exponent from a bias envelope, then compares optimization methods that differ only in their oracle.

E.2.1 What happens with an exact residual

  • Form (b) tracks the lower envelope within 3% and 5%, fitting exponents 2.91 and 2.94 against the design value 3; form (a)'s cross-term window makes its fitted line uninformative.Both truncations have the same rate; only the prefactor M changes, while form (b) requires maintaining the residual.Source: §E.2.1 · pp. 32–33
  • Residual updates cost no more than the oracle call at each step, but this amortization relies on both reading the same m rows.With m′ ≪ m sampled rows, the call becomes cheaper while the m-entry residual update remains; form (a) is then the available stateless option.Source: §E.2.1 · pp. 33–34

E.2.2 Reading γ: the envelope, and where the fit starts

  • Six probes—the origin and five iterates—estimate each level's largest bias; using the final probe alone yields exponents of only 1.38–1.94 across seeds, versus 2.92–2.99 for the envelope.The probes are taken along a 400-step descent driven by the finest-level oracle.Source: §E.2.2 · p. 34
  • Starting the fit at k = 32 excludes the coarse plateau, dividing the exponent spread by eleven and bringing every seed within 1% of the closed form.The plateau ends at an absolute k, so a larger design widens the usable range rather than moving the cut.Source: §E.2.2 · p. 35

E.3 What is measured, and how

  • The comparison reads a single frontier from two methods that share everything except the oracle.This matches the comparison addressed by Theorem 4.Source: §E.3 · p. 35

E.3.1 The two methods

The experiment compares plain gradient descent with a fixed-level oracle against the same optimizer driven by the randomized telescope. Its frontier reports the lowest observed compute for each target, with a more finely tuned baseline ladder to avoid handicapping the fixed-level method.

E.3.1 The two methods

  • Both methods use plain gradient descent, but the baseline uses its level-specific smoothness while the multilevel method uses the finest-level smoothness throughout.Each method is tested at its prescribed step size and half that size, keeping whichever yields a cheaper frontier.Source: §E.3.1 · p. 35

E.3.2 The frontier, and the baseline it is compared to

  • The reported frontier takes the lowest cost at which each target was reached across trajectories, then reports the median across seeds when at least half reached it.The methods are charged alike for products and residual updates; loss is read from the maintained residual without additional diagnostic flops.Source: §E.3.1 · p. 35, §E.3.2 · p. 36
  • The baseline uses ten truncation levels, including the oracle's four levels and six finer choices, so those extra choices can only lower its cost at a target.The baseline ladder has ratio 2 rather than 2^γ.Source: §E.3.2 · p. 36
  • The multilevel exponent is smaller on all ten seeds in both truncation forms, with a gap exceeding 1 on nine exact-residual seeds and one truncated-residual seed.The table reports per-seed exponents at m = 2048, fitted over the same grid of relative targets; the fixed-level method is one shared column.Source: Table 2 · p. 36
  • At the loosest target, the telescope's overhead makes it more expensive; the two methods cross near L/L0 = 0.3.Table 3 gives median flop counts over ten seeds.Source: Table 3 · p. 37

E.4.1 Where the measurement stops

The measured exponent is read only over a bounded range: the loss floor, a theorem-regime threshold, finite design size, and available compute constrain the targets. The reported checks quantify these boundaries rather than treating the fitted exponents as unrestricted.

E.4.1 Where the measurement stops

  • The restricted problem has a nonzero floor: 0.9% of L0 on average across ten seeds, with a 0.3%–2.0% range, so targets must remain above it.The iterates stay in the first kmax coordinates, and the reported loss is L rather than L − L∗.Source: §E.4.1 · p. 37
  • Targets stop above µd0^2 because below that threshold Theorem 4's slope changes to at most γ/2, mixing two regimes in a single fit.On this design, that threshold coincides with the loss floor.Source: §E.4.1 · p. 37
  • Finite truncation understates the finest-level bias by a relative (n/kmax)^(1−2/φ), steepening the fitted line and lowering γ.With n = 256 kmax, the residual deviation follows the predicted law and shrinks as its cause is removed.Source: §E.4.1 · pp. 37–38
  • At the tightest target, the analysis requires about 4·10^5 steps while the run takes 2.5·10^5, leaving a thin budget margin.The one-fifth-budget check returns an exponent of 3.31, showing that the fitted exponent still moves with budget.Source: §E.4.1 · p. 38

E.4.2 What is established, and what is not

The measured hierarchy exponent closely matches its predicted value, and the multilevel method has a smaller cost exponent than fixed-level optimization across the reported seeds and truncations. Absolute fitted exponents fall short of their theorem-allowed values because the analysis uses a worst-case bias prefactor while descent experiences a local one.

E.4.2 What is established, and what is not

  • The measured exponent is 2.963 ± 0.007 against the closed-form value 3, with R2 ≥ 0.999 on every seed.The multilevel cost exponent is smaller on all ten seeds in both truncations, by 0.682 ± 0.083 and 1.254 ± 0.054, respectively.Source: §E.4.2 · p. 38
  • Measured exponents 3.438 ± 0.093 and 2.184 ± 0.097 fall 0.52 and 0.78 below their theorem-allowed values.Assumption 1 uses the largest bias prefactor over the ball, whereas a descent pays an average prefactor along its trajectory.Source: §E.4.2 · p. 38
  • Because the prefactor is the square root of loss, its local saving shifts frontier slopes without bending them and is capped at γ/2 = 1.48.Both methods use the same oracle, so the difference between them comes from iteration count rather than the oracle.Source: §E.4.2 · p. 38
  • The experiment tests exponents and their separation, not the theorem's constant: the frozen-ball bound lies orders of magnitude above observed compute.The stated bound uses Λγ = 2.6 · 10^4 with M frozen at the ball's radius.Source: §E.4.2 · p. 38

Related papers

Loading 2609.35418v1…