Research map / Learning theory and algorithms / Sample complexity
Approximation theory for 1-Lipschitz ResNets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that 1-Lipschitz ResNets built from explicit Euler steps of negative gradient flows are universal approximators for scalar 1-Lipschitz functions, both with unbounded width/depth and with fixed width (d+3) when norm-constrained linear maps are interleaved.
Problem
Approximation capabilities of 1-Lipschitz residual networks: whether they can approximate any scalar 1-Lipschitz function on a compact domain, and whether this holds at fixed width.
Approach
Uses the Restricted Stone-Weierstrass theorem (lattice + point separation) and a constructive piecewise-affine argument to show that ReLU-based negative-gradient residual layers with spectral-norm constraints are dense in C_1; interleaves norm-constrained linear maps (block row-norm constraints) so width can be fixed at d+3.
Key results
- Shows that the set of 1-Lipschitz ResNets with ReLU negative-gradient residual layers is dense in scalar 1-Lipschitz functions on compact domains (unbounded width and depth).
- Proves that every scalar piecewise affine 1-Lipschitz function is exactly representable by the proposed architecture.
- Shows density holds with fixed width h = d+3 by interleaving norm-constrained linear maps between residual blocks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ReLU residual blocks based on explicit Euler steps of negative gradient flows, with width and depth allowed to grow | 1-Lipschitz ResNets · compact domains | approximation capability | Helped |
| insert suitably constrained linear maps between residual blocks | 1-Lipschitz ResNets with fixed width · compact domains | approximation capability | Helped |
Limitations
- Unbounded-width result relies on an unconstrained lifting layer Q, which is hard to enforce in implementation.
- Fixed-width construction needs affine maps between residual steps that are not 1-Lipschitz as maps on the full space, restricting the residual maps to a smaller set.
- Results are purely theoretical; extension to vector-valued functions with Lipschitz enforcement is left for future work.
Experimental setup
Builds on: Restricted Stone-Weierstrass Theorem Proximal/gradient-flow 1-Lipschitz residual networks (Neural ODE-based Lipschitz GroupSort / MaxMin activations
Closest papers by meaning
- Characterizing ResNet's Universal Approximation Capability (ICML 2024 · similarity 0.90)
- A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations (ICML 2025 · similarity 0.89)
- Some Fundamental Aspects about Lipschitz Continuity of Neural Networks (ICLR 2024 · similarity 0.88)
- ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks (NeurIPS 2024 · similarity 0.88)
- Monotone, Bi-Lipschitz, and Polyak-Łojasiewicz Networks (ICML 2024 · similarity 0.88)
- Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.