PaperlayerView exact revision on arXiv

Source-linked AI summary

Lipschitz Bounds for Neural Networks Using a Two-Copy Linear Fractional Transformation

Felix Biertümpfel, Bin Hu, Peter Seiler

arXiv:2610.22692v1eess.SYcs.SY

TL;DR

Incremental neural-network analyses can discard bias information and limit activation constraints to differences, which may yield arbitrarily conservative bounds. This paper uses a two-copy LFT with biased quadratic constraints; its examples recover exact Lipschitz bounds where bias-blind analyses remain looser.

  • Problem

    Incremental formulations omit bias terms and restrict quadratic constraints to signal differences, and either limitation can make gain bounds arbitrarily conservative.

    Source: §I · p. 1

  • Method

    A two-copy LFT drives independent network inputs while sharing the bias input, enabling biased quadratic constraints on stacked nonlinear signals.

    Source: §I · p. 1

  • Results

    The two-copy analysis recovered exact bounds in the dead-neuron and inverted-pendulum examples, while the corresponding bias-blind analyses remained looser.

    Source: B. Dead Neuron Example · p. 11, D. Inverted Pendulum Controller · p. 12

  • Takeaways & Limitations

    Retaining bias information and using richer, non-incremental constraints can reduce conservatism in global Lipschitz analysis.

    Source: §I · p. 1, §VII · p. 13

    Verifying copositivity is co-NP-complete, so the paper uses an inner approximation to obtain a tractable semidefinite program.

    Source: A. General Setup · p. 9

Abstract

from arXiv · show

This paper proposes a new method to bound the global Lipschitz constant of a neural network (NN). Our formulation uses a two-copy linear fractional transformation (LFT) representation of the NN with stacked signals. We use biased quadratic constraints (QCs) to bound the input/output behavior of the nonlinear activation functions. We then formulate a linear matrix inequality condition, using these biased QCs, to bound the Lipschitz constant of the NN. The best (smallest) Lipschitz bound is computed via a convex, semidefinite program. There are two key distinctions of the proposed two-copy formulation in comparison to existing methods that rely on a single incremental representation with incremental signals. First, the NN bias terms are eliminated in the standard incremental representation, but appear in our formulation. Second, there is a larger class of QCs that can be expressed for the nonlinearities in our formulation than in the incremental representation. We show that our proposed formulation yields less conservative Lipschitz bounds due to these two differences. We illustrate these points via several simple, motivating examples. We also demonstrate the proposed method using a benchmark problem with a NN controller for an inverted pendulum.

I. INTRODUCTION

Incremental formulations can lose bias information and restrict activation constraints to differences, making Lipschitz bounds arbitrarily conservative. The paper presents a two-copy LFT formulation and places it in the broader LFT model of neural networks.

I. INTRODUCTION

  • Bias loss and difference-only quadratic constraints can each make incremental gain bounds arbitrarily conservative.These limitations motivate a formulation that retains bias information and permits richer constraints on the activation functions.Source: §I · p. 1
  • The two-copy LFT uses independent inputs with a shared bias input, enabling biased, nonincremental quadratic constraints on stacked nonlinear signals.The authors specialize it to global Lipschitz bounds for feedforward networks and note an extension to incremental ℓ2 analysis of dynamical systems.Source: §I · p. 1
  • For ReLU, the paper characterizes biased quadratic constraints through copositivity and designs a tailored cutting-plane algorithm for computation.The paper demonstrates the approach on examples including a dead neuron, exponentially growing Lipschitz bounds, and an inverted-pendulum controller.Source: §I · p. 2

II. PROBLEM FORMULATION

  • A neural network is modeled as a lower LFT coupling a known matrix with a repeated nonlinearity; its matrix includes bias terms.The formulation covers implicit networks, and well-posedness requires a unique solution for each input; strict lower-triangular structure of the relevant block suffices.Source: §II · p. 2
  • The problem is to verify that a well-posed network has a Lipschitz constant no greater than a specified bound.The paper first illustrates how a feedforward multilayer perceptron fits the lower-LFT representation.Source: §II · p. 2

III. BACKGROUND

Quadratic constraints provide a way to describe activation input/output behavior for Lipschitz analysis. Sector and slope restrictions yield QC classes, while richer multipliers and ReLU-specific constraints expand the available choices.

A. Quadratic Constraints (QCs)

  • A quadratic constraint characterizes activation input/output behavior and can simplify Lipschitz analysis, though the constraint may be conservative.The multiplier specifies the quadratic constraint.Source: A. Quadratic Constraints (QCs) · p. 3
  • Sector-bounded activations admit diagonal, nonnegative QC multipliers; slope-restricted activations also satisfy sector bounds.For slope-restricted functions, doubly hyperdominant matrices provide a richer multiplier class than diagonal nonnegative matrices.Source: A. Quadratic Constraints (QCs) · pp. 3–4
  • For repeated ReLU, the complete QC set is characterized by copositivity conditions and defines the largest possible class of such constraints.The complete set is denoted McReLU.Source: A. Quadratic Constraints (QCs) · p. 4

