Sorting out Lipschitz function approximation

Cem Anil; James Lucas; Roger Grosse

Source-linked AI summary

Sorting out Lipschitz function approximation

Cem Anil, James Lucas, Roger Grosse

arXiv:1811.05381v2Nov 13, 2018cs.LGstat.ML

TL;DR

Strict Lipschitz constraints can limit neural-network expressivity, especially when layers must preserve gradient norms. The paper combines GroupSort activations with norm-constrained weights, proving universal approximation and reporting stronger empirical performance for Wasserstein estimation and robust classification. A key scope boundary is that spectral normalization is not gradient-norm-preserving by construction, and empirical Wasserstein estimates may be loose relative to the data-generating distribution.

Problem
Strict Lipschitz constraints provide useful guarantees but can create expressive limitations, motivating architectures that retain expressivity under norm constraints.
Method
The paper combines the gradient-norm-preserving GroupSort activation with norm-constrained, including orthonormal, weight matrices.
Results
Norm-constrained GroupSort networks are provably universal Lipschitz function approximators and empirically provide better Wasserstein estimates and adversarial robustness than existing architectures.
Takeaways & Limitations
Gradient norm preservation enables expressive Lipschitz networks that support Wasserstein distance estimation and provable adversarial robustness.
Takeaways & Limitations
Spectral normalization is not gradient norm preserving by construction, and the Wasserstein distance to the empirical distribution may be a loose upper bound on the distance to the data-generating distribution.

Abstract

from arXiv · show

Training neural networks under a strict Lipschitz constraint is useful for provable adversarial robustness, generalization bounds, interpretable gradients, and Wasserstein distance estimation. By the composition property of Lipschitz functions, it suffices to ensure that each individual affine transformation or nonlinear activation is 1-Lipschitz. The challenge is to do this while maintaining the expressive power. We identify a necessary property for such an architecture: each of the layers must preserve the gradient norm during backpropagation. Based on this, we propose to combine a gradient norm preserving activation function, GroupSort, with norm-constrained weight matrices. We show that norm-constrained GroupSort architectures are universal Lipschitz function approximators. Empirically, we show that norm-constrained GroupSort networks achieve tighter estimates of Wasserstein distance than their ReLU counterparts and can achieve provable adversarial robustness guarantees with little cost to accuracy.

2. Background

The paper defines Lipschitz networks by constraining each layer and motivates them through robustness, generalization, Wasserstein estimation, and related applications.

Network notation: A neural-network layer computes an affine transformation followed by an activation, with the network output given by the final pre-activation.The notation uses W_l and b_l for layer weights and biases, z_l for pre-activations, and h_l for activations.
Lipschitz construction: A 1-Lipschitz network can be built by composing 1-Lipschitz affine transformations and activations.The composition property extends the construction to K-Lipschitz functions by scaling the output by K.
Lipschitz construction: Constraining each linear map to be 1-Lipschitz is equivalent to requiring its matrix p-norm to be at most 1.The matrix 2-norm is the largest singular value, while the matrix ∞-norm has a row-sum characterization.
Lipschitz construction: Common activations, including ReLU, tanh, and maxout, are 1-Lipschitz when appropriately scaled.Being 1-Lipschitz alone does not establish the expressive properties studied later in the paper.
Applications: Small Lipschitz constants are associated with adversarial robustness, generalization, and interpretable gradients, while Wasserstein distance estimation optimizes over 1-Lipschitz functions.The paper also identifies regularization and GAN stabilization as applications of Lipschitz constraints.

3. Gradient Norm Preservation

The paper argues that expressive norm-constrained networks must preserve gradient norms during backpropagation, motivating orthonormal weights and gradient-norm-preserving activations.

