acceptodds
Under review as a conference paper at ICLR 2027

Convex Optimization Is Free When Accuracy Is Expensive

Abstract

This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like in the accuracy . When , 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 , than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy by an unbiased estimator of it, whose variance becomes a second, independently priced dial: the cost of one call drops from to . Plain inexact gradient descent driven by that oracle reaches loss at expected compute in the convex case, against for the same method run at a fixed accuracy: randomization buys a full power of . Under -strong convexity the exponent halves, to , 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.

Primary area:
optimization
Keywords:
Convex optimization, MLMC, HTMC

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_2yBXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper considers a problem: given a hierarchy of approximating algorithms with increased rate of computational-cost but also increased rate of accuracy, what is the optimal allocation when used in a first-order optimization task.

The paper biggest weakness is in that the introduction does an extremely poor job in framing the result, explaining it's purpose and describe the novel contributions. A reader whose research interest are weakly-aligned with the present scope will find it extremely hard to understand what this paper is about and what is it trying to achieve.

For example, the paper starts with listing as motivation - Neural Networks. Clearly in a conference like ICLR that would be the typical example. But, given the claimed purpose of this paper (estimating gradients) this is somewhat confusing. The claim seems not to be about gradient estimation, given that in standard models noisy and unbiased gradients are normally assumed making it an MC problem. So overall either this example should be further developed or the paper should distinguish approximation of a prediction function, approximation of a scalar objective, and approximation of its gradient. Its theorem assumes the third, while some of its motivating evidence concerns the first.

The relation to previous work and the contribution is also poorly developed:

"Randomized multilevel estimators for biased oracles have been studied by Hu et al. who obtain the same cost exponents in the regime that corresponds to γ > 2"

The comparison here should be further discussed it does not make the incremental contribution sufficiently explicit. As a reviewer, it is hard to assess the overall state of the art.

The contribution is summarized in the sentence:

In both, the oracle exposes a single accuracy knob. What is new here is an oracle with two, a bias and a variance bought at unrelated exponents, and the consequence that the iteration count leaves the bill altogether

This sentence, which summarizes the main contribution was very unclear. If this is the technical novelty then the introduction should be explain why this allows the acclaimed result, how it leads to reduction in total computational cost, and brief discussion on how it is achieved and what are the obstacles.

I think the overall direction and research question is interesting, so I am not pushing for rejection, but overall the lack of clarify makes it hard to assess the result within the existing literature and I think the author will do a great service to the paper if he made major revision in the exposition.

Critical strengths

Overall the formal results are interesting. The message that optimization is at the cost of a single gradient calculation is both surprising and conceptually smart.

Critical weaknesses

The paper is not presented well. Misses context, and is hardly accessible to a reader whos is not an expert in the field.

Questions for authors

I don't have special questions. I think the writing doesn't meet the standard.

1 comment

We thank the reviewer for the insightful questions and remarks.

Regarding clarity of the introduction, we have added more explanation for the motivation of this paper, as well as an explanation of the "two knobs" technique. We have also added some clarification throughout the text, thanks to your and the other reviewer's remarks. Please tell us if there is any other aspect that should be clarified.

We have also discovered new things that have completely changed the way we compare our results to the work of (Hu et al. 2024): The first proposed algorithm (V-MLMC) is inadapted to our setting and yields suboptimal rates, and while comparing our work we have identified an error in the proofs for the three other algorithms which results in incorrect rates. We have added a more thorough comparison in Appendix A, but since the rates and proofs are incorrect we do not discuss them too much in the main.

Reviewer_rXrAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies convex optimization when the gradient is available only through a hierarchy of deterministic approximations AkA_k with error 2−k2^{-k} and cost (c 2k)γ(c\,2^{k})^\gamma. A randomized truncated telescope over the levels gives an oracle with bias δ\delta and variance σ2\sigma^2 at cost cγδ2−γσ−2c^\gamma\delta^{2-\gamma}\sigma^{-2} for γ>2\gamma>2 (Proposition 3). Gradient descent with this oracle reaches loss ε\varepsilon at cost (cd0/ε)γ(cd_0/\varepsilon)^\gamma for convex losses and (c/με)γ(c/\sqrt{\mu\varepsilon})^\gamma up to a logarithm for strongly convex ones. Neither bound depends on the step size (Theorem 4). Theorem 7 gives a lower bound with the same exponent. Propositions 9 and 10 state that acceleration does not help for γ>2\gamma>2. The validation is a least-squares problem with truncated features at γ=3\gamma=3.

