ECLipsE-Gen-Local: Efficient Compositional Local Lipschitz Estimates for Deep Neural Networks
Authors: Yuezhu Xu
S Sivaranjani
Venue: Accepted by TMLR ()

Abstract: The Lipschitz constant is a key measure for certifying the robustness of neural networks to input perturbations. However, computing the exact constant is NP-hard, and standard approaches to estimate the Lipschitz constant involve solving a large matrix semidefinite program (SDP) that scales poorly with network size. Further, there is a potential to efficiently leverage local information on the input region to provide tighter Lipschitz estimates. We address this problem here by proposing a compositional framework that yields tight yet scalable Lipschitz estimates for deep feedforward neural networks. Specifically, we begin by developing a generalized SDP framework for Lipschitz estimation that is highly flexible, accommodating heterogeneous activation function slope bounds for each neuron on each layer, and allowing Lipschitz estimates with respect to arbitrary input-output pairs in the neural network and arbitrary choices of sub-networks of consecutive layers. We then decompose this generalized SDP into a equivalent small sub-problems that can be solved sequentially, yielding the ECLipsE-Gen series of algorithms, with computational complexity that scales linearly with respect to the network depth. We also develop a variant that achieves near-instantaneous computation through closed-form solutions to each sub-problem. All our algorithms are accompanied by theoretical guarantees on feasibility and validity, serving as strict upper bounds on the true Lipschitz constant. Next, we develop a series of algorithms, termed as ECLipsE-Gen-Local, that explicitly incorporate local information on the input region to provide tighter Lipschitz constant estimates. Our experiments demonstrate that our algorithms achieve substantial speedups over a multitude of benchmarks while producing significantly tighter Lipschitz bounds than global approaches. Moreover, we demonstrate that our algorithms provide strict upper bounds for the Lipschitz constant with values approaching the exact Jacobian from autodiff when the input region is small enough. Finally, we demonstrate the practical utility of our approach by showing that our Lipschitz estimates closely align with network robustness. In summary, our approach considerably advances the scalability and efficiency of certifying neural network robustness, while capturing local input–output behavior to deliver provably tighter bounds, making it particularly suitable for safety-critical and adaptive learning tasks.

Published in Transactions on Machine Learning Research (03/2026)
ECLipsE-Gen-Locai: Efficient Compositional Local Lipschitz Estimates for Deep Neural Networks
Yuezhu Xu Edwardson School of Industrial Engineering Purdue University
rul mu17320purdue.commmmmm edu
S. Sivaranjani
sseetha Spurdue edu
Edwardson School of Industrial Engineering Purdue University
Reviewed on OpenReview: https: // openreview. net/ forum? id= CugnFjeu5a
Abstract
The Lipschitz constant is a key measure for certifying the robustness of neural networks to imput perturbations. However, computing the exact constant is NP-hard, and standard approaches to estimate the Lipschitz constant involve solving a large matrix semidefinite program (SDP) that scales poorly with network size. Further, there a potential to efficiently leverage local information on the input region to provide tighter Lipschitz estimates. We address this problem here by proposing compositional framework that yields tight yet scalable Lipschitz estimates for deep feedforward neural networks. Specifically, we begin by developing generalized SDP framework for Lipschitz estimation that is highly flexible, accommodating heterogeneous activation function slope bounds for each neuron on each layer, and allowing Lipschitz estimates with respect to arbitrary input-output pairs in the neural network and arbitrary choices of sub-networks consocutive layers. We then decompose this generalized SDP into equivalent small sub-problems that can be solved sequentially, yielding the ECL.ipsE-Gen series of algorithms, with computational complexity that scales linearly with respect to the network depth. We also develop variant that achieves near- instantancous computation through closod-form solutions to cach sub-problem. All our algorithuo hiss are accompanied by theoretical guarantees on feasibility and validity, serving as strict upper bounds on the true Lipschitz constant. Next, we develop a series of algorithms, termed as Laei-oaa-GeeLLoall F that explicitly incorporate local information on the input region to provide tighter Lipschitz constant estimates. Our experiments demonstrate that algorithms achieve substantial speedups over multitude of benchmarks while producing significantly tighter Lipschitz bounds than global approaches. Moreover, demonstrate that our algorithms provide strict upper bounds for the Lipschitz constant with values approaching the exact Jacobian from autodiff when the input region is small enough. Finally, we demonstrate the practical utility of our approach by showing that our Lipschitz estimates summary, our approach considerably advances
closely align with network robustness. the scalability and efficiency of certifying neural network robustness, while capturing local input-output behavior to deliver provably tighter bounds, making it particularly suitable for safety-critical and adaptive learning tasks.
This work was partially supported by the Air Force Office of Scientific Research grant, FA9550-23-1-0499 http:://wthaaacccoocceeeuee//// com./Yuezhuux//CI.ppt and the associated Python package can be installed via
"Our code available at ftttps://githuu... PyP1 at hhtpp::/pyppi http://pp...o/pooooo//////ssaaaa

---

Published in Transactions on Machine Learning Research (03/2026)
1 Introduction
Neural networks (NNs) are extensively deployed in wide range of domains (LeCun et al. (2015) from
autonomous systems (Antsaklis et al. (1990): Tang et al. (2022)) ). power system (Haque & Kashtiban 2000
to medical diagnostics (Amato el al.] 2013 While AN-based models have achieved remarkable performance,
it remains a major challenge to provide rigorous guarantees on the behavior of NNs,, especially in safety- critical
applications. Specifically, it is desirable to provide robustness certificates (Carlini & Wagner (2017); Zhang
ct al. (2018); Fazlyab et al. (2020); Tan & Wu (2024); Fazlyab et al. (2023)) ), achieve resilience against
adversarial attacks (Tsuzuku et al. (2018); Amini & Ghaemmaghami (2020): F Finlay et al. (2018); Zihhle &
Kudenko (025 ), and ensure stability in NN-based control, (Aswani et al. (2013); Brunke et al. (2022) Yin
el al. [2021); ;; Xu & Sivaranjani (2023); Sun et al. (2019). In these applications, it is essential to characterize
the behavior of model outputs under imput perturbations to ensure safety and robustness.
One widely adopted metric is the Lipschitz constant, which quantifics the worst-casc output deviation per unit input change. Despite its fundamental role in certifying robustness, computing the exact Lipschitz constant of a neural network is NP-hard (Virmaux & Scaman| (2018)). Consequently, significant efforts have been made to obtain tight and provable upper bounds for feedforward networks (FNNs) and variety of network architectures beyond, such as convolutional neural networks (CNNs), and residual networks (Pauli et al. [2023); ; Wang et al.] (2024); Pauli et al. (2024); Fazlyab et al. (2023) ) For FNNs, both global and local Lipschitz bounds are addressed in these studies, considering networks with different type of activation functions, such as piecewise linear (most commonly ReLU) (Virmaux & Scaman (2018)), differentiable Latorre et al. (2020)), or general ones (Xu & Sivaranjani (2024)). Also, Lipschitz constants defined for various norm choices, such as l- (Jordan & Dimakis (2020)), lp- (Virmaux & Scaman (2018)), fac- (Shi et al.
(2022)), and cross-norms (Wang et al. (2022)) ), are investigated. A detailed compilation of these works is presented later in this section.
In this paper, we focus on the problem of estimating both the global and local fz-norm Lipschitz constants for FNNs. The fz-norm is a standard robustness metric in signal processing, control theory, and scientific modeling domains (Fazlyab et al. (2019); Tsuzuku et al. (2018)). It also plays a central role in reachability analysis for NN-based models, which is crucial in safety-critical control applications like autonomous driving, robotics, and power systems (Ruan et al. (2018): [Everett et al. (2021); ; Xiang et al. (2020); Huang al. (2019))- Tn machine learning, many theoretical generalization bounds for NNs are directly linked to their L2-Lipschizz constant (Bartlett et al. (2017); Neyshabur et al. (0117) ). These applications have also motivated
the development of methods to design NNs with certifiable robustness guarantees Huang et al. (2021)
Fazlyab el al. (2023 Wang & Manchester (2023 Araujo et al. 2023 : Havens el al. 2024
Typical approaches for fg-norm Lipschitz estimation involve semidefinite program (SDP), as in the LipSDP framework (Fazlyab et al. (2019)), ), where the slope-restrictedness of the NN activation functions is leveraged to formulate the problem of Lipschitz estimation as a large linear matrix inequality (LMI). Despite their accuracy, the computational complexity of SDP-based methods grows exponentially with network depth. Approaches
to enhance scalability of SDP-based Lipschitz estimation methods include neglecting specific neuron coupling constraints at the expense of bound tightness (Fazlyab et al. (2019)), exploiting matrix sparsity through chordal decomposition to generate smaller, more tractable LMIs (Nwtonn & Papachristodoulou (2021)
dissipativity--aast approaches (Pauli et al. (2023 2024)), cigenvalue optimization and memory-cfiiiin computations through autodiff (Wang et al. (2024) and compositional methods that leverage the geomet ric properties of the underlying SDP decompose it into a series of sequential sub-problems (Xu & Sivaranjani (2024)), significantly advancing the practical utility of SDP-basod Lipschitz estimation methods for deep neural nelworks. However, all these works remain limited to estimating the global Lipschitz constant over the entire Fuclidean space. In contrast, exploiting local information about the input domain can yield more precise Lipschitz bounds, which is a key contribution of this paper.
Theoretical Approach. We start with generalizing the certificate of Fazlyab et al. 2019 to allow
heterogencous, nontrivial slope-restricteddnss bounds (briefly, slope bounds) for the activation functions at each neuron, as well as Lipschitz constant estimates for subsets of NN layers and arbitrary selections of input-output indices. We then build on the compositional decomposition framework in the ECLipsE series of algorithms proposed in Xu & Sivaranjani 2024 to decompose the resulting large LMI into series
2

---

Published in Transactions on Machine Learning Research (03/2026)
of small-subproblems that are solved sequentially. It is important to note that the algorithms in Xu & Sivaranjani (2024) assume that the lower slope bound of each activation function is zero and are no longer directly applicable when we generalize to heterogeneous and general slope bounds. The result is a series of algorithms, termed ECLipsE-Gert to determine the decision variables al each stage. Further, in contrast lo ECLipsE Xu & Sivaranjani (2024), we incorporate local information on the input region to derive tighter slope bounds for the activation functions of each neuron, yielding more accurate local Lipschitz estimates. In our algorithms, we iteratively refine the slope bounds for each neuron at each stage, and compute a messenger matrix that passes local information from one stage to the next. This sequential algorithm achieves computational complexity that scales linearly with the network depth, while yielding tight Lipschitz bounds. We further relax the sub-problems to derive a variant, EClipsE-Gen--ooeee Gen-Local-CE that provides closed-form solutions at each stage, completely eliminating the need lo solve any SDP, while achieving lighter Lipschitz bounds compared to ECLipsE-Fast Xu & Sivaranjani (0024).
Contribution. In this work, we propose scalable compositional framework that leverages local information the input region to yield lighter, certified Lipschitz estimates for deep FNNs. Our main contributions are as follows:
1. We generalize the Lipschitz constant certificates in Fazlyab al. (0119) by allowing heterogeneous, nontrivial slope bounds for each neuron, and subsequently decompose the resulting large SDP into series of small, computationally tractable sub-problems inspired by Xu & Sivaranjani 20224). The resulting algorithms are termed the ECLipsE--Gen series.
2. We develop ECLipsE-Gen-Loon region to iteratively refine slope bounds while propagating information layer by layer, enabling tighter local Lipschitz upper bounds compared to the global bounds, while providing strict theoretical guarantees on feasibility, validity, and tightness.
series of algorithms that incorporate local information of the input
3. We provide extensive experiments demonstrating that our algorithms consistently produce more accurate Lipschitz estimates compared to global methods, while achieving computational speedups of several orders of magnitude over traditional SDP-based approaches. Furthermore, when the inpul region is considerably small (the neighborhood of a specific point), our local estimates approach the ezact Lipschitz constant represented by the norm of the Jacobian at the region's 's center, reaching the tightness level of the values obtained by autodiff and thus validating the exceptional tightness of our proposed method, ECLipsE-Gen-Loon
empirically show that
4. We establish generalized certificate that supports arbitrary input-oulpul indeæ selections and consecutive-layer subsets (Theorem Bj. This flexibility is not only used internally for our layer-wise slope-bound refinement, but also serves as a versatile foundation for targeted downstream certification tasks. As one representative example, we leverage the certificate to perform reachability analysis by computing a certified over-approximation of the reachable output region (Theorem G/.
Beyond standard robustness certification, the flexibility offered by our framework to select arbitrary indices and layer subsets enables specific certified analyses in modular pipelines. For instance, arbitrary index selection allows for coordinate-lovel sonsitivity bounds, which are crucial when outputs represent distinct physical quantities in control systems (e.g., Wei & Liu (2022)) ) or physical surrogates (e.g., NN surrogates for power flow physics Zhao et al. (2020); Pan (2021)). Similarly, consecutive-layer selection supports the verification of intermediate representations in architectures like carly-cxit networks (Teerapittayanon et al. 2016)), encoder-decoder structure (Hinton & Salakhuidinov (2006)), multi-task models (Misra el al. (016 ). Additionally, our reachability analysis (Theorem ( provides certified output set over-approximations,
explicitly illustrating the practical benefit of reduced conservatism for safety verification.
Related Work. Estimating the Lipschitz constant of neural networks NP-hard (Virmaux & Scaman 2018
The most basic method the naive upper bound based on the product of induced weight norms (Szegedy et al. (2013)), which is highly conservative. Other practical methods include automatic differentiation-besee
approximations, which have practical utility but do not provide strict upper bounds on the true Lipschitz
constant (Virmaux & Scaman (018)). More advanced analyses leverage the composition of non-expansive
3

---

Published in Transactions on Machine Learning Research (03/2026)
and affine operators (Chen et al. (2020)) ) and scalable alternatives using bound propagation to derive local Lipschitz estimates (Zhang et al. (2019) Shi et al. (2022) ). Exact layer-wise analytic estimates have been developed for spocific architectures Avant & Morgansen (022)) on each layer. Jacobian composition analyses (Zhang et al.] (2019)) provide tighter bounds by analyzing compositions of activation functions directly, yielding both upper and lower bounds for the Jacobian. Besides, optimization-basee methods have made substantial progress in tightening Lipschitz bounds. For example, taking advantage of the piecewise linear nature of the ReLU activation function, Weng et al. (2018) and Jordan & Dimakis (2020) formulate the Lipschitz constant estimation problem into a linear program (I.P) or mixed-integer program (MIP) respectively. Another approach is to encode Lipschitz estimation as a sparse polynomial optimization and further relax the probloms into more tractable forms such as quadratically constrained quadratic program (QCQP), second-order cone program (SOCP); and SDP Latorre el al. (2020). Tight estimates can also be obtained using saauch-and-bouse
methods via partitioning Bhowmick et al. (2021), which can be further
integrated with other approaches (Shi al. (2022)). ). Various methods also dlfferr in their norm specificity,
including the general L, 4,-ormm Virmaux & Scaman 2018|; Bhowmick et al. (2021 Weng et al.
20018) ), the
fz-norm (Fazlyab et al. (2019) : Xue et al. [2022); ; Avant & Morgansen (0023] Wang et al. (2022]
Pauli et al.
(2023 2024); Wang et al. (2024); Xu & Sivaranjani (2024)), --orr Jordan & Dimakis (020 -oom
Latorre et al. )020);; Jordan & Dimakis (2020); Shi el al. (2022)) ), and mot accommodating arbitrary
norms (Combettes & Pesquet| (2020) Chen et al. (0000) Zhang et al. (2019)).
Typical æz-norm Lipschitz estimation methods such as LipSDP (Fazlyab et al. 2019: rely on SDPs, which
while offering accurate Lipschitz estimates often suffer from poor scalability with increasing neural network depth. Strategies to enhance scalability of SDP-based Lipschitz estimation methods include relaxing neuron
coupling constraints (Fazlyab et al. (2019) ), dissipativity--base formulations (Pauli et al. (2023 2024g),
sparsity exploitation via chordal decomposition (Newlon & Pappchrristodoulou (2021)), eigenva lue optimization
and memory-efficien implementations (Wang et al. (2024)) via autodiff (Rumelhart et al. (1986). )), and
compositional decompositions of the SDP into smaller sub-problems (Xu & Sivaranjani (2024)). While these advances enhance scalability, they are still confined to global Lipschitz estimation, whereas this work leverages local input information to obtain sharper bounds on the lg norm Lipschitz constant. of deep NNs.
2 Problem Formulation and Background
Notation. We define Σn = (1....,, N), where N is a natural number excluding zero For set X and its subset Y, X is the complement of set Y in X. |X] represents the number of elements in set X. Identity matrix of dimension n is denoted as In or briefly I with dimension clear from the context. A symmetric positive-definite matrix P E Raxn is represented as /
(and as P 2 0, if it is positive semi-definite). For symmetric matrix A and B, A (>)B mcans A - B 2 (>)0. For two vectors and y, x S (2)y means x is no smaller (larger) than y elementwise. We denote the largest singular value or the spectral norm of matrix A 1 0 by ma) (A). The set of positive semi-definite diagonal matrices is written as ID+. For any vector x, DR represents the matrix with the entries of x along its diagonal. We use calligraphic style such as K. for a set of indices. (z)x denotes the subvector of x indexed by the set K. Briefly, We denote (r)x if KC = {k}. (A),,, selects rows KC and columns L; (A) and (A),x,,) select all rows or columns with columns or rows indexed by L or K, respectively. O is the point-wise multiplication. We represent the ball with center e and radius r by B(c,r).
2.1 Problem Formulation
Consider a standard feedforward neural network (FNN) with N layers, where the input is 2 E Z C R and the output is y y y S Rdx, with the input output mapping of the FNN given by y= f(2. Here, Z denotes the local domain of interest, and y is the corresponding codomain. The function f is defined recursively through layers L,, for i E ΣN, as follows:
L 2 = -(0 ViE ZN-1,
kw:y=((>) = = v(N)
= 2,
(1)
where (+)) 1i + bi, with W, and b, denoting the weight matrix and bias vector for layer Li, respectively. The activation function Φ Rdh + Rd is applied element wise to its input. The final layer, LN, is referred to
4

---

Published in Transactions on Machine Learning Research (03/2026)
as the output layer. We use d, to denote the number of neurons in layer L, for each E ΣN. We also define function f()) Rd - IR. to be the mapping from 200) to u(t), so that f= f For notational consistency, we let f(0) : Rd - Re to be the identity mapping, i..,, (2) = 2 for any 2 E Rd
Definition 1. For any given region 2 - RR,, the function f R + Rd is locally Lipschitz continuous on if there exists a conslant >> 0 such that (1](2)) - ( S Li|zi - 22l12, Vzi, 22 E Z. The smallest positive L satisfying this inequality is termed the local Lipschilz constant of the function f on domain 2.
Problem. We aim to estimate a tight and strict upper bound for the local Lipschitz constant of the FNN in ① over the local region Z -(zc, with 8z O.
Without loss of generality, we assume W, # 0, E ZN, as any zero weights will lead to the trivial case where the output corresponding to any input will remain the same after that layer. The goal is to utilize local information from domain Z and provide a scalable approach to efficiently calculate a tight upper bound for the local Lipschitz constant > O. Note that the proofs of all the theoretical results in this paper are included in Appendix A.1
2.2 Preliminaries
We begin with a slope-restrictedness property satisfied by most activation functions, which is typically leveraged to to derive SDPs for Lipschitz certificates (Fazlyab et al. (2019): Xu & Sivaranjani (2024)).
Assumption (Sloperestrictednnss). For the neural network defined in slope-restricted (a, (),, a S B in the sense that Vun, 02 E TR,,, we have alv diieent-wiee, Consequently, we have that for VA D+,
i the activation function & is
v2) S (b(1)) (b(1)) S B(11 - 02)
1i 1/ (o(1)) 6(v2)
]
[
-mA] A
1i 02 o(()) 6(v2) 50, p=a m (a + 3)/2.
(2)
The assumption holds for all commonly used activation functions. For example, it holds with a a= 0, B 1, that is, p= 0, m = 1/2 for the ReLU, sigmoid, tanh, ELU (exponential lincar functions). For Leaky ReLU activation function, defined as (xx)= = max(7 x)) for some fixed E 1), the assumption is satisfied with a y and B = 1, i.., p= = (7 + 1)/2 and m = (1 + 72/22.
We first introduce LipSDP framework Fazlyab et al. 2019), which provides an accurale upper bound for the global Lipschitz constant, as follows. Note that the matrix inequality presented here has a slightly different, but mathematically equivalent to to the original formulation in Fazlyab et al. (0019)
Theorem 1 (LipSDP). For the FNN ( satisfying Assumption
7 if there caists F > 0 and nonnegative
diagonal matrices A, E ED,, i E ZN-1 such that with p o3 and m a+8
2
TI + pW? W -mA, W.
-WW A1 A1 + pW, A2W2 m2
0
-mW A2 Aa + nW AgWa
>>
-mA-= AN-2 +WW WN-1
-m. AAy-1 AN FW WWWWX
-mAx-1WN-1
(3)
(N) - [N) S 11FF -000 then 12
(0)
2'' which provides sufficient condition for the Lipschitz constant
L to upper bounded by vI/F.
Practically, LipSDP maximizes F satisfying 3 to obtain striet Lipschitz upper bound by v1/F. LipSDP also provides two variants (Fazlyab et al. (2019); Pauli et al. (022)): ): LipSDP-Neuron with A E D, and LipSDP-Layer with A, = 7 (A, 2 0), E Z which decrease computational complexity by reducing the number of decision variables at the cost of some accuracy. Nevertheless, solving 3 becomes exponentially costly as the number of layers increases. Recently, Xu & Sivaranjani (2024) introduced the ECLipsE framework, which provides a scalable approach by decomposing the large matrix inequality (3) into smaller sub-problems, resulting in linear computational cost with respect to the number of layers. Specifically, the ECLipsE framework provides two algorithms that tradeoff accuracy and computational efficiency: ECLipsE
5