B. Incremental QCs

Incremental quadratic constraints describe activation behavior using differences between two inputs and outputs. The resulting incremental system supports an LMI sufficient condition for bounding a network’s Lipschitz constant, with the best bound obtainable by an SDP.

B. Incremental QCs

  • Incremental quadratic constraints apply to differences between two activation inputs and their corresponding outputs.For slope-restricted nonlinearities, the standard incremental QC class is defined by diagonal, nonnegative multipliers.Source: B. Incremental QCs · p. 4

C. Global Lipschitz Bounds

  • In the incremental LFT, biases cancel from the equations, while still affecting the mapping through the nominal activation input.The nonlinear output difference depends on both original inputs, not generally on the input difference alone.Source: C. Global Lipschitz Bounds · pp. 4–5
  • An incremental QC and a feasible LMI provide a sufficient condition that the network’s Lipschitz constant is bounded by γ.When the multiplier set has affine constraints, minimizing the bound is a convex semidefinite program.Source: C. Global Lipschitz Bounds · p. 5
  • For slope-restricted activations, strict feasibility of the specified LMI can also establish network well-posedness.The cited result applies to the stated multiplier set for activations slope restricted to [0, 1].Source: C. Global Lipschitz Bounds · p. 5

IV. MAIN RESULTS

The section shows why incremental Lipschitz analysis can be conservative: it removes bias information and restricts the available quadratic constraints. A two-copy view can retain both biases and a richer class of constraints.

A. Motivation

  • LipSDP gives γ = 4 for the example although its true Lipschitz constant is γtrue = 2, even with the complete incremental ReLU multiplier set.The complete set gives the least conservative bound achievable within the LipSDP framework.Source: A. Motivation · pp. 5–6
  • For bias b1 = [−1 1]⊤, the true Lipschitz constant is 4, while the bias-free case has a true constant of 2.LipSDP gives the same bound for all bias choices because its condition does not involve the biases.Source: A. Motivation · p. 6
  • Incremental QCs constrain only input and output increments, excluding valid joint constraints on the two separate copies.The section identifies bias elimination and this restriction on QCs as sources of conservatism in incremental analysis.Source: §IV · p. 5, A. Motivation · p. 6
  • The stacked function admits valid QCs beyond those with the special block structure induced by incremental QCs, and these additional choices can reduce conservatism.This larger class can couple the two copies' inputs and outputs.Source: A. Motivation · p. 6

B. Lipschitz Bounds With Extended LFT System

The extended system runs two copies of the network on independent inputs while sharing the constant input associated with the biases. Its output difference is used to establish a Lipschitz bound.

B. Lipschitz Bounds With Extended LFT System

  • The two copies receive independent inputs and share the constant input associated with the biases; the stacked output is Δy = ȳ − ŷ.Bounding the output difference by γ times the input difference gives a Lipschitz bound for the original network.Source: B. Lipschitz Bounds With Extended LFT… · p. 6
  • The stacked system is represented as an interconnection of the matrix Gs and the stacked nonlinearity Φs, with the two copies' signals stacked together.Φs maps the stacked inputs vs to stacked outputs ws.Source: B. Lipschitz Bounds With Extended LFT… · pp. 6–7, Figure 5 · p. 7
  • Unlike the incremental system, the stacked system retains bias term G21 and the signals needed to express a larger class of QCs.This supports constraints beyond those expressible using incremental QCs.Source: B. Lipschitz Bounds With Extended LFT… · p. 7

C. Bias Quadratic Constraints

Biased quadratic constraints augment the usual nonlinearity signals with a constant coordinate, allowing affine and constant terms. The section derives a complete characterization of these constraints for ReLU.

C. Bias Quadratic Constraints

  • A biased QC is defined on [1, v, w], allowing its quadratic form to include affine and constant terms that ordinary QCs lack.The paper uses these constraints to retain bias-dependent information.Source: C. Bias Quadratic Constraints · p. 7
  • The paper derives a complete set of biased QCs for ReLU, extending the nonincremental results in to the biased setting.The characterization is stated for the repeated ReLU nonlinearity.Source: C. Bias Quadratic Constraints · p. 7
  • The ReLU characterization uses 2m copositivity conditions from possible sign patterns, and the theorem states that membership in this set is necessary and sufficient for satisfying the biased QC.The theorem characterizes the full set of biased ReLU QCs.Source: C. Bias Quadratic Constraints · p. 7