Critical strengths

S1. A clear and complete picture of the cost-of-accuracy setting. Table 1 puts the deterministic, the randomized and the accelerated methods side by side in all three regimes γ<2\gamma<2, γ=2\gamma=2 and γ>2\gamma>2. It also shows how the limits behave at γ→0\gamma\to0 and γ→2\gamma\to2. The main observation is simple and useful. For γ>2\gamma>2 the step size cancels between T∝η−1T\propto\eta^{-1} and σ−2∝η\sigma^{-2}\propto\eta, so the smoothness constant leaves the bound and a smaller step costs nothing (Corollary 5). The strongly convex bound also loses the factor κ\kappa that the fixed-level method pays (Remark 21). The paper gives intuition for each regime, which makes the threshold γ=2\gamma=2 easy to understand.

S2. A lower bound and a careful, honest presentation. Theorem 7 is, as far as I know, the first lower bound in this oracle model. "Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles" (Hu, Wang, Chen, He) leave the limits of the regime where cost grows faster than variance decays as an open question. The two-instance argument is simple and correct, and it also covers accelerated methods. The paper is open about its limits. It says that a Krylov method beats both curves in Section 4 and that the bound is far above the measured compute (Appendix E.4.2). The appendix checks the assumptions it relies on, such as the unbiasedness of the estimator, the flop accounting and the measured rate of the hierarchy.

Critical weaknesses

W1. Most of the results for γ>2\gamma>2 are already known. The introduction says that Hu et al. "obtain the same cost exponents". Their Theorem 2, for cost rate cc above variance rate bb, gives total cost ε−1−(c−b)/a\varepsilon^{-1-(c-b)/a} for strongly convex and ε−2−(c−b)/a\varepsilon^{-2-(c-b)/a} for convex objectives. A deterministic hierarchy has b=2b=2 and c=γc=\gamma. Their Proposition 1 gives the same error bound under a squared gradient bias 4−k4^{-k} and the PL condition. With a=2a=2 this yields ε−γ/2\varepsilon^{-\gamma/2}, the strongly convex row of Theorem 4 for γ>2\gamma>2. Their convex rate with a=1a=1 is ε−γ\varepsilon^{-\gamma}, the convex row, although their assumption bounds loss values and not gradients. The same trade-off appears in the earlier "On the Bias-Variance-Cost Tradeoff of Stochastic Optimization" (Hu, Chen, He). Proposition 3 is the MLMC complexity theorem of Giles with separate bias and variance budgets. Assumption 1 and the estimator match "Polynomial Speedup in Diffusion Models with the Multilevel Euler-Maruyama Method" (Jacot), including the choice Akmin⁡−1=0A_{k_{\min}-1}=0. The proof of Theorem 4 is a standard biased-SGD step (Lemma 14) multiplied by the per-call cost. What is new is the convex bound under a gradient-error assumption, which Hu et al. do not cover (their Remark 7), the rates for γ<2\gamma<2, and Theorem 7. This is a modest addition for an ICLR paper. Appendix A should give the explicit parameter map.

W2. The claims that go beyond prior work are not supported as stated.

(a) Propositions 9 and 10 turn the gradient error into a (2δD,β)(2\delta D,\beta)-oracle (Lemma 32(a)). This gives an accumulated error Tδd0T\delta d_0 and forces δ∼ε3/2\delta\sim\varepsilon^{3/2}. "Accelerated gradient methods with absolute and relative noise in the gradient" (Vasin, Gasnikov, Dvurechensky, Spokoiny) note that this reduction is pessimistic. Their bound R~δ+kδ2/(2L)\tilde R\delta+k\delta^2/(2L), eq. (14), allows δ=O(ε)\delta=O(\varepsilon) when the iterates stay at distance R~=O(R)\tilde R=O(R). By my calculation, accelerated SGD with the same oracle then costs (R/ε)γ(R/\varepsilon)^\gamma, so acceleration is neutral rather than "strictly loses". Accelerated GD at a fixed level then costs ε−(γ+1/2)\varepsilon^{-(\gamma+1/2)}. Randomization buys ε1/2\varepsilon^{1/2} over it, not "a full power of ε\varepsilon". The paper has no lower bound for deterministic methods, and the Θ(ε−(γ+1))\Theta(\varepsilon^{-(\gamma+1)}) in Section 3.1 is an upper bound for one method.

(b) In Appendix B.1.1 the choice Akmin⁡−1=0A_{k_{\min}-1}=0 with ∥Ak−f∥∞≤2−k\Vert A_k-f\Vert_\infty\le2^{-k} forces sup⁡∥∇L∥≲c\sup\Vert\nabla L\Vert\lesssim c. This is incompatible with μ\mu-strong convexity on Rd\mathbb R^d. The hard pair in equation 19 has an unbounded gradient λv±δ\lambda v\pm\delta, so Theorem 4, as proved, does not apply to the instances on which Theorem 7 is attained. Proposition 11 holds only on a ball, the method has no projection, and Lemma 15 controls the iterates only in mean square. With the parameters of Theorem 4(a), one draw of the top level can move the iterate by up to about 0.4d00.4d_0 at γ=3\gamma=3. Appendix E.3.1 truncates diverged runs. A bounded domain with projection would likely repair this, but the theorems must be restated.

(c) The experiment does not test the theory. Remark 34 states γmin⁡(∇L)=0\gamma_{\min}(\nabla L)=0. The exact gradient has a fixed cost, and Section 4 notes that a Krylov method beats both curves. The fitted slopes, 2.76 and 3.44, lie below the upper bounds 3 and 4, so they cannot confirm them. The ladder has only four levels.

Questions for authors

Q1. Regarding W1, which statements of Theorem 4 for γ>2\gamma>2 do not follow from Theorem 2 and Proposition 1 of Hu et al. with b=2b=2 and c=γc=\gamma? What in the analysis needed new tools?

Q2. Regarding W2(a), do Propositions 9 and 10 still hold with the bound of Vasin et al.? Can you show that deterministic methods need more than ε−γ\varepsilon^{-\gamma}?

Q3. Regarding W2(b), can Theorems 4 and 7 be restated on a bounded domain with projection, with Assumption 1 required only there?

Q4. Regarding W2(c), a suggestion that would raise my score: one small experiment where γ>2\gamma>2 is genuine. The introduction lists PDE discretizations and nested simulation, so PDE-constrained inversion with mesh refinement would do. The comparison should include the RT-MLMC method of Hu et al. and the deterministic schedule of "Optimal inexactness schedules for tunable oracle based methods" (Van Dessel, Glineur).

Q5. Clarification. The bounds hold "up to a factor depending only on γ\gamma", but this factor is Λγ=16γ−1Cγ\Lambda_\gamma=16^{\gamma-1}C_\gamma against 348−γ\frac34 8^{-\gamma} in Theorem 7. The gap is about 2⋅1072\cdot10^{7} at γ=3\gamma=3 and 6⋅10376\cdot10^{37} at γ=18\gamma=18. How should the reader interpret the value γ≈18\gamma\approx18 for language models in Remark 2? As far as I can see, it comes from a test-error scaling exponent, not from a measured gradient approximation error.

2 comments

We thank the reviewer for their detailed questions and remarks. We have made changes to address the issues raised:

(W1) While trying to apply the algorithms of (Hu et al. 2024) to our setting, we realized that (1) their V-MLMC algorithm collapses to a single level estimator in our setting, yielding suboptimal rates (2) applying their other algorithms (RT/RU/RR)-MLMC appears to obtain better rate than ours (in contradiction with our Theorem 8!), this is because there is an error in the proof of Lemma 6 of (Hu et al. 2024) at page 43. In this new light our paper is the first to prove the correct rates, and we will soon notify the authors. This error explains why we struggled to map our result onto theirs. For a detailed description of the mapping and the mistake in (Hu et al. 2024), you can check our new discussion in Appendix A.

