Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
Abstract
We study the query complexity of optimization with exact scalar-value information. For globally L-smooth convex functions on ℝd with a minimizer in a Euclidean ball of radius R, we prove the lower bound Ω(dmin{d,√(LR2/ε)}) 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 √(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 Ω(rmin{r,√(CRxRy/ε)}) queries, where r=min{ dx,dy}. 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.
Related
- A switching proximal gradient method for constrained difference-of-convex optimization problems
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems
- Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
- Complexity of Multiblock Convex-Concave Saddle-Point Problems with General Smooth Coupling
BibTeX
@misc{dorn2026lower,
title = {{Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems}},
author = {Yuriy Dorn and Darina Dvinskikh and Timofei Loginov and Osman Osmanov and Aleksandr Shestakov and Nazarii Tupitsa and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00345},
eprint = {2610.00345},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00345},
}
RIS
TY - UNPB
TI - Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
AU - Yuriy Dorn
AU - Darina Dvinskikh
AU - Timofei Loginov
AU - Osman Osmanov
AU - Aleksandr Shestakov
AU - Nazarii Tupitsa
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00345
UR - https://arxiv.org/abs/2610.00345
AB - We study the query complexity of optimization with exact scalar-value information. For globally L-smooth convex functions on ℝ^d with a minimizer in a Euclidean ball of radius R, we prove the lower bound Ω(dmin{d,√(LR^2/ε)}) 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 √(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 Ω(rmin{r,√(CR_xR_y/ε)}) queries, where r=min{ d_x,d_y}. 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.
ER -