Improved lower bounds are established on the minimax expected regret of stochastic bandit convex optimization for $1$-Lipschitz functions on the $d$-dimensional Euclidean ball, showing that stochastic bandit convex optimization is fundamentally harder than linear bandits.
Abstract
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 study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives $f$ that are jointly $L$-smooth in the primal and dual variables $(x,y)$, concave in $y$, and whose primal value function $\Phi(x) := \max_{y\in\mathcal Y} f(x,y)$ satisfies the initial-gap condition $\Phi(0)-\inf_{x\in\mathcal X}\Phi(x)\le \Delta_\Phi$, with a bounded dual domain satisfying $\operatorname{diam}(\mathcal Y)\le D_{\mathcal Y}$. We measure stationarity by the norm of the gradient of the Moreau envelope of $\Phi+\iota_{\mathcal X}$ with parameter $1/(2L)$. We prove that any deterministic zero-respecting first-order algorithm requires $\Omega\left(L^2D_{\mathcal Y}\Delta_\Phi\epsilon^{-3}\right)$ oracle evaluations to find an $\epsilon$-stationary point. Under an unbiased stochastic first-order oracle with bounded variance, any stochastic zero-respecting algorithm requires $\Omega\left(L^3D_{\mathcal Y}^2\Delta_\Phi\epsilon^{-6}\right)$ oracle evaluations. The same lower bounds hold when $\Delta_\Phi$ is replaced by the initial primal-dual gap $\mathcal G_0$. These deterministic and stochastic lower bounds match the corresponding upper bounds of [14] and [29], respectively, up to a logarithmic factor in the deterministic setting.
We study the deterministic oracle complexity of smooth convex optimization when the algorithm receives only exact function values. The objective is a globally $\beta$-smooth convex function, all queries and the final output are restricted to the Euclidean ball of radius $R$, and the unique minimizer lies in the ball of radius $R/2$. We establish an upper bound of $O(d\sqrt{\beta R^2/\epsilon})$ using coordinate finite differences together with an error-robust accelerated projected method. Our main contribution is a matching lower bound, up to the high-accuracy saturation of the construction: any deterministic adaptive value-oracle algorithm requires $\Omega\!\left(d\min\{\sqrt{\beta R^2/\epsilon},(d/\log(ed))^{1/3}\}\right)$ queries. Consequently, the minimax oracle complexity is $\Theta(d\sqrt{\beta R^2/\epsilon})$ throughout the moderate-accuracy regime $\beta R^2(\log(ed)/d)^{2/3}\leq\epsilon\leq c\beta R^2$ for a universal constant $c>0$. The lower bound must account for the fact that a single exact real value can encode arbitrarily much information. To overcome this difficulty, we construct a single fixed smooth convex hard instance using a Moreau-smoothed biased max chain, an exact prefix-shielding mechanism, and batched delayed rotations. These techniques preserve consistency with the full adaptive transcript and establish the optimality of the square-root complexity branch for deterministic bounded-query algorithms.
Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al.· 0 citations
We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let $d$ be the dimension, $K$ be the menu size, and $T$ the time horizon. For $2\le K\le d$, we prove an upper bound $\widetilde O(K^{1/4}\sqrt{dT})$. When $T\ge d^2$, we further prove a lower bound $\Omega(K^{1/4}\sqrt{dT})$. Thus, for $T\ge d^2$ and $2\le K\le d$, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on $K$ is optimal. Compared with the previous $\widetilde O(\sqrt{dKT})$ bound, our upper bound improves the dependence on $K$ by a factor of $K^{1/4}$. For $K\ge d$, we prove an upper bound $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)$ and a lower bound $\Omega\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)$. Here, $\widetilde O_{d,T}$ omits logarithmic factors only in $d$ and $T$. In particular, for polynomially large $K\ge d$, the upper and lower bounds both scale as $d^{3/4}\sqrt T$ up to logarithmic factors, improving the standard $\widetilde O(d\sqrt T)$ rate by a factor of $d^{1/4}$. As $K$ grows further, the regret smoothly recovers the $d\sqrt T$ scale once $\log K$ reaches order $d$.
We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence $h$ satisfying $h(n) = o(\sqrt{n})$, a bound of order $h(n)/\sqrt{n}$, holding simultaneously for all $n$ with probability at least $1-\alpha$ and uniformly over the problem class, is achievable if and only if \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2}<\infty. \] The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.
We study the deterministic first-order oracle complexity of smooth nonconvex-concave minimax optimization over a bounded convex dual domain. Let $\ell$ denote the joint smoothness constant, $D_{\mathcal{Y}}$ the diameter of the dual domain, and $\Delta$ the initial gap. We prove that every deterministic first-order algorithm requires $\Omega(\ell^2D_{\mathcal{Y}}\Delta/\epsilon^3)$ oracle queries in the worst case to find an $\epsilon$-optimization-stationary point whenever $\epsilon\lesssim\min\{\ell D_{\mathcal{Y}},\sqrt{\ell\Delta}\}$. We then develop Tracked-FOAM, a first-order method that attains a matching upper bound, removing the logarithmic factor from previous upper bounds. Together, these results establish the optimal dependence on all problem parameters in the stated regime.
We establish near-optimal higher-order oracle bounds for smooth monotone variational inequalities. For fixed $p\ge2$, let $F$ be monotone on a known compact convex set $X$ of diameter at most $D$, with $\operatorname{Lip}(D^{p-1}F)\le L_p$. Each feasible query returns the complete jet $(F,DF,\ldots,D^{p-1}F)$, and the goal is to find $x$ with tangent residual $\operatorname{dist}(0,F(x)+N_X(x))\le\varepsilon$. Writing $Q=L_pD^p/\varepsilon$, we improve the $\widetilde O_p(Q^{1/p})$ upper bound of Chen et al. to $\widetilde O_p(Q^{2/(3p-1)})$ via a dimension-independent deterministic algorithm that returns an explicit tangent-residual certificate. We prove a matching $\Omega_p(Q^{2/(3p-1)})$ lower bound for arbitrary adaptive deterministic algorithms and randomized algorithms with per-instance success probability at least $2/3$, without span or tensor-update restrictions. Hence the high-dimensional worst-case oracle complexity is $\widetilde\Theta_p((L_pD^p/\varepsilon)^{2/(3p-1)})$. The same method applies to smooth convex--concave minimax problems, improving the fixed-geometry accuracy exponent from $4/(3p+1)$ to $2/(3p-1)$ and matching the known lower-bound exponent.
Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