The (Jacot 2026) paper is much closer in setting, though it makes no convexity assumption and only studies the rate of convergence to the continuous limit, not the convergence to a minimum. If one were to adapt the proofs of (Jacot 2026) to our setting directly, we would obtain similar rates for the strictly convex case, but applying it to the convex case is less obvious.

(W2) (a) You are right and we thank you for the pointer to Vasin et al. Our Propositions 9-10 used the (2δD,β)(2\delta D,\beta)-oracle reduction which gives a bias accumulation of Tδd0T\delta d_0. This was indeed pessimistic and so our conclusion that acceleration strictly loses for γ>2\gamma>2 was wrong. We redid the analysis in Appendix D.

Lemma 34 now bounds an accelerated scheme, under a biased and noisy oracle: E[L(yT)−L∗]≤d022AT+2δd0+(δ2+σ2) η(2T+1)3,\mathbb E[\mathscr{L} (y_T)-\mathscr L^\ast]\le\frac{d_0^2}{2A_T}+2\delta d_0+(\delta^2+\sigma^2)\,\frac{\eta(2T+1)}3, using the bias term of eq.(14) of Vasin et al., which does not grow with TT, and the noise term of Lan (2012). We prove it ourselves, by a simple adaptation of these works, as Theorem 6.3 from Vasin et al. does not separate the bias from the noise (whereas our cost model prices them differently). This confirms your derivation: above the threshold γ>2\gamma>2 the accelerated method costs 4Λγ(cd0ε)γ4\Lambda_{\gamma}(\frac{cd_0}{\varepsilon})^{\gamma} (Proposition 10). Acceleration is therefore neutral in the exponent above this threshold, not worse: both methods attain the lower bound of Theorem 8. Below the threshold the result is unchanged and acceleration still helps strictly. Table 1 was revised to include fixed-level accelerated descent, at O(ε−(γ+1/2))O(\varepsilon^{-(\gamma+1/2)}) and the abstract states the gain accordingly. As for the second part of Q2, we cannot show that deterministic methods need more than ε−γ\varepsilon^{-\gamma}. Theorem 8 still binds every algorithm at ε−γ\varepsilon^{-\gamma} while the best deterministic method we know, with acceleration, costs ε−(γ+12)\varepsilon^{-(\gamma+\frac{1}{2})} and whether this gap can be closed remains open. We changed the Θ(ε−(γ+1))\Theta(\varepsilon^{-(\gamma+1)}) of Section 3.1 to an OO to reflect this.

(b) You are right, using Akmin⁡−1=0A_{k_{\min-1}}=0 doesn't hold under Assumption 1 on Rd\mathbb{R}^d, as a strongly convex gradient is unbounded and no finite level can approximate it uniformly by 00 (as your example states). Our revision therefore poses Assumption 1 on a bounded, closed, convex set Ω\Omega of Rd\mathbb{R}^d containing both y0y_0 and a minimizer y∗y^\ast. We now run projected inexact gradient descent. To answer Q1 precisely, the third condition (sup⁡Ω∥f∥≤c\sup_\Omega\|f\|\le c) is the assumption. Since 2−(kmin⁡−1)≥c2^{-(k_{\min}-1)}\ge c, it says that 00 approximates ff on Ω\Omega within 2−(kmin⁡−1)2^{-(k_{\min}-1)}, at zero cost (Appendix B1.1). We adapt all subsequent theorems and results to account for projected gradient descent: each are restated on Ω\Omega and hold using the non-expansiveness of the projection. The projection is not an oracle call: like the vector operations of the iteration, it is free in the oracle model and, on a ball (the natural choice for Ω\Omega), it is a rescaling in O(d)O(d) operations. In the experiment, it is charged like everything else, a norm test at every step and a rescaling on the steps where it acts, and it stays below 0.1%0.1\% of the compute.

