Introduction
Deep neural networks are notoriously sensitive to small, adversarial perturbations. A mathematically grounded defense strategy involves bounding the model's Lipschitz constant, which limits how much the output can change for a given change in the input. While exact computation of the Lipschitz constant is NP-hard, the 1-path-norm has emerged as a tight upper bound that correlates well with generalization. However, its non-smooth and non-convex nature makes it difficult to optimize using standard gradient-based methods like SGD via automatic differentiation.
Methodology: Exact Proximal Mapping
This work introduces an efficient algorithm to compute the exact proximal mapping of the 1-path-norm for shallow networks. By leveraging first-order optimality conditions, the authors demonstrate that the optimal solution's non-zero weights maintain the magnitude order of the inputs. This allows for a binary search-based algorithm with $O(m \log m)$ complexity, making the proximal step computationally comparable to a standard stochastic gradient update.
During training, the model utilizes Proximal-SGD: it takes a standard gradient step on the loss function, followed by this exact proximal step to handle the non-smooth path-norm penalty.
Experimental Results
Optimization Performance
The proposed Proximal-SGD method significantly outperforms standard SGD in minimizing the regularized objective. As shown in the convergence plots, Proximal-SGD consistently reaches lower loss values across multiple datasets, including Fashion-MNIST and KMNIST. While standard SGD (solid lines) struggles with the non-differentiable regions of the path-norm, the proximal approach (dashed lines) converges more reliably to the global minimum of the proximal subproblem.
Sparsity and Robustness Trade-offs
A key advantage of the proximal approach is its ability to induce true weight sparsity. Unlike standard $\ell_1$ regularization or weight decay, which may only shrink weights to small values, the 1-path-norm proximal operator mathematically guarantees that a specific number of weights are driven exactly to zero early in the training process.
In adversarial evaluations using PGD attacks, 1-path-norm regularization provides a superior trade-off between clean accuracy and robust error. As illustrated in the figure above, the path-norm approach (orange crosses) often achieves lower robust error at higher levels of sparsity (lower nnz) compared to standard $\ell_1$ baselines (blue circles).
Conclusion and Future Directions
The authors provide a rigorous framework for optimizing the 1-path-norm in shallow networks, yielding models that are both sparse and robust. While the exact proximal mapping is currently limited to one-hidden-layer architectures, the authors suggest that extending these methods to deeper networks—perhaps by applying the mapping to consecutive layer pairs—is a promising direction for future research.
Summary updated