We introduce a new zeroth-order algorithm for private stochastic optimization
on nonconvex and nonsmooth objectives. Given a dataset of size $M$, our
algorithm ensures $(\alpha,\alpha\rho^2/2)$-R\'enyi differential privacy and
finds a $(\delta,\epsilon)$-stationary point so long as
$M=\tilde\Omega\left(\frac{d}{\delta\epsilon^3} +
\frac{d^{3/2}}{\rho\delta\epsilon^2}\right)$. This matches the optimal
complexity of its non-private zeroth-order analog. Notably, although the
objective is not smooth, we have privacy ``for free'' whenever $\rho \ge
\sqrt{d}\epsilon$.

我们介绍了一种新的零阶算法，用于非凸和非光滑目标的私有随机优化。给定一个大小为 M 的数据集，我们的算法确保（α，αρ²/2）-Rényi 差分隐私，并找到一个（δ，ε）- 稳定点，只要 M=Ω^(~)[(d/(δε³)) + (d^(3/2)/(ρδε²)) ]。这与其非私有的零阶模拟的最优复杂度相匹配。值得注意的是，尽管目标不是光滑的，只要 ρ ≥ √(d)ε，我们就有了 “免费” 的隐私。

私密的零阶非光滑非凸优化

Private Zeroth-Order Nonsmooth Nonconvex Optimization

We consider the block coordinate descent methods of Gauss-Seidel type with
proximal regularization (BCD-PR), which is a classical method of minimizing
general nonconvex objectives under constraints that has a wide range of
practical applications. We theoretically establish the worst-case complexity
bound for this algorithm. Namely, we show that for general nonconvex smooth
objectives with block-wise constraints, the classical BCD-PR algorithm
converges to an epsilon-stationary point within O(1/epsilon) iterations. Under
a mild condition, this result still holds even if the algorithm is executed
inexactly in each step. As an application, we propose a provable and efficient
algorithm for `Wasserstein CP-dictionary learning', which seeks a set of
elementary probability distributions that can well-approximate a given set of
d-dimensional joint probability distributions. Our algorithm is a version of
BCD-PR that operates in the dual space, where the primal problem is regularized
both entropically and proximally.

该论文主要介绍了基于 Gauss-Seidel 类型的块坐标下降算法（BCD-PR）的近端正则化方法，以及提出了一种双重正则化的原始问题的对偶算法，并将其应用于 Wasserstein CP - 字典学习中，从而实现了优化问题的求解。

带有近端正则的块坐标下降复杂度及其在 Wasserstein CP 字典学习中的应用

Complexity of Block Coordinate Descent with Proximal Regularization and  Applications to Wasserstein CP-dictionary Learning

Despite their popularity, the practical performance of asynchronous
stochastic gradient descent methods (ASGD) for solving large scale machine
learning problems are not as good as theoretical results indicate. We adopt and
analyze a synchronous K-step averaging stochastic gradient descent algorithm
which we call K-AVG. We establish the convergence results of K-AVG for
nonconvex objectives and explain why the K-step delay is necessary and leads to
better performance than traditional parallel stochastic gradient descent which
is a special case of K-AVG with $K=1$. We also show that K-AVG scales better
than ASGD. Another advantage of K-AVG over ASGD is that it allows larger
stepsizes. On a cluster of $128$ GPUs, K-AVG is faster than ASGD
implementations and achieves better accuracies and faster convergence for
\cifar dataset.

采用同步 K 步均值随机梯度下降算法，解决机器学习问题，证明 K-AVG 算法的收敛性，解释为什么需要 K 步延迟，表明在大规模数据集上，K-AVG 算法优于 ASGD 算法。