---

Published in Transactions on Machine Learning Research (03/2026)
solves small matrix inequalities that scale with the size of the weight matrices in consecutive layers, and F.ClipsB-Fast provides closed-form solutions for X E NN- achieving further scalability at the cost of some accuracy in the Lipschitz bounds.
Despite its scalability, ECLipsE has several limitations. First, it is constrained activation functions whose slope bounds satisfy 22 with p = O, and thus can cannot accommodate several activation functions such Leaky RcLU, PReLU (Parametric ReLU), SiLU (Sigmoid Linear Unit), and ELU (Exponential Lincar Unit), which also commonly used in practice. More importantly, ECLipsE does not incorporale any local information from the imput domain and is thus limited to computing the global Lipschitz constant, which is typically less tight that a local onc. Morcover, ECLipsE cannot provide bounds for the Jacobian in an element- wise or partially indexed fashion. In the following sections, we address these issues by developing more general scalable algorithms obtain tight local Lipschitz estimates for NNs with a wide variety of activation functions.
3 Methodology
3.1 SDP-based Lipschitz Estimates with General Slope Bounds and Arbitrary Input-Output Indices
We start with allowing heterogeneous slope bounds for the activation functions for each neuron in each layer. Specifically, the slope bounds are given by two sets of vectors {a² { (lower) and ( (upper). Then, Theorem from the LipSDP framework can be generalized as follows.
Theorem 2 (Hletereogeneous Slope Bounds). For the FNN [1] satisfying Assumption 1 we denote the lower and upper slope bounds for the activation functions on the 1th neuron in the ith layer to of and Bi, respectively, with Ed,, E LN. Let a there exists F > 0 and non-negative diagonal matrices A, E D4 E EN-1 such that
[a af, oi................. ... a 1 and B [8] [2., ......, .b]] i EN-1- If
P
R₂
RS
P2
R3
O
R
P3
> 0,
(4)
R.N
0
0
RT
PN
where, for I.....
W+ D.
fi=1
P
Am1 + D. W.,
25i<N
AN-1- -FWWF
i=
(5)
R. W. + -gt-1)A--1 i= 2..,..,
then 12 - (
S 1/F
22 (0)
2
(0)
This serves as a sufficient condition for the Lipschitz constant L
to be upper bounded by VI/F.
We now extend the above result to allow Lipschitz constant estimates with respect to arbitrary input-output pairs and arbitrary subsets consecutive layers. For uniformity of notation, we denote Ao & la, Concretely, provide the certificates for L K.C
(p.i) such that for any I. C Ed, and L L Ed,, 0 S p<iiii N,
(c11)) - (1(0) (1)))(ll=
5
L
L
(p.4)
( (0( K - (p) xx112
(6)
holds for any possible (1(2) x
1/2
and
(o(0)
(1)
where (0)
v 22 122
(0) (0) (0)
E Z C Rd.

---

Published in Transactions on Machine Learning Research (03/2026)
Theorem 3. For any K - Zd, and L S Zd. 0 S L (p.)) K.C. = 11/F>/ such that
<
< N, inequality holds if there erists
Pp+1
Rxt2
0
0
R442
Ppt2
Rp43
0
0
R
Pp+3
0
>
0,
(7)
R.
0
0
RT
P.
where
(Ap)ec,K) + ((W DavliApti Dap12 (Wp+))ox))
m == p+
Pm
Am-1 + W Derm Am Dam Wm,
p+2 2 m <i
A ((Wi)ce.)) (Wi)
m m=i
((W)+))(0x))) (Darti + Darti) Aptz: m m= p
Rm
WD-1(Dam + Dam-1)Am-2
Here, arbitrary layers and indices are accommodated by retaining only the weights between the selected layers, and appropriately selecting the sub-matrices of weights in the first and last selected layers corresponding to selected input-output indices. All other components remain unchanged. This operation whenever bounds for arbitrary layers and indices are required. Note that we present the following theory for the entire NN; however, the results can be analogously extended to arbitrary subsets of layers and input-output pains in the same manner.
be applied
develop scalable a algorithms based on this generalized SDP formulation, we build on the exact decomposition from Xu & Sivaranjani (2024): Agarwal et al. (2019), to derive sufficient and necessary conditions for the matrix inequality (4).
Theorem 4. Motrir inequality holds if and only the following sequence of matrir inequalities is satisfied:
X; > 0, ZN-2
XN-1 - -FWWWN > 0,
(9)
where
I I+ WT D& A,Dg
= 0
X;
A: A1 + Dgx)) + Dg:)A, + W Dattiaiss Dztt Wet E nN
AN-1 (Dax- + DDN- (W DøN-I)AN-1
N - 1
(10)
This result extends Theorem 3 of Xu & Sivaranjani 2024 to allow heterogencous slope bounds for the activation function on every single neuron, where slope bounds of and Bi l E Za, E ZN, be non-zero.
To facilitate the algorithms, we further define for all i ΣN-1, 2 2, messenger matric
M A, 1 A + 4
Dg.-1)
(11)
For notational consistency, we sct Mo I. In other words,
= = M D.
Zx-1 i.
(12)
M-1
With the extensions mentioned above, develop series of algorithms, termed the ECLipsE-Gen series follows.
From 10 we observe that X, is obtained in recursive manner and depends on A₃ and X,-1;

---

