CS Paper Radar

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity

Cedar Site Bai

cs.LG math.OCstat.ML ·submitted 2026-11-03 19:25 UTC · v1
theory

Abstract

In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose $p^{th}$-order derivatives are Hölder continuous with degree $ν$ and parameter $H$, and that are uniformly convex with degree $q$ and parameter $σ$. When these orders match, namely, $q = p + ν$, we show that any deterministic algorithm with access to derivatives up to order $p$ requires $Ω\left(\left(\frac{H}σ\right)^{\frac{2}{3(p+ν)-2}}\log\frac{Δ_0}ε\right)$ oracle calls to reduce an initial optimality gap of $Δ_0$ to $ε$. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization

cs.LG math.OC ·2026-09-18 ·David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina
similarity 0.65
Abstract

We study the optimization of convex objectives with $(L,κ-1)$-Hölder-continuous gradients in $\ell_q$ over $R B_p^d$, $1<κ\le 2$. (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every $p<q$ and generally reduces Lipschitz convex optimization to bounds on the movement of selectors. We couple that movement with Hölder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime $T\le d$ and for $p<\min\{q,2\}$, has error $$ \widetilde O_{κ,p,q}\!\left( \frac{LR^κ}{T^{κ(1+1/p-(1/q-1/2)_+)-1}} \right), $$ after $T$ queries to a first-order oracle, solving the COLT 2015 open problem of (Guz15), up to logarithmic factors. At $(p,q)=(1,2)$, the rate is $\widetilde{O}(LR^κ/T^{2κ-1})$, including $\widetilde{O}(LR^2/T^{3})$ cubic decay in the smooth case.

0.40

Optimal High-Order Methods for Solving Monotone Variational Inequalities

cs.GT math.OCstat.ML ·2026-09-20 ·Xinliang Zhang, Lesi Chen, Linxuan Pan, Chengchang Liu, Junchi Yang +1 more
theory similarity 0.63
Abstract · Improve our previous note in https://arxiv.org/abs/2608.08463 and achieve optimal complexity

We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at a rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subclass of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved this rate to $\tilde{\mathcal{O}}( T^{-1.75})$. However, the result has a substantial gap compared to the lower bound of $Ω(T^{-2.5})$ established by Chen et al. (2026). In this paper, we propose a novel second-order method that achieves the optimal rate of $\mathcal{O}(T^{-2.5})$. Our algorithm also extends to higher-order methods: for any integer $ p \ge 1$, we obtain a $p$th-order method with a convergence rate of $\mathcal{O}(T^{-(3p-1)/2})$, matching the known lower bounds and therefore establishing optimal rates across all orders.

0.54

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

cs.CC stat.MLcs.LGmath.ST ·2026-11-02 ·Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao +1 more
theory similarity 0.60
Abstract

We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

0.17

Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime

cs.LG math.OC ·2026-11-18 ·Leonardo Galli, Daniela Angela Parletta, Andrea Paudice
theory similarity 0.59
Abstract

In this paper, we study stochastic gradient descent in the smooth interpolation regime, where the population objective shares a common minimizer with the sample losses. In contrast to prior work, which has largely focused on in-expectation analysis, we obtain high-probability convergence guarantees under the same assumptions. In the convex case, we prove a fast rate of order $\log(β^{-1}) \cdot n^{-1}$ after $n$ iterations, with failure probability at most $β$. In the strongly convex case, we derive a family of moment-based bounds of order $β^{-p} \cdot \exp(-\mathcal{O}(p \cdot n))$ for $p \in (0,1]$, and complement them with a matching lower bound showing that the corresponding deterioration in the exponential rate is essentially unavoidable. In both settings, our theoretical results are unified across a broad class of step-size schedules. Building on this analysis, we extend our results to a low-noise regime and to nonconvex objectives satisfying the Polyak-Lojasiewicz condition.

0.06

Optimal Stochastic Bilevel Optimization with First-Order Oracles

cs.LG math.OC ·2026-10-01 ·Linxuan Pan, Junchi Yang
theory similarity 0.59
Abstract

We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-$p$ finite differences. For any fixed finite smoothness order $p\ge1$ in the lower-level variable, MRT-FD finds an $\varepsilon$-stationary point using $\mathcal{O}(\varepsilon^{-4-2/p})$ stochastic gradient queries. We also prove a matching $Ω(\varepsilon^{-4-2/p})$ oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on $\varepsilon$ is optimal for every fixed finite $p$, closing the upper--lower complexity gap in this stochastic first-order oracle setting.

0.29

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

cs.LG math.OCstat.ML ·2026-10-02 ·Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang
theoryhighly cited similarity 0.59
Abstract

This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations. Under this setting, we show a lower bound of $Ω(m+ m^{1/7} ε^{-2/7})$ on the number of total iterations to find an $ε$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})$ and is tight up to logarithmic factors.

0.37

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

cs.LG math.OC ·2026-09-17 ·David Martínez-Rubio, Cristóbal Guzmán
similarity 0.58
Abstract · polished writing, added a few more general results (such as a better lower bound, and a more general potential-energy center)

We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_q$-norm over an $\ell_p$-ball of radius $R$, where $1\leq p,q\leq\infty$. For $p<q$, we obtain error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$ after $T$ oracle queries, attaining the lower bounds in a COLT 2015 open problem (Guz15b) with efficient algorithms. In particular, the rate is $\widetilde{O}(GR/T)$ for Euclidean Lipschitzness with an $\ell_1$-ball domain of radius $R$ ($p=1,q=2$). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem (BBE+20) in sublevel sets of an evolving maximum of affine lower bounds, that is, the bundle (LNN95): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm nearly optimally. For nested convex subsets of the $\ell_p$ ball $R B_p^d$, we introduce novel stable selectors whose movement is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented for our optimization algorithm in polynomial time in the real-arithmetic model.

0.54

The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

cs.LG math.OC ·2026-09-20 ·Guy Kornowski
theoryhighly cited similarity 0.57
Abstract · 13 pages

We study the complexity of finding $(δ,ε)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension $d$ [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in $d$. We answer this question negatively by proving a lower bound of order $(1/ε)^{Ω(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.

0.54