D. Analysis Condition With Extended System

The analysis condition is an LMI on the stacked system and a candidate Lipschitz bound. When its assumptions hold, feasibility certifies that bound for the network.

D. Analysis Condition With Extended System

  • If the stacked nonlinearity satisfies a biased QC and Le(Mb, γ^2) ⪯ 0 for γ ≥ 0, then γ bounds the network's Lipschitz constant.The theorem assumes the neural network is well-posed.Source: D. Analysis Condition With Extended… · p. 8
  • The proof uses the biased QC to obtain ∥Δy∥2 ≤ γ∥Δu∥2, which establishes the claimed Lipschitz bound.The QC applies to the stacked nonlinearity.Source: D. Analysis Condition With Extended… · pp. 8–9
  • The condition depends on bias G21 and uses nonincremental QCs; it can yield smaller bounds than the incremental condition, with improvement dependent on the problem.The stacked-system analysis is no more conservative than the incremental analysis.Source: D. Analysis Condition With Extended… · p. 8

V. COMPUTATIONAL APPROACH

The computational approach minimizes the Lipschitz bound through an SDP over valid biased-QC multipliers. For repeated ReLU, a cutting-plane method manages the complete multiplier constraints, which involve copositivity.

A. General Setup

  • Theorem 3’s LMI yields the smallest bound within the chosen biased-QC multiplier set by solving an SDP with affine multiplier constraints.Larger multiplier classes generally reduce conservatism at the cost of increased numerical complexity.Source: A. General Setup · p. 9
  • The complete repeated-ReLU multiplier set uses 4m copositivity conditions, but checking copositivity is co-NP-complete and its SDP inner approximation is generally not exact.The relaxation is guaranteed exact for m = 1.Source: A. General Setup · p. 9

B. Cutting-plane Algorithm for Complete Set of ReLU

  • The cutting-plane method solves a master SDP on a working subset, searches for violated constraints among the full set, then adds selected violations.Only a fraction of the 4m constraints are usually active, motivating the working subset.Source: B. Cutting-plane Algorithm for… · p. 9
  • For sufficiently small networks, the method tests all 4m activation patterns and terminates when none violates a constraint.For larger networks, it combines Hamming-neighborhood search to find candidate cuts with uniformly sampled patterns for its randomized stopping test.Source: B. Cutting-plane Algorithm for… · p. 10
  • With no violations in an independent validation sample of at least Nreq patterns, the probability of a relaxation violation is at most εv with confidence of at least 1 − βv.The Hamming samples identify cuts but are not used in the randomized stopping test.Source: B. Cutting-plane Algorithm for… · p. 10

VI. NUMERICAL EXAMPLES

The examples test the proposed analysis with several biased-QC parameterizations, including a ReLU network with a dead neuron and an inverted-pendulum controller. The motivating and dead-neuron examples show cases where the complete multiplier set recovers the true Lipschitz constant.

VI. NUMERICAL EXAMPLES

  • The numerical examples include a ReLU feedforward network with a dead neuron and a network with an exponentially growing Lipschitz bound, followed by an inverted-pendulum NN controller.The analyses compare four biased-QC parameterizations.Source: §VI · pp. 10–11

A. Motivating Example Revisited

  • For bias [1, −1]⊤, only the complete-set multiplier recovers the true value 2; the simple, nonnegative, and copositive multipliers give 4.For the bias-free case, the nonnegative, copositive, and complete-set multipliers recover 2, while the simple multiplier gives 4; all four give 4 for bias [−1, 1]⊤.Source: A. Motivating Example Revisited · p. 11

B. Dead Neuron Example

  • γ = 1.4142 matches the dead-neuron network’s true Lipschitz constant, while incremental LipSDP gives 28.284.The nonnegative and copositive multipliers take less than 0.8 s; the complete-set cutting-plane analysis takes approximately 3.2 s and checks all 4m patterns for this m = 4 network.Source: B. Dead Neuron Example · p. 11

C. Exponentially Growing Lipschitz Bound

The repeated-layer example shows that incremental bounds can grow exponentially despite a true Lipschitz constant of 1, while the inverted-pendulum comparison shows the benefit of a complete biased QC. The section concludes that retaining biases and using richer QCs can reduce conservatism.

C. Exponentially Growing Lipschitz Bound

  • 2^N: standard LipSDP gives this exponentially growing bound for repeated layers although the deep network’s exact Lipschitz constant remains 1.The single network has true Lipschitz constant 1 and a standard LipSDP bound of 2; the observation is independent of QC parameterization.Source: C. Exponentially Growing Lipschitz Bound · p. 11
  • Approximately 1: the proposed analysis’s copositive, nonnegative, and complete-set multipliers recover a depth-independent bound, unlike its simple affine multiplier.The table reports bounds for N repeated hidden layers using different biased QC parameterizations.Source: C. Exponentially Growing Lipschitz Bound · pp. 11–12, Table I · p. 12