Published in Transactions on Machine Learning Research (03/2026)
E IN- We propose three algorithms where we derive A, and simultaneously compute M, i E Zx-1 in a sequential manner, laying the foundation for compositional Lipschitz estimation methods whose computational cost grows only lincarly with respect to the depth of FNN. We directly present the algorithms here and deliberately defer the supporting rationale and theory in Section 3.5 for clarity.
ECLipsE- ECLLppE-Genn-Ae For the most general case where A, can have heterogeneous elements on the diagonal, can obtain As, E ZN-1 at cach stage i using the information from the next layer, i.c. WH+1 by solving the following small SDP:
A, - G +1 W1+1
aA. + +D: X,-1
max G s.t. G,A,
(D + D
> 0, A G> 200
(13)
Recall from 100. with W,, D A,-,, and X;-2 known at stage i, each block matrix above linear
A; and c in each block matrix. Thus, 13 semidefnitte program (SDP) of small size, involving only the weights from two consecutive layers. With the solution Ai, we can directly compute M2 11
Fast In the special case where A, is relaxed to A; >,,, E 21-1, and is calculated by solving
max O s.t. MM--WWii W++ 2Ac( + DB: H (Dar + Dz))
0, A 2 0, 9>0,
(14)
X,-1
where X,-1 denotes the matrix X,,1 with the substitution = AsI
In this variant, the number of decision variables at cach stage is reduced from (d; + 1) to just two variables (A; and q) compared to ECLipsE-Gen-Ast at each stage, resulting in decreased computational complexity, albeit at the expense of some accuracy. We use the solution A; I to compute M2 as 111.
ECLipsE-Gent Gen- CF. If the slope bounds a' and 8 for cach ncuron do not have different signs (i.e., a' 3 2 0), we have X,-1 2 M,-1, enabling further relaxation. Specifically, if a O B = O, we have x, = M,-1, which enables an optimal closed-form solution for (14). Under the assumption that a'O O 2 0, we can adjust ,', as follows. For each j E Zd, if S (a'); S (B'), set (a),.))) (0, (3); if (a'), 5 (B')) I O, set (a), B8) - *a),, 0). We denote the adjusted slope bounds as aad and giadi Note that after adjustment, a andd O giadd = 0 is satisfied. This yields the optimal closo-form solution for A layer L, as
2
A
(15)
O Omax (DD + oo
(Daii + Dgiad))) ))
With A, del, we can further derive the corresponding optimal e from Proposition 1. With A, ATT in 15,, the optimal o; oblained from is
14 follows.
1
(16)
max Wi+1 (M:) W
where Mj is computed as
1 Ag (Da + Dgs W, (X (Darnes + Dasnes) Ai.
M, A 4
(17)
It is worth mentioning that the assumption a' O g' > 0 holds for almost all commonly used activation functions. Notably, ECLipsE-Gen-CF completely eliménates the need to solve matrix inequality SDPs altogether, thus significantly enhancing computational efficiency.
After all Ass, i E ΣN-1 are decided using any of the above algorithms, we obtain the smallest 1/F which yields the smallest Lipschitz estimate L, as
L L= 1/F Tman (WXWw((x-))-1) = = amar ( (Wx(Xx-I)-WW3)
(18)
Note that the second equality holds because of the Lemma in Xu & Sivaranjani (0224) restated below.
8

---

Published in Transactions on Machine Learning Research (03/2026)
Lemma 1 (Lemma 1 in Xu & Sivaranjani 2024 ). If > 0, then WWW, WM, and W((M,-1)- share the same non-zero eigenvalues.
Proposition 2. For given As, E ÆN-1 that satisfies X; 0, i E ΣN-2, the tightest upper bound for Lipschitz constant is L V Omaz (Wx(Xx-I)-WW3)
Gen-psE provides accurate Lipschitz estimates by solving small semidefinite programs (SDPs). ECLippFF-Gon-Fstt, with fewer decision variables, offers improved computational speed at the expense of some accuracy. Under very mild assumptions, ECLipsE-Gen-CP relaxes the sub-problems at each stage and yields a closed-form solution for each sub-problem that makes it extremely fast. These algorithms embody different trade-offs between efficiency and accuracy; one may choose ECLipsE-Genn Gen-Ace, if pursuing accuracy, and ECLipsE- Gen-Fast or ACLipsE-Genn-C (depending on the slope of the activation function), for applications where scalability is of the essence. Note that ECL.isEE-Gen-Ce involves adjustment of slope bounds a relaxation achieve closed-form solutions, which can introduce additional conservatism. The slack introduced is discussed in Appendix A.4
Having introduced the three algorithms,, we now describe how to generalize each to arbitrary subsets of layers and input-output pairs. To extend ACLipssE-Gen-Aee ECLipsE FaatE-GGn-FFatt,, and ECLipsE--Gen isolate the sub-network between the chosen layers and appropriately select the associated weights and A variables. Specifically, when estimating L
we simply
(p.5) C.C. p < i, K. Ed, L S Ed., we keep only W,, i = p+l,..., and Ar, = p=p+1.... -1, substitute Wp+1 and W; with (W++1)(.xX) and (Wi),c,)), and similarly substitute Ap and A;-1 with (Ap) and (A,-1),,0)- The sequence of small sub-problemns start al stage p + 1. The remainder of the procedure and the structure of the optimization problem for each algorithm remain unchanged.
Remark 1. All these extensions are essential not only for exploiting local properties of the input domain, as will be illustrated in the following section, but also for facilitating the modular/ colluaar/coopoor compositional analysis and dccomposition of NNs, paving the way for scalable certification of NNs in a wide varicty of applications.
3.2 Utilizing Local Information
The key to utilizing the local information to obtain tighter Lipschitz estimates is to refine the slope bounds of the activation function for each individual neuron. Intuitively, more accurate (i.e., narrower) slope bounds lead to tighter Lipschitz estimates. This intuition can be formalized as follows.
Theorem 5 (Monotonicity of Estimates with Respect to Slope Bounds). Consider two sets of slope bounds for the octivation functions, ( N-1 and (ā', ("= where for some j,ú, [ā], c [á), and for all other entries the slope bounds are identical, i.e. á'= "'' B.. Let F and F denote the marimam values that salisfy (4) (5) when using (0',3') and (,,,))) respectively. Then we have F 2 F, and thus the
corresponding Lipschilz upper bound salisfies /1/P&V11
In other words, using narrower slope bounds for the activation functions yields a tighter upper bound on the Lipschitz constant in Theorem 2 To obtain narrower slope bounds for each individual neuron, we leverage both the input region and the Lipschitz bound with respect to (() j E Za, N, and the input layer. o Specifically, we use a first-order method based on the mean value theorem to estimate the range of output values at each neuron and then refine the slope bounds corresponding to various classes of activation functions.
Theorem 6 (First-order Method via Mean Value Theorem). We consider any E 2 & B(ze, 52), where 8₂ > O. Let g IRdo + R be a locally Lipschitz continuous function over Z with Lipschitz constant L > 0. Then for all 2 E Z,
1g(z)- - g(2))] < L|122|12.
(19)
In other words, we have the ronge for g(2), E 2, as
o(z.) 0||02||2 g(2) g((c) L||02||2
(20)
We can now utilize Theorem to bound 0 j Ea, i E N at each neuron and refine the slope bounds.
9

---

Published in Transactions on Machine Learning Research (03/2026)
Proposition 3. Consider layer L, of FNN ( of
IN-1- Let Φ denote the activation function. If we have (6) b), e Zd. C R, then the refined slope bounds for neuron in layer Lg are given by
a inf inf())))) vEla,ò]
B
sup sup(do(u)}
(21)
vEla,b]
where ('()) denotes the subdifferential of o at v.
Given activation function o, of and of (briefly a and 3 here) can computed explicitly, We present few representative examples below.
ReLU: ((x) max (0. The subdifferential is
{0), x < 0
0ō(x)=
[0,1], 0
(1},
x> 0
Therefore, we have a = and =
Tanh: x(x) tanh(x). The subdifferential 0Φ(x) {1 1 tanh Thercfore,
tanh² (max/[a), (613), B 1 tanh (minf[a), (6[))
Sigmoid: ((x) = (1 e -)- The subdifferrntial is 05(x) = (b(x) ((x)]} Therefore, a min {p(a)[] -(aa), @b)[[ (()]),
B = 0.25
Leaky ReLU: ((x) = max(1æ, x}, with y E (0, 1). The subdifferential is
{th. < 0
0Φ(x)=
1, x
[1}, 0
Therefore, we have y and 8 1.
ELU: ((x)
The subdifferential
7 -16e-11,+ 1), <<> 0"
{1}.
x 0
0б(z)- =
x < 0 {re"),
b 1],
x 0
Therefore,
7: b b
7, b<0 1, a<0<b or 620
a =
7, a
< 0 < b
as0sb,
==
1, a a20
3.3 ECLipsE-Gen-Local Scalable and Accurate Algorithm for Local Lipschitz Estimates
With the generalized algorithm series ECLipsE--Gen for given slope bounds presented in Section 3.1 and the approach to utilize the local information of the input region to refine slope bounds as described in Section we now derive the compositional algorithm series EClipsE-Gent Gen-Local for estimating local Lipschitz constants. The key idea refine the slope bounds layer-by-layer each A,, i Æx-1- Intuitively, while messenger matrices propagate coupling information, local information is simultaneously propagated
conjunction with the determination of
reach each layer by computing the reachable local region and encoding this information into refined slope bounds.
10

---

Published in Transactions on Machine Learning Research (03/2026)
Specifically, at each stage i, given messenger matrix M and Wa we first calculate L (0.5) ..
for each / E Ex,
L 10.0
= Vomar (I(W))a))) (M-11(
(22)
Let L = (0.1) (..0)
(0,0] IRd,, We claim that we can compute L (0.3) for all E Σz, simultane- ously, accelerating the estimating process, E ZN-1-
L
.d:
Proposition 4. For any E -N-1, let W 1d:xd,11 and M1-1 E Rd Rd ixd=1 be symmetric positive definite. Then, the 1-th diagonal entry of the matrix (M(, yields:
(W((M-1) a.) maax ([(W))o))) (Wa)a.
(23)
In other words, to obtain L (1) it suffices to compute the matrix W.(M;-1)~ and take its diagonal entries. In fact, since only the diagonal entries are needed, further computational acceleration is possible.
Lemma 2. Denole a (W.(M-1))- an for I- = -I....,d, dg and d() [a h
(1)
Let
A, (M Rd: xxd:
1 d = (W)) @ ((A))
(24)
This mcans that, in practice, the diagonal entries can be computed efficiently in a vectorizod fashion, thereby avoiding compulation of the entire matrix.
In the next step, we combine the input region Z = B(ze 8%) and f()) i ΣN-I. to enable refinement on the slope bound of each neuron layer by layer. By the structure of neural network (1), it is natural to apply f() in a recursive manner to avoid repeated calculation. Specifically, let ve((1) (ze), E {0) U ZN. Then, starting with ga(()) f(0) (ze) = Ze, we calculate for i ZN.
0 = (2) = =
+ bz).
(25)
According to Theorem the ranges for the values on neurons are given by:
( v" [o0000 ||02||2L (1) v06 + ||0z||2L (0)
(26)
We then refine slope bounds for all the neurons on layer I, according to Proposition 3 as
a'= inf inf (oo ((v(0))) evi
inf inf foo ((1(0))) eve
inf inf do eev
(27)
g sup sup fōo do ((v(t))) eeve
{ foo ((o(t))))
sup sup do (((() gvs
}
T
sup sup eee
Consequently, we determine A, based on M₁-1, W,, and the refined slope bounds a', 8 using any of the algorithms BCnipsE-Gen-Ace, Een-psE-Gen-Past, Gast or ECLipsE-Gen-CPP and subsequently compute Mj. This process is repeated iteratively for each layer, starting with M, = I. When it comes to the last layer, where we already have AN-1, and XN MN-1, and the final Lipschitz bound is simply computed [8
Note that at each stage, we have the flexibility to choose any variant from the ECLipsE-Gen series. The algorithms are formally summarized in Algorithm D with the theoretical justification in Section 3.5
Remark 2. (Guidance Variant Selection). The selection of variants within the ECLipsE- Gen series depends the desired trade-off between tightness and computational cost: choose
11

---

Published in Transactions on Machine Learning Research (03/2026)
(if applicable) when speed is critical (e.g. online tasks), ECLipsE- Gen-Loll-e-- when precision is paramount (e.g,, safety certification), and ECTippeF--Gen-Local-aas for a. balanced tradeoff. Practically, we recommend starting with ECLipsE-Goon-Local-CT for online tasks due to its negligible cost. If the resulting bound is too conservative, one can upgrade -Ceipal-Gen-LLcall-- sequential nature of the algorithm allows users to estimate the total runtime after processing the first layer (as the computation time scales linearly with respect to the depth of NN), and accordingly choose the most accurate variant that fits their time budget.
or ACLipsE-Gen-LLoce
Additionally, the
Algorithm ECLipsE- Scalable Local Lipschitz Estimation
Input: Weights {W)) biases (b. [b:) activation function Ø; input region Z BBee, 62); variant
ALGO (Acc,Fast, CF}
Output: Local Lipschitz estimate L
3: Set Mo + I, (e.(0) + 2c
4: for i = 1, ........A.
5: Compute d with a = (W:(M-1))- Jan for 1 = 1...., di, using acceleration techniques 24
T
6: Set L Valo...... ..... V Vali
(i)
Compute y (0 = f(0 per 25
8:
Calculate range V for (() as in 26
9:
Refine a²,, B using 1d as in 27
10:
Choose Acc/Fast then
11:
Obtain A, via (13 or 144 using refined slope bounds a', ,
12:
Update M, as in [11 using a², /
13:
else if Choose CF then
14:
Assert a² ② 8 2 0
15:
for j = 1......... d; do
16:
0 (a')) ) s (B'), then
(atadi)) ) t 0, (giadl)) t (Bi)
17:
18:
else if (ae ) S (B)), 50 then
(a aadi),
(a))), (gi.all), t- 0
19:
20:
end if
21:
end for
Obtain x; via 15 using ar and Biadd
22:
23:
Set A; + X
24:
Compute Mj as in 17 using A
25:
end if
26: end for
27: Using 188,
compute final L = 1I/F = Jman (Wx(Xx-I)-IW3) with XN-1 = MN-1
28: return
3.4 Acceleration and Stability Safeguards
We augment FCT.ipFF-Gen-Locai with targeled accelerations for special cases and introduce stability safeguards for reliable performance in degenerate slope-bound scenarios, resulting in faster and more robust algorithms.
3.4.1
Acceleration in Special Cases
Affine Layers. In the special case of a === B layer La becomes affine layer. In this setting, we skip the layer L; and construct a new equivalent layer with weight W411 and bias b defined as
W W...DaWW. b W Darb + b
(28)
12

---

Published in Transactions on Machine Learning Research (03/2026)
If there exist consecutive layers Lj = = 1,.,, p such that all of them are affine, i.c. a² = 3 for j = i, i 1,.....tt i we repeat this process for p times. In other words, we skip layers T,,, j = i, i,.,,...., 1. and directly proceed to construct a new oquivalent layer Litp as follows.
Proposition 5. Let ( denote a sequence of conseculive affine layers, where for each Lıj, α² = Bi for i +p. Then, these (p +1 affine layers are equivalent to a single layer, denoted Lito, with weight matric and bias vector given by:
j=i....,it
stp-1 II
p+1
Etp-1
Witp=
Wat W.. b-pp= 1=1
Σ
II j
(Wst)Da))bs
(29)
where the product Wat reduces to the identity matriz if k p 1.
Note that, in Algorithm only the computation of (zc) in step involves the biases b;, and the value of (zo) remains unchanged regardless of whether any layers are skipped. Therefore, whenever sequence of consecutive layers is affine, we retain the computation of (ze) as before, and for all other steps in Algorithm | we skip the intermediate layers and directly reach layer Tatps replacing the weights with the equivalent weight Wi-p as in 29
3.4.2 Numerical Instability in Degenerate Slope Bounds
Although the feasibility of optimization problems 13 and 14 is theoretically guaranteed (as will be discussed in Section 3.5), numerical issues can arise in cases where the entries of a; and B; coincide partially. This scenario commonly arises in local Lipschitz estimation, particularly for piecewise linear activation functions such ReLU and LeakyReLU, where the slope remains constant over certain regions. Let Ti C Zd, be the index set where (a'),, (0") ). and define M, e Za, \J. Note that if J, Zd, (i.e., a' B²), then layer L is affine; in this reduced case we directly apply the acceleration introduced in Section 3.4.1 Here we focus on the case J, _ Zd, and M, A Za, NJ. + 0.
ECLipsE- (CLipsE-Gen-AAce Gen-Ace. Intuitively, when a and Bg coincide at an index set Ts S. Ed, the value of (Ar) is not upper-bout upper-bounded boundod by the constraints and can grow arbitrarily large. As a result, directly solving 13) can lead the optimization solver to assign extremely large values to (A,)(a..3) ; in stark contrast. to the other diagonal entries. This scale disparity introduce significant numerical instability, especially after multiple iterations. In the following, we formally characterize the source of this potential nunerical issue and present practical remedy.
Proposition 6 (Unboundedness of A, on Equal Slope Bounds Subset). Consider the oplimization problem 13) at layer i E Zx-1- Let T, C Edd be an index subset for which the slope bounds satisfy (o'),,, = )z Then there exists a constant > 0 such that when (A4) = Ula,, the optimal value e₁ is attained. Moreover, for any (AT)) Ia,,, the value a remains optimal and unchanged. In other words, the block (Ai)(a is unbounded above al oplimalily without affecting the mazimal Ci.
Based on Proposition 6 propose the following method to obtain A, at stage i, ie ΣN-1-
We first obtain (A.)(M..M)) similarly as 13
(Ai)cM..M)) Co (WWZZWHH))MMMM [[(()))m (D.. + (o
3(A))M.., DW)),, > 0.
max 4.(A))MMMM)
s.t.
8.n1 8
(Ad)MMiM) E DD, a 00
(30)
where 8,-1 M,-1 [(W)) (1)) (D
Then, avoid numerical issues, we ensure that all the elements of Ar are of similar scale by setting
4
(Arhs
Σ (A)))
je Jr.
(31)
[M
McM.
where 4 is moderately large scalar chosen to avoid numerical instability due to scale differences.
13

---

Published in Transactions on Machine Learning Research (03/2026)
ECLipsE- Gen-Fast, Similar to the ECeipsE-Gen-Ace case, we keep only the part corresponding to the index set M, = Zd. NJ+ + and solve
x c. (ena) oM (Da +Da)) DF.)(M.M.)
2T.(Daa + D&t (()) >0,
max G s.t. q,
X1-1
(32)
2 0 6q > 0,
where Xi-1- Mi-1 > (Da (
Then take A; A,I.
Remark 3. As M, + 0, both optimization problems (30 and 32 are well-defined.
3.4.3 Numerical Feasibility Verification and Stability Safeguards
Despite the fact that theoretical feasibility is guaranteed (discussed shortly in Section 3.5 in practice SDP solvers may occasionally fail to converge to truly optimal solution due to finite-precision issues. To address these issues, we employ the following practical procedure at each layer:
(i) For FastFFatt, with a candidate A at layer L, obtained by solving (32) we explicitly verify whether the block matrix constraint satisfied. If not, we switch to ECLipsE-Gent for layer L, Note that as ECLipsE-Gen-- provides a closed-form solution, it does not suffer numerical issues and always yields valid solution.
(ii) Similarly for ECClissE- Gen--cc, with candidate A; layer L; obtained by solving 30
we explicitly verify whether the block matrix constraint is satisfied. If not, at layer Lg select from ECLipsE- Gen-Fast and EClipsF-Gen-CC the algorithm that yields the larger feasible with the block matrix being strictly positive as a substitute. Note that if E'CLipsE-GGen Fest also fails for the block matrix constraint verification, we directly use the results from ECLipsE-Gen-CEE
(iii) For numerical stability, we impose an upper bound on the magnitude A, for all layers.
These procedures ensure robust feasibility and numerical stability throughout the algorithm, even in the pres- ence of solver limitations degeneracies in the slope bounds. For clarity, we summarize these improvements in separate algorithm with the full pseudocode deferred to Appendix A.2 for brevity of exposition.
3.5 Theoretical Guarantees and Mathematical Intuition
This section establishes theoretical guarantees for the fcasibility of the algorithm and for the resulting estimates serving as provable upper bounds on the true Lipschitz constant, and explains the underlying intuition behind the algorithms in the ECLipsE-Ger Gen and ECLipsE-Gen-Local series.
We first show that steps that involve solving SDPs in Algorithm are always fcasible under mild conditions.
Theorem 7. Let a² Bi be the refined slope bounds at each stage i E ZN-1 in Algorithm 1 If O 2 for all i E Ix- then al every slage i, the oplimization problems 13 and (14 are always feasible, and the closed-form solution 15 is always well-defined and positive. Thus, the corresponding A, can be properly determined at each stage, regardless of the algorithmic variant chosen.
Remark 4. The condition a' @ 3 2 0 is a very mild assumption. For all commonly used activation functions, such as ReLU, sigmoid, tanh, ELU, and leaky ReLU, the global slope bounds satisfy this property, since both lower and upper bounds are nonnegative for all possible intervals. Moreover, any refined local slope bounds, being subintervals of the global range, will also satisfy a gr 2 0.
We then establish the provable strictness and validity of all Lipschitz upper bounds and the refined slope bounds generated in Algorithm Specifically, we show that (i) all slope bounds a', e and all intervals v
computed at each layer are guaranteed to hold for any 2 E 2; and (ii) ( [o.00) I I. (0,00) and the final local Lipschitz estimates L from Algorithm I are strict, provable upper bounds for the corresponding Lipschitz constants over the region& Z. We have the following results.
e.d.
Thcorom 8. Let Z = B(ze, 52) be the input region. For any lager L E ZN-1, if D valid in the sense that 6 holds for Ed.-19 then the range V and the corresponding refined slope bounds a', , produced by
14

---

Published in Transactions on Machine Learning Research (03/2026)
Algorithm are valid, that is, for d2 E 2
w E Vi
s's
inf Yoo )
8t sup { do (v())}
Theorem 9. Let Z = Beze, 02) be the imput region. For any layer Lu, E ΣN and any neuron ( E Ld. the Lipschilz estimate ! produced by Algorithmm salisfies (7). In other words,
(
1. zall2; V21, E
(33)
Moreover, the final local Lipschåtz constant L estimated by Algorithm satisfies the striciness of the Lipschitz upper bound L.
with L VIF ensuring
Notice that (. E Zd,; does not rely any slope bounds. Consequently, its validity establishes the foundation to guarantee, via recursion, that all subsequent slope bounds and Lipschitz constants remain valid throughout the process according to Theorem g and Theorem
Now we explain the underlying intuition behind the design of our algorithms. Specifically, we aim to decide appropriate As at each stage that will translate to lighter Lipschitz estimate at the output layer. At stage i, we have messenger matrix M,-1 that, encapsulates information from all previous i layers, as well as the weight matrices of the current and subsequent layers, W; and W441. We analyze backwards, starting at the output layer. Recalling (18), we aim to find the largest F, or equivalently, minimize maz (Wx(XN-))-WWa) = maz (WāW, (XN-1)=") Therefore, at stage i N in Step of Algorithm
when deciding AN- we solve the following problem:
max CN-1 s.t. XN-1 WN-IW
-N-1-N-1
(34)
Xx-1= AN-1 AN- + DXx-))Wx((XX-x) -1 DaN-1).
Note that the optimization problem (34,, together with the condition Xx-2 0, equivalent
13 with
N - 1. Moving backwards, at stage 1, the goal is to select A;-1 to maximize the feasible region of X, 0 in the subsequent step. We observe that
x; = A; - 1 A.( D.)
+ D3.)A, +
W4+1
4
(35)
X,- = M + W? D.
i E
While a², , and A; are not yet decided 35 we expect that minimizing the scale (:(X;-1)- W
the sense of its spectrum will yield larger feasible region for A in the next stage. Similarly from (12). the term containing a', Br, and A; is not decided at the stage. However, scale of W: (M, to enlarge the feasible region for A; in the next stage, which is directly aligned with our goal of minimizing Fmar WWX at the last stage since XN-1 MN-1 in 12
can still strategically minimize the
Therefore, we solve the following optimization problem to derive A;-
max A.
s.t. M.
(36)
1 A -
D3t-1)Ai-1
Together with the condition X,-2 > 0, applying the Schur complement shows that this is equivalent to
13
Furthermore, in computing L (0.i) the procedure is identical to that for computing the Lipschitz constant
of the mapping flo) ()) + v0 except that the weight matrix W; is trimmed to retain only its (-th row.
denoted (W))..)) Concretely, when we obtain _!0.") for the hh neuron at stage i, i e Z, by Proposition 4
the hth diagonal entry of W, (M, provides exactly the associated maximal eigenvalue as follows:
(W,(M,-)--WW)) (1.)) = Fmax
= xmax
15

---

Published in Transactions on Machine Learning Research (03/2026)
Therefore, our goal of minimizing the scale of ([MM--1)--W"" is consistently applied both at the network output and at each neuron for all E -N-
4 Experiments
We conduct three sets of experiments to systematically evaluate our methods. The first set considers randomly generated neural networks of both small and large sizes. We compare our methods to an extensive set of benchmarks to illustrate the scalability, efficiency and tightnees of our algorithms.. In the second set, we vary the size of the imput region and demonstrate how our algorithm leverages local information achieve very tight Lipschitz estimates. The final set compares the local Lipschitz estimates on two networks, trained conventionally and the other trained with robust objectives, highlighting the practical utility of our approach. The details of the experimental setup, and generation of the neural networks (both randomly generated and trained on the MNIST dataset), and complete experiment data are described in Appendix A.3
Benchmarks, We evaluate against methods that share the same SDP framework: ECLipsE- SeLipsE-Gen--iee -aLEE-Gen-Locaa (our method), F.ClipsF. (Xu Sivaranjani (2024)), LipSDP (Fazlyab et al. (2019)) GLipSDP (Pauli et al. (2024)) For (CLiipsE-Gen-LLcal-Ae
A;; E Zx-1 can have different diagonal entries, which directly benchmarks ECLipsE, GLipSDP, and LipSDP-Neuron For CeLipsE-GeenLLoalAe
and ECLipsE-Gent CF, A, X E 2N-1, which benchmarks to LipSDP-Layer and BCIispE-Fass. Additionally, we compare our Lipschitz
estimates to the naive upper bound Lnoine = ||illl (Szegeyy et al. (011 SeqLipp Virmaux & Scaman (2018)) ) GeoLip (Wang et al. (002 AAO (Combettes & Pesquet (2020), and LipDiff (Wang et al. (2024)).
All Lipschitz constants are computed with respect to the fz-induced operator norm, making the comparisons
across benchmarks directly comparable.
While we consider three variants that choose among the Acc, Fast, and CF homogeneously for all layers, we note that our framework also offers the flexibility of combining these options on a per-layer basis. For brevity of exposition, we abbreviate our ECLipsE-GGri Gen-Local scries of algorithms as: Acc (ECLipsE-Gen-Localll and CF (ECTipsT-Gen--ooall-0
Fast (BCLLipEE-Gen-Locall
4.1 Scalability, Efficiency, and Tightness on Randomly Generated Networks
We implement algorithms to estimate the local Lipschitz constant whenever applicable; otherwise, we fall back to the global estimate given by the algorithm. All the generated neural networks generated have input size do = 5 and output size dy = 2. The local region is picked as Z = B(2e, 52) with 2e = [0.4, 1.8, -0.,, -1.3, 0.9]T and 8₂- 1.
Case 1: Small Neural Networks.
Setup. We conduct a total of 20 experiments for all the 13 algorithms randomly generated FNNs, corresponding to all combinations of the number of layers in 15,10,15,20,25) and the number of neurons in (0,200,00600) As the benchmark SeqLip only applies to ReLU activation function, the FNNs are all generated with ReLU. To systematically evaluate the scalability, efficiency and tightness of different algorithms, we present the normalized Lipschitz estimates with respect to the naive upper bound and the computation time in seconds. While the complete results are provided in Appendix A.3.4 for clarily of presentation, we focus on two representative cases: (i) fixing the number of layers be 20 while varying the number of neurons; (ii) fixing the number of neurons to be 40 while varying the number of layers. We set cutoff time of 10 minutes for all experiments.
Effect of depth tightness. From Fig. la we first examine the tightness. LipDiff yields the loosest bounds, while AAO provides better estimates but is still outperformed by all other methods. GcoLip achieves accuracy comparable to Fast. Within the SDP-based methods for the special case A, = X,I 2 0, CF produces slightly tighter results than ECL,psE-Fastt, while Fast achieves level of tightness comparable to LipSDP-layer and, notably, even approaches the tightness of ECLipsE, which allows larger flexibility in A,, This improvement stems from efficiently leveraging local information. At the top end, SDP- methods with fully flexible A; 2 0 deliver the tightest estimates: LipSDP, GLipSDP, and Acc consistently outperform other benchmarks,
16

---

Published in Transactions on Machine Learning Research (03/2026)
with ECLipsE being somewhat looser. In certain cases (e.g., 20 layers), Acc demonstrates outstanding performance, indicating the success in capturing local information.
Effect of depth- - computation time. Turning to the computation time in Fig. Ib SeqLip fails to provide results even for networks with as few as 5 layers, while AAO breaks down 20 layers. Among the methods that succeed for this case, GeoLip and LipSDP- are the most time-consuming, although they demonstrate good accuracy. Within the SDP-based family, LipSDP-neuron and LipSDP-layer both incur rapidly growing computational cost with depth. In contrast, GLipSDP, Acc, ECLipsE, and Fast (in decreasing order for running time) exhibit linearly increasing computational cost with depth, demonstrating clear scalability. At the most efficient and scalable extreme, ECLipsE-Fass and CF have near-instantancon running time thanks to closed- fored--fomm solutions at each stage.
Tightness of Lipechitz Estimates for FNN with 40 Neurons
Time for Lipechitz Estimates for FNN with 40 Neurons
100
90
Ludt7 Auger
Normekzed Lppectkr Extiatte
10
Mo
DC-
2
60
Co Cervice dec
Sodio ueddo laye
80
1n7
AAD
Suadon
1111
20
E0kpet Oar LF
15
20
25
10
80
Number Layers
Number Layers
(a) Lipschitz estimates normalized to trivial bound
(b) Computation time (seconds)
Figure 1: Performance for incrcasing network depth, with 40 neurons. The red x markings indicate that the algorithm fails to provide an estimate within the computational cutoll time beyond this network size.
Effect of width. From Fig. 2 most trends mirror the above case where we varies network depth. Here, LipDiff remains the loosest, and GeoLip again matches the accuracy of Fast. Within the restricted SDP family, CF is tighter than FCTipsFF-Fast, while Fast nearly matches LipSDP-layer and approaches FCLipsF.. The highest tightness is still attained by LipSDP, GLipSDP, and Acc. In terms of computation time, AAO fails immediately and SeqLip breaks down at width 10. GeoLip, GLipSDP, and LipSDP- -eurrn are most affected by increasing width, with computational costs rising much faster than for our proposed methods. LipDifT is less sensitive to width than the other benchmarks; however, the computation time still grows faster than our proposed algorithms, while yielding looser estimates. LipSDP-layer also shows noticeable growth in computation time with network depth but remains acceptable. By comparison, Acc, ECLipsE, and Fast exhibit slightly faster than linear computation times, yet scale much more favorably than the benchmarks. At the most efficient extreme, ECLipsEi-Fast and CF continue to have negligible runtime.
Taken together, these results highlight distinct groups of algorithms. LipSDP-neuron. LipSDP-layer, and GeoLip provide reasonably good accuracy but are not scalable, with costs growing rapidly as networks enlarge. LipDiff scales better but yiclds overly loose estimates, limiting its practical valuc. GLipSDP shows scalability with respect to depth but becomes increasingly costly as width increases. By contrast, the ECLipsE family demonstrates a clear trend of maintaining scalability while preserving competitive accuracy. Acc takes slightly more time than ECLipsE but remains equally scalable and produces bounds at the same better level than LipSDP-neuron. Fast runs faster while matching the accuracy of LipSDP-layer and ECLipsE. Finally, the closed-form variants, ECT.ppsF-Fast and CF, incur negligible runtime, with the latter yielding tighter estimates. While the advantages are only partially revealed in this small-scale setting, the trends point toward the much clearer separation we will observe in the large-network experiments discussed next.
Case 2: Large Neural Networks. Setup. As we observed in Case 1, SeqLip and AAO fail at small network sizes and are therefore excluded from further experiments. To examine scalability with larger networks, we consider FNNs with the number of layers in (30, 40, 50, 60, 70) and the number of neurons in (60, (60,80, 100, 120). For this setting, we generate networks with the ELU activation to demonstrate the consistently superior
17

---

Published in Transactions on Machine Learning Research (03/2026)
Tightneza of Lipachitz Estimates for PNN with 20 Layers
Time for Lipachitz Extimatis for FNN with 20 Layers
200
10
1950 Rayer
C0 Ist LodssAee
Secup
E.Spaic Gan ECloopt Over Line
UpDrt
107
180
Noemol
103
10
80
10
80
Namber of Neurons
Number of Neurans
(a) Lipschitz estimates normalized to trivial bound
(b) Computation time (seconds)
Figure 2: Performance for increasing network width, with 20 layers. The red x markings indicate that the algorithm fails to provide an estimate within the computational cutoff time beyond this network size.
performance of our algorithms even with nonlinear activation functions. The cutoff time for this set of experiments is set to 60 minutes.
Tightness Lipschitz Estimates Neurons
for Lipschitz Estimates for FNN 100 Neurons
1000
Riigal
Normatae Liperittz Estiaaess
10
800
1
000
10
400
10
Rasiical
800
Number Layers
Number of Layers
(a) Lipschitz estimates normalized to trivial bound
(b) Computation time (seconds)
Figure 3: Performance for increasing network depth, with 100 neurons.
Although LipSDP-neuron and LipSDP-layer have exponential running times as the number of layers increases, they adopt a splitting strategy Fazlyab et al. (2019) to mitigate the scalability issue, wherein they split the network into sub-networks, and multiply the Lipschitz constants of the sub-networks to obtain the final estimate. In our benchmarks, we consider the split versions of both algorithms, termed LipSDP neuson--eurn--pllit and LipSDP-layerspliit respectively. For LipSDP-ncuron-sple and LipSDP-layor-split,, the FNNs are split into sub-networks 10 layers each and three workers are used for parallel computation to accelerate the process.
We choose the split variants of LipSDP as a baseline primarily because the standard LipSDP variants exceed the cutoff time for Lipschitz estimation without splitting and parallclization. Note that while our method can be similarly parallelized by splitting the network into sub-networks, full network as it is scalable and computationally efficient by design, while prioritizing tightness. This choice allows us to retain coupling information across the full network where standard LipSDP fails.
apply ECLipsE-Gen-Lovee to the
Results. Among the benchmarks, we report that GeoLip fails at the smallest configuration (30 layers, 60 neurons) due to kernel crashes, while LipDiff consistently produces invalid estimates larger than the naive upper bound. Therefore, for the remainder of this discussion, we focus on the remaining algorithms, reporting results for two cases: (i) fixing the number of layers to 60 while varying the number of neurons, and (ii) fixing the number of neurons to 100 while varying the number of layers.
18

---

Published in Transactions on Machine Learning Research (03/2026)
Tightness of Lipschitz Estimates for FNN with 60 Leyers
Time for Lipschitz Eatimates for FNN with 60 Layers
1000
updpn Ganiucaiies
1420
Canuicai Fasl
EC4
Normllzedd Locahiz Eddiaats
10"3
1000
updon
updin avaespi
1100
8900
800
Scleeli der Local
Scluul der Lo
400
200
120
120
Number Neurons
Number Neurons
(a) Lipschitz estimates normalized to trivial bound
(b) Computation time (seconds)
Figure 4: Performance for increasing network width, with 60 layers. The red x markings indicate that the algorithm fails to provide an estimate within the computational cutoff time beyond this network size.
Tightness. Across both cases, namely, varying the network depth with 100 neurons and varying the network width with 60 layers, we observe that the same insights emerge according to Figs. B and 4 First, we observe that while GLipSDP scales with depth, it fails beyond the 60-neuron cases for the wide networks considered here. Tn terms of tishtness, in Fig. 3a LipSDP-layer-splitt, with CF slightly tighter than ECLipsE-Fast, but comparatively looser than Fast. ECLipsE, LipSDP-neurron-ppiit, Fast, and Acc form close cluster in accuracy, with Acc consistently tighter than Fast. Nolably, Fast is almost as light as ECLipsE, despile the relaxation with A, X,T. When the outpul landscape is locally flat over the input region, the advantage of our methods capturing local information becomes particularly pronounced. For example, in Fig. [3| with 40 layers, Acc is more than 107 times tighter than
4a F.Ct and CF yield tighter estimates than
in Fig. 4a with 120 neurons, Acc is over 10 tighter than LipSDP-nnuroo--plltt.
Computation time. Even with splitting and parallelism that requires more computional resources (three cores versus one for our methods), LipSDP-neuron-splii is only slightly faster in Fig. 3b and generally slower than Acc in Fig. 4b at similar tightness, while LipSDP-layer-splis is essentially par with Fast. However, we emphasize that ECLipsE- Fast and CF remain negligible in time cost owing to closed form solutions, with CF uniformly tighter than ECLissE-Past.
methods achieve this performance without relying parallel computation. Once again,
In conclusion, Acc offers the tightest bounds with strong scalability, Fast matches the accuracy of LipSDP- layer-split and ECLipsE at lower cost, and ncar-instantancous while being tighter than ECLipsE-Fast These properties underscore the practical advantage of the GennpslF-Ge--Local family in estimating local Lipschitz constants for large networks.
4.2 Tightness of Local Estimates: Achieving Provable Upper Bounds at autodiff Level
We have demonstrated scalability, efficiency, and tightness of our algorithms in the previous section. Here, we study the lightness of the cerlified local bounds as the local region shrinks. We consider
BB 5g) centered at 2 = [0.4, 1.8, -0.5, 1.3,, 0.9]T with radius chosen from 82 E {5, 1/5, 1/52, 1/53, 1/5', 1/55). J. We evaluate three FNNs of 5, 30, and 60 layers (128 neurons cach) with Leaky (a = 0.01). While the insights are commou across all three cases, we present the 30-lr case here and defer the others to Appendix A.3 For reference, the trivial bound (valid for the entire region 2) is 3.070 x 1010, contrasting the scale of the certified upper bounds for the chosen regions.
From Fig. we observe that as the radius of the input region decreases, the estimates from all three variants Acc, Fast, and CF tighten monotonically by many orders of magnitude. Among the three variants, CF, though generally looser, has negligible runtime and continues to improve as the radius shrinks, capturing the local behavior of FNN at small óz. Acc is uniformly the tightest and Fast closely tracks Acc. The local Lipschitz estimates from Acc, and Fast drop sharply at input radius 1/25 for Acc and 1/125 for Fast, and approach
19

---

Published in Transactions on Machine Learning Research (03/2026)
the autodiff level, that is, the gradient norm at the center 2e, when the radius d₂ is small enough. Notably, the gradient norm at & generated by autodiff is a strict lower bound on the Lipschitz constant, making our algorithms essentially optimal in terms of tightness. Importantly, unlike autodiff that provides gradient norm at the center of the input region, our estimates are provable upper bounds serving as certificates for the entire local region.
Remark 5. (Local vs. Global) The practical value of local estimates depends on the scale of the input region. For large regions or when model behavior is expected to be homogeneous over the full domain, the local bound is close to the global constant. In such cases, scalable global estimation algorithms like ECLipsE (if applicable) are preferable due to lower computational cost. However, when the region is small to moderate, such as in robustness certification around a specific input (as will be demonstrated in Sec. 4.3), the proposed local method exploits the local landscape to yield significantly tighter bounds, justifying the additional computation cost.
Tightness vs. Input Radius
30 layors (128)
10
Lipschitz estimate AAtodiif
108
ECiieE-Gee Loca-loa
EClipeE-Gen-Loode Genee------Lool-aa
10
EClipeE-Gen-Loaaee Autodiff
10
10
10
5
1/5
1/25
1/125
1/625
1/3125
Input radius
Figure 5: Lipschitz estimates normalized to autodiff value at 2e (0.0015). Naive bound: 3.0698 x 1010.
4.3 Lipschitz Estimates on Standard vs. Robustly Trained Networks
Setup. The final set of experiments estimate the local Lipschitz constant for various sizes of the input region on two networks, one trained conventionally and the other trained with robustness objectives, highlighting the practical utility of tight estimates from methods. We use the MNIST dataset and train two FNNs with identical architectures: three hidden layers of 128 units with ELU activations. The baseline network is trained with standard cross-entropy loss, while robustly trained network employs Jacobian regularization (JacobianReg) (Hoffman et al. (2019)). ), which penalizes the norm of the derivatives of the network's ' outputs with respect to its inputs in order to encourage smoother mappings and improve robustness. Both FNNs achieve an accuracy of at least 98% on the test. set. We assess robust using a standard l2 projected gradient descent (PGD) attack on the test set (Madry et al. (2017)): for each test point x, we search for misclassifications under attack within the lg ball {2 1 2/12 c). Details on the training and testing of both networks are included in the Appendix A.3
To establish the relationship between robustness and Lipschitz estimates, we first empirically quantify the robustness of the two networks by recording the failure rate of both networks under an E, PGD attack with radius e chosen from 1/4, 1/8, 1/16, 1/32, 1/64, 1/128, 1/256]. This means that adversarial perturbations are chosen from an & ball of size e around each test point. Independently, we randomly sample 20 data points from the valid input region of the MNIST dataset and compute certified local Lipschitz constants 20 points on the same e-balls using Fast. This experiment design provides statistically meaningful comparison between robustness to adversarial perturbations and Lipschitz estimates at matched scales. Fast is chosen
20

---

Published in Transactions on Machine Learning Research (03/2026)
for its balance of accuracy and efficiency, as it is computationally cheaper than Acc and captures local region information more effectively than CF.
The Utility the Estimates Regarding Robustness
90
10%
Lipechitz Estinates (base)
80
Lipachitz Estimates (i)
9%
Failum rata (base)
Fallure re under adver attack (%6
ECLipsE-Gent -e---o---oo--aa estimate (maan
Fallure rata (?)
8%
30
7%
50
6%
40
5%
30
4%
3%
10
2%
1%
1/2
1/4
178
1/16
1/32
1/64
1/128
1/226
Inpu: radius (e)
Figure 6: Lipschitz estimates for different size of input region on baseline model and robustly trained model. The blue and orange solid lines plot the mean the Lipschitz estimates for the baseline and robustly trained models, with the shaded interval representing the standard deviation of the Lipschitz estimates across the sampled points. On the same axes we report the failure rate of each network under adversarial perturbations of radius e, shown lighter curves on the secondary vertical axis.
Results. Figure 6 shows how certified Lipschitz estimates relate to robustness, which is quantified as the empirical failure rate under adversarial attacks. For each e, compare the local Lipschitz estimates on the input region of radius e, and the failure rate of each network under adversarial perturbations of radius e. It is clear that the robustly trained model consistently exhibits smaller Lipschitz estimates together with lower failure rates for every e. Meanwhile, the standard deviation of the estimates shows an increasing trend as decreases, indicating that our method manages capture the diversity of local landscapes around different points. These aligmments between the certified Lipschitz estimates and observed robustness illustrates the practical utility of our method in capturing robustness through provable and tight Lipschitz upper bounds.
Robustness cerlificules. To further demonstrate the utility of light and strict Lipschitz estimates, report robustness certificates on the regularized MNIST model using the standard Lipschitz-margee certificate for multi-class logits (Tsuzuku et al. (0018)) ). This Lipschitz-based robustness cortificate provides a lower bound on the l2 perturbation magnitude required to eliminate the logit margin between the predicted class and its closest competitor, thereby guaranteeing label invariance within the certified radius. We sweep the same radií 1/4, 1/.,... 1/256 and use the same test points as in our local Lipschitz evaluation. For each test point 2, compute certified local Lipschitz bound L(x, e) that is valid within the analyzed radius e, compute the logit margin m(x)= fg(x) maxjø9 [xx,, and form the candidate radius rese(æ, = mxx)/ e)). Since a Lipschitz bound certified on radius e is also valid for any smaller radius, we use the valid certificate Feere c) = min(rese(2;; c), c), which guarantees that any perturbation with ||ō']2 < Toere(z, <) cannot change the predicted label. We then report the least conservative certified radius across the swept scales via r(z) = max (1.,, (x, Detailed results, along with comparisons against the certified radius obtained from the global trivial bound Liris = 236.4329, are reported in Appendix A.3. The mean certified radius produced by our local Lipschitz estimates is 6.14 times larger than the mean certified radius obtained from Ltries indicating substantial reduction in conservatism.
21

---

Published in Transactions on Machine Learning Research (03/2026)
5 Conclusion
In this work, we introduced ECLipsE-Gen-Local a compositional framework that provides certified upper bounds for the Lipschitz constants of deep leedforward networks. By adapting SDP-based Lipschitz certificales to accommodate heterogeneous slope bounds for the activation functions, systematically incorporating local information on the input-region, and decomposing the largo-scale SDP for Lipschitz estimation into soquential sub-problems, our algorithms provide provably valid and tight estimates with linear complexity in depth. Notably, propose a variant that provides closed-form solutions at each sequential sub-problem, achieving near-istanntaneuus computation while retaining certification guarantees. Through extensive experiments, we showed that our methods deliver outstanding scalability and produce substantially tighter bounds than global approaches, with local estimates approaching the the exact Lipschitz constant in small regions. Finally, since our certificate relics only on affine transformations and sector- sector-buundd activations, it is natural to exlend this framework to other architectures such as Convolutional Neural Networks and Residual Networks. Future work will focus on extending the framework other architectures, and on integrating local Lipschitz certificates into robust training for safety-critical tasks.
References
Etika Agarwal, S Sivaranjani, Vijay Gupta, and Panos Antsaklis. Sequential synthesis of distributed controllers for cascade interconnected systems. In 2019 America Control Conference (ACC), pp. 5816 5821. TEEE, 2019.
Filippo Amato, Alberto López, Eladia María Peñia-Méndez, Petr Vañhara, Aleš Hampl, and Josef Havel. Artificial neural networks in medical diagnosis, 2013.
Sajjad Amini and Shahrokh Ghaemmaghami. Towards improving robustness of deep neural networks to adversarial perturbations. IEEE Transactions on Multimedia, 22(())1889- 1903, 2020.
Panos J Antsaklis et al. Neural networks for control systems. IEFE Transactions on Neural Networks, 1(2): 242 244, 1990.
Alexandre Araujo, Aaron Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. A unified algebraic perspective on lipschitz neural networks. arXiv preprint arXiv:2303. 2i5i::2303.01699, 2023.
Anil Aswani, Humberto Gonzalez, S Shankar Sastry, and Claire Tomlin. Provably safe and robust learning- based model predictive control. Automatica, 49(5):1216- 1226, 2013.
Trevor Avant and Kristi A Morgansen. Analytical bounds on the local lipschitz constants of relu networks. IEFE Transactions on Newral Networks and Learning Systems, 2023.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally- normmalzze margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Aritra Bhowmick, Meenakshi D'Souza, and G Srinivasa Raghavan. Lipbab: Computing exact lipschitz constant. of relu networks. In Artificial Neural Networks and Machine Learning- ICANN 2021: 30th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 14-17, 2021, Procetdings, Part IV 30, pp. 151 162. Springer, 2021.
Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning in robotics: From learning-bai based control to safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5(1):411 444, 2022.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pp. 39-57. Icce, 2017.
Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimization for lipschitz constants of relu networks. Advonces in Neural Information Processing Systems, 33:19189-1920 2020.
22

---

Published in Transactions on Machine Learning Research (03/2026)
Patrick L Combettes and Jean- Chan-Chrittophe Pesquet. Lipschitz certificates for layered network structures driven by averaged activation operators. STAM Journal on Mathematics of Data Science, 2(2):529-58) -57, 2020.
Michael Everett, Golnaz Habibi, Chuangchuang Sun, and Jonathan P How. Reachability analysis of neural feedback loops. IEEE Access, 9:163938 163953, 2021.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in neural information processing systems, 32, 2019.
Mahyar Fazlyab, Manfred Morari, and George J Pappas. Safety verification and robustness analysis of neural networks via quadratic constraints and semidefinite programming. IEFE Transactions on Automatic Control, 67(1):1-15, 2020.
Mahyar Fazlyab, Taha Entesari, Aniket Roy, and Rama Chellappa. Certified robustness via dynamic margin maximization and improved lipschitz regularization. Advances in Neural Information Processing Systems, 36:34451-34464, 2023.
Chris Finlay, Adam Oberman, and Bilal Abbasi. Improved robustness to adversarial examples using lipschitz regularization of the loss. 2018.
M Tarafdar Haque and AM Kashtiban. Application of neural networks in power systems; a review. Power, 2005, 2000.
Aaron Havens, Alexandre Araujo, Siddharth Garg, Farshad Khorrami, and Bin Hu. Exploiting connections between lipschitz structures for certifiably robust deep equilibrium models, Advances in Neurol Information Processing Systems, 36, 2024.
Gooffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504 507, 2006.
Judy Hoffman, Daniel A Roberts, and Sho Yaida. Robust learning with jacobian regularization. arXiv preprint arXie: 1 1908. 02729, 2019.
Chao Huang, Jiameng Fan, Wenchao Li, Xin Chen, and Qi Zhu. Reachnn: Reachability analysis of neural- network controlled systems. ACM Transactions on Embedded Computing Systems (TECS), 18(5s):1 22, 2019.
Yujia Huang, Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local lipschitz bounds. Advances in Newral Information Processing Systems, 34:22745 22757, 2021.
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. Advances in Newral Information Processing Systems, 33:7344-7353, 2020.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. arXie preprint 27X6::2004.08688, 2020.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553):336 444, 2015.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXic: 106.0003660003,, 2017.
Ishan Misra, Abhinav Shrivastava, Abhinav Gupta, and Martial Hebert. Cross-stitch networks for multi-task learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3994-4003, 2016.
Matthew Newton and Antonis Papachristodoullu. Exploiting sparsity for neural network verification. In Learning for dynamics and control, pp. 715 1277 PMLR, 2021.
23

---

Published in Transactions on Machine Learning Research (03/2026)
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. arXiv preprint Xrxiv: 1rXii:1777.0000 707.09564 2017.
Xiang Pan. Deepopf: deep neural networks for optimal power flow. In Proceedings of the 8th ACM International Conference on Systems for Energy- Effrcye-f Buildings, Cities, and Transportation, pp. 250 251, 2021.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. Training robust neural networks using lipschitz bounds. IEEE Control Systems Letters, 6:121-126, 2021.
Patricia Pauli, Dennis Gramlich, and Frank Allgöwer. Lipschitz constant estimation for 1d convolutional neural networks. In Learning for Dynamics and Control Conference, pp. 1321-1332. PMLR, 2023.
Patricia Pauli, Dennis Gramlich, and Frank Allgöwer. Lipschitz constant estimation for general neural network architectures using control tools. arXie preprint arXiv:2405.011 01 125, 2024.
Wenjie Ruan, Xiaowei Huang, and Marta Kwiatkowska. Reachability analysis of deep neural networks with provable guarantees. arXiv preprint arXiv:1805.022 02242, 2018.
David E Rumelhart, Geoffrey E Hinton, and Ronald Williams. Learning representations by back-propagating errors. nalure, 323 -3663336-3361113 1986.
Zhouxing Shi, Yihan Wang, Huan Zhang, J Zico Kolter, and Cho-Jui Hsich. Efficiently computing local lipschitz constants of neural networks via. bound propagation. Advances in Neural Information Processing Systems, 55:2350-2364 2022.
Xiaowu Sun, Haitham Khedr, and Yasser Shoukry, Formal verification of neural network controlled autonomous systems. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, pp. 147-156, 2019.
Christian Szegedy, Wojciech Zaremba, Tlya Sutskever, Joan Bruna, Dumitru Erhan, Tan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Wallace Gian Yion Tan and Zhe Wu. Robust machine learning modeling for predictive control using lipschitz-constraince neural networks. Computers & Chemical Engincering, 180:108466, 2024.
Yang Tang, Chaoqiang Zhao, Jianrui Wang, Chongshen Zhang, Qiyu Sun, Wei Xing Zheng, Wenli Du, Feng Qian, and Jürgen Kurths. Perception and navigation in autonomous systems in the era of learning: A survey. IEEF Transactions on Neural Networks and Learning Systems, 34(12):9604-9624, 2022.
Surat Tecrapittayanon, Bradley McDanel, and Hsiang- Kung. Branchynet: Fast inference via carly exiting from deep neural networks. In 2016 23rd international conference on pallern recognition (ICPR), pp. 2464-2469. IEEE, 2016.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz margin training: Scalable certification of perturbation invariance for deep neural networks. Advances in neural information processing systems, 31, 2018.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deop noural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018
Ruigang Wang and Tan Manchester. Direct parameterization of lipschitz-buunded deep networks. In International Conference on Machine Learning, pp. 36093 36110. PMLR, 2023.
Zi Wang, Gautam Prakriya, and Somesh Jha. A quantitative geometric approach to neural-network smoothness. Advances in Neural Information Processing Systems, 35:34201-342155, 2022.
Zi Wang, Bin Hu, Aaron Havens, Alexandre Araujo, Yang Zheng, Yudong Chen, and Somesh Jha. On the scalability and memory efficiency of semidefinite programs for lipschitz constant estimation of neural networks. In The Twelfth International Conference on Learning Representations, 2024.
24

---

Published in Transactions on Machine Learning Research (03/2026)
Tianhao Wei and Changliu Liu. Safe control with neural network dynamic models. In Learning for Dynamics and Control Conference, pp.
PMLR, 2022.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference Machine Learning, pp. 5276 5285. PMLR, 2018
Weiming Xiang, Hoang-Dung Tran, Xiaodong Yang, and Taylor T Johnson. Reachable set cstimation for neural work control systems: A simulatioo-guideed approach. IEEE Transactions on Neural Networks and Learning Systems, 32(5))1821-188 1830, 2020.
Yuezhu Xu and S Sivaranjani. Learning dissipative neural dynamical systems. IEEE Control Systems Letters, 7:3531 3536, 2023.
Yuezhu Xu and Sivaranjani. Eclipse: efficient compositional lipschitz constant estimation for deep neural networks. In Proceedings of the 38th International Conference on Neural Informalion. Processing Systems, pp.
2024.
Anton Xue, Lars Lindemann, Alexander Robey, Hamed Hassani, George J Pappas, and Rajeev Alur. Chordal sparsity for lipschitz constant estimation of deep neural networks. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 3389-3396. IEEE, 2022.
He Yin, Peter Seiler, and Murat Arcak. Stability analysis using quadratic constraints for systems with neural network controllers. IEEE Transactions on Automatic Control, 67(4):1980-1987, 2021.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Yu Chen, Cho-Jui Hsich, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in neural information processing systems, 31, 2018.
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsich. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5757 5757-5764, 2019.
Tianyu Zhao, Xiang Pan, Minghua Chen, Andreas Venzke, and Sleven H Low. Deepopf+: A deep neural network approach for de optimal power flow for ensuring feasibility. In 2020 IEEE international conference on communications, control, and computing technologies for smart grids (SmartGridCommm) pp. 6. IEEE, 2020.
Monty-Maximilian Maximilian Zühlke and Daniel Kudenko. Adversarial robustness of neural networks from the perspective of lipschitz calculus: A survey. ACM Computing Surveys, 57(6):1-44) 2025.
A Appendix
A.1 Proofs
Proof of Theorem 2 Let 2 22 be the outputs of layer L; for two arbitrary inputs, and define Ar
(0)
=10 - (1) Au(0 = vi u2 for all i E [O]UZN- Zy. Consider the stacked vector Az = (A7 A2(N-1)T
Left and right multiplying the matrix 4 by AzT and Az and utilizing the fact that Az(2) = (N-1)
we obtain
N
(i-11)7
T
A2(1-1)7
(A= (0)
+
Σ
A2
Y1
A=
(() 0,
(37)
1=1
where Y, A D.
WT (Dai + DB:)A,
LA( + W
A;
By the slope-restricteduuss condition in Assumption 1 for E EN-1, we have a'Ao(0 < A (.'A(0).
25

---

Published in Transactions on Machine Learning Research (03/2026)
Equivalently, for any A₂ E ++
A
Da Do Ai + Dg.)
-2 + D3:)A,
[v(t)
Az
A
Az(1)
S O.
Since Ar W,Az(111, this yields
A Az(i-1) 1) Az
Y
S
Thus, every summand in 37 involving Y, is non-positive. Therefore,
(A=')))>>>))) (0) (44 0,
which further gives
|A 112 S 1//FI
implying that the Lipschitz constant is at most vI/F.
Proof of Theorem The proof is similar to that of Theorem 2 Let 21 200 be the outputs at layer
(p) Tag for two arbitrary inputs, and define A=ú) = =1/ - 2 for j p...., ,. Let Azl and A denote the subvectors of (p(P) and Az indexed by X. S Es, and L S Ld,, respectively.
(6)
Consider the stacked vector
Az = (A= (Aa(+t))yr ...., (A2(1-1)77*
Left and right multiplying the matrix
by Az yields and utilizing the fact that d= (
Az (m T
(m(m-1)]
(A= (p)
(A=
Σ
(m)
Ym
Am(m)
- (TA= ((Aa(i-))) 0.
(38)
m=pt1
where
W Da am Am Dm Wn - WT (Dam + Dmm Amm Am DDm + D3m Wm,
Y,
Am
Similarly, by the slope-restrictednnss condition in Assumption 1 for each m, and for any Am ID+,
Av(m)) T
DamAm Dgm (Dam + Dam Am
Au(m)
(m)
1 (D Dgm)
Am
Am)m)
Since (m Wm (m-))) 1), this yields
(m- (m-m-1)7
(m( (m)
Ym
(m
$0.
Therefore, all terms involving Y., in 38 are non-positive.
Hence,
(Az (p) (Ap) (A ( - F()=(0) (W:) (Wo)c..)(A 2 0.
Since (Az(0)) (W.)(c.)) Az(i-1), this further gives
| 1 122 < /1/FIAe('11 122
establishing that inequality 6 holds.
26

---

Published in Transactions on Machine Learning Research (03/2026)
Proof of Theorem 4 The result follows by applying Lemma 2 in Agarwal et al. 2019 to the symmetric
block tridiagonal matrix in defined as
By Lemma in Agarwal et al. (2019). a symmetric block tri-diagonal matrix
P1
R₂
0
RT
P2
R3
0
RJ
P3
0
0
RV-1
PN-1
RN PN
0
R
is positive definite and only if
X, 0,
Vi (0) UZ-UZ
where
Pr
if == 0, if Z,-1- R
X,
For our matrix, we directly substitute P, with P,, R2 as defined in 5 and we have the result that the block tridiagonal matrix in (4] is positive definite if and only if the sequence of inequalities in holds, with X, defined in 10
Proof of Proposition 1 Applying the Schur complement to the LMI 14 with slope bounds aadj and giadi directly gives an equivalent condition be M, c. WW W4+1 2 0, where
1 N; (Daraa) + -Dginnn) W. (X WT (Darsas + Dasinss) ) Ai- M, = A 4
This holds if and only if amad WT,, W441 M, r). According to Lemma maxx (W Ws+1 M,¹)
Omax (Wi+1 M WT.). completing the proof.
Proof of Proposition By Theorem 4 with X; > 0, i E -2, remains to prove that KN-I-FWTT WN
0. This is equivalent XI-1/F3 > WNWN. Then, the smallest possible 1/F Jmaz (WN (M(-) By
Theorem the tightest upper bound for the Lipschitz constant then vI/F = Omaz (W N WWNNNNNNN))
Further, Trom Lemma D and the fact that MN-1 > 0 we have the certified Lipschitz constant to be
Vmazz Fonaz(WN(Cer (WN(Mx)))-
Proof of Theorem 5 Let "e and (a', ".,, be two sets of slope bounds for the activation
functions, where for some i, (aj. 3y] (aj.B3)) and all other entries are identical. Let F and f denote the
maximal values such that the matrix inequalities in (4 and (5) are satisfied for the respective choices of slope
we left and right multiply the matrix in 4 by AZT and Az, where Az [A= AN and obtain
bounds. Adopting the notations in the proof of Theorem 2
(A: ( A (0)
N-1
Σ
Ao
T
D.i (Da(Da +Dz)
1D + +D ).:
Ao A2
F(A > 0. (39)
A
For the second term in 139
for each layer Ls, we have
Da:A,Do (DAi(Da:+Dp
-1 + D3:)A,
An(i)
50.
A2
A
Az(1)
Expanding this block diakonia form, with X3 being the jth diagonal entry of Ar, we obtain equivalently
[
af
- -2 +
+
An (
5..
(40)
[a + BA)A
X5
A2
27

---

Published in Transactions on Machine Learning Research (03/2026)
Let Jt,1 = (j: laj, 891 c 1áz, pJ1
and Jt.2 [j:1a.. - l6g. 031). Then, we split (40) as
de Σ 1=1
(a),
Σ (2) +
Σ
JEJ
JEJi2
For j E Jt, ( 03] C ( R3]. With the slope bounds assumption in Assumption and X3 0, we have
s o0 AAvY A22" X 2 0,
For j E J122
-f
Then, for all (Auli, A we have
Σ
o (a)
Σ (a),
Substituting the above inequality into 139
we have, for any fixed choice of { with Ar E Ii+
N- d
(A (0)
+
Σ
(()=))))))
1=1
N-1 d -(A,
((A= (0)
Σ Σ i=1 1=1
This mcans that for any fixed choice of {A,} with A, E D+. the largest value F and the largest value F such that (39h holds with slope bounds (ā², } and {á', (') respectively, satisfy
F(AH) Z F(AA)).
Consequently, taking the supremum over all choices
{Ai} with A; E D+, we obtain
F P"2 F
where F = supta, F((A.)), f = sup F(AA))
Therefore, the corresponding Lipschilz upper bounds satisfy v1/B= S v1/F
Proof of Theorem G Let 2 E Z = B(2e, 5z), and define d2 = Ze. By Clarke's Mean Value Theorem, for any 2, 2e E 2, there exists X 2. + 1(2 za) E Z for some E [0. 1], and E 0g(X), such that
g(z) - g(zc) = T= ze),
where 0g(X) denotes the Clarke subdifferential of g at X, defined as
0g(X) co
lim Vg(ze) 24 X, g differentiable at zk & k
with denoting the convex hull.
Since g is locally Lipschitz with constant L over Z, for any u E 0g(X) and any X E 2,
Ig(z) g(2+) < L 62112
28

---

and Published in Transactions on Machine Learning Research (03/2026)
Therefore,
g(=e) L||øz||2 S g(=) S ((z)) + L||02|12:
which is exactly (20
Proof of Proposition 3 We require [a], [f] to contain all subgradients of & over v E [a, b], that is,
U
0p(v) S [of./9)
Thus, the minimal (tightest) interval is naturally given by
af inf inf (n((a)())) B] = sup sup(O)()))
rE(a.
ve(a,
Proof of Proposition Observe that for any row index the 1-th diagonal entry of (M(M;-1)-
(Wi(M:-1)- (1.1) = (M.)))
(41)
By Lemma 1 if M > O, then (M,-)) and A(M;-1)~1A"" share the same nonzero eigenvalues for any matrix A. Applying this to the row vector (W.)(..)) we see that (M)) share the same nonzero eigenvalues. Therefore,
Omax (wo)) (Ma Tmax (M. (M-))
The last equality holds as (M--1) (Mi-) Notice that for each = 1, ........de de
is scalar. Combining with (41 completes the proof.
Proof of Lemma
d (W.(M--)) (1.))
(M--)
Let A; = (M E Rdd ixd; Then, for each 1,
d:11 d Σ (Wa)aassAA))
Now, observe that (W)) is the k-th column of W, and (A)(a..)) is the k-th row of A, The elementwise
product (W @ (1))) is a vector in Rd whose I-th entry is (Wa),,)))))
d--
Summing over k, we have (())
Σ (Wi) @ (())) which establishes (24).
Proof of Proposition 5 For cach j E fi. p} with a =3², layer Lj acts
200 Dasu(i) = Dav (w,zb-1)+ +b))
(42)
We prove 29 by induction on s E (1. p} that
(1+s) = Wits 2 (i-1) + Biter
(43)
where
i
WH++
II
W Wat W..
(44)
29

---

Published in Transactions on Machine Learning Research (03/2026)
bits
II
(W (a)+Daa)bt
(45)
where the product W Ded reduces to the identity matrix if s+1.
When 1, at layer Lj+1, have
(0+11 W W5+12 + bb411-
(46)
Substituting 42 into vl+1) directly gives
(l++1) War (Wzz(+-1)+ +b²) + +bb+1 Wit1Dar Wj 20-1) + Wi+1Dawbb + bjt1.
(47)
$ W,411
by41
Now assume 43
45
holds for 8, 2p-1- Using a²= =Bits
((tts-1)
Wi+++12 2(+x)) + bits+1
-Wi+o+1 D Dattulltt) bi-st1
(48)
Wits41 D WateWWi (0-1) Wits+ Dai-niius + Dets-1-
By induction, we have
i+s Wtt Doe Wi,
W4s+1 = Wits+1 Dasta Wits
(49)
and
s+1
i+s-l
bi+041 W Wits4iDattaee bi+041
Σ
(W,+1 Dai biak-1
(50)
j=ith-1
We first show that the feasible set is non-empty and the maximum of e can be attained. As the feasible set with strict incqualities is open, we consider the closed relaxation of (13
Proof of Proposition c
A; - N--aW_,We W+4 (D.: + +Da)AA
{ + +Dz) W,
max C s.t. A.A.
20, A 4; 420.
(51)
X1-1
Select an such that < < min(1, 2/0maz ((Da + DD:) W? + D3:))) and let
A =T,
G 40maz (W7 6+1 W
Applying the Schur complement to the LMI in 51 with the fact that X,-1 > 0, we obtain that (51 is strictly feasible. Thus Slater's condition holds, implying that the feasible set of (51) is closed and convex. As the objective is linear, and the optimal value is finite, we conclude that the maximum & is attainable.
Denote (cf At) to be an optimal solution. Now we prove that for any A, > A and ot, the constraints are all satisfied. Note that constraints on A, and e are automatically satisfied and we focus on the LMI. The
13
LMI in (13) is equivalent to the following statement. For any V x
Rd:+4 1 11
y
(W aT A₂ a (W++20]((W++1)) x² A,(DD D " WW (Da: + D3:)AAz
(52)
+ n (MM WT A; W.) 0.
30

---

Published in Transactions on Machine Learning Research (03/2026)
Let Ti 22 Lu, be the index set where (a')s, = (8'),, and define M₁ Zd. VJs + 0. We further split the left hand side of 52 by index sets J. and M2 as
H(A, c.)
(AN + [())M] (A)cMMMMM)))))) +o Mi-18
+ ((W.)a, (o (Dai)i
(Wa))., + (Maii) (MiMM))
(Wir).:
(3T.5)
+2( (d"AiiDar + D3i)) (o.3i) (Wiy)a, 1 {x (x="Ai(D'' +D.)) (o.Mi)
(Wiy).:
+ [(waa)el'
+ = ( + Da D2g))A)))
J.
M: (Waz)) (x)M.
-ca ((()))))) ((WWea) (W (Wi+1) (x) (+)
[())m.) +[())a] (1(W=))) (WW (D)
(z)M. +
(W > O.
We denote the part dependent on (A.)( to be
G((A))().3))) - (A.)) + ((Wa)) (Dai../))) (I..3))
(Wiy)
+ 1 (T (i +Da)) (Jr.Jt)
(Wa)s, + 1 ((Wa))))) (Dot + DΦ )1arr J.
= =(()), + D ( Ag ((z) + (a.y))
The last equality holds by the definition of J., (Der)., = (Do.),, Therefore for any A > Aj,
H(A,, - ci) =G((A)) - G((A))))))))
((z)s, + Da (W.)s)) A ((x) 20.
-()))))))))))),).))))))))))))))) Da (. ((F)s + (Waa))) A ((x)a, (W.())))))
By the arbitrariness of x and y, conclude that constraints in 13 are satisfied with any A, > A while the {AA)) completes the proof.
optimum of is attained. Taking | = max
jEZd;
Proof of Theorem Under the mild assumption a' @ g 2 0 for all i E ZN-1 and using the fact that
Mo = 1 > 0, it suffices to show by induction that at layer L,, i E EN-1, the following claims hold:
(i) Given M,-1 > 0, the feasible set of the SDP constraints 13 and 14 is always nonempty and the closed-form solution (15) always well-defined and positive.
Optimization problems 13
and equation [15 can each yicld a solution A, such that M; >
Since 14 is special case of 13 with A, X,I, it suffices to prove feasibility and M; 0 for the same conclusions for 13 then follow directly, and no separate proof is required.
Regarding we prove that at stage i E EN- there exists a X; 2 0 and > 0, such that
S; a AI a.- 411 W+1
M, > 0, Dr + DDz > 00
(53)
H.. (D Dz:)
Mi1
where M, X,I tA + Dg: WW. - (D (Dai + D2:), i Zn and Mo I.
Given Mi 0, by the Schur complement, S; equivalent to
T, A c.T W4+1 1 xD + D3. W. (D + Da.) > 0.
Let
0, max
+ 1DDD++DD.....11113 (D.: + D3:)) > 0,
77 max (WT+)1411) W(41) 0.
(54)
31

