acceptodds
Under review as a conference paper at ICLR 2027

The Complexity of Convex Optimization with Mismatched Geometry

Abstract

Optimal first-order methods on non-Euclidean domains such as the ball pair the prox-function with the norm in which smoothness is measured. When the gradient is -Lipschitz in the Euclidean norm only, the accelerated method with a Euclidean prox-setup reduces the functional gap to after first-order queries (an entropic prox-setup replaces by the constant , at the cost of a factor and with the same exponent). The lower bound of Guzmán and Nemirovski is of order , and whether the upper bound can be brought down to that order is a question of A. S. Nemirovski. We show that for this mismatched problem the minimax value of the gap is of order up to logarithmic factors, for deterministic and for randomized methods alike, and already in dimension proportional to the number of queries. The upper bound is attained by a Steiner-point level method: every supporting hyperplane seen so far is kept as a level cut, and the next query is made near the Steiner point of the resulting localization polytope. The analysis rests on a single geometric fact: along nested subsets of the ball the Steiner points travel a distance that is polylogarithmic in the dimension, in contrast to for the Euclidean ball. All queries stay feasible, and a randomized selector keeps the internal work polynomial. The same geometry yields optimal rates for nonsmooth objectives, Hölder gradients, higher-order oracles and Lipschitz monotone operators, the last with a matching deterministic lower bound. For convex quadratics, a curvature-learning method attains the optimal rate on every ball with and without logarithmic loss. Experiments confirm the predicted behaviour on objectives that are hard for Euclidean methods.

Primary area:
optimization
Keywords:
Convex Optimization, First-Order Methods, Acceleration, Oracle Complexity Lower Bounds

Reviews

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

The paper studies convex optimization over an ℓ1\ell_1 ball of radius RR when regularity is measured in the Euclidean norm. Its main result is a first-order minimax error of Θ~(LR2/N3)\widetilde\Theta(LR^2/N^3) for convex functions with Euclidean LL-Lipschitz gradients, improving the N−2N^{-2} guarantee of standard accelerated methods. The upper bound holds in every dimension; the deterministic and randomized lower bounds require n≥N+1n\geq N+1 and n≥32N+1n\geq32N+1, 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 N−1N^{-1}. The paper extends the framework to nonsmooth, H"older, higher-order, and monotone-operator problems, and separately extends curvature-learning acceleration for quadratics to ℓp\ell_p balls with 1≤p<21\leq p<2. 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 ℓp/ℓq\ell_p/\ell_q Nondual Convex First-Order Oracle Optimization} (\url{https://arxiv.org/abs/2609.21880}), claim the same smooth and H"older exponents at (p,q)=(1,2)(p,q)=(1,2) 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 ℓ1\ell_1 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 N−3N^{-3} behavior is too broad. The general level method has a reported slope near −2.3-2.3; 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
AuthorsOpenReview ↗

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\ell_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 ε\varepsilon, put Q=LR2/ε≥2Q=LR^2/\varepsilon\ge2, D=1+log⁡(2n)D=1+\log(2n) and H=1+log⁡(2+QD)H=1+\log(2+QD). Here LL is the Euclidean smoothness constant, RR the ball radius and nn 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*.
AuthorsOpenReview ↗

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, nn counts the random shifts and the query space is Rn+1\mathbb R^{n+1}. Let a0=0a_0=0, let a1,…,ana_1,\ldots,a_n be independent exponentials with mean δ\delta, and define the Moreau envelope with parameter λ>0\lambda > 0 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.
AuthorsOpenReview ↗

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 f⋆f^\star; 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 N+1N+1 center estimates, failure probability 0.10.1 and n=2N+1n=2N+1, the sufficient rule requires 1257, 4126 and 14001 directions per center for N=16,32,64N=16,32,64, respectively. Only m=4096,N=16m=4096,N=16 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 max⁡u∈K⟨g,x−u⟩\max_{u\in K}\langle g,x-u\rangle, where xx is the approximate model minimizer, gg a model subgradient at xx, and KK 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.

AuthorsOpenReview ↗

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 HN\mathcal H_N, with dimension n=2N+1n=2N+1 and minimizer 0.9e10.9e_1. The error decreases by a factor of about 8.78.7 between budgets 400 and 800, with local slope about −3.1-3.1. These measurements compare a family whose instance and dimension change with the budget. The slope near −2.3-2.3 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.

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