(W2) (c) We agree with the scope you describe and the revision states it in Remark 36 (formerly 34). The instance presented here is a mere measuring device for the scaling law of a given family, not an intrinsically expensive gradient and what it establishes is equally narrow. The hierarchy obeys the scaling law (γ=2.963±0.007\gamma=2.963\pm0.007 against the closed form 33), and the multilevel method has a strictly smaller cost exponent than the fixed level on all ten seeds and in both truncations (0.64±0.080.64\pm0.08 and 1.25±0.051.25\pm0.05). Slopes below the upper bounds cannot confirm them exactly, as you point out, but we only claimed the ordering.

Our Section 4 indeed indicates that a Krylov method beats both curves on this instance. This comes from least squares itself: truncation restricts the problem to a subspace, so the loss gap of a level is the square of its gradient bias, and a quadratic restricted to a subspace is exactly what conjugate gradients solve best. This does not contradict our lower bound as Theorem 8 is a worst-case statement and least squares is not a worst case. However, a Krylov method cannot avoid the truncation: with the exact gradient, each iteration is a product with the full design, 4mn≈1.1⋅1094mn\approx1.1\cdot10^{9} flops here, which is more than the cost of our whole multi-level run with the exact residual (Table 3). That cost grows with the dimension, whereas ours depends only on the rate of the hierarchy. Without this structure things are different, as a Krylov method needs a linear system. Hence, for a non-quadratic loss, the relevant competitor is fixed-level accelerated descent, which costs ε−(γ+1/2)\varepsilon^{-(\gamma+1/2)} against our ε−γ\varepsilon^{-\gamma} (Table 1). The same holds on a quadratic whose hierarchy is not variational, where a bias δ\delta costs δd0\delta d_0 in loss, as on the hard instances of Theorem 8: in the worst case, a fixed-level Krylov method then does no better than accelerated descent. And under strong convexity, a fixed-level method pays the condition number on top, κ\kappa for gradient descent and κ\sqrt\kappa for Krylov in high dimension, while Corollary 7 pays neither κ\kappa nor a logarithm. These are comparisons of upper bounds, and a hierarchy without the variational structure of least squares is what the next experiment should test.

(A PDE experiment was not feasible reliably within the discussion period, but we agree it is the subsequent test this theory calls for. We will try to work on more significant experiments for the final deadline, but we cannot guarantee anything.) For the comparison to Van Dessel and Glineur, the fixed-level baseline run already uses their optimal schedule for gradient descent. Because we average, every step has the same impact coefficient and they state it means their optimal schedule reduces to the constant one. Their non-constant schedules concern accelerated methods and it gains a constant factor, not an exponent. The RT-MLMC estimator should yield essentially the same rate as ours (since we are in the HTMC regime).

(Q5) The two statements are consistent: the theorem only certifies the exponent, not the constant, so the gap you compute is the price of that. We also corrected a constant in Theorem 8 (its hard instances have prefactor 2c2c), which raises your 2⋅1072\cdot10^7 to about 1.5⋅1081.5\cdot10^8 at γ=3\gamma=3.

You are correct that the γ≈18\gamma\approx 18 estimate is for evaluating the outputs of the network, not its gradient. It seems natural to expect the gradient to be at least as costly to approximate as the function itself, therefore leading to the same or larger exponent γ\gamma. We hope to extend this theory to the training of DNNs in subsequent work, and measure these rates more precisely.

Reviewer_xqMxOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2(−1)
Soundness
2
Read review
Paper summary

This paper studies convex optimization with a hierarchy of deterministic gradient approximations whose evaluation cost grows as δ−γ\delta^{-\gamma}, where δ\delta is the approximation error. It constructs a randomized multilevel estimator intended to provide separately tunable bias and variance. In the regime γ>2\gamma>2, the proposed oracle has expected cost proportional to δ2−γσ−2\delta^{2-\gamma}\sigma^{-2}. Combining this cost model with inexact stochastic gradient descent yields an O((cd0/ε)γ)O((cd_0/\varepsilon)^\gamma) optimization cost in the convex case and an O~((c/με)γ)\widetilde O((c/\sqrt{\mu\varepsilon})^\gamma) cost under strong convexity.

In addition, the paper also presents an oracle lower bound, a time-varying accuracy schedule intended to remove the logarithmic factor in the strongly convex setting, and an analysis comparing accelerated and unaccelerated methods. It provides a synthetic least-squares experiment with truncated features.

