This work proves the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization, and develops a posterior mean energy method for adaptive exact max observations.
Abstract
Whether exact scalar feedback intrinsically incurs the additional dimension $d$ paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a universal Lipschitz scale, the value only bound $O(d^2\log(d+1)\log(1/\epsilon))$ and two-point bound $O(d\epsilon^{-2})$ yield the upper bound $\widetilde O\left(d\min\{d,\epsilon^{-2}\}\right)$. By contrast, prior lower bounds for arbitrary randomized algorithms give only $\Omega(\min\{d,\epsilon^{-2}\})$, leaving a factor $d$ unexplained. We close this gap, up to logarithmic factors, for arbitrary adaptive randomized algorithms minimizing a convex objective with a universal Lipschitz scale over the $d$-dimensional Euclidean unit ball, where each query returns only the exact scalar value. Let $T_\epsilon$ denote the minimum number of queries required to return an $\epsilon$-suboptimal point with probability at least $1/2$, uniformly over the function class. We prove that \[T_\epsilon\ge c\,\frac{d\min\{d,\epsilon^{-2}\}}{\log\!\bigl(\min\{d,\epsilon^{-2}\}\bigr)},\] for $d\ge d_0$ and $0<\epsilon\le\epsilon_0$, where $c,\epsilon_0>0$ and $d_0\in\mathbb N$ are universal constants. This gives $\Omega\left(\frac{d}{\epsilon^2\log(1/\epsilon)}\right)$ in the low-accuracy regime $\epsilon\ge d^{-1/2}$ and $\Omega\left(\frac{d^2}{\log d}\right)$ in the high-accuracy regime $\epsilon\le d^{-1/2}$ with the latter independent of $\epsilon$. These bounds match the corresponding upper bound up to logarithmic factors. To our knowledge, this is the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization. The proof uses a random support function hard family and develops a posterior mean energy method for adaptive exact max observations, in place of first-order zero chain constructions and noise based transcript inequalities.
It is proved that every deterministic first-order algorithm requires a first-order oracle that returns both the function value and the full subdifferential at every query point, and establishes the optimal deterministic oracle complexity.
A sharp lower bound is proved for smooth nonconvex stochastic optimization with uniformly bounded gradient noise with uniformly bounded gradient noise and resolves the question raised by whether almost-surely bounded oracle error permits a better rate than bounded variance.
We establish improved lower bounds on the minimax expected regret of stochastic bandit convex optimization for $1$-Lipschitz functions on the $d$-dimensional Euclidean ball. For time horizons $n\ge d^{10/3}$, we prove a lower bound of $\Omega(d^{4/3}\sqrt{n})$, the first nontrivial bound that exceeds the $d\sqrt{n}$ dependence of linear bandits, showing that stochastic bandit convex optimization is fundamentally harder than linear bandits. For $d^2\le n\le d^{10/3}$, we obtain a lower bound of $\Omega(\sqrt{d}n^{3/4})$, matching the regret of the algorithm of Flaxman et al. (2005), establishing its optimality in this regime. The hard class of convex functions we construct takes the following form in dimension $2d$: for an action $a=(a^1,a^2)\in \mathbb{B}^{2d}$, each function is the scaled soft maximum of a"tube", $r^{-1}\|W^\star a^1-\frac{r}{8\varepsilon}a^2 \|$ (hyperparameterized by $\varepsilon,r$), and a squared distance function, $\frac12\|a^1-u^\star\|^2-\frac12\|u^\star\|^2$. Here $u^\star\in\mathbb{R}^d$ is the unknown target determining the minimizer, while $W^\star\in\mathbb{R}^{d\times d}$ hides the region in which the quadratic curvature is observable. Indeed, observations reveal substantial information about $u^\star$ only when the learner acts near the hidden tube $a^2\approx \frac{8\varepsilon}{r}W^\star a^1$; away from it, the tube branch masks the quadratic branch. Thus the learner must pay to uncover the geometry encoded by $W^\star$ before it can effectively exploit the curvature that identifies $u^\star$. Formalizing this tradeoff yields a sample complexity lower bound of $\Omega(\frac{d^{5/2}}{\varepsilon^2}\wedge\frac{d^2}{\varepsilon^4})$ for finding an $\varepsilon$-optimal action, and ultimately the $\Omega(d^{4/3}\sqrt{n}\wedge\sqrt{d}n^{3/4})$ regret lower bound. The proof was developed by GPT-5.5 Pro and GPT-5.6 Sol Pro under the authors'guidance.
We establish a near-linear quantum query lower bound for high-accuracy convex optimization over an explicit family of $n$-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error $\Theta(n^{-2})$ requires $\Omega\!\left(\frac{n}{\log n\,\log\log n}\right)$ membership queries. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within $\Theta(n^{-2})$ distance from the feasible set. This resolves, up to logarithmic factors, an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gily\'en, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real $n\times n$ matrix requires at least $n/2$ matrix-vector product queries. The construction also yields an $\Omega(n)$ phase-query lower bound for estimating the minimum eigenvalue of a real symmetric $n\times n$ matrix to additive accuracy $\Theta(n^{-2})$. These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove a near-optimal gradient-query lower bound for constant-accuracy optimization of smooth and strongly convex functions.
It is proved that every deterministic first-order method requires $\Omega(\ell\Delta\kappa/\epsilon^2)$ oracle queries in the worst case to find $x$ satisfying $\Phi(0)-\inf_x\Phi(x)$ and that the linear dependence on $\kappa$ is unavoidable for deterministic first-order methods.
For the $n\times n$ lower-triangular all-ones matrix $Q$, we prove a near-optimal lower bound \[ \gamma_{2,1}(Q) := \inf_{Q=AB} \|A\|_{2\to\infty}\|B\|_{1\to1} = \Omega\!\left( \frac{\log^{3/2}n}{(\log\log n)^{3/2}} \right), \] where the infimum ranges over real factorizations of arbitrary finite inner dimension. This cost is a central parameter in space bounds for factorization-based rank and quantile estimation in turnstile streams and in error bounds for matrix mechanisms for continual counting under pure differential privacy. The proof combines right-sided Haar projections with a scale-dependent numerical-sparsity decomposition of the rows of $B$. At each scale, a rank--Frobenius argument shows that the numerically sparse rows cannot account for all of the required Schatten $2/3$ mass, while a Haar projection estimate bounds the contribution of the remaining rows. Summing these bounds over the dyadic scales yields the result. The proof was obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors verified the proof and made minor revisions.
Honghao Lin, V. Mirrokni, David P. Woodruff· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
