ReSQueing Parallel and Private Stochastic Convex Optimization

We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. Combining ReSQue with recent advances in ball oracle acceleration [CJJJLST20, ACJJS21], we develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings. For a SCO objective constrained to the unit ball in ℝd, we obtain the following results (up to polylogarithmic factors). We give a parallel algorithm obtaining optimization error εopt with d1/3εopt-2/3 gradient oracle query depth and d1/3εopt-2/3 + εopt-2 gradient queries in total, assuming access to a bounded-variance stochastic gradient estimator. For εopt ∈ [d-1, d-1/4], our algorithm matches the state-of-the-art oracle depth of [BJLLS19] while maintaining the optimal total work of stochastic gradient descent. Given n samples of Lipschitz loss functions, prior works [BFTT19, BFGT20, AFKT21, KLL21] established that if n gtrsim d εdp-2, (εdp, δ)-differential privacy is attained at no asymptotic cost to the SCO utility. However, these prior works all required a superlinear number of gradient queries. We close this gap for sufficiently large n gtrsim d2 εdp-3, by using ReSQue to design an algorithm with near-linear gradient query complexity in this regime.