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

Due to their simplicity and excellent performance, parallel asynchronous
variants of stochastic gradient descent have become popular methods to solve a
wide range of large-scale optimization problems on multi-core architectures.
Yet, despite their practical success, support for nonsmooth objectives is still
lacking, making them unsuitable for many problems of interest in machine
learning, such as the Lasso, group Lasso or empirical risk minimization with
convex constraints.
In this work, we propose and analyze ProxASAGA, a fully asynchronous sparse
method inspired by SAGA, a variance reduced incremental gradient algorithm. The
proposed method is easy to implement and significantly outperforms the state of
the art on several nonsmooth, large-scale problems. We prove that our method
achieves a theoretical linear speedup with respect to the sequential version
under assumptions on the sparsity of gradients and block-separability of the
proximal term. Empirical benchmarks on a multi-core architecture illustrate
practical speedups of up to 12x on a 20-core machine.

本研究提出了一种基于 ProxASAGA 算法的并行异步稀疏方法，用于解决多核架构下大规模优化问题中的非光滑目标，并在实验中取得了多项实际加速。

突破不光滑障碍：复合优化可扩展并行方法

Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite  Optimization

Linearized alternating direction method of multipliers (ADMM) as an extension
of ADMM has been widely used to solve linearly constrained problems in signal
processing, machine leaning, communications, and many other fields. Despite its
broad applications in nonconvex optimization, for a great number of nonconvex
and nonsmooth objective functions, its theoretical convergence guarantee is
still an open problem. In this paper, we propose a two-block linearized ADMM
and a multi-block parallel linearized ADMM for problems with nonconvex and
nonsmooth objectives. Mathematically, we present that the algorithms can
converge for a broader class of objective functions under less strict
assumptions compared with previous works. Furthermore, our proposed algorithm
can update coupled variables in parallel and work for less restrictive
nonconvex problems, where the traditional ADMM may have difficulties in solving
subproblems.

本篇论文提出两种针对非凸非光滑目标函数的扩展线性交替方向乘子法 (ADMM)，均在较少的前提下保证收敛，并且可以使用多个块来并行计算协同变量以更有效地求解问题。