Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints

Abstract

We establish the optimal query complexity of smooth convex quadratic optimization from exact function values. For dimension $d$, smoothness $L$, and minimizer radius $R$, the sharp rate at small relative error is $\Theta(d\min\{d,\sqrt{LR^2/\varepsilon}\})$. The lower bound has no logarithmic loss and holds even for adaptive randomized algorithms with unrestricted query locations, precision, and computation. It also matches upper bounds for general smooth convex objectives at moderate accuracy. We obtain, to our knowledge, the first lower bounds matching known smooth and nonsmooth rates, up to logarithmic factors, under Euclidean regularity and $\ell_p$ localization or feasibility, $1\le p<2$. These bounds determine the optimal polynomial dimension dependence in these geometries. A geometric framework covers arbitrary norms and known regularizers; exploiting regularizer sublevels can strengthen lower bounds by an unbounded factor. For convex-concave saddle-point problems with unequal block dimensions, we isolate coupling costs even with known, perfectly conditioned block Hessians. Separate reductions show that scalar evaluations remain necessary despite unlimited access to one block's partial gradients.