---

Published in Transactions on Machine Learning Research (03/2026)
Choose X₂ = > 0 and C; 2 d;
0.9 ds%
> 0. Then,
2
0.9
1 4
T; 2
1
W
W11
4 0,
0,
2
0.9
-
1
WT 4+1
W
0:
a
02
1
0.9
1
0
ai
where the last inequality uses [+1 W1+1 $ n:I. Finally, M, = T; + + W4+ 2 T > 0.
With 53 being feasible for E -N-1, the LMI for E 22-
(14 is naturally satisfied with A 2 and G > because
A & Wi+1 N,W7(Dat + D3r))
Ddi(Da:+ D
0 (
= =
2 S 2 0,
X,-1
Ait W Darti +1 D3 W(+1
and for = N- - 1,
A AI-aW 4. Wi+1 FAWTT (Dai Dg:)
}M1(D + DD: )
S; > 0.
X,-1
Then we procoed to show that claims (i) and (ii) hold for the closed-form solution al stage: i, 115 is well-defined and positive. So suffices to show that using \; as in M, > E [0] U -N-
15
Given that M₁-1 >
15 always guaranlees
At stage recall that
M, 11- - Ae( + Dgi. ) (Dai.ml + Dgi.wu))
=111- Xe(Das.mn + Dg WW, )
W? (Dasias + Dgnoa))
The second equality holds because D Dociaas O Diiiad = 0.
Let 0, Fmax ((Dartin)) + Da >W,n,, WT (Daiml) + Dgsmm))) > 0. For the closed-form solution 15
A a: 0. By definition of oi we have (Daint + D Drr mi WW, MT, (Da Dgi.us)) S o,I. Therefore,
M 2 6. 1= = 1,1 > O.
Proof of Theorem Let = B(zc, |60 l2) be the input region. Consider any layer L;, i E ZN-1- Given the validity of the Lipschitz constant _." for each E Zd,-, ie., for any 21, E Z, the map from to the I-th component of 2(0) satisfies
(x)) =1 (1) (=2) < || 22|12-
In particular, taking 22 = ze and arbitrary 21 2, and using the fact that || 2ell2 S 1|62112, we have
(=) - 2 (0
(2x) < L 12 V.
Therefore, for each I,
(2) E 21 (z.) L 11122112 =1 =0)(z)) + + _ 1
E 2.
Thus, the region V defined in Algorithm A Algorithm I the refined slope bounds given by
valid enclosure for all (()) over Z. Next, by construction in
of = inf inf @o(v), VEVi
B = sup (u)).
Ev
Since (2) E Vi for all & E 2, it follows that
af < inf do (2)),
3 2 Sup (z)), (z)),
Vz Z.
32

