Efﬁcient Proximal Mapping of the 1-path-norm of Shallow Networks

Sep 17, 2026

We demonstrate two new important properties of the 1-path-norm of shallow neural networks. Despite its non-smoothness and non-convexity, it enables a closed-form proximal operator that can be computed efficiently, supporting stochastic proximal-gradient-type methods for regularized empirical risk minimization. When activation functions are differentiable, it provides an upper bound on the network’s Lipschitz constant, tighter than trivial layer-wise products, motivating robust training against adversarial perturbations.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages28

Reading Time1 h 11 min

AccessFree to download

Introduction

Robustness and sparsity in neural networks

Measuring robustness via Lipschitz constants and regularization

Existing upper-bound methods: product vs convex-optimization

Path-norm as a complexity measure

Optimization challenges and main contributions

Optimization: proximal-gradient with 1-path-norm

Efﬁcient Proximal Mapping of the 1-path-norm of Shallow Networks Fabian Latore 1 Paul Rolland 1 Nadav Hallak 1 Volkan Cevher 1 Abstract We demonstrate two new important properties of the 1-path-norm of shallow neural networks. First, despite its non-smoothness and non-convexity it allows a closed form proximal operator which can be efﬁciently computed, allowing the use of stochastic proximal-gradient-type methods for regularized empirical risk minimization. Second, when the activation functions is differentiable, it provides an upper bound on the Lipschitz constant of the network. Such bound is tighter than the trivial layer-wise product of Lipschitz constants, motivating its use for training networks robust to adversarial perturbations. In practical experiments we illustrate the advantages of using the proximal mapping and we compare the robustness-accuracy trade-off induced by the 1-path-norm, L1-norm and layer-wise constraints on the Lipschitz constant (Parseval networks) . 1. Introduction Neural networks are the backbone of contemporary applications in machine learning and related ﬁelds, having huge inﬂuence and signiﬁcance both in theory and practice. Among the most important and desirable attributes of a trained network are robustness and sparsity. Robustness, is often deﬁned as stability to adversarial perturbations, such as in supervised classiﬁcation methods. The apparent brittleness of neural networks to adversarial attacks in this context has been considered in the literature for some time, see e.g.,(Biggio et al., 2013 ; Szegedy et al., 2013 ; Madry et al., 2018) and references therein. A fundamental question in this regard is how to measure robustness, or more importantly, how to encourage it. One prominent approach supported by theory and practice (Raghunathan et al., 2018 ; Cisse et al., 2017), is to use *Equal contribution 1Learning, information and optimization systems laboratory (LIONS), EPFL, Switzerland. Correspondence to: Fabian Latorre . Proceedings of the 37th International Conference on Machine Learning, Vienna, Austria, PMLR 119, 2020 . Copyright 2020 by the author(s) . the Lipschitz constant of the network function to quantize robustness, and regularization to encourage it. This approach is also supported theoretically with generalization bounds in terms of the layer-wise product of spectral norms (Bartlett et al., 2017 ; Miyato et al., 2018), which particularly upper-bounds the Lipschitz constant. However, a recent empirical study (Jiang* et al., 2020) has found in practice a negative correlation of this measure with generalization. This casts doubts on its usefulness and signals the fact that it is a rather loose upper bound for the Lipschitz constant (Latorre et al., 2020) . Current methods that compute upper bounds on the Lipschitz constant of neural networks can be roughly classiﬁed into two classes: (i) the class of product bounds, comprising all upper bounds obtained by the multiplication of layer-wise matrix norms; and,(ii) the class of convexoptimization-based bounds, which addresses the network as a whole entity (Raghunathan et al., 2018 ; Fazlyab et al., 2019 ; Latorre et al., 2020) . A trade-off between computational complexity and quality of the upper bound seems apparent. An ideal bound would achieve a balance between both properties: it should provide a good estimate of the constant while being fast and easy to minimize with iterative ﬁrst-order algorithms. Recently, the path-norm of the network (Neyshabur et al., 2015) has emerged as a complexity measure that is highlycorrelated with generalization (Jiang* et al., 2020) . Thus, its use as a regularizer holds an increasing interest for researchers in the ﬁeld. Despite existing generalization bounds (Neyshabur et al., 2015), our understanding of the optimization aspects of the path-norm-regularized objective is lacking. Jiang* et al.(2020) refrained from using automatic-differentiation

FAQs

What two key properties of the 1-path-norm are established?

It admits an efficient closed-form proximal operator for stochastic proximal-gradient-style optimization, and—under differentiable activations—provides an upper bound on the Lipschitz constant.

Why is the Lipschitz upper bound from the 1-path-norm considered useful?

The bound is tighter than the trivial layer-wise product of Lipschitz constants, which motivates training networks to be robust to adversarial perturbations.

How does the work address optimization for the 1-path-norm-regularized objective?

It proposes an efficient optimization approach based on the new proximal mapping, avoiding issues that can arise when automatic differentiation fails for nonsmooth function compositions.

Sep 17, 2026

Uploaded by Valentina