Necessary condition: In a norm-constrained 1-Lipschitz network, gradient norms cannot increase as they pass through layers.Representing scalar functions with input-output gradient norm 1 almost everywhere therefore requires preservation at every layer.
Necessary condition: If a matrix-2-norm-constrained network with monotonic 1-Lipschitz activations has gradient norm 1 almost everywhere, then the represented function is linear.Thus common monotonic activations cannot retain both full gradient norm and nonlinear processing under these constraints.
ReLU limitation: For ReLU layers, gradient norm preservation requires every output-relevant activation to remain positive, forcing the input-output mapping to be linear.The paper notes an exception for units that do not affect the network output.
Empirical implication: As the Lipschitz constant decreases, networks sacrifice nonlinear processing capacity to maintain adequate gradient norm.This tension is examined empirically later in the paper.
Orthonormal weights: Each weight matrix can be replaced without changing the computed function by one whose singular values all equal 1.Such matrices are orthonormal in the paper’s terminology and preserve gradient norms more directly than merely bounding singular values.

4. Methods

The method combines GroupSort activations with norm-constrained or orthonormal weight matrices to construct expressive 1-Lipschitz networks and support robustness applications.

Design principle: The architecture targets 1-Lipschitz networks by requiring every layer to be 1-Lipschitz, with K-Lipschitz functions obtained by output scaling.The focus is on L2 and L∞ metrics.
GroupSort activation: GroupSort sorts pre-activations within groups and outputs the combined sorted vector as a general-purpose 1-Lipschitz activation.Its Jacobian is a permutation matrix, so it preserves every vector p-norm and therefore gradient norms.
Activation variants: Grouping size 2 is called MaxMin, while sorting the entire input is called FullSort; the two operations are equally expressive under the norm constraint.FullSort can emulate MaxMin through paired biases or be implemented by successive MaxMin layers, although it can be harder to train.
Geometric interpretation: Under the matrix 2-norm constraint, MaxMin has the expressive power of absolute value and can support folding along arbitrary hyperplanes through rigid transformations.This gives a geometric interpretation of how these networks represent nonlinear functions.
Weight constraints: The method enforces orthonormality so all weight singular values equal 1, using differentiable Björck operations during training.The paper also discusses projections, Parseval networks, spectral normalization, and ∞-norm weight projections as practical alternatives or complements.
Scope: The analyses are presented for fully connected layers but also apply to convolutions after unfolding them into linear transformations.Bounding the spectral norm of convolutional filters bounds the spectral norm of the unfolded operation.
Adversarial robustness: For robustness, a classifier with Lipschitz constant K is guaranteed robust to L∞ perturbations of size ϵ when its margin satisfies M(x) > Kϵ/2.Training uses an ∞-norm-constrained-weight multiclass hinge loss with κ controlling margin enforcement.

5. Related Work

Prior Lipschitz-network methods either lack global guarantees or restrict expressive power, while classical universality constructions generally violate the required norm constraints.

Existing Lipschitz methods: Regularization methods can perform well empirically but do not provably enforce Lipschitz constraints globally.Architectural methods constrain layer operator norms and provide guarantees, but can reduce expressive power.
Motivation: Theoretical and empirical work connects smaller network Lipschitz constants with generalization performance and adversarial robustness.Non-vacuous generalization bounds can be derived when the network Lipschitz constant is small.
Universal approximation gap: Classical universal-approximation constructions use large Lipschitz constants, so they do not directly apply to Lipschitz-constrained networks.Earlier work also showed that ∞-norm-constrained ReLU networks cannot approximate absolute value.

6. Universal Approximation of Lipschitz Functions

The paper establishes that norm-constrained GroupSort networks universally approximate Lipschitz functions, using lattice structure and point separation. The result applies to bounded domains with specified norm constraints, while universality under 2-norm constraints remains open.

Universal approximation results for continuous functions do not directly apply to Lipschitz networks because their constructions typically use large Lipschitz constants.
Norm-constrained GroupSort networks approximate any Lipschitz function in Lp distance by forming a lattice that separates points.The proof uses a restricted Stone-Weierstrass theorem as the universality criterion.
Theorem 3 proves density for fully connected networks with group-size-2 GroupSort activations and prescribed ∞-norm constraints on weight matrices.The first weight matrix satisfies ||W1||p,∞ = 1, while subsequent matrices satisfy ||W||∞ = 1.
The construction preserves point separation by fitting a 1-Lipschitz single-layer line through prescribed values whose difference does not exceed the input distance.
GroupSort combines networks through concatenated and block-diagonal layers, then computes pointwise maxima or minima from their outputs.This closure under max and min supplies the lattice property required by the universality proof.
Universality is established in the L∞ setting as density in 1-Lipschitz functions under the L∞ metric, but analogous universality for 2-norm-constrained GroupSort networks remains open.The authors report no empirically unapproximable function for the 2-norm version, while noting that the construction relies on ∞-norm constraints.