---

Published in Transactions on Machine Learning Research (03/2026)
Thus, the refined slope bounds a',8 3 are valid for all 2 2, as claimed.
0
Proof of Theorem Let 21") (6) 22 be the layer outputs for two arbitrary imputs, and define Az(9) 2) 22
(2)
Au(1) (
(0) for all i E (0) U ZN. We claim and prove by induction on the layer index d:
(1) maa
[[()))a.))] T (W
are valid Lipschitz constants for 4I E Zd, as defined in (6)
(ii) 1 M + WTT Do,A,Dg W; > 0, and
(iii M,- = A, - AD, + D3: - (D + DB.)A, >0.
For the first layer (i 1), we have
Ao = 11
For any neuron I Zdi the I-th entry is
(Aol)) ())
By the Cauchy-Schwand inequality,
(A s (I(W)) ((Wi)a,)lla |A> = omea ([(W)aa)) (Wi)a..) || 12-
Since Mo = I, the bound can be written equivalently as
L (. Vomar (1(W))oo)' (Wo)
From SCLipsE-Gen-Acc in 13 at i 1, Ai satisfies
A W/
AAi(Da + DD: Xo
WWT D3:)A)
> 0, Ai E D4, ei > 0.
By Schur complement, this is equivalent to
Xo 0, A - w.-,W, 1 Ai + D.)) - D3 > 0.
Therefore, (Xo) -1 well-defined and with e1 > 0,
Mi (Ai WoWw 1 A + (xx) + D3t)Ai) + +oW 0 W W3 2.
Now by induction, assume that at layer I,, Zx-1, we have X3 > O, Wk E Z,-2, and M₁ > 0, Vj Z
By Theorem ad B, Vj E Z4-1, are valid slope bounds. To show the validity of L (0.4) suffices to prove that there exists A j E Z such that
0. by Theorem 3 it
P
R₂
0
0
R3
P2
R3
0
O
R
Ps
0
>
0
R.
0
RT
P.
33