The paper studies convex optimization over an ℓ1\ell_1 ball when smoothness is measured in the Euclidean norm. Its principal result is a first-order minimax error of Θ~(LR2/N3)\widetilde{\Theta}(LR^2/N^3). Theorem 1 combines an upper bound attained using feasible queries with deterministic and randomized lower bounds in dimensions proportional to the query budget. The proposed algorithm combines an accelerated level method with approximate Steiner points of nested localization polytopes. A bound on the centers’ total movement controls their accumulated squared displacements, yielding the additional factor 1/N1/N relative to standard accelerated guarantees. The paper extends this construction to nonsmooth and Hölder objectives, higher-order oracles, and monotone variational inequalities. A separate curvature-learning method extends an existing quadratic result to ℓp\ell_p balls for 1≤p<21\le p<2. Experiments investigate these mechanisms on constructed optimization problems.

Critical strengths
  1. The paper addresses a significant problem and develops substantial theoretical results. The accelerated level construction provides a direct way to incorporate stable centers, with one first-order query per trial.

  2. The authors discuss implementation assumptions and report unfavorable experimental results, including substantial computational costs and configurations where the proposed methods offer little improvement.

Critical weaknesses
  1. The distinct contribution beyond concurrent work is insufficiently established in the main text. [Martínez-Rubio et al. (2026b)] already obtain the same O~(LR2/N3)\widetilde{O}(LR^2/N^3) smooth upper rate for N≤nN\le n, handle constrained minimization without knowing f⋆f^\star, and count the oracle calls required by their inner procedures. Furthermore, [Martínez-Rubio and Guzmán (2026)] explicitly use Steiner points, movement bounds, and Monte Carlo linear optimization on the ℓ1\ell_1 ball. The overlap therefore concerns both the rate and the underlying geometric mechanism.

  2. Algorithmic differences need to be connected to substantive advantages or new capabilities. SP-Level uses explicit accelerated combinations and a displacement-based acceptance test, whereas Martínez-Rubio et al. use an envelope line search with inner proximal bundle solves. Does the new construction improve logarithmic factors, computational complexity, proof simplicity, or the range of accessible extensions?

Questions for authors
  1. Can the authors provide a direct comparison with the Martínez-Rubio algorithms, identifying which results are already covered, which follow through straightforward adaptations, and which require genuinely additional arguments? In particular, what advantages does the accelerated level construction provide over the envelope-based construction?

  2. For the globally smooth class of Theorem 1, does applying the concurrent theorem to F(x,z)=f(x)F(x,z)=f(x) in dimension d=max⁡{n,N}d=\max\{n,N\} recover the same cubic exponent for all query budgets ?

  3. Can the authors clarify the status of the O(N−2)O(N^{-2}) rate for the standard methods considered on the same ℓ1\ell_1-constrained class, with relevant references? Is it their available upper guarantee, or is it known to be a tight worst-case rate for those particular algorithms?

  4. Can the authors explain why complete SP-Accel does not exhibit the claimed cubic behavior in the reported experiments ?

7 comments
AuthorsOpenReview ↗

Weaknesses 1 and 2: Concurrent work and query bounds.

Thank you for your review and questions.

Weaknesses 1 and 2: Concurrent work and query bounds.

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\ell_1 ball with Euclidean regularity coincide with those in Martínez-Rubio et al.'s Near-Optimal Acceleration. Stable Movement by Martínez-Rubio and Guzmán also uses Steiner points, their short movement, cuts that require a specified decrease in a linear model, and sampling of solutions to linear programs. Their smooth method keeps queries feasible, works without knowing the minimum value f⋆f^\star, and counts the queries made by its inner procedures. Their first-order theorems cover more norm pairs. Our accelerated level method gives a smaller explicit upper bound on the number of queries in the common setting and a direct accelerated level proof.

Number of queries. Let ε\varepsilon be the target objective error, δ\delta the failure probability, and

Q=LR2/ε≥2,D=1+log⁡(2n),H=1+log⁡(2+QD).Q=LR^2/\varepsilon\ge2,\qquad D=1+\log(2n),\qquad H=1+\log(2+QD).

Here LL is the Euclidean smoothness constant, RR the ball radius and nn the dimension. Proposition C.2 gives the complete SP-Accel bound

Tours(ε)=O(1+Q1/3D1/3H1/3).T_{\mathrm{ours}}(\varepsilon)=O(1+Q^{1/3}D^{1/3}H^{1/3}).