Critical strengths

a) The problem is meaningful and the main cost cancellation is interesting. When gradient accuracy is expensive, iteration complexity alone can be misleading. The paper clearly explains how tolerating greater variance may offset a larger number of iterations.

b) The SGD analysis contains some technical novelty. Conditional on the advertised oracle guarantees, the one-step recursion, convex bias budget, and strongly convex noise-floor argument are largely sound.

c) I found the lower-bound argument interesting. The indistinguishability construction captures why a sufficiently accurate query is necessary in the explicitly priced hierarchy model.

Critical weaknesses

a) Appendix B.1.1 takes Akmin⁡−1=0A_{k_{\min}-1}=0 because its evaluation cost is at most one. This does not follow from Assumption 1. This may be problematic in the stated unconstrained setting. For example, an exact hierarchy for L(y)=y2/2L(y)=y^2/2 satisfies the approximation upper bounds, but replacing its coarse approximation by 0 creates an unbounded first increment. More generally, a globally strongly convex objective has an unbounded gradient and cannot admit a uniformly accurate 0 approximation at a finite level.

The authors may need either a bounded domain or to add Akmin⁡−1A_{k_{\min}-1} to the analysis.

b) In Appendix B.3, the Bernoulli probabilities scale as pk=O(η)p_k=O(\eta), while a selected increment produces a jump of size O(η/pk)=O(1)O(\eta/p_k)=O(1). This does not justify a continuous-martingale limit. A jump-process construction and convergence argument are needed.

c) In the last lines of Lemma 27, the authors define Ak′(z)A'_k(z) as the output of an optimization algorithm and assert ∣Ak′(z)−∇L∗(z)∣≤2−k|A'_k(z)-\nabla L^*(z)|\le 2^{-k} for every zz. However, the optimization algorithm provides only an expected-loss guarantee, which implies an expected squared-distance bound, not a sure uniform approximation guarantee.

The authors acknowledge this distinction immediately after Proposition 28 and suggest that logarithmically many repetitions and a union bound over the optimization horizon suffice to recover a sure guarantee. This argument is not established: controlling finitely many stochastic evaluations along an optimization trajectory is different from constructing a single deterministic approximation with uniformly bounded error over the input domain.

Questions for authors
  1. What precise assumption will allow replacing Akmin⁡−1A_{k_{\min}-1} by zero while retaining its approximation guarantee?

  2. Can Proposition 6 be proved for the actual jump-process limit? Is there a finite-step version achieving the claimed cost without a logarithmic factor?

  3. How is the randomized expected guarantee in Lemma 27 converted into a deterministic uniform approximation with the same circuit-complexity exponent?

  4. Although the authors included discussion of (Hu et al., 2024), I am not sure what the advantages are over their oracle.

3 comments

We thank the reviewer for their detailed questions and remarks. We have made changes to address the issues raised:

(a) You are right, using Akmin⁡−1=0A_{k_{\min-1}}=0 doesn't hold under Assumption 1 on Rd\mathbb{R}^d, as a strongly convex gradient is unbounded and no finite level can approximate it uniformly by 00 (as your example states). Our revision therefore poses Assumption 1 on a bounded, closed, convex set Ω\Omega of Rd\mathbb{R}^d containing both y0y_0 and a minimizer y∗y^\ast. We now run projected inexact gradient descent. To answer Q1 precisely, the third condition (sup⁡Ω∥f∥≤c\sup_\Omega\|f\|\le c) is the assumption. Since 2−(kmin⁡−1)≥c2^{-(k_{\min}-1)}\ge c, it says that 00 approximates ff on Ω\Omega within 2−(kmin⁡−1)2^{-(k_{\min}-1)}, at zero cost (Appendix B1.1). We adapt all subsequent theorems and results to account for projected gradient descent: each are restated on Ω\Omega and hold using the non-expansiveness of the projection. The projection is not an oracle call: like the vector operations of the iteration, it is free in the oracle model and, on a ball (the natural choice for Ω\Omega), it is a rescaling in O(d)O(d) operations. In the experiment it is charged like everything else, a norm test at every step and a rescaling on the steps where it acts, and it stays below 0.1%0.1\% of the compute.