---

Published in Transactions on Machine Learning Research (03/2026)
where
m = Ao + D
Pm
A Am- W D Am Dam W
2 m <
m mi Ai- F ((W)) (W:)(..)
W mh-1 aDam-1 D-m D)m--))Am11
2 m S 1
Rm
W.i (Da--1 + DJL-)) (1.)) (Ai-1)a.), 2
m=i
with
(55)
maax (I(W)),.)) (Mi)
According to Theorem
it is equivalent to show that
N > O,
Ak E Zx-2,
8,-1 - -LW. >0,
where
Da' W1
Xx=
As (D + ( + Dot)) + + Dat Á I +
h Z
+ -3:-1)Ai-1
= -
Let Ä j E Z;- be decided according to Algorithm from the previous layer, that is, Ag = Ay, j E Z,-1.
Then X Nx. & Zi-2 and X,-1 M,-1. Then the following statements hold:
55 is well-defined because by induction, Mi-1 > O,
(b) by induction, X Xx 0, k Z,-2, and X (T.)
(c) with F from 55
M (W,)), > 0.
Therefore, Voman ([WW))..>)* (M--1)) are valid Lipschitz constants for Vl E Zd, as in (6)
Similarly, the ECLipsF-Gen series of algorithms gives A, that satisfy
A; W JAr(Dar DD:)W;;) > >.AEED 1 (D + D3:)A;
X1-1
By Schur complement, this is equivalent to
X,-1 0, A w W. 1 Ar(Da + DD ( DD:)A,, 0.
Therefore, (X1-1) well-defined and with 6s >0.
1 + WK Ag))A) + F.W W4+1
M, = (A; GWT 241 W.+1 4
wW? W W
This completes the proof of claims (i)-ii Proceeding, by Proposition 4 and Lemma L (0.4) produced by Algorithm is strict upper bound for the local Lipschitz constant. of the 1-th neuron on layer Ta, E La, i E ÆN-1-
For the final local Lipschitz constant L estimated by Algorithm 1 the proof follows identically to the neuron-wise case above, except that the final matrix inequality involves Wy instead of (Wx) With F == 1/0mmax (Wx(Mx-))-WW) obtain L /1/F to be valid Lipschitz constant (strict upper bound) for the entire network.
34

---

