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 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 use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
