- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies convex optimization over an ball of radius when regularity is measured in the Euclidean norm. Its main result is a first-order minimax error of for convex functions with Euclidean -Lipschitz gradients, improving the guarantee of standard accelerated methods. The upper bound holds in every dimension; the deterministic and randomized lower bounds require and , respectively. Queries return values and gradients, and internal computations are free in this oracle model. The method replaces the prox step of an accelerated level scheme with an approximate Steiner point of the localization polytope. A short-path bound for these centers supplies the additional factor of . The paper extends the framework to nonsmooth, H"older, higher-order, and monotone-operator problems, and separately extends curvature-learning acceleration for quadratics to balls with . Synthetic experiments show geometric stability and selected reductions in oracle calls, with substantial computational overhead.
Critical strengths
-
A compelling mechanism for faster oracle convergence. The combination of short Steiner paths and an accelerated level method is conceptually clean and consequential.
-
Lower bounds and extensions add value beyond the smooth upper bound. The randomized lower bound in dimension proportional to the query budget is particularly significant. Sampling the hard function before interaction, using exponential shifts and controlling the information exposed by smoothing, addresses a challenge that a deterministic resisting oracle alone cannot resolve.
Critical weaknesses
-
The headline novelty needs clearer qualification. Appendix J acknowledges substantial overlap with concurrent work: Mart'inez-Rubio et al., \emph{Near-Optimal Acceleration for Smooth Nondual Convex First-Order Oracle Optimization} (\url{https://arxiv.org/abs/2609.21880}), claim the same smooth and H"older exponents at in a broader norm setting. Mart'inez-Rubio and Guzm'an (\url{https://arxiv.org/abs/2609.20701}) obtain the nonsmooth rate through stable movement and deep cuts. Ouyang (\url{https://arxiv.org/abs/2609.10314}) already establishes the quadratic cubic upper bound. The introduction should make the remaining distinctive contribution of this submission much more explicit. This does affect the significance assessment of the key result.
-
The empirical claims exceed the evidence for the proved algorithms. The abstract's statement that experiments confirm behavior is too broad. The general level method has a reported slope near ; the near-cubic observation concerns CLA on a selected quadratic family. Several experiments vary both dimension and instance with the budget, use the exact optimal level, reuse selector directions, or depart from proved parameter schedules.
Questions for authors
-
Relative to the concurrent papers discussed in Appendix J, which main statements and algorithmic ingredients are distinctive? Please distinguish a different proof of an overlapping rate from a genuinely additional guarantee, including the dimension dependence of randomized lower bounds.
-
In Appendix D.5.2, can you isolate and justify the conditional-information lemma showing that unrevealed shifts retain independent shifted-exponential laws after arbitrary adaptive global queries? This is central to my assessment of the randomized lower bound.
-
Which reported experiments satisfy the proved selector and inner-solve assumptions? Is there a guarantee for shared-direction sampling, or should those runs be explicitly designated heuristic?
-
Will the cubic empirical claim be restricted to the quadratic CLA evidence, and will polynomial internal-work claims be explicitly scoped to the algorithms for which that complexity is proved?
4 comments
Q2: Conditional information under adaptive queries.
Q2: Conditional information under adaptive queries.
Lemma D.9 in Appendix D.5.2 proves that the unrevealed shifts remain independent shifted exponentials after every adaptive query. In this paragraph, counts the random shifts and the query space is . Let , let be independent exponentials with mean , and define the Moreau envelope with parameter by
+\frac{\\|z-x\\|_2^2}{2\lambda}\right\\}.$$ The oracle returns $h_a(x)$ and $p=\nabla h_a(x)$. Its answer is equivalent to $(t,p)$, where $$p_i=\frac{(x_i-a_i-t)_+}{\lambda},\qquad t=h_a(x)-\frac{\lambda}{2}\\|p\\|_2^2.$$ If $p_i > 0$, the answer reveals $a_i=x_i-t-\lambda p_i$. If $p_i=0$, it gives the lower bound $a_i\ge x_i-t$. We prove the conditional law by induction over queries. Initially the shifts are independent and their cutoffs are $b_i=0$. Given the previous answers and the algorithm's independent random seed, the next query $x$ is fixed. On an answer with active set $J=\\{i:p_i > 0\\}$, $$t=\frac{\sum_{j\in J}(x_j-a_j)-\lambda}{|J|}$$ depends only on the active shifts. The answer determines every newly active shift, and those shifts, together with the previous answers, determine $t$ and $p$. For each still unrevealed shift, the remaining condition is the separate lower bound $a_i\ge x_i-t$. Conditioning on the answer therefore leaves a product of separately truncated exponential densities. Thus $$a_i=b_i'+E_i,\qquad b_i'=\max\\{b_i,x_i-t\\},$$ conditionally on the answers, with independent exponential $E_i$ of mean $\delta$. This also covers queries that reveal no new shift. The statement holds for almost every history and does not assume that the vector of oracle answers has a probability density. Queries may be anywhere in $\mathbb R^{n+1}$. The lemma also gives, for the parameters used in the lower bound, $$\mathbb E[\text{newly revealed shifts}\mid\text{previous answers and seed}] \le1+n(1-e^{-\lambda/\delta})\le1+n\lambda/\delta\le2.$$ To obtain this bound, write $s_i=x_i-a_i$ and $M=\max_i s_i$. Since $t\ge M-\lambda$, only coordinates with $s_i > M-\lambda$ can be newly revealed. Condition further on $M$ and its maximizing index. Each other unknown shift then has cutoff $c_i=\max\\{b_i,x_i-M\\}$ and an independent exponential residual. The maximizer accounts for at most one revelation. For each other unknown shift, the event $s_i > M-\lambda$ restricts its exponential residual to an interval of length at most $\lambda$, with probability at most $1-e^{-\lambda/\delta}$. Summing these probabilities gives the stated bound.Q3: Sampling and numerical subproblems in the experiments.
Q3: Sampling and numerical subproblems in the experiments.
Proposition C.4 requires fresh directions independent of the current set. Reusing directions makes later localization sets depend on the sample. Those runs are heuristic and have no proved convergence rate.
SP-Level and SP-Accel. The main comparisons use shared directions. The exact-level SP-Level runs are also given ; their query counts omit the level search. The doubling rule in Appendix I.2 has a query bound under the prescribed center accuracy. With reused directions, the returned error certificate remains valid, while the number of trials is controlled heuristically.
The fresh-sample, exact-level SP-Level runs in Table 8 use independent directions. With center estimates, failure probability and , the sufficient rule requires 1257, 4126 and 14001 directions per center for , respectively. Only meets that rule. This sample count assumes exact linear-program solutions. The experiments use floating-point solves; Proposition C.5 specifies a separate finite-precision implementation.
SP-Cut, SP-VI and SP-Prox. These runs also reuse directions. SP-Cut and SP-VI choose cut depths from their computed error certificates rather than the proved schedule. Their certificates still bound the error or gap of the returned mixture, up to numerical error in the linear programs. The sampling and cut-depth rules are heuristic. SP-Prox also uses fewer samples than prescribed; its query counts include all inner gradient calls. The Steiner-path experiments measure center movement along prescribed chains of sets.
Quadratic methods. Both CLA and CLA(c.p.) stop their model solves using an objective duality gap, a bound on suboptimality of the model value. Definition H.3 instead requires a certified bound on , where is the approximate model minimizer, a model subgradient at , and the feasible set. This is the largest feasible decrease predicted by that subgradient. The experiments check the objective gap; Proposition H.4 requires this subgradient bound. The label (c.p.) identifies the prescribed parameter values.
Q4: Empirical rates and internal work.
Q4: Empirical rates and internal work.
Yes. The near-cubic empirical claim is restricted to practical CLA on the quadratic-chain family , with dimension and minimizer . The error decreases by a factor of about between budgets 400 and 800, with local slope about . These measurements compare a family whose instance and dimension change with the budget. The slope near is from SP-Level with the exact optimal level. Complete SP-Accel stays at its initial objective in the sample-size experiment discussed in Appendix I.8.3.
The polynomial computation guarantee applies to the smooth first-order implementation with fresh independent samples. Proposition C.4 bounds the number of linear programs, and Proposition C.5 gives an implementation in finite precision under its stated assumptions on the oracle and input representation. For higher-order model searches and certified quadratic inner solves, the proofs establish finite termination, without a polynomial bound on arithmetic work.
Q1: Concurrent work and contributions.
Thank you for your review and questions.
Q1: Concurrent work and contributions.
Our submission was almost simultaneous with the Martínez-Rubio preprints. Their nonsmooth papers appeared on 17 September 2026 and the smooth paper on 18 September, around the 18 September abstract deadline and before the 25 September full-paper deadline. Our accelerated level method, higher-order methods and lower-bound arguments were complete before we learned of these papers. We developed them independently: the proofs of our rates and lower bounds do not use their results or constructions. We discussed these preprints in Appendix J of the original submission.
The smooth and Hölder exponents on an ℓ1 ball with Euclidean regularity coincide with those in Martínez-Rubio et al.'s Near-Optimal Acceleration. The nonsmooth rate, Steiner points and cuts based on a prescribed decrease in a linear model also appear in Stable Movement by Martínez-Rubio and Guzmán. Their first-order results cover more norm pairs.
Our accelerated level method makes one value-and-gradient query per trial. Its proof combines an inequality for accepted steps with a bound on center movement. For target error ε, put Q=LR2/ε≥2, D=1+log(2n) and H=1+log(2+QD). Here L is the Euclidean smoothness constant, R the ball radius and n the dimension. The sufficient query budgets for the complete methods are
T_{\mathrm{concurrent}}=O(1+Q^{1/3}D^{1/3}H^{7/3}).$$ We derive the second bound from their estimates for the individual steps, using the same order of movement bound and choosing the phase lengths accordingly. This comparison fixes the failure probability and uses the range of their main theorem, where the query budget is at most $n$. The two additional logarithms come from the bundle solve and the bisection for the envelope function in their Proposition 13. Our direct update avoids these nested queries. The gain is in the sufficient query bound. Dimension padding gives the concurrent smooth exponent for every budget, and their Theorem 12 also states an all-budget rate. Ordinary restart is a standard adaptation. ***Higher-order oracles.*** For an oracle returning derivatives through order $k\ge2$, Appendix E.3 gives error $$\widetilde O_k\\!\left(L_{k,\nu}R^{k+\nu}/N^{2(k+\nu)-1}\right), \qquad 0\le\nu\le1,$$ where $L_{k,\nu}$ is the $\nu$-Hölder constant of the $k$th derivative. The notation hides logarithmic factors and constants depending on $k$; a Lipschitz Hessian gives $\widetilde O(L_{2,1}R^3/N^5)$. We bound the largest feasible decrease predicted by the Taylor-model gradient. Appendix D gives the corresponding higher-order lower-bound constructions. ***Operators and strong convexity.*** Appendix G treats monotone variational inequalities, convex–concave saddle-point problems and strongly monotone operators. Appendix F characterizes deterministic strongly convex complexity in terms of $\Lambda=L/\mu_1-n\ge8$, where $\mu_1$ is the strong convexity constant in $\ell_1$. ***Randomized lower bound.*** Appendix D proves the smooth lower bound for arbitrary adaptive first-order queries, including queries outside the feasible set, in dimension $n\ge32N+1$. The hard function is sampled before the interaction. The proof controls the information revealed by each query, as explained in Q2. ***Quadratics.*** Appendix H extends Ouyang's method from $p=1$ to $1 < p < 2$ using a regularizer that is quadratic near zero and has a $p$-power branch outside that region. The cubic $p=1$ result is due to Ouyang's *An $O(1/T^3)$ Algorithm for Minimizing Convex Quadratic Functions over the $L_1$ Ball*.