Published in Transactions on Machine Learning Research (03/2026)
A.2 Algorithm
We present the practical algorithm that enhances ECLipsE-Gen-Locee with acceleration and stability here.
Algorithm Enhanced ECLipsE-Gent LoccLoal with Accelcration and Numerical Stability
1: Input: Weights (Wi) biases {br activation function input region = Blze, 6z); large scalar
Cap > O for numerical upper bound; variant ALGO E (Acc, Fast, CF)
2: Output: Local Lipschitz estimate L
Set Mg f- I, v²((0) +- Ze: skipt
for = 1, ..... N do
Set Worli +- W;
if skip then
7:
W; + W; Das-1 W,-1
8:
end if
Compute d with d,"
W Jan for I,..., .....,dg, di, using 24
Set L [Vaio..... Va
10:
Compute (e(()) = (zc) per 25 with (Warig b.)
11:
12:
Calculate range Vi for v00 as in 26
13:
Refine a', 8 using V as in 27
14:
if a = B then
15:
skip+1
16:
continue
17:
else
18:
skip 0
19:
end if
20: Let J. =
M; ; Zd, $
21: Obtain A, (and c;) according to Algorithm (ACC), (Fast), (CF)
22: Update M, as in using Dat, DB-
23: end for
24: Using 18), compute final vIFF Omar (Ww(Xx-1)- with XN-1 = MN-1
25: return
Algorithm Procedure Acc: Obtain A;
Input: W,, Mi-1, Da', Dæs, index sets Tr, M,, large scalar Cap
Output: (4),
Solve (30) on Mi to get (Ai)(M).M)) and
Set (Ai)is +- [.M Emem, (A:)(m.m) for all j E T: (ef. 31
5: (Ai)ss + min(Cop (Aj),s} for j
6: Compute X; as in 100 using A;
7: X, > then return (i)
else
(Afast fast Algorithm 4
10:
11: (AFt cff f- Algorithm 5
12: return the pair with larger among {Affatt .dist, (A (Af)))1))
13: end
35

---

Published in Transactions on Machine Learning Research (03/2026)
Algorithm Procedure Fast: Obtain A;
Input: W,, M Dai, Dæ., index set M,, large scalar Cap > 0
Output: (4)
Solve (32 on M; to get d; and a;;
X < min((app Capp, )r}
5: Set A; t- A
6: Compute X; as in 10 using A
X, then return C)
else
10: return (i) Algorithm 5
11: end if
Algorithm Procedure CF: Obtain A;
Input: W,, Mr-1, Dac, Das, activation function
Output: (Ai,4)
Assert a² @ f¹ 2
4: for j 1, 1,2,..., d, do
5:
if 0 S (a'), s (B)) then
(ad ; + 0, (gi ) + (3t),
else if (a'), s (B'), s then
(ottad)) ) (a'), (Bradi); +
end if
10: end for
11: Obtain A via 15 using Ladi and gi,ddj
12: Set A + III
13: Compute M, as in 17 using Ar
14: Compute G 1/0mass WW+1 (M,) -1 WTT.)
15: return (A)
36

---

Published in Transactions on Machine Learning Research (03/2026)
A.3 Experimental Details
A.3.1
Computational Resources
All algorithms except LipDiff are implemented a Windows laptop with 12-core CPU and 16 GB of RAM. LipDiff is accelerated using compute node equipped with single NVTDIA A100 GPU (80 GB onboard memory) and 512 GB of system RAM.
A.3.2 Randomly Generated Neural Networks
For the experiments in Section 4.1 network weights are generated such that the fo-norm of each layer weight
lies in [0.8, 2.5]. This is accomplished by first sampling a target value uniformly from [0.8, 2.5) for each layer, and then normalizing the randomly generated weight matrix. Similarly, for the networks in Section 4.2 the fz-norm of each layer weight, is constr to [2, 2.5]. When applying Algorithm EClipsF-Gen-Toooll
set 4 = 100 in 31
A.3.3 MNIST Training and Robustness Evaluation
We evaluate adversarial robustness on the MNIST dataset, which consists of 28 x 28 grayscale images of handwritten digits from 0 to 9. Each image is vectorized into 784-dimensional input, and the networks output a 10-dimensional vector corresponding to the ten digit classes. All feedforward networks used in this experiment therefore have input size 784 and outpul size 10. The models are trained with Adam (learning rate 10-3 3 weight decay 10=4) for up to 50 epochs with early stopping at 98% test accuracy. The baseline uses cross-entropy loss, while the Jacobian regularized model adds a Frobenius norm penalty estimated with one Hutchinson probe (Hoffman al. (2019)) and penalizing weight =.
Adversarial robustness is measured using projected gradient descent (PGD) attacks. Given image with label constraint ||0]|2 E. Starting from a small randomized initialization, we perform 40 steps of gradient ascent with normalized gradients and step size a = e/10. After each step, the perturbed input x + 5 is projected back onto the L2 ball of radius and clipped to the valid pixel range [0, 1]74, We sweep E {1/2, 1/4, 1/16, 1/32, 1/64, 1/128, 1/256] and report the failure rale, defined as the fraction of test. examples for which the classifier prediction changes under attack.
optimize the cross-entropy loss with respect to perturbation ō subject to the Le
37

---

Published in Transactions on Machine Learning Research (03/2026)
A.3.4 Complete Experimental Results
Case of Section 4.1 The Lipschitz constant estimates and computation times for the randomly generatod neural networks with the number of layers chosen from (5, 10, 15, 20, 25), and number of neurons chosen from {10, 20, 40, 60) (small neural networks), are provided below.
Table la: Lipschitz constant estimates
Neurons Layers
10
15
20
25
10
21.028
105.687
1530.490
12360.291
564727.209
Trivial
20
3.314
14.138
98.836
32738.399
34901.424
40
24.280
81.681
1208.555
5187.447
24404.492
60
2.567
109.017
4524.267
2693.936
106596.360
Neurons Layers
10
15
20
25
10
8.724
10.281
91.219
419.907
2206.16
SeqLip
20
> >10min
>> ~10min
>> 10min
>> >10min
> 10min
40
60
LipSDP -neSDonneuron
Neurons Layers
10
15
20
25
10
4.943
2.049
8.263
4.937
26.230
20
0.635
0.305
0.415
14.109
4.502
40
3.766
1.950
3.911
3.193
2.113
60
0.447
2.446
16.205
1.615
7.947
Neurons Layers
10
15
20
25
LipSDP-layer layer
10
6.784
4.843
27.348
30.823
328.444
20
0.988
0.709
1.243
66.064
26.522
40
5.537
3.800
10.111
10.932
9.567
60
0.616
4.824
34.621
4.264
30.627
Neurons
Layers
15
GooLIP
10
12.028
5.291
23.537
11.698
61.922
20
1.632
0.765
0.992
38.569
11.774
40
9.319
5.257
10.111
8.932
5.644
60
1.270
6.872
45.046
4.562
22.026
Neurons Layers
10
15
20
25
10
10.300
13.010
102.766
>10min
10min
AAO
20
1.469
1.904
5.245
40
9.006
11.023
56.829
60
0.994
13.741
208. 126
38

---

Published in Transactions on Machine Learning Research (03/2026)
Table la: Lipschitz constant estimates (Continued)
Neurons) Layers
10
15
LipDiff
10
8.939
56.672
1448.136
10801.918
417370.969
20
0.936
6.281
49.406
25191.828
29123.996
40
10.958
52.335
888.581
5007.855
24095.277
60
1.254
56.494
4461.550
2589.449
94250.664
Neurons Layers
10
15
20
25
GLPpSDP
10
4.943
2.049
8.263
4.937
26.230
20
0.635
0.305
0.415
14.109
4.502
40
3.766
1.950
3.911
3.193
2.113
60
0.447
2.446
16.205
1.615
7.947
Neurons Layers
10
15
20
25
EC
10
6.935
4.599
28.314
16.643
239.018
20
0.814
0.554
1.039
49.224
22.429
40
4.941
3.559
9.166
10.572
8.977
60
0.538
3.970
31.956
4.849
34.150
Neurons Layers
10
15
20
E-sst.
EC Fast.
10
9.373
11.770
72.343
148.690
2234.919
20
1.301
1.577
3.586
314.856
149.244
40
8.685
8.755
33.455
50.758
75. 75.140
60
0.924
10.869
130.256
24.092
270.349
EClipsE-Gennt Gen-L-al---LL EClipsE- Gon-Tool--or
Neurons Layers
10
15
20
25
10
5.926
4.617
35.025
16.637
0.004
20
0.273
0.010
0.007
35.641
24.639
40
4.572
2.069
6.211
0.170
1.322
60
0.235
0.581
28.264
3.830
0.002
Neurons Layers
10
15
20
10
7.184
5.058
27.996
35.167
307.104
20
0.680
0.276
0.766
78.350
32.456
40
5.428
3.672
10.755
9.752
10.066
60
0.417
4.334
35.002
4.689
26.923
39

---

Published in Transactions on Machine Learning Research (03/2026)
Table la: Lipschitz constant estimates (Continued)
Neurons Layers
10
15
20
25
EClipsE-Gen-LLcaal
10
8.944
11.707
66.348
148.690
1736.535
20
0.959
0.526
2.256
267.457
147.714
40
7.887
7.796
31.828
42.772
62.424
60
0.629
9.091
120.746
22.579
205.990
Table 1b: Computation time (seconds)
Neurons Layers
10
15
20
SogLip
10
0.460
1.042
1.576
2.330
2.656
20
10min
10min
10min
>> 10min
> >10min
40
60
LipSDP -neuron
Neurons Layers
10
15
20
25
10
1.176
1.097
1.040
1.307
2.247
20
1.463
1.303
3.194
6.677
9.003
40
7.396
7.229
21.173
51.123
97.725
60
3.761
27.857
100.512
211.487
417.170
Neurons Layers
10
15
20
HipSD--layer
10
12.368
1.468
1.229
1.992
2.540
20
1.851
1.800
2.650
5.592
9.672
40
1.973
6.753
13.897
32.194
58.683
60
2.175
12.753
43.746
102.167
186.108
Neurons Layers
10
15
20
25
GeoLIP
10
0.487
0.867
1.968
2.107
3.290
20
0.456
3.746
10.257
12.034
17.586
40
2.230
23.392
52.746
58,190
96.382
60
13.128
50.634
101.734
238.743
329.327
Neurons Layers
10
15
20
25
10
0.050
0.764
14.693
733.7
> >10min
AAO
20
0.033
2.071
23.885
1032.956
40
0.020
2.587
92.613
3348.118
60
0.051
5.319
200.619
8336.229
40

---

Published in Transactions on Machine Learning Research (03/2026)
Table 1b: Computation time (seconds) (Continued)
Neurons) Layers
15
LipDiff
10
3.728
3.163
4.373
22.935
18.885
20
3.057
14.661
25.913
27.072
30.921
40
5.419
27.389
42.046
51.114
76.681
60
30.183
36.831
74.760
99.843
144.564
Neurons Layers
10
15
20
25
GLPpSDP
10
0.158
0.127
0.284
0.304
0.508
20
0.524
0.949
1.775
2.912
3.157
40
6.016
16.463
29.642
46.906
49.518
60
24.422
86.695
185.803
226.214
339.035
Neurons Layers
10
15
20
25
EC
10
3.635
6.893
10.706
14.542
18.357
20
3.603
7.674
11.762
16.931
21.438
40
4.794
10.346
16.767
22.757
28.872
60
6.405
15.514
26.935
36.545
43.624
Neurons Layers
10
15
20
Fasst.
EC Fast.
10
0.002
0.003
0.002
0.004
0.003
20
0.006
0.003
0.006
0.006
0.009
40
0.008
0.015
0.017
0.030
0.035
60
0.009
0.018
0.028
0.043
0.050
EClipsE-Geni Gen-Loall--LL EClipsE- Gen-Too----oo
Neurons Layers
10
15
20
25
10
3.605
10.674
15.059
26.974
15.522
20
4.383
12.651
9.502
25.950
33.685
40
7.289
14.403
24.690
32.200
44.148
60
5.966
16.271
40.690
55.340
35.773
Neurons Layers
10
15
20
10
3.143
6.484
10.065
13.545
17.497
20
3.158
6.812
10.517
14.793
19.061
40
3.614
8.268
13.356
17.745
22.745
60
3.709
10.290
16.386
22.882
33.784
41

---

Published in Transactions on Machine Learning Research (03/2026)
Table 1b: Computation time (seconds) (Continued)
Neurons Layers
10
15
20
EClipsF. Gea---Gn--LLoa-CC
10
0.013
0.017
0.021
0.033
0.032
20
0.014
0.043
0.057
0.076
0.102
40
0.039
0.131
0.175
0.280
0.332
60
0.039
0.120
0.203
0.310
0.313
Case of Section 4.1 We present the complete results for large networks, where the number of layers is chosen from {30, 40, 50, 60, 70}, and number of neurons is chosen from {60, 80, 100, 1203.
Table 2a: Lipschitz constant estimates
Neurons Layers
40
50
60
Trivial
60
50682.053
306543.948
1.037 10
3.337 x 10
7.383 x 10
80
138841.58
13156333.51
4.359 10
7.420x10'
x
100
28052.064
557532783.5
3.942 10
4.882x10"
9.530
120
152201.865
8.456x109
1.724x10"
2.860x1011
8.036x
LipSDP meeroo
Neurons Layers
30
40
50
60
70
60
1.289
0.239
24.916
24.717
1760.327
80
3.607
13.23 13.234
1259.817
802.203
808.099
100
0.777
443.184
1085.570
5743.067
37482.662
120
4.932
7655.233
48749.689
360.014
32328.464
Neurons Layers
30
40
50
60
70
LipSDP-laye llaee
60
6.557
1.614
240.577
563.315
49382.204
80
18.590
84.237
10936.840
13099. 736
20612.931
100
3.120
3003.417
8924.823
94284.796
701407.288 224
120
16.737
46840.490
350361.288
3935.794
678055.572
Neurons Layers
30
40
50
60
LipDiff
60
46488.457
278692.438
1.530
8.720x1016
1.980 10)2
80
131847.211
11986194
1.060 10
4.000x1020
1.860x1024
100
27995.222
1.205x10'
2.470x10"
4.500x10'0
4.340x1029
120
152062.031
1.812x 10
1.210x1023
2.260 1020
6.340 10
42

---

Published in Transactions on Machine Learning Research (03/2026)
Table 2a: Lipschitz constant estimates (Continued)
Neurons) Layers
40
50
60
GLipSDP
60
0.577
0.078
5.321
3.410
200.713
80
1.657
>> 1h
> lh
>> >1h
> 1h
100
120
Neurons' Layers
30
40
50
60
70
F.ClppsE
60
3.214
0.734
71.574
99.558
9117.857
80
6.626
30.452
3184.903
2311.671
2686.612
100
1.368
843.970
2436.388
12623.369
96935.788
120
7.943
13707.418
91196.080
766.803
67675.878
Neurons Layers
30
40
50
60
70
EClipsF- Fast
60
40.357
22.005
4872.017
15334.703
2762962.864
80
106.481
963.729
227516.599
354590.087
958744.578
100
20.276
33545.214
185024.991
2392851.817
3.331x10"
120
101.125
473490.3449
7784374.437
134759.991
3.058
EClipsE--Gen- Geen--eeolll-eee Acc
Neurons Layers
30
40
50
60
70
60
2.561 x 10-6
3.626x10- 10-7
2.637x10
55.177
1.317x10-10
80
6.019x10-6
1.216x10
2.970x10-0
1253.190
x797xx011 10
100
1.746x10-5
5.142x10-5
1902.287
6496.172
11026.134
120
6.309x10
8306.746
37259.193
9.428x
4764.049
CClipsE-Gen-Localee EC Gen-Local- Fast.
Neurons Layers
30
40
50
60
70
60
1.083x 10
5.799 10
5.501
82.116
1.655 10
80
2.238
2.568x10-1
2.343x
2272.633
1.348x 10
100
9.010x10
466.795
2421.066
13916.972
66516.583
120
5.423
14380.517
76385.146
329.169
52766.628
Neurons Layers
40
50
60
60
28.629
20.747
4378.720
14540.358
2180308.622
80
97.800
657.517
204800.834
3346555.66
862880.611
100
8.597
28903.208
177659.392
2219501.561
3. 3.127x10'
120
96.418
453716.467
6822130.953
116706.452
2.842 107
43

---

Published in Transactions on Machine Learning Research (03/2026)
Table 2b: Computation times (seconds)
LipSDP LipSDP-neurol -neuron
Neurons' Layers
30
40
50
60
70
60
109.070
152.040
149.638
727.651
172.854
80
261.885
313.565
295.342
1267.712
422.347
100
371.482
625.229
595.804
961.680
861.610
120
692.723
1065.468
1179.913
1394.512
1603.990
Neurons Layers
30
40
50
60
70
LipSDP-las -layer
60
94.361
99.127
77.136
72.664
79.716
80
89.473
187.850
151.267
111.975
136.632
100
130.927
159.697
223.201
194.210
221.094
120
201.007
222.053
313.597
274.748
411.751
Neurons Layers
40
50
60
LipDiff
60
179.812
469.768
716.592
1257.711
1897.470
80
390.254
794.557
1625.415
2519.319
3523.333
100
696.663
1617.582
3127.469
4006.535
4803.644
120
1177.954
2459.011
3977.822
6283.629
9192.057
Neurons Layers
30
40
50
60
70
GLipSDP
60
126.677
454.171
633.618
569.647
562.881
80
3902.751
>1h
>1h
>
100
> 1h
120
Neurons) Layers
30
40
50
60
70
EClipsF
60
57.061
82.713
121.571
221.483
163.846
80
103.047
164.912
207.042
378.171
309.558
100
164.315
276.264
555.429
549.838
520.602
120
275.917
472.231
893.199 199
923.932
770.500
Neurons Layers
30
40
50
60
70
EClipsF--Fas Fassatt
60
0.099
0.076
0.110
0.127
0.130
80
0.117
0.158
0.192
0.251
0.294
100
0.204
0.222
0.292
0.314
0.382
120
0.251
0.335
0.414
0.496
0.557
44

---

Published in Transactions on Machine Learning Research (03/2026)
Table 2b: Computation times (seconds) (Continued)
Neurons Layers
30
40
50
60
70
EClipsF. Gen---ooall--e
60
127.009
100.012
159.432
284.597
130.782
80
442.548
117.682
263.666
504.913
229.356
100
320.838
660.533
795.924
1108.792
989.315
120
611.638
956.523
1109.196
927.641
1431.236
EClipsE- Cee--Gnnn------- Leeaa--Gen-Loppp Fast.
Neurons Layers
30
40
50
60
60
34.299
48.792
125.322
157.239
95.297
80
54.192
79.973
157.899
211.596
237.253
100
54.362
187.273
215.903
276.621
323.633
120
92.174
228.984
181.819
368.509
352.321
Neurons Layers
Layers
30
40
50
60
70
60
0.398
0.535
0.809
0.839
1.048
80
0.676
0.970
1.178
1.555
2.047
100
0.894
1.225
1.700
2.019
2.632
120
1.187
1.834
2.257
3.117
3.406
Results for Section
4.2
Lipschitz Estimates FNN with 5 Layers and 128 Neurons for Different Input Radii
Trivial bound: 66.975, autodiff: 0.235
Algorithm
r ==
r
1/5
r 1/52
r = 1/53
y= 1/54
== 1/5
EClipsE--Gen Gen-
12.206
9.175
1.612
0.946
0.304
0.235
0.235
Local-Acc
EClipsE'-Gen Local-Fast
13.798
12.465
6.855
3.290
0.824
0.235
0.235
BClipsE--en-- Local-CF
23.028
20.702
15.210
11.510
10.875
10.294
10.271
45

---

Published in Transactions on Machine Learning Research (03/2026)
Lipschitz Estimates on FNN with 5 Layers and 128 Neurons for Different Input Radii
Trivial bound: 3.070 x 10 autodiff: 1.539 x 10-3
Algorithm
r
1/5
r 1/52
1/53
r 1/5
r r= 1/5
EClipsE-Gen
1,804 106
9.382
8.471 X 10a
9.031
2.113
2.209 x
1.539
Local-Acc
105
10-3
10-3
10-3
10-3
EClipsE-Gee Gen-
2.201 106
1.849 10"
6.603 x
6.754
6.934
2.843 x
1.539 x
Local-Fast
10
104
10
10
10-3
RClipsFE-Gen
2.062 10?
1.811 x 107
1.197 x
6.010 x
2.672 x
1.296 x
6.008 x
Local-CF
107
106
106
106
10a
Lipschitz Estimates FNN with 60 Layers and 128 Neurons for Different Input Radii
Trivial bound: 4.324 x 1021, autodiff: 6.324 x 10-6
Algorithm
r= 5
r= 1
1/5
r 1/52
r= 1/53
1/54
r= 1/5
ECT.psF--Gnn
1.68 x 10
1.37 x
9.29 x
2.91 x
1.14 x
6.32 x
6.32 x
Local-Acc
10
10a
10-5
10
10 6
10-6
ECT.psFF-Gen Local-Fast
1.81 10
1.70 x
7.87
6.92
2.00 x
6.32
6.32
1014
1013
10
10-5
10-6
10-6
ECTipsF--Gen. Local-CF
1.33 10
1.29
9.86
5.78
2.62
1.31
5.74
10
10
10
10
10
10
Robust training in Section
4.3
The complete results are follows.
Local Lipschitz Estimates on Baseline MNIST Model for Different Input Radii
Sample
1/2
1/22
1/23
1/21
r
1/25
1/26
1/27
1/28
78.71098
78.70734
78.61906
74.36818
58.13149
44.6177
26.05712
16.33641
2
78.71098
78.70682
78.60065
71.53018
57.27216
42.98288
28.55629
18.88016
3
78.71098
78. 78.70626
78.59112
69.64929
55.56146
43.45022
29.32234
21.11356
78.71098
78. 73.70635
78.59286
71.67161
54.69806
41.45828
26.19779
17.52604
78. 78.71
78. 78770774
78.6268
73.33843
58. 15701
42.77248
22.93037
14.57802
Continued on next page
46

---

Published in Transactions on Machine Learning Research (03/2026)
(Contimued)
6
78.71098
70579
78.58708
69.20899
55.67301
41.0769
26. 26.20351
16.5844
78.71098
78. 13.70628
78.59743
71.60393
56.94831
40.92923
25.57324
17.9801
78. 78.71099
78.70736
78.61574
71.19789
58.25083
40.83705
25.64
16.33402
78.71098
70670682
78.60921
71.91748
38.53037
41.81912
23.86733
16.24717
10
78.71099
78. 70770
78.62238
71.71447
58.31806
37.37913
21.85074
15.73135
11
78.71098
78. 70659
78.53775
72.1146
56.06148
42.75571
28.95411
18.57977
12
78.71099
78.7079
78.6297
72.59098
56.81893
40.59961
25.43528
18.3823
13
78.71098
78.70692
78. 78.60969
72.93557
55.63917
40.56271
25.40254
17.13129
14
78.71099
78.70701
78.60111
71.52446
56.58831
39.78379
24.79018
18.5912
78.71098
78.70657
78.59976
70.00147
56.8946
38.23369
25.27076
16.24316
78.71098
78. 70637
78.60351
71.28439
58.42006
38.85839
23.427
15.95628
17
78.71098
78. 70606
78.59739
71.30552
55.61067
43.27397
28.03724
18.91537
18
78.71098
78. 70686
78.60872
73. 13.12516
58.85767
44.68016
31.1804
20.87262
19
78.71099
78.708
78.63192
71. 71.6684
54.38538
38.4346
22. 12.11
14.83256
20
78.71098
78.70636
78.59858
70.45079
54.85386
40.67774
27.49389
18.38262
Local Lipschitz Estimates on Robustly Trained MNIST Model for Different Input Radii
Sample
1/2
1/22
1/23
1/24
r 1/25
1/26
1/27
1/28
59.95561
59.76889
68.32222
55.58214
47.47068
34.9161
14.29093
6.055722
2
59.95561
59.94913
58.33661
55.45571
49.27195
39.23655
23.30358
9.705545
3
59.95561
19.77215
58.33239
54.83087
51.01784
38.43811
20.2736
7.281093
59.95561
59.73319
58.24574
55.33866
49.84949
38.30965
17.83903
8.109753
59.95561
59.94582
58.32322
55.47847
48.87655
34.17816
13.47338
7.282262
59.95561
59.68513
57.9313
55.21375
50.24844
40.44054
18.9907
7.287764
Continued on next page
47