D. Inverted Pendulum Controller

  • The reduced controller has 12 hidden neurons and an exact Lipschitz constant of 0.8649, about 2.5% different from the benchmark controller’s.It imitates the released controller from closed-loop rollout samples, with RMSE 3.2 · 10^-3, and satisfies the stated specification on the validation grid.Source: D. Inverted Pendulum Controller · p. 12
  • 0.8649: the biased complete-set multiplier matches the enumerated global Lipschitz constant, while the other three multipliers and the bias-blind analysis give 0.9637.The cutting-plane algorithm takes approximately 300 s to converge; exhaustive separation over 4^12 sign patterns is described as computationally prohibitive.Source: D. Inverted Pendulum Controller · pp. 12–13, Table II · p. 12

VII. CONCLUSION

  • The two-copy LFT retains bias information and permits richer nonincremental biased QCs, which the conclusion identifies as ways to reduce conservatism.The conclusion notes that future work will consider local Lipschitz bounds using the stacked system representation.Source: §VII · p. 13

APPENDIX

The appendix gives biased quadratic-constraint classes for bounded and hyperbolic-sector nonlinearities, then presents several ReLU-specific constructions. For ReLU, the elementwise nonnegative multiplier class is a tractable inner approximation of the copositive class.

A. Examples of Biased-QCs

  • Componentwise bounds alone yield biased QCs for nonlinearities whose function values lie between specified lower and upper bounds.This construction does not exploit additional structure from the repeated nature of the nonlinearity.Source: A. Examples of Biased-QCs · p. 13
  • Hyperbolic-sector-bounded nonlinearities also admit biased QCs under the stated sector parameters.The passage identifies this class as previously proposed in [34].Source: A. Examples of Biased-QCs · p. 13
  • For ReLU, the appendix lists affine and copositive biased QC classes, with the copositive construction using ReLU’s componentwise relations and complementarity.The simple affine class is attributed to and the copositive class to.Source: A. Examples of Biased-QCs · pp. 13–14
  • Elementwise nonnegative ReLU multipliers provide a tractable inner approximation of the copositive multiplier class.The construction relies on every elementwise nonnegative symmetric matrix being copositive.Source: A. Examples of Biased-QCs · p. 14

B. Efficient Separation Procedure

The efficient separation procedure tests candidate feasibility with inexpensive checks before invoking the separation SDP. Elementwise nonnegativity and positive semidefiniteness can certify feasibility, while a negative diagonal entry certifies violation.

B. Efficient Separation Procedure

  • Elementwise nonnegativity certifies a candidate as feasible by choosing the nonnegative matrix equal to the tested matrix, avoiding a separation SDP.This is the first check in the procedure.Source: B. Efficient Separation Procedure · p. 14
  • A negative diagonal entry of the tested matrix certifies violation because no nonnegative matrix can be subtracted from it to yield a positive semidefinite matrix.The smallest diagonal entry also supplies a lower bound on the separation gap and a violation score.Source: B. Efficient Separation Procedure · p. 14
  • If earlier checks are inconclusive, positive semidefiniteness can certify feasibility with the zero nonnegative matrix; candidates still unresolved proceed to the separation SDP.The PSD test uses a shifted Cholesky factorization within numerical tolerance.Source: B. Efficient Separation Procedure · p. 15

C. Randomized Separation and Cut Selection

The randomized separation procedure combines Hamming-guided candidates with uniform-random exploration to find violated constraints, then uses a fresh independent random sample for its stopping test. It selects a limited, diversity-constrained set of violations for each cutting-plane iteration and independently validates the final multiplier.

C. Randomized Separation and Cut Selection

  • The search combines Hamming-distance neighbors of recent cuts with uniform-random patterns, reserving guided samples for finding candidate cuts rather than the stopping test.Guided candidates are capped at 25% of the initial search budget; up to ten recent cuts serve as parent patterns.Source: C. Randomized Separation and Cut… · p. 15
  • After the search detects no violations, a fresh independent set of Nreq uniform samples is used for the randomized stopping test; no detected violation there permits convergence.When violations are sparse, additional uniform-random exploration is performed before the stopping test.Source: C. Randomized Separation and Cut… · pp. 15–16
  • Each iteration retains up to 150 unique violations and adds up to 50 high-scoring cuts, requiring Hamming distance of at least two among cuts selected that iteration.The final multiplier is also checked on an independent validation set of at least Nreq patterns.Source: C. Randomized Separation and Cut… · pp. 15–16
Loading 2610.22692v1…