(b) You are right and this was an imprecision in our submission which described the η→0\eta\to0 limit as a flow and treated the noise in Appendix B.3 as a continuous martingale, whereas a selected increment moves the iterate by Dk/λkD_k/\lambda_k, a jump that does not shrink with η\eta. This argument wasn't necessary and our revision now works with the correct object, a multilevel Poisson jump process, which jumps at the times of independent Poisson processes of intensities λk(t)\lambda_k(t) to ΠΩ(y−Dk(y)/λk(t))\Pi_\Omega\big(y-D_k(y)/\lambda_k(t)\big). We analyze this process directly, without taking any limit, and Dynkin's formula applied to ∥yt−y∗∥2\|y_t-y^\ast\|^2 gives the same master inequality as before so Proposition 6 can keep its conclusion. For your other question, we provide a finite-step version without logarithm in Corollary 7: restarting Theorem 4a in stages that halve the square distance to the optimum gives E[Cost]≤8γ/21−2−γ/2 Λγ(c/με)γ\mathbb E[\mathrm{Cost}]\le\frac{8^{\gamma/2}}{1-2^{-\gamma/2}}\,\Lambda_\gamma\big(c/\sqrt{\mu\varepsilon}\big)^\gamma which matches the lower bound from Theorem 8, up to a factor depending on γ\gamma only.

(c) You are right that our description of how to upgrade our random oracle into a deterministic one using repetition was vague. Looking at this argument again, we realized that such an upgrade was unnecessary: we only need the deterministic oracles AkA_k to build the weakly biased oracle f~δ,σ\tilde{f}_{\delta,\sigma} using Proposition 3, but the proof of Proposition 3 can handle random oracles Ak′A'_k (whose compute and squared error is bounded in expectation) with almost no changes. We can therefore directly upgrade our random oracle A\'_k into a weakly biased oracle f~δ,σ\tilde{f}_{\delta,\sigma}, there is no need to first obtain a deterministic oracle AkA_k.

(Question 4) While trying to apply the algorithms of (Hu et al. 2024) to our setting, we realized that (1) their V-MLMC algorithm collapses to a single level estimator in our setting, yielding suboptimal rates; (2) applying their other algorithms (RT/RU/RR)-MLMC appears to obtain better rate than ours (in contradiction with our Theorem 8!). This is because there is an error in the proof of Lemma 6 of (Hu et al. 2024) at page 43. In this new light our paper is the first to prove the correct rates, and we will soon notify the authors. This error explains why we struggled to map our result onto theirs. For a detailed description of the mapping and the mistake in (Hu et al. 2024), you can check our new discussion in Appendix A.

Thank you to the authors for the detailed response and revisions. I think the changes in points (a) and (b) have improved the rigor of the paper.

However, with the bounded-domain assumption, Lemma 27 only seems to provide a local guarantee for approximating the conjugate gradient. I am not sure whether this will affect its use of Lemma 28 and Proposition 29. More importantly, the revised argument allows the approximations in Lemma 28 to be randomized, with their squared errors and computational costs bounded in expectation. But γmin⁡\gamma_{\min} is still defined in terms of deterministic circuit complexity with uniform approximation guarantees. I do not see how the current proof bridges this gap.

Overall, I believe the main theorems are improved. There is also some room for improvement in writing. I increased my rating to 2.

Thank you for your response and for updating your rating.

Regarding Lemma 27 you are right that this create issues for this specific argument. We have now completely reworked this section and changed the proofs:

  • We put the main emphasis is on how the duality preserves the computational rate γ\gamma, which is the main interest of this section anyway (the fact that it implies/suggests the lower bound is nice, but we already have proven the lower bound in the previous section).
  • The cleanest way to prove this duality is to remove the projection, and add an extra assumption that AkminA_{k_min} can be chosen as Akmin(x)=rxA_{k_min}(x)=rx for some μ≤r≤β\mu \leq r \leq \beta. We also only consider random oracles to avoid needing to derandomize.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.