Overparameterization constitutes one of the most significant hallmarks of
deep neural networks. Though it can offer the advantage of outstanding
generalization performance, it meanwhile imposes substantial storage burden,
thus necessitating the study of network pruning. A natural and fundamental
question is: How sparse can we prune a deep network (with almost no hurt on the
performance)? To address this problem, in this work we take a first principles
approach, specifically, by merely enforcing the sparsity constraint on the
original loss function, we're able to characterize the sharp phase transition
point of pruning ratio, which corresponds to the boundary between the feasible
and the infeasible, from the perspective of high-dimensional geometry. It turns
out that the phase transition point of pruning ratio equals the squared
Gaussian width of some convex body resulting from the $l_1$-regularized loss
function, normalized by the original dimension of parameters. As a byproduct,
we provide a novel network pruning algorithm which is essentially a global
one-shot pruning one. Furthermore, we provide efficient countermeasures to
address the challenges in computing the involved Gaussian width, including the
spectrum estimation of a large-scale Hessian matrix and dealing with the
non-definite positiveness of a Hessian matrix. It is demonstrated that the
predicted pruning ratio threshold coincides very well with the actual value
obtained from the experiments and our proposed pruning algorithm can achieve
competitive or even better performance than the existing pruning algorithms.
All codes are available at:
this https URL

本文研究了深度神经网络的过度参数化问题，提出了一种全局一次性网络剪枝算法，并通过计算高维几何中的正交宽度来确定剪枝比率的相变点，该值等于基于 $l_1$ 正则化损失函数的某个凸体的平方高斯宽度除以参数的原始维度。

深度网络剪枝的几何视角：有多稀疏可以剪枝？

How Sparse Can We Prune A Deep Network: A Geometric Viewpoint

We study embedding a subset $K$ of the unit sphere to the Hamming cube
$\{-1,+1\}^m$. We characterize the tradeoff between distortion and sample
complexity $m$ in terms of the Gaussian width $\omega(K)$ of the set. For
subspaces and several structured sets we show that Gaussian maps provide the
optimal tradeoff $m\sim \delta^{-2}\omega^2(K)$, in particular for $\delta$
distortion one needs $m\approx\delta^{-2}{d}$ where $d$ is the subspace
dimension. For general sets, we provide sharp characterizations which reduces
to $m\approx{\delta^{-4}}{\omega^2(K)}$ after simplification. We provide
improved results for local embedding of points that are in close proximity of
each other which is related to locality sensitive hashing. We also discuss
faster binary embedding where one takes advantage of an initial sketching
procedure based on Fast Johnson-Lindenstauss Transform. Finally, we list
several numerical observations and discuss open problems.

研究了将单位球面子集嵌入到 Hamming 立方体中的方法，利用高斯宽度表征了失真和样本复杂度之间的权衡关系，并提供了嵌入点的局部嵌入以及更快的二进制嵌入等改进方案。

任意集合的二元嵌入的近似最优界限

Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets

Empirical Risk Minimization (ERM) is a standard technique in machine
learning, where a model is selected by minimizing a loss function over
constraint set. When the training dataset consists of private information, it
is natural to use a differentially private ERM algorithm, and this problem has
been the subject of a long line of work started with Chaudhuri and Monteleoni
2008. A private ERM algorithm outputs an approximate minimizer of the loss
function and its error can be measured as the difference from the optimal value
of the loss function. When the constraint set is arbitrary, the required error
bounds are fairly well understood \cite{BassilyST14}. In this work, we show
that the geometric properties of the constraint set can be used to derive
significantly better results. Specifically, we show that a differentially
private version of Mirror Descent leads to error bounds of the form
$\tilde{O}(G_{\mathcal{C}}/n)$ for a lipschitz loss function, improving on the
$\tilde{O}(\sqrt{p}/n)$ bounds in Bassily, Smith and Thakurta 2014. Here $p$ is
the dimensionality of the problem, $n$ is the number of data points in the
training set, and $G_{\mathcal{C}}$ denotes the Gaussian width of the
constraint set that we optimize over. We show similar improvements for strongly
convex functions, and for smooth functions. In addition, we show that when the
loss function is Lipschitz with respect to the $\ell_1$ norm and $\mathcal{C}$
is $\ell_1$-bounded, a differentially private version of the Frank-Wolfe
algorithm gives error bounds of the form $\tilde{O}(n^{-2/3})$. This captures
the important and common case of sparse linear regression (LASSO), when the
data $x_i$ satisfies $|x_i|_{\infty} \leq 1$ and we optimize over the $\ell_1$
ball. We show new lower bounds for this setting, that together with known
bounds, imply that all our upper bounds are tight.

本文介绍了隐私保护数据集下 Empirical Risk Minimization（ERM）的改进算法 —— 不同 ially private ERM Algorithm。该算法通过利用限制条件的几何特性，在 Lipschitz、强凸和光滑函数等情况下，提供了更严格的误差上界，并针对稀疏线性回归（LASSO）提出了新的下界。