This includes the search for f⋆f^\star. Let N(ε)N(\varepsilon) be the number of trials prescribed for an interval of width ε\varepsilon containing f⋆f^\star. The lengths of all phases sum to at most 24N(ε)24N(\varepsilon). Thus the level search adds only a constant factor. The implementation using fresh independent samples has the same query bound; a smaller failure probability requires more linear programs, but no further evaluations of ff or its gradient.

Equation (26) of Near-Optimal Acceleration gives the sufficient budget

[1+\log(2n)+\log(2+Q)+\log(2/\delta)]^8\right).$$ For fixed $\delta$ and a query budget at most $n$, we obtain a smaller sufficient bound from their estimates by choosing the phase lengths as follows. The proof of Theorem 9, equations (27)--(28), in *Stable Movement* (v1) gives the same order of total center movement as ours: $P_m=O(R\sqrt{D\log(2m)})$ over $m$ steps. Proposition 11 in their analysis allows center error $O(R/m)$ with fresh independent samples. These errors add $O(R)$ to the total movement in a phase. Dividing the allowed failure probability among phases preserves this movement bound without further queries to $f$ or its gradient. Using this movement estimate in their smooth phase argument gives a sufficient phase length $$m_\Gamma=O(1+(Q_\Gamma D H_\Gamma)^{1/3}),\qquad Q_\Gamma=LR^2/\Gamma,\qquad H_\Gamma=1+\log(2+Q_\Gamma D),$$ where $\Gamma$ is the error level of the phase. Their Proposition 13 bounds the number of value-and-gradient queries per transition by $$O\\!\left(\log(2+AR^2/\tau)\log(2+AR^2/\eta)\right)=O(H_\Gamma^2).$$ Here $A\asymp L$ is their regularization parameter and $\tau,\eta\asymp\Gamma/m_\Gamma$ are the accuracy tolerances of the inner procedures. The two factors come from the bundle solve and the bisection for the envelope function. Summing over phases gives the sufficient bound $O(1+Q^{1/3}D^{1/3}H^{7/3})$ from their component estimates. Our direct update avoids the bundle and bisection factors. Both calculations use the same movement bound. The computational comparison, proof and extensions are given in our reply to Q1.
AuthorsOpenReview ↗

Q1: Algorithmic differences and additional guarantees.

Q1: Algorithmic differences and additional guarantees.

The smooth and Hölder exponents on the ℓ1\ell_1 ball with Euclidean regularity and the use of short Steiner paths overlap with the concurrent work. The full query comparison is in our response to Weaknesses 1 and 2.

Computation. Each SP-Level trial makes one value-and-gradient query, adds a linear cut, computes an approximate Steiner point, and checks how far that point moved. Forming and accepting the accelerated update needs no further queries. The concurrent method makes several queries within each bundle solve and repeats these solves during bisection for the envelope function.

In our implementation with fresh independent samples, the remaining optimization tasks are linear programs: they test feasibility and maximize linear functions over the set defined by the accumulated cuts. The programs used for one center estimate are independent. Proposition C.4 bounds their number by

