OpenAlex ·

Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems

Yuriy Dorn, Darina Dvinskikh, Timofei Loginov, Osman Osmanov, Aleksandr Shestakov, Nazarii Tupitsa and Alexander Gasnikov

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.00345
Original
Read it at the publisher
Topics
Artificial IntelligenceComputational ComplexityNumerical Analysis

Abstract

We study the query complexity of optimization with exact scalar-value information. For globally $L$-smooth convex functions on $\mathbb R^d$ with a minimizer in a Euclidean ball of radius $R$, we prove the lower bound $Ω(d\min\{d,\sqrt{LR^2/\varepsilon}\})$ for adaptive randomized algorithms in the stated accuracy range. Queries are unrestricted, and the bound contains no logarithmic factor. It holds for quadratics and matches the minimum of two elementary upper bounds on that class. Prescribed strong convexity introduces the additional cap $\sqrt{L/μ}$. The proof compares the mean of a matrix with the mean of its inverse on arbitrary affine slices and bounds posterior moments after adaptive measurements. We extend these information bounds to saddle-point problems with independent block dimensions. For compact bilinear games, the coupling alone yields $Ω(r\min\{r,\sqrt{CR_xR_y/\varepsilon}\})$ queries, where $r=\min\lbrace d_x,d_y\rbrace$. A strongly convex--strongly concave construction yields a condition-dependent lower bound even with known isotropic diagonal Hessians. Separate reductions establish scalar query lower bounds under mixed value and partial-gradient access, including for outer objective accuracy. A Euclidean-image radius yields smooth and nonsmooth extensions to independently specified norms and known penalties.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Artificial Intelligence

Get the few papers worth your time in Artificial Intelligence every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics