ReSQueing Parallel and Private Stochastic Convex Optimization
ReSQueing Parallel and Private Stochastic Convex Optimization
复制标题
DOI：
10.1109/focs57990.2023.00124
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
Y. Carmon;A. Jambulapati;Yujia Jin;Y. Lee;Daogao Liu;Aaron Sidford;Kevin Tian
中科院分区：
文献类型：
--
作者：
Y. Carmon;A. Jambulapati;Yujia Jin;Y. Lee;Daogao Liu;Aaron Sidford;Kevin Tian
我们介绍了一种用于随机凸优化（SCO）的新工具：用于函数与（高斯）概率密度卷积的梯度的重加权随机查询（ReSQue）估计器。结合ReSQue和球oracle加速的最新进展[CJJ+20]， [ACJ+21]，我们开发了在并行和私有环境中实现最先进的SCO复杂性的算法。对于SCO目标约束于$\mathbb{R}^{d}$中的单位球，我们得到以下结果（直至多对数因子）。1)我们给出了一种并行算法，在假设访问有界方差随机梯度估计器的情况下，以$d^{1 / 3} \epsilon_{\text {opt} }^{-2 / 3}$梯度oracle查询深度和$d^{1 / 3} \epsilon_{\text {opt} }^{-2 / 3}+\epsilon_{\text {opt} }^{-2}$梯度查询的总查询量获得优化误差$\epsilon_{\text {opt} }$。对于$\epsilon_{\text {opt} } \in\left[d^{-1}, d^{-1 / 4}\right]$，我们的算法匹配最先进的oracle深度[BJL+19]，同时保持随机梯度下降的最佳总工作量。2)给定n个Lipschitz损失函数样本，先前的工作[BFTT19]， [BFGT20], [AFKT21]， [KLL21]确定，如果在SCO效用没有渐近代价的情况下获得$n \gt rsim d \epsilon_{\mathrm{dp}}^{-2},\left(\epsilon_{\mathrm{dp}}, \delta\right)$ -差分隐私。然而，这些先前的工作都需要超线性数量的梯度查询。我们通过使用ReSQue来设计一个在该机制下具有近线性梯度查询复杂度的算法，从而缩小了这个差距$n \gt rsim d^{2} \epsilon_{{\bf d p}}^{-3}$。
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 [CJJ+20], [ACJ+21], 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 $\mathbb{R}^{d}$, we obtain the following results (up to polylogarithmic factors).1)We give a parallel algorithm obtaining optimization error $\epsilon_{\text {opt} }$ with $d^{1 / 3} \epsilon_{\text {opt} }^{-2 / 3}$ gradient oracle query depth and $d^{1 / 3} \epsilon_{\text {opt} }^{-2 / 3}+\epsilon_{\text {opt} }^{-2}$ gradient queries in total, assuming access to a bounded-variance stochastic gradient estimator. For $\epsilon_{\text {opt} } \in\left[d^{-1}, d^{-1 / 4}\right]$, our algorithm matches the state-of-the-art oracle depth of [BJL+19] while maintaining the optimal total work of stochastic gradient descent.2)Given n samples of Lipschitz loss functions, prior works [BFTT19], [BFGT20], [AFKT21], [KLL21] established that if $n \gt rsim d \epsilon_{\mathrm{dp}}^{-2},\left(\epsilon_{\mathrm{dp}}, \delta\right)$-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 \gt rsim d^{2} \epsilon_{{\bf d p}}^{-3}$, by using ReSQue to design an algorithm with near-linear gradient query complexity in this regime.