\qquad M=N(\varepsilon),\quad \mathsf b_M=1+\lceil\log_2M\rceil,\quad \mathsf c_n=1+\lceil\log_2(2n)\rceil.$$ Here $\varepsilon$ is the target error, $\delta$ the failure probability, and $N(\varepsilon)$ the prescribed trial count for an interval of width $\varepsilon$ containing $f^\star$. Their cost depends on dimension, the number of cuts and numerical precision. For arithmetic work, both methods have polynomial bounds in exact arithmetic. The sharper bound concerns the number of queries. Proposition C.5 gives an implementation in finite precision under its stated assumptions on oracle accuracy and the representation of input numbers. ***Proof.*** Let $\ell$ be the target objective level, $y_t$ the accelerated iterate, $A_t$ its accumulated weight, and $d_t$ the Euclidean distance between two successive approximate centers. Convexity, the level cut and smoothness give $$A_t(f(y_t)-\ell) \le A_{t-1}(f(y_{t-1})-\ell)+\tfrac12d_t^2$$ for each accepted trial. Suppose all localization sets remain nonempty, and let $P_N$ be the bound on total movement of the exact Steiner points over $N$ trials. The algorithm estimates each center to accuracy $P_N/(4N)$ and accepts a trial when $d_t\le4P_N/N$. These choices give at least $N/2$ accepted updates, $$A_N\ge N^2/(16L),\qquad \sum_{\mathrm{accepted}}d_t^2\le6P_N^2/N.$$ Summing the first inequality and using these two bounds gives $f(y_N)-\ell\le48LP_N^2/N^3$. ***Higher-order oracles.*** For an oracle returning $f$ and its derivatives through order $k\ge2$, Appendix E.3 gives error $$\widetilde O_k\\!\left( \frac{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. Each trial makes two queries returning the function value and derivatives through order $k$. These are oracle bounds; the model-search proof gives finite termination. Appendix D also gives higher-order lower-bound constructions. ***Operators and strong convexity.*** We construct methods and error certificates for monotone variational inequalities, convex--concave saddle-point problems and strongly monotone operators (Appendix G). For strongly convex objectives, Appendix F characterizes deterministic complexity in terms of $\Lambda=L/\mu_1-n\ge8$, where $\mu_1$ is the strong convexity constant in $\ell_1$. Ordinary restart gives generic strongly convex bounds; the dependence on $\Lambda$ requires an additional argument. We also construct a method using gradients without function values (Appendix E). The comparison with higher-order variational-inequality methods is in Appendix J. ***Randomized lower bound.*** Appendix D proves the smooth randomized lower bound for arbitrary adaptive first-order queries, including queries outside the feasible set, in dimension $n\ge32N+1$. ***Quadratics.*** Appendix H extends Ouyang's quadratic method from $p=1$ to $\ell_p$ balls with $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*. Dimension padding and ordinary restart are standard adaptations. Suitable changes of domain or smoothness metric also apply to the concurrent movement-based construction.
AuthorsOpenReview ↗

Q2: Dimension padding.

Q2: Dimension padding.

Yes. Set d=max⁡n,Nd=\max\\{n,N\\} and F(x,z)=f(x)F(x,z)=f(x) on Rd\mathbb R^d. Then ∇F(x,z)=(∇f(x),0)\nabla F(x,z)=(\nabla f(x),0) and

\le L\\|x-y\\|_2\le L\\|(x,z)-(y,w)\\|_2.$$ The projection of $B_1^d(R)$ onto the first $n$ coordinates is $B_1^n(R)$, so the constrained minima agree. Each query to $F$ costs one query to $f$, and projecting the output preserves feasibility and error. Since $N\le d$, the concurrent main theorem gives the cubic exponent for every budget, with its dimension logarithms evaluated at $d=\max\\{n,N\\}$. The same argument applies to globally Hölder gradients. Their feasible Theorem 12 also states an all-budget rate. The query-count comparison in Q1 uses the stated range $N\le n$ directly.
Reviewer_PiBoOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies convex optimization over the ℓ1\ell_1 ball when the objective is smooth with respect to the Euclidean norm. The authors establish matching upper and lower bounds, up to logarithmic factors, for the minimax first-order oracle complexity, with an O~(LR2/N3)\widetilde{O}(LR^2/N^3) upper bound and lower bounds for both deterministic and randomized methods in sufficiently high dimensions. For the upper bound, they propose a Steiner-point-based accelerated level method that exploits the short total movement of Steiner points along nested localization polytopes. The authors also extend the approach to nonsmooth and higher-order optimization, strongly convex problems, and monotone variational inequalities, and study a curvature-learning method for convex quadratics over ℓp\ell_p balls.

Critical strengths
  • This reviewer finds the paper clear and well organized.
  • This reviewer believes that the main theoretical result is meaningful. The paper addresses the gap between the classical O(1/N2)O(1/N^2) upper bound and the Ω(1/N3)\Omega(1/N^3) lower bound for smooth convex optimization with mismatched geometry. This reviewer finds that establishing nearly matching oracle complexity bounds is a meaningful contribution.
  • This reviewer finds the proposed accelerated level method interesting. In particular, leveraging the short total movement of Steiner points to obtain an upper bound that nearly matches the known lower bound is nontrivial yet intuitive.
  • This reviewer also appreciates the breadth of the theoretical contributions.
Critical weaknesses

This reviewer did not identify any critical weaknesses in the paper.

Questions for authors

The paper already addresses many of this reviewer's questions, and this reviewer has no further questions that would materially affect the assessment, as specified in the reviewer guidelines.

1 comment

Thank you for your review and we appreciate your positive evaluation of our work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.