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

We study convex stochastic optimization with $m$ expectation constraints, $\min \{f(x)=\text{E}F(x,\xi ):g_i(x)=\text{E}{G}_i(x,\xi )\le 0,i=1,\dots ,m,x\in \text{Q}\}$, when only noisy function values are available. At each call the oracle returns the vector $(F(x,\xi ),G_1(x,\xi ),\dots ,G_m(x,\xi ))$ at two points, with the same realization of $\xi$ at both (two-point feedback). The data may be smooth or nonsmooth, and the objective may be strongly convex. We count three resources separately: \emph{sequential oracle rounds} $\text{Nseq}$ (batches of queries that can be sent in parallel), \emph{oracle calls}, split into calls used for the objective and calls used for the constraints, and \emph{inner operations} that need no new round, such as proximal steps or matrix–vector products with stored Jacobian samples.