7. Experiments

The experiments test whether norm-constrained GroupSort networks retain expressivity and perform competitively on Wasserstein estimation, gradient-capacity use, and robust classification. GroupSort generally outperforms non-gradient-norm-preserving activations, especially as dimensionality increases.

Quantifying expressive power: The experiments evaluate expressivity on absolute-value and circular-cone approximation tasks, including higher-dimensional cones.The Wasserstein objective is used to assess how closely learned functions match analytically specified optimal dual surfaces.
Quantifying expressive power: Non-GNP activations cannot approximate the absolute value function effectively, although increasing depth provides some improvement.The representational barrier becomes more limiting as the problem dimensionality increases.
Quantifying expressive power: Non-GNP networks can distort circular-cone shapes when increasing slope, and increasing the Lipschitz constant does not fix this WGAN-critic pathology.Optimal critics for different Lipschitz constants are equivalent up to scaling.
Quantifying expressive power: Increasing dimensionality causes significant Wasserstein-objective drops for non-GNP activations, while depth only slightly improves performance; shallow FullSort approximates high-dimensional cones easily.MaxMin performs better but requires large depth to learn the optimal solution.
Gradient norm preservation: The GroupSort network uses the 10-Lipschitz capacity more tightly than the ReLU network, whose observed Lipschitz constant is closer to 8 than 10.The comparison uses the spectral-radius distribution of network Jacobians on MNIST.
Gradient norm preservation: Lipschitz-constrained ReLU training increases positive activations, leaving about 10% of units active all the time and reducing nonlinear processing.These activation-statistics changes indicate compromises made to maintain adequate gradient norm.
Wasserstein distance estimation: Norm-preserving activations produce tighter lower bounds when estimating Wasserstein distance between MNIST and CIFAR10 GAN generator and data distributions.The estimators are independent 1-Lipschitz feedforward networks trained after freezing the generators.
Robustness and interpretability: The Lipschitz classifiers support theoretical accuracy lower bounds against perturbations of strength ϵ, while Lipschitz networks also exhibit interpretable gradients without adversarial training.The experiments report that the architecture could not match margin training’s large-perturbation performance with the tested capacity.

8. Conclusion

The paper identifies gradient norm preservation as critical for expressive Lipschitz networks and combines GroupSort with orthonormal weights. The resulting networks are provably universal 1-Lipschitz approximators and improve Wasserstein estimation and provable robustness empirically.

Conclusion: Gradient norm preservation is critical to Lipschitz network expressivity, and GroupSort with orthonormal weights yields provably 1-Lipschitz universal approximators.The paper reports empirical gains in expressivity, Wasserstein estimation, and provable adversarial robustness.

Appendices

The appendices explain how GroupSort networks compute simple functions, compare GroupSort with other activations, and analyze grouping size and computational complexity.

Appendices: The appendices cover GroupSort visualizations, activation comparisons, grouping-size expressivity, and computational complexity.

A.1. Visualizing GroupSort Networks

The appendix visualizes GroupSort’s computation of simple 1D functions and establishes relationships among GroupSort, absolute value, and common activations. It also discusses equivalent grouping sizes and implementation cost.

Visualizing GroupSort Networks: GroupSort networks visualize approximations of the absolute-value function and a slope-1 curve resembling “W”.The examples use one hidden layer with two units and two hidden layers with four units, respectively.
Activation comparisons: MaxMin and FullSort can recover ReLU, Leaky ReLU, concatenated ReLU, and maxout through sorting and linear transformations.Maxout with groups of size k is obtained by selecting the first sorted element from each group.
Expressivity: GroupSort activations with different grouping sizes have the same expressive power, and GroupSort and absolute-value networks are equally expressive under the matrix 2-norm constraint.
Expressivity: FullSort implements MaxMin by separating biased activation pairs into distinct magnitude scales, while MaxMin layers can implement FullSort using BubbleSort.The BubbleSort construction uses permutation matrices for weights.
Expressivity: The constructions preserve the matrix 2-norm constraint by choosing B so that 2x + √2B remains positive throughout the domain.
Computational complexity: A naive CPU GroupSort implementation costs n k O(k log k), but GPU parallelization makes its additional training and inference cost comparatively small.MaxMin can be implemented with a custom CUDA kernel at efficiency comparable to ReLU.
Weight constraints: Parseval updates differ from the paper’s forward-pass optimization because they update weights after the primary gradient step, whereas the proposed approach directly optimizes near the Stiefel manifold.The proposed method is more expensive but keeps weights close to orthonormal during training.