---

Published in Transactions on Machine Learning Research (03/2026)
(Contimued)
7
59.95561
59.71394
58.32489
55.74624
49.53914
34.69735
16.43406
7.998252
59.95561
59.94728
58.341
55.34873
50.55051
38.52287
18.44644
7.479875
59.95561
59.67834
58.32869
55.74314
48.33398
34.24256
15.96027
7.561291
59.95561
59.94594
58.32607
55.66811
49.44189
33.5797
17.50552
6.006573
11
59.95561
59.94523
58.33124
55.08831
49.56107
37.93311
22.16714
8.042922
12
59.95561
59.59303
58.32403
55.49748
52.38679
32.91855
15.00071
8.27143
13
59.95561
59.88001
58.33205
56.58481
52.77126
35.00035
18.14338
7.062218
14
59.95561
59.80707
58.33666
55.47049
49.36892
35.28665
12.42868
5.485892
15
59.95561
59.45832
58.16557
55.67141
47 17.28045
34.83791
16.80016
7.039371
59.95561
59.7419
58.32438
55.95442
50.13239
36.0773
17.53038
8.491852
59.95561
59.68881
58.32994
54.71 305
47.55917
34.46926
15.94367
7.291772
18
59.95561
59.9465
58.32893
55.67932
51.16427
32.14587
13.33776
7.268891
19
59.95561
59.49008
58.02768
54.94707
49.34491
31.38572
16.15183
6.080519
20
59.95561
59.71931
58.11977
55.95374
51
61.04859
41.01665
19.68835
7.429283
Failure Rate of Models MNIST Under PGD Attacks within Given Range (%)
Model
1/2
1/22
1/23
r 1/24
1/25
1/26
1/2?
1/28
Baseline
9.65%
4.6%
2.94%
2.48%
2.11%
2.04%
1.99%
1.95%
Robustly Trained
4.25%
2.7%
2.26%
1.97%
1.94%
1.9%
1.88%
1.87%
48

---

Published in Transactions on Machine Learning Research (03/2026)
A.3.5
Detailed Results for Robustness Certificates in Section 4.3
Sample
7a.125
Fo:051225
Yb-015625
70-0078125
70.0000002
Tourt
0.011458
0.011494
0.011779
0.01236
0.0144722
0.015625
0.0078125
0,0039062
0.015625
0.0029057
2
0.0045758
0.0043763
0.0047028
0.0049471
0.005568
0,0069921
0.0078125
0.0039062
0,0078125
0.001 1604
0.0059098 3
0.010478
0.01051
0.010769
0.011457
0.012313
0.015625
0.0078125
0.0039062
0. 0.015625
0.002637
0.0059318
0.0060833
0.0064029
0.007
0.009249
0.0078125
0.0039062
0.009249
0.00149966
5
0.013115
0.013117
0.013482
0.014173
0.016087
0.015625
0.0078125
0.0039062
0.016087
0.0033257
6
0.0067095
0.0067399
0.0069439
0.0072857
0.0080057
0.0099472
0.0078125
0.0039062
0.0099472
0.1017014
7
0.0045022
0.0045204
0.0046281
0.0048422
0.0054489
0.0077796
0.0078125
0.0039062
0.0078125
0.0011417
0.00016575
0,00016578
0.00017034
0,00017955
0.00019639
0.00025797
0.00053874
0,0013286
0,0013286
4. 4:20e-05
0.0096509
0.0096957
0.0099201
0.01038
0.011971
0,015625
0.0078125
0,0039062
0.015625
0.0024173
10
0.017381
0.017384
0.017867
0.01872
0.021077
0.015625
O. 00088125
0.0039062
0. 0.021077
0.00444075
0.0023155
0.0023159
0.00238
0.0025201
0.0028012
0.0036598
0.0062628
0.0039062
0.0062628
0.00058718
12
0.0032582
0.003278
0.0033494
0.0035199
0.003729
0.0059343
0.0078125
0.0039062
0.0078125
0.00082623
13
0.0071663
0.0071753
0.0073657
0.0075932
0.0081419
0.012276
0. 00008812
0.0039062
0.012276
0.0018172
14
0.010999
0.011026
0.011301
0.011888
0.013358
0.015625
0,0078125
0.0039062
0.015625
0.0027892
0.008976
0.0090501
0.0092512
0.0096637
0,011381
0.015446
0.0078125
0.0039062
0.015446
0.0022759
16
0.010617
0,010655
0,010914
0,011377
0.012698
0,015625
O. 0.0078125
0.0039062
0.015625
0.0026921
17
0.0056556
0.0056809
0.0058132
0.0061975
0.007 1297
0.0098373
0.0078125
0.0039062
0.0098373
0.0014342
0.0083519
0,0083532
0.0085849
0.0089934
0.009787
0.015577
0.0078125
0,0039062
0.015577
0.0021179
19
0.0065651
0.0066164
0.0067832
0.0071635
0.0079768
0.012541
0.0078125 25
0.0039062
0.012541
0.0016648
20
0.0091699
0,0092062
0.0094596
0.0098258
0.01077
0.0134404
0,0078125
0.0039062
0.013404
0.0023254
Moan
0.01222977
0.001990887
Ratio meau()oww) (eenu
6.142874701
Table 1: Certified radii across e 11/2,1/4.... 1/256) for 20 test points. Columns report Teart (eort e). Column Teert reports the least conservative (largest) certified radius obtained by sweeping over the same set of e values. Column Tuiv reports the certified radius using the global trivial Lipschitz bound.
49

---

Published in Transactions on Machine Learning Research (03/2026)
A.3.6
Additional Plots for Section 4.2
Tightness Input Radius
layers (128)
FOipuF-Gen
EClpsE-Gen
10
CCipaE-3an-Looee Ban-Loodi-CF
Aurodit
Lipschitz estimaio ate Autodlit
10
10
5
1/5
1/25
1/125
1/825
1/3125
Input radius
Figure 7: Lipschitz estimates are normalized to autodiff value (0.2347). Naive bound: 66.9754.
Tightness vs. Input Radius
60 layers (128)
10
Lipschizz estimate Autoolf
EClpri-Gen Gene--ee----rrre Lora-otal-Ass Aco
10
ECIisE Gen Local Fast
ECiipE Gen Local
10
1.0
1/3125
Input radius
Figure 8: Lipschitz estimates normalized to autodiff value at 2e (6.3224 x 10-9). Naive bound: 4.3244 x 10
A.4 Slack introduced by the CF slope adjustment
In ECLipsEE-Gen-Loca--e at cach stage i, after obtaining refined per-neuron slope bounds |
Bi] from
local propagation, we replace them with a valid superset [ that satisfies i.ad @ Bi.ad: = 0 to
enable a closed-form update, i E 1N-1- Under A; = =,; the term removed from X,- 14 is
Alookk = A.W. Dg.
(56)
Therefore, the induced slack is small when the refined lower slope bounds are already close to zero (D.: is small). The slack can be substantial when both a and I are non-negligible and the scale or alignment of W, amplifies W. Da Dz: W
50


Reviews:
[{"review_id": "cLoP60D0bQ", "reviewer": "Reviewer_24gS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the problem of estimating Lipschitz constants to certify the robustness and safety of neural networks. This is an NP-hard problem where existing approximation approaches either fail to scale or yield looser bounds. The paper argues that (1) the global Lipschitz constants are often overly conservative, especially when robustness is needed only on a local input region, and (2) existing scalable SDP relaxations either sacrifice tightness or cannot exploit local slope information of activations. The paper proposes that the Lipschitz constants can be estimated by decomposing global SDPs compositionally across layers (ECLipsE-Gen), and iteratively refining neuron-wise slope bounds using local input information (ECLipsE-Gen-Local). \n\nThe experiments are conducted by systematically comparing different algorithms on randomly synthesized neural networks with varied configurations and trained networks. The results indicate that the proposed local bounds are consistently much smaller than global bounds and asymptotically exact. In addition, the robustness analysis shows that local bounds correlate better with observed robustness, whereas global bounds often overestimate worst-case effects.", "claims_and_evidence_yn": "No", "claims_explanation": "The paper’s claims are well supported by theoretical guarantees and carefully designed experiments, with empirical results demonstrating tightness, scalability, and the correlation with robustness in local Lipschitz estimation.\n\n1. ECLipsE-Gen-Local series estimates tight Lipschitz constants and scalable for both depth and width. The paper presents the empirical evidence in Section 4.1 (Figure 1 - 4).\n2. Both theory (Section 3.5) and experiments (Section 4.2) demonstrate that the proposed local Lipschitz estimates tighten monotonically with shrinking input regions and converge to the exact Jacobian norm at the region center, as verified by automatic differentiation (Figure 5, Figures 7 - 8). In addition, the local estimation is related to the robustness of the trained network (Section 4.3; Figure 6).\n\nHowever, the generality claim and downstream analysis (Contribution 4) might not have a direct empirical evidence support and need further clarification.", "audience_yn": "Yes", "audience_explanation": "Estimating the Lipschitz constant of neural networks is a relevant problem. TMLR’s audience working on theoretical neural network robustness would find this paper's findings interesting.", "requested_changes": "1. Clarify which contributions are both theoretically and empirically supported, which are only theoretically supported.\n2. Demonstrate or clarify some downstream applications, such as sensitivity analysis, output range estimation, or partial verification.\n3. Discuss extension beyond fully connected networks.\n4. Justify the choice of neuron networks. In the LipSDP paper, they experimented with up to 500 layers. In addition, it would be nice to clarify the need for LipSDP parallelization. Would it be possible to do the same with ECLipsE-Gen-Local?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yGWMWYXSGV", "reviewer": "Reviewer_bFAb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of efficiently computing tight and certified local Lipschitz constant upper bounds for deep feedforward neural networks. Building upon SDP-based Lipschitz certificates (notably LipSDP) and recent compositional decompositions (ECLipsE), the authors propose a generalized framework—ECLipsE-Gen—that supports heterogeneous neuron-wise slope bounds, arbitrary input–output index selection, and subnetwork-level certification. More importantly, the paper introduces ECLipsE-Gen-Local, which explicitly incorporates local input region information to iteratively refine neuron-wise slope bounds, yielding substantially tighter local Lipschitz estimates with provable guarantees.\n\nStrengths:\nThe paper is technically solid and presents a well-motivated combination of generalization, locality, and scalability. The proposed framework substantially expands the applicability of certified Lipschitz estimation and is supported by both theoretical analysis and empirical validation.\n\nWeaknesses:\nThe presentation is mathematically dense, and the intuition behind the compositional and local refinement procedures could be explained more clearly. In addition, the distinction between the proposed method and prior ECLipsE-based approaches could be made more explicit.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The above assessment focuses on the paper’s main technical contributions while also reflecting areas where the work could be improved. Although the proposed framework extends prior SDP-based and compositional approaches in meaningful ways, several of the contributions rely heavily on existing ideas (e.g., ECLipsE-style decomposition and slope-bounding techniques), which makes it important to clearly delineate what is fundamentally new versus what is a generalization or refinement. Additionally, while the theoretical development is rigorous, the presentation places a substantial burden on the reader, and some algorithmic choices and intuitions are not immediately transparent. These considerations motivate a balanced summary that acknowledges the technical depth and practical relevance of the work while also noting limitations in clarity and positioning that may affect accessibility and perceived novelty.", "audience_yn": "Yes", "audience_explanation": "Compared to prior work, this paper goes beyond incremental improvements: it significantly expands the expressive power of Lipschitz certification frameworks while maintaining computational feasibility. The ability to compute local, neuron-level, and subnetwork-specific Lipschitz bounds is particularly appealing and aligns well with TMLR’s emphasis on foundational yet practically meaningful advances.", "requested_changes": "1. Add illustrative examples: The paper would benefit from including concrete examples demonstrating how the proposed method operates in practice. This would help clarify the theoretical developments and make the contributions more tangible to the reader.\n\n2. Explain the role of the estimated Lipschitz constant: The authors should explicitly discuss how estimating the Lipschitz constant contributes to robustness certificates or enhances resilience against adversarial attacks. A clear connection between the theoretical results and practical robustness implications would strengthen the paper.\n\n3. Empirical validation: If possible, include experiments demonstrating the effectiveness of the proposed method in real-world applications, particularly in the context of adversarial robustness. Even small-scale empirical results illustrating the method’s utility would significantly improve the paper’s impact and persuasiveness.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iGqNB2M9JL", "reviewer": "Reviewer_tQzA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents ECLipsE-Gen-Local, a method for efficiently estimating certified local Lipschitz constants for deep neural networks. It extends the prior ECLipsE framework to handle activation functions with heterogeneous slope bounds (like LeakyReLU, ELU) and, most importantly, incorporates local information about the input region to produce much tighter bounds than global methods, especially for small regions. The method decomposes a large, intractable Semidefinite Program (SDP) into a sequence of small sub-problems, achieving computational complexity linear in network depth. The authors propose three algorithmic variants (Accurate, Fast, Closed-Form) offering a trade-off between bound tightness and computation speed. Extensive experiments show significant speedups over SDP benchmarks and demonstrate that the local bounds can approach the exact Jacobian norm for very small input regions.\n\n-----------\nPros:\n--------------\n-Strong Technical Contribution: The generalization to heterogeneous slope bounds and the systematic integration of local information are clear and valuable advances over the state-of-the-art (ECLipsE, LipSDP).\n-Solid Theoretical Foundation: The paper provides rigorous proofs for the validity, feasibility, and tightness of the proposed bounds, building on a well-established SDP certification framework.\n-Comprehensive and Convincing Experiments: The evaluation is thorough, covering scalability (depth/width), tightness vs. input region size, and a practical link to adversarial robustness. The comparison against 13 different benchmarks is impressive.\n-Practical Engineering: The discussion of numerical stability safeguards, handling of affine layers, and the provision of three algorithmic variants show attention to real-world implementation challenges.\n-Clear Presentation: The paper is well-structured and the methodology is explained logically.\n\n--------------------------------------\nCons / Points for Clarification\n-------------------------------------\n-Practical meaning of “local” bounds needs clearer discussion.\nThe advantage of the local variants appears strongest when the input region is very small, as shown clearly in Experiment Set 2, where the bounds approach the Jacobian norm. However, in the scalability experiments (Set 1), which use much larger input regions, the local methods achieve accuracy that is similar to the global variants, while incurring additional computational cost. This suggests a nontrivial trade-off between region size and practical benefit. The paper does not explicitly discuss this trade-off, which makes it harder to understand in which regimes the local approach provides a clear advantage.\nA more explicit discussion would be helpful: for what region sizes does locality meaningfully improve the bound, and when does it effectively reduce to a global estimate?\n\n-Limited guidance on choosing among Acc, Fast, and CF variants.\nThe paper introduces three algorithmic variants (Acc, Fast, and CF), but offers little guidance on how a practitioner should choose between them. While performance differences are visible in the experiments, the paper does not summarize typical tightness gaps or computational trade-offs in a direct way.\nFor example, it would be useful to explicitly state scenarios such as: CF is preferred when speed is critical and moderate looseness is acceptable; Acc should be used when tightness on small regions is the main goal; Fast offers a compromise. Without such guidance, the practical decision-making burden is left entirely to the reader.\n\n-Effect of the closed-form (CF) slope adjustment is not analyzed.\nThe CF variant relies on adjusting the refined slope bounds to satisfy the condition a*b=0. While this adjustment is stated to preserve validity, the paper does not quantify or analyze the loss in tightness introduced by this constraint. This omission is important, because it likely explains why CF bounds in Fig. 5 remain noticeably looser than those produced by Acc and Fast, even on small regions.\nA clearer discussion would help here: how much tightness is typically lost due to this adjustment, and is this loss expected to grow with depth or region size? Understanding this cost would clarify the real price paid for the closed-form speedup.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claim of linear scalability with depth is convincingly demonstrated by the clear, linear growth curves in runtime vs. depth plots (Figs. 1b, 3b), significantly outperforming non-compositional SDP methods.\n\nThe claim of tighter local bounds is compellingly validated by Experiment Set 2 (Fig. 5), which shows local estimates monotonically tightening by many orders of magnitude as the input region shrinks, eventually approaching the exact Jacobian norm—a direct and clear measure of optimal tightness.\n\nThe claim of practical utility is supported by the robustness correlation experiment (Fig. 6), which shows a clear alignment between lower certified Lipschitz estimates and lower empirical adversarial failure rates.\n\nThe only nuance is that the evidence for the advantage of \"local\" is split across experiments. The dramatic tightness gain is proven for small regions, while the scalability experiments use a larger region where the benefit is less pronounced, a point that could be stated more clearly. Overall, the evidence is accurate, comprehensive, and convincing.", "audience_yn": "Yes", "audience_explanation": "Yes. Researchers working on certified robustness, neural network verification, and safety-critical learning would be interested, as the paper proposes tighter and more scalable Lipschitz bounds with formal guarantees. The local perspective is especially relevant for those studying robustness near specific inputs rather than worst-case global behavior.", "requested_changes": "* Clarify when and why local Lipschitz bounds provide a clear advantage over global ones, especially as the input region grows.\n* Provide practical guidance on choosing between Acc, Fast, and CF, including typical tightness–cost trade-offs.\n* Quantify and discuss the tightness loss introduced by the closed-form (CF) slope adjustment.", "broader_impact_concerns": "No major ethical concerns. The work focuses on theoretical methods for certifying robustness and is primarily relevant to safety-critical and verification settings; potential misuse is limited and not unique to this approach.", "additional_comments": "Overall, the paper is technically solid and addresses an important problem in robustness certification. Clarifying the practical regimes where locality matters most and providing more guidance on algorithm selection would further improve its usefulness to practitioners and reviewers.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)