We introduce a new framework for the exact point-wise $\ell_p$ robustness
verification problem that exploits the layer-wise geometric structure of deep
feed-forward networks with rectified linear activations (ReLU networks). The
activation regions of the network partition the input space, and one can verify
the $\ell_p$ robustness around a point by checking all the activation regions
within the desired radius. The GeoCert algorithm (Jordan et al., NeurIPS 2019)
treats this partition as a generic polyhedral complex in order to detect which
region to check next. In contrast, our LayerCert framework considers the
\emph{nested hyperplane arrangement} structure induced by the layers of the
ReLU network and explores regions in a hierarchical manner. We show that, under
certain conditions on the algorithm parameters, LayerCert provably reduces the
number and size of the convex programs that one needs to solve compared to
GeoCert. Furthermore, our LayerCert framework allows the incorporation of lower
bounding routines based on convex relaxations to further improve performance.
Experimental results demonstrate that LayerCert can significantly reduce both
the number of convex programs solved and the running time over the
state-of-the-art.

该研究提出了一种名为 LayerCert 的新框架，利用 ReLU 网络的分层几何结构解决点精确的 L_p 鲁棒性问题，进一步减少所需解决的凸规划数量和大小并提高了性能。

针对对抗鲁棒性的分层验证

Hierarchical Verification for Adversarial Robustness

This paper considers convex programs with a general (possibly
non-differentiable) convex objective function and Lipschitz continuous convex
inequality constraint functions. A simple algorithm is developed and achieves
an $O(1/t)$ convergence rate. Similar to the classical dual subgradient
algorithm and the ADMM algorithm, the new algorithm has a parallel
implementation when the objective and constraint functions are separable.
However, the new algorithm has a faster $O(1/t)$ convergence rate compared with
the best known $O(1/\sqrt{t})$ convergence rate for the dual subgradient
algorithm with primal averaging. Further, it can solve convex programs with
nonlinear constraints, which cannot be handled by the ADMM algorithm. The new
algorithm is applied to a multipath network utility maximization problem and
yields a decentralized flow control algorithm with the fast $O(1/t)$
convergence rate.

本文研究具有一般凸目标函数和 Lipschitz 连续凸不等式约束函数的凸规划问题，并提出了一种简单的算法，用于实现 O (1/t) 的收敛速度。此外，该算法还可用于处理非线性约束条件。最终将该算法应用于多路径网络效用最大化问题，并产生具有快速 O (1/t) 收敛速度的分散式流量控制算法。

一种简单的并行算法，对于一般的凸规划问题具有 O（1/t）的收敛速率

A Simple Parallel Algorithm with an $O(1/t)$ Convergence Rate for  General Convex Programs

Random projection (RP) is a classical technique for reducing storage and
computational costs. We analyze RP-based approximations of convex programs, in
which the original optimization problem is approximated by the solution of a
lower-dimensional problem. Such dimensionality reduction is essential in
computation-limited settings, since the complexity of general convex
programming can be quite high (e.g., cubic for quadratic programs, and
substantially higher for semidefinite programs). In addition to computational
savings, random projection is also useful for reducing memory usage, and has
useful properties for privacy-sensitive optimization. We prove that the
approximation ratio of this procedure can be bounded in terms of the geometry
of constraint set. For a broad class of random projections, including those
based on various sub-Gaussian distributions as well as randomized Hadamard and
Fourier transforms, the data matrix defining the cost function can be projected
down to the statistical dimension of the tangent cone of the constraints at the
original solution, which is often substantially smaller than the original
dimension. We illustrate consequences of our theory for various cases,
including unconstrained and $\ell_1$-constrained least squares, support vector
machines, low-rank matrix estimation, and discuss implications on
privacy-sensitive optimization and some connections with de-noising and
compressed sensing.

该研究探讨了使用随机投影进行维度降低的方法来近似解决具有凸性质的问题，在计算有限的情况下具有广泛的应用，同时还可以提高隐私保护和降低存储和计算成本。研究证明了该方法的近似比率可以用约束集合的几何特性来界定，对于一类广泛的随机投影，其投影结果数据矩阵的维度相对于原始问题的维度相对较小，该理论还与降噪、压缩感知等领域有关系。