B.2. Comparing Bj¨orck and Spectral Normalization

Bj¨orck orthonormalization provides a differentiable route to norm-constrained weights, and experiments show faster convergence and better high-dimensional cone approximation than spectral normalization.

Spectral normalization constrains each weight matrix’s largest singular value below 1, but all singular values rarely equal 1 in practice.
1-Lipschitz networks are evaluated by fitting distributions whose exact Wasserstein Distance is 1 and whose optimal dual surface is a unit-gradient cone.
Bj¨orck-trained networks approximate high-dimensional cones better and converge faster than spectral-normalized networks, with the performance gap increasing with dimensionality.
The Bj¨orck algorithm converges when ||W^T W − I||2 < 1, achievable by scaling weights so all singular values are at most 1 beforehand.
Matrix-vector-product implementations reduce Bj¨orck computation, but the method requires O(3^k) matrix-vector products and scales poorly for many iterations.
With norm-preserved gradients, constrained weight matrices can be replaced by matrices whose singular values all equal 1 without changing the computed function.

E. Universal Approximation of 1-Lipschitz Functions

GroupSort networks with suitable norm constraints are dense in continuous 1-Lipschitz functions on compact domains, using lattice constructions based on max and min operations.

The resulting network class forms a lattice that separates points, so the restricted Stone-Weierstrass theorem yields density in continuous functions.
The approximation proof constructs G with ||g − G||∞ < ϵ by finite max-min combinations of functions in the lattice.
Theorem 3 establishes density in C_L(X, R) for GroupSort networks with group size 2 and specified Lp,∞ and L∞ norm constraints.
The proof constructs max(f, g) and min(f, g) using parallel channels, block-diagonal weights, and a final MaxMin operation.
Different-depth networks are aligned by inserting identity layers representable with MaxMin activations.
The result extends to vector-valued 1-Lipschitz functions under L∞ distance by applying the construction coordinatewise.

G.1. Classification

Across classification and generative experiments, GroupSort-based Lipschitz networks remain expressive, improve constrained classification behavior, and produce near-isometric Jacobians relative to ReLU networks.

Lipschitz neural networks learn expressive classifiers without sacrificing performance on benchmark classification tasks.
GroupSort performs well for classification, particularly when the Lipschitz constraint is enforced, while spectral Jacobian regularization is most effective by classification performance.
Parseval networks may fail to remain 1-Lipschitz under early stopping because small β values converge slowly toward orthonormal weights.
Lipschitz-constrained networks significantly improve generalization in limited-data experiments, although Dropout is the most effective regularizer in that setting.
MaxMin can replace ReLU in WGAN architectures using gradient-norm penalties, while the authors defer a more thorough study of this setting.
In 2-norm-constrained MNIST classifiers, ReLU Jacobian singular values spread from 4–8, whereas GroupSort concentrates them between 9–10.

H.5. Robustness and Interpretability

The robustness experiments use projected fully connected MNIST classifiers and evaluate adversarial attacks, while interpretability experiments visualize input-output gradients under 2-norm constraints.

Adversarial robustness experiments train three-hidden-layer MNIST classifiers with 1024 units per layer and project each weight-matrix row after every update.
The FGS and PGD attacks required stronger settings to generate adversarial examples for the Margin-0.3 MaxMin network.
Interpretability visualizations compute input-output gradients with respect to the loss using 2-norm-constrained networks, which make uniform gradient scale easier to display.
WGAN critics using gradient-norm-preserving units were evaluated on MNIST and CIFAR10 samples.