acceptodds
Under review as a conference paper at ICLR 2027

ScaLip: Bridging the Scalability–Tightness Gap in Lipschitz Estimation of Deep Neural Networks

Abstract

Tight Lipschitz constant estimation is fundamental to the certified robustness of deep neural networks. While state-of-the-art Semidefinite Programming (SDP) formulations yield tight formal bounds, their monolithic Linear Matrix Inequality (LMI) constraints couple decision variables globally, scaling poorly with network depth and width. Recent compositional approaches mitigate this by breaking the massive LMI into smaller layer-wise SDPs; however, to achieve this decoupling, they should rely on intermediate surrogate objectives that inherently degrade the final bound. Moreover, despite this decomposition, the resulting layer-wise SDPs remain computationally intractable for convolutional layers. In this paper, we propose ScaLip, a novel reformulation of the exact SDP problem into an unconstrained optimization objective. By introducing a recursive framework, the strict feasibility of the underlying LMI constraints is guaranteed by construction. This reformulation allows the global Lipschitz bound to be computed efficiently, end-to-end, using highly scalable first-order methods. We mathematically prove that our unconstrained objective preserves the optimal value of the original SDP formulation. Empirical results demonstrate that ScaLip matches the tightness of monolithic SDPs while requiring only a fraction of their computational cost. Remarkably, it scales substantially better than even existing layer-wise SDP approaches, which have so far offered the most scalable SDP-based alternative. This enhanced scalability extends tight SDP-based Lipschitz estimation to convolutional neural networks and paves the way for analyzing much larger architectures.

Primary area:
optimization
Keywords:
Lipschitz Constant Estimation, Robustness Analysis of Neural Network, First-Order Optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_PzexOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes ScaLip, a scalable method for estimating the global Lipschitz constant for deep neural networks. It builds on the exact decomposition proposed by EClipsE, develops an unconstrained parameterization for the multipliers along with the rescaling techniques, and solves them jointly towards a tight final Lipschitz bound using a first-order method. ScaLip achieves the optimal value of the large monolithic SDP methods while maintaining scalability. GPU acceleration is also enabled for further improving efficiency. Experiments on random networks and trained models demonstrate solid improvements in the trade-off between computational cost and certificate tightness. Overall, I find the contribution theoretically sound, meaningful, and of substantial practical value.

Critical strengths
  1. The parameterization of multipliers and first order method enables joint optimization so that the optimal value of the original SDP formulation is proved to be preserved. Such method allows the multipliers to be optimized with global information of the neural network rather than having only the Mi−1M_{i-1} certificates and the information from the next layer, improving the tightness.

  2. In comprehensive experiments on both random neural networks and trained ones, ScaLip considerably reduces conservatism relative to ECLipsE-Fast, particularly in the fixed-depth experiments with increasing width. It also beats EClipsE on both tightness and computational time. Comparing to the original SDP formulation (LipSDP) when available, it is shown that ScaLip obtains numerically matching bounds at substantially lower computational cost, showing the substantial practical use.

  3. I also appreciate the transparent reporting of memory limitations and runtime costs, which clearly illustrates the challenges of certifying wide neural networks. Although these networks remain computationally demanding, the experiments demonstrate meaningful progress while frankly acknowledging the remaining limitations.

Critical weaknesses
  1. Section 2.3.1 of paper "Demystifying Lipschitz verification: positive matrices, negative results" already discusses the same diagonal rescaling and its use in tightening Lipschitz bounds from SDP methods. This connection should be cited and the paper needs to clarify how its contribution differs. As I understand,the novelty of ScaLip lies not in the rescaling principle itself, but instead in how to build this scaling freedom into an equivalent, recursively feasible formulation within the joint optimization process.

  2. Equivalence of optimal values does not guarantee convergence of the first-order procedure. The recursive dependence on Mi−1−1M_{i-1}^{-1} couples feasible region for the multipliers across layers, potentially making optimization dependent on initialization. ECLipsE-Fast initialization is well motivated, but whether the first order method will drive the multipliers towards a near optimal solution is not clear, especially for ill-conditioned weights whose effects may not be sufficiently mitigated by rescaling alone.

Questions for authors

Are there mild or reasonable assumptions under which the joint optimization (or its equivalent problem) admits convexity or other properties sufficient to guarantee convergence to the global optimum of LipSDP?

3 comments
AuthorsOpenReview ↗

Response to Reviewer Pzex (Part 1/2): Weakness 1

We thank the reviewer for their constructive feedback and careful evaluation of our work. Below is a detailed response to the points raised by the reviewer. We have also summarized all updates to the revised manuscript in the General Response and Summary of the Revision, which we kindly invite the reviewer to check.

Weakness 1: Section 2.3.1 of paper "Demystifying Lipschitz verification: positive matrices, negative results" already discusses the same diagonal rescaling and its use in tightening Lipschitz bounds from SDP methods. This connection should be cited and the paper needs to clarify how its contribution differs. As I understand, the novelty of ScaLip lies not in the rescaling principle itself, but instead in how to build this scaling freedom into an equivalent, recursively feasible formulation within the joint optimization process.

Response: We thank the reviewer for mentioning this relevant paper, which we have now cited and discussed in Section 3.2 of the revised manuscript. In Section 2.3.1 of that work, the authors highlight the invariance of ReLU layers to positive diagonal weight rescaling, analyze the role that this rescaling plays in SDP-based methods such as LipSDP, and show that the naive product of layer-wise spectral norms can be tightened via diagonal rescaling. However, rescaling the naive spectral-norm product still treats layers independently and does not capture the cross-layer coupling of the [0,1][0,1] slope restrictions, remaining looser than SDP-based bounds. As the reviewer accurately noted, our contribution does not lie in the rescaling principle itself, but rather in embedding this diagonal scaling freedom (θi\theta_ i) together with the layer-wise margins (cic_ i) directly into the exact Schur-complement recursion to convert the constrained LipSDP problem into an equivalent unconstrained formulation that can be solved end-to-end via an accelerated first-order method.

AuthorsOpenReview ↗

Response to Reviewer Pzex (Part 2/2): Weakness 2 & Question

Weakness 2: Equivalence of optimal values does not guarantee convergence of the first-order procedure. The recursive dependence on Mi−1−1M_ {i-1}^{-1} couples the feasible region for the multipliers across layers, potentially making optimization dependent on initialization. EclipsE-Fast initialization is well motivated, but whether the first-order method will drive the multipliers towards a near-optimal solution is not clear, especially for ill-conditioned weights whose effects may not be sufficiently mitigated by rescaling alone.

Response: We completely agree with the reviewer and thank them for this insightful comment that inspired us to add Proposition 1 to the revised manuscript. While Theorem 1 proves the theoretical equivalence of the optimal values, analyzing the optimization landscape of the unconstrained formulation is important to explain why first-order optimization consistently drives the variables toward the global optimum in practice. We address this by adding Proposition 1 in Section 3.1 (proof in Appendix A.3).

Specifically, Proposition 1 proves that the unconstrained optimization problem in Theorem 1 has no non-global (spurious) local minima and has no saddle points (i.e., any differentiable point with zero gradient is a global minimizer). Briefly, our proof in Appendix A.3 proceeds in three steps:

  • (i) Our method starts from the LipSDP formulation, in which the LMI is affine in the decision variables and therefore convex. We then consider the decomposition of this monolithic SDP in EclipsE. In the first step of the proof, we show that because this decomposition reformulates the constraint of the original problem into equivalent layer-wise constraints, it inherits the convexity of the original problem. More precisely, the feasible set S=Θˉ:Mi≻0,∀i\mathcal{S} = \\{\bar{\Theta} : M_ i \succ 0, \forall i\\} of the decomposed problem (4) is convex, and its objective g(Θˉ)=λmax⁡(WDMD−1−1WD⊤)g(\bar{\Theta}) = \lambda_ {\max}(W_D M_ {D-1}^{-1} W_D^\top) is a convex function on S\mathcal{S}.

  • (ii) In the second step, we show that if we augment this problem with a few redundant scalar decision variables r=(r1,…,rD−1)∈R++D−1r = (r_ 1, \dots, r_ {D-1}) \in \mathbb{R} _ {++}^{D-1} as g~(Θˉ,r)=g(Θˉ)\tilde{g}(\bar{\Theta}, r) = g(\bar{\Theta}), our unconstrained formulation becomes a bijective one-to-one change of variables. The augmented objective g~\tilde{g} preserves the convexity of gg on S×R++D−1\mathcal{S} \times \mathbb{R} _ {++}^{D-1}, and our change of variables Φ:(θˉ,c)↦(Θˉ,r)\Phi: (\bar{\theta}, c) \mapsto (\bar{\Theta}, r) (and (γ,u)↔(θˉ,c)(\gamma, u) \leftrightarrow (\bar{\theta}, c) via element-wise exp⁡\exp and σ\sigma) forms a continuous one-to-one mapping with a continuous inverse Φ−1\Phi^{-1} (given explicitly in Eq. (8) of Appendix A.3). Because a continuous bijection with a continuous inverse preserves local minima, our unconstrained objective J(θˉ,c)J(\bar{\theta}, c) cannot have any non-global local minima.

  • (iii) Finally, we prove the absence of saddle points. Because Φ−1\Phi^{-1} is directionally differentiable everywhere (since λmax⁡\lambda_ {\max} is convex), applying the chain rule to g~(Θˉ,r)=J(Φ−1(Θˉ,r))\tilde{g}(\bar{\Theta}, r) = J(\Phi^{-1}(\bar{\Theta}, r)) shows that at any differentiable point where ∇J=0\nabla J = \mathbf{0}, the directional derivative of the convex objective g~\tilde{g} vanishes in every direction. By the convexity of g~\tilde{g}, any such point must be a global minimizer, ruling out saddle points.

Such a bijective mapping can bend the landscape, but cannot create spurious local minima or saddle points. Consequently, there are no suboptimal local valleys for the first-order optimization algorithm to be trapped in, even at non-smooth points, and any point with zero gradient to which the algorithm converges is guaranteed to be a global optimum of LipSDP.

Question: Are there mild or reasonable assumptions under which the joint optimization (or its equivalent problem) admits convexity or other properties sufficient to guarantee convergence to the global optimum of LipSDP?

Response: As detailed above, although our unconstrained formulation in Theorem 1 is not convex, Proposition 1 establishes that it has a favorable optimization landscape with no non-global local minima and no saddle points. Specifically, the absence of non-global local minima holds everywhere in the domain without requiring any assumptions on the network weights (beyond the trivial condition Wi≠0W_ i \neq \mathbf{0}, since Wi=0W_ i = \mathbf{0} would make the Lipschitz constant of the network zero). Furthermore, to ensure continuous differentiability of the objective JJ so that every stationary point (∇J=0\nabla J = \mathbf{0}) is guaranteed to be a global optimum of LipSDP, the only mild assumption required is that the maximum eigenvalues in the recursion and objective have multiplicity 11, which holds generically almost everywhere.

We thank the reviewer again and welcome any further questions during the discussion period.

My main concern has been substantially addressed and I am raising my score to 4.

Reviewer_fJkTOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces ScaLip, a method for computing the global Lipschitz constant of a neural network based on SDP relaxations. By formulating the LMI constraints into a recursive sequence, they improve the scalability of the method. The proof described in the appendix is based on a change of variables in the Xu & Sivaranjani (2024) formulation of the global LMI.

To ensure computational efficiency and soundness of the bounds, the approach uses a warm-started Lanczos algorithm for maximum eigenvalue estimation and Cholesky factorization, and a guardrail fallback with exact maximum Eigenvalue computation.

They claim the same performance (same Lipschitz constant estimation) as LipSDP, with speed (x2)/scalability (x10) comparable to EclipsE-like methods (that provide looser bounds).

Critical strengths

1/ They elegantly resolve a computational bottleneck. By reformulating a coupled LMI into an unconstrained problem without relying on surrogate objectives, the bounds seem competitive (comparable to SOTA methods).

2/ Empirically, ScaLip matches the bounds of LipSDP (SOTA) while being faster and scaling to dimensions where other SDP methods encounter OOM errors.

Critical weaknesses

1/ The paper claims that ScaLip scales to CNNs but the description is very short. Besides, if I understand correctly the method requires unrolling convolutions into dense matrices. While the method increases scalability compared to SOTA methods, unrolling has memory bottlenecks. This limitation is not explored in the experiments as they are limited to medium-depths CNNs on cifar10. Claiming general CNN scalability can be misleading, as this unrolling requirement fundamentally prevents the method from handling modern architectures.

2/ The guardrail fallback ensures mathematical soundness if the Lanczos approximation fails. However, this fallback has not been triggered in the experiments (l345). Hence, in ill-conditioned setups, neither the algorithm's equivalence to the original formulation nor its computational cost has been validated.

Questions for authors

1/ Please provide a deeper explanation of how your algorithm extends to convolutions. Besides, how does ScaLip's memory scale when unrolling deeper convolutional models ? Is the dense matrix representation a fundamental limit for handling CNNs?

2/ Does your framework open up the possibility of computing Lipschitz constants for models trained on higher-resolution datasets like ImageNet? or does the memory explosion from dense unrolling fundamentally limit the approach at CIFAR-10 resolutions?

3/ Are there specific weight initializations, deep architectures, or specific training regimes that successfully trigger the exact guardrail fallback? For instance, matrices that induce a slow Lanczos convergence rate (due to an unfavorable distribution of eigenvalues) ? If so, what is the practical performance impact on runtime when this guardrail is activated?

4 comments
AuthorsOpenReview ↗

Response to Reviewer fJkT (Part 1/3): Weaknesses

We thank the reviewer for the valuable comments that helped us improve the revised manuscript. Below is a detailed response to the points raised by the reviewer. We have also summarized all updates to the revised manuscript in the General Response and Summary of the Revision, which we kindly invite the reviewer to check.

Weakness 1: The paper claims that ScaLip scales to CNNs but the description is very short. Besides, if I understand correctly the method requires unrolling convolutions into dense matrices. While the method increases scalability compared to SOTA methods, unrolling has memory bottlenecks. This limitation is not explored in the experiments as they are limited to medium-depths CNNs on cifar10. Claiming general CNN scalability can be misleading, as this unrolling requirement fundamentally prevents the method from handling modern architectures.

Response: We agree with the reviewer that the explanation regarding CNNs was brief in the original manuscript. We have now expanded Section 3.3 and added Appendix B.3 in the revised manuscript to clarify both the formulation and its limitations. We have also clarified the detailed formulation in our response to Question 1 below. As the reviewer correctly pointed out, our framework, similar to the existing SDP Lipschitz estimation literature including LipSDP, EclipsE, and LipDiff, requires unrolling convolutional layers into dense matrices and treating them similarly to fully connected layers. We agree that dense unrolling is not the most memory-efficient way to represent convolutional layers and introduces memory bottlenecks on large feature maps. However, due to the lightweight nature of the computations in our method, ScaLip significantly outperforms the SDP-based methods LipSDP and EclipsE on CNNs, where the SDP solvers run out of memory in all tested cases. Nevertheless, as the reviewer rightly noted, scaling convolutional layers to larger modern architectures remains a limitation of our current work and is an important direction for future work, which we have now explicitly acknowledged in Section 3.3 and in the Conclusion of the revised manuscript.

Weakness 2: The guardrail fallback ensures mathematical soundness if the Lanczos approximation fails. However, this fallback has not been triggered in the experiments. Hence, in ill-conditioned setups, neither the algorithm's equivalence to the original formulation nor its computational cost has been validated.

Response: We agree that empirically validating both the correctness and the computational cost of the fallback mechanism is beneficial, although the fact that the guardrail fallback was never triggered across our experiments demonstrates the practical reliability of the warm-started Lanczos approximation. To this end, we artificially degraded the Lanczos algorithm by setting its iteration count to 11 instead of 1010 (which reduces the maximum eigenvalue estimation to a single Rayleigh quotient λ~max⁡(Ki)=q⊤Kiq\tilde{\lambda} _ {\max}(K_ i) = q^\top K_ i q for a unit random vector qq), forcing the Cholesky guardrail fallback to trigger at every single step, and re-ran Experiment 1 under this setup on both CPU and GPU. We have added these results to Table 1 of the revised manuscript under the column FF (Forced Fallback). As shown by the results, the bounds remain identical and the runtimes are very close to those of the non-accelerated exact version, since the only additional overhead comes from the 11-step Lanczos evaluation and the failed Cholesky check prior to falling back to exact eigendecomposition. We thank the reviewer for raising this point and helping us extend the empirical results of the manuscript.

AuthorsOpenReview ↗

Response to Reviewer fJkT (Part 2/3): Questions 1 & 2

Question 1: Please provide a deeper explanation of how your algorithm extends to convolutions. Besides, how does ScaLip's memory scale when unrolling deeper convolutional models? Is the dense matrix representation a fundamental limit for handling CNNs?

Response: Since a 2D convolution is a linear operation, our framework (similar to LipSDP, EclipsE, and LipDiff) represents a convolutional layer in the standard matrix-vector form Wixi−1+biW_ i x_ {i-1} + b_ i by flattening its input and output feature maps of sizes din×hin×wind_ {\text{in}} \times h_ {\text{in}} \times w_ {\text{in}} and dout×hout×woutd_ {\text{out}} \times h_ {\text{out}} \times w_ {\text{out}} into 1D vectors of lengths ni−1=dinhinwinn_ {i-1} = d_ {\text{in}} h_ {\text{in}} w_ {\text{in}} and ni=douthoutwoutn_ i = d_ {\text{out}} h_ {\text{out}} w_ {\text{out}}. As a simple toy example, consider a single-channel (din=dout=1d_ {\text{in}} = d_ {\text{out}} = 1) 3×33 \times 3 input convolved with a 2×22 \times 2 filter F=[f11f12f21f22]F = \begin{bmatrix} f_ {11} & f_ {12} \cr f_ {21} & f_ {22} \end{bmatrix} with valid padding to produce a 2×22 \times 2 output. Flattening the input and output row-wise into vectors xi−1∈R9x_ {i-1} \in \mathbb{R}^9 and xi∈R4x_ i \in \mathbb{R}^4 rewrites the 2D convolution as Wixi−1W_ i x_ {i-1}, where Wi∈R4×9W_ i \in \mathbb{R}^{4 \times 9} is the doubly block-Toeplitz matrix

Wi=[f11f120f21f2200000f11f120f21f22000000f11f120f21f2200000f11f120f21f22]=[T1T200T1T2],W_ i = \begin{bmatrix} f_ {11} & f_ {12} & 0 & f_ {21} & f_ {22} & 0 & 0 & 0 & 0 \cr 0 & f_ {11} & f_ {12} & 0 & f_ {21} & f_ {22} & 0 & 0 & 0 \cr 0 & 0 & 0 & f_ {11} & f_ {12} & 0 & f_ {21} & f_ {22} & 0 \cr 0 & 0 & 0 & 0 & f_ {11} & f_ {12} & 0 & f_ {21} & f_ {22} \end{bmatrix} = \begin{bmatrix} T_ 1 & T_ 2 & \mathbf{0} \cr \mathbf{0} & T_ 1 & T_ 2 \end{bmatrix},

in which each 2×32 \times 3 block T1,T2T_ 1, T_ 2 is Toeplitz and the blocks themselves are arranged in a Toeplitz structure. For multi-channel layers (dind_ {\text{in}} input and doutd_ {\text{out}} output channels), Wi∈Rni×ni−1W_ i \in \mathbb{R}^{n_ i \times n_ {i-1}} simply stacks dout×dind_ {\text{out}} \times d_ {\text{in}} such matrices, and is then processed in Algorithm 1 in exactly the same way as a fully connected layer.

Regarding memory scaling, at each layer ii, Algorithm 1 forms the unrolled weight and intermediate matrices Wi,W~i,Yi⊤∈Rni×ni−1W_ i, \tilde{W} _ i, Y_ i^\top \in \mathbb{R}^{n_ i \times n_ {i-1}} along with the ni×nin_ i \times n_ i matrices HiH_ i, Ki=W~iHi−1−1W~i⊤K_ i = \tilde{W} _ i H_ {i-1}^{-1} \tilde{W} _ i^\top, and the Cholesky factor Li∈Rni×niL_ i \in \mathbb{R}^{n_ i \times n_ i}. Because automatic differentiation stores the intermediate matrices along the forward pass to compute gradients during backpropagation, the memory usage increases with the matrix dimensions ni×ni−1n_ i \times n_ {i-1} and ni×nin_ i \times n_ i at each layer. While this memory footprint is still much smaller than that of interior-point SDP solvers (which run out of memory even on our smallest 2-layer MNIST CNN in Table 2), explicitly forming dense ni×ni−1n_ i \times n_ {i-1} and ni×nin_ i \times n_ i matrices remains a practical bottleneck when the flattened feature dimensions ni=douthoutwoutn_ i = d_ {\text{out}} h_ {\text{out}} w_ {\text{out}} become very large. Even though the unrolled Toeplitz matrix WiW_ i itself is sparse, Hi−1−1H_ {i-1}^{-1} and KiK_ i become dense, so overcoming this limitation for larger CNNs will require more memory-efficient handling in future work.

Question 2: Does your framework open up the possibility of computing Lipschitz constants for models trained on higher-resolution datasets like ImageNet? or does the memory explosion from dense unrolling fundamentally limit the approach at CIFAR-10 resolutions?

Response: Since the key factor in unrolling convolutional layers is the flattened output dimension of each hidden layer, ni=douthoutwoutn_ i = d_ {\text{out}} h_ {\text{out}} w_ {\text{out}}, which determines the size of the recursive matrices HiH_ i and KiK_ i, it is still possible to apply our framework to higher-resolution datasets such as ImageNet if aggressive downsampling (e.g., via large strides) is used in the initial layers. However, for standard full-resolution ImageNet architectures (224×224×3224 \times 224 \times 3) without aggressive early downsampling, early convolutional layers easily reach ni>105n_ i > 10^5, where explicitly forming and storing dense ni×nin_ i \times n_ i matrices across layers exceeds the memory of a mid-range GPU such as our 24 GB NVIDIA L4. Thus, certifying full ImageNet-scale networks on standard hardware and within a reasonable runtime is currently bottlenecked by dense unrolling and, as noted in our previous response, will require more memory-efficient convolutional representations in future work.

AuthorsOpenReview ↗

Response to Reviewer fJkT (Part 3/3): Question 3

Question 3: Are there specific weight initializations, deep architectures, or specific training regimes that successfully trigger the exact guardrail fallback? For instance, matrices that induce a slow Lanczos convergence rate (due to an unfavorable distribution of eigenvalues)? If so, what is the practical performance impact on runtime when this guardrail is activated?

Response: Regarding the practical runtime impact when the guardrail is activated, please see our response to Weakness 2 above: even when we force a 100100\\% fallback trigger rate by setting only 11 iteration for warm-started Lanczos in Experiment 1, the runtime remains nearly identical to the non-accelerated exact baseline, as the failed Cholesky check adds negligible overhead before falling back to exact eigendecomposition.

We also investigated whether a pathological set of neural network weights could naturally trigger the fallback with the default 1010 iterations of the Lanczos algorithm, but found that this does not occur in practice. As shown in Appendix B.1, the Cholesky guardrail is triggered at layer ii if and only if the warm-started Lanczos estimate λ~max⁡(Ki)\tilde{\lambda} _ {\max}(K_ i) with Ki=W~iHi−1−1W~i⊤K_ i=\tilde{W} _ i H_ {i-1}^{-1} \tilde{W} _ i^\top under-approximates the true maximum eigenvalue λmax⁡(Ki)\lambda_ {\max}(K_ i) severely enough that c~i=ciλmax⁡(Ki)λ~max⁡(Ki)≥1\tilde{c} _ i = c_ i \frac{\lambda_ {\max}(K_ i)}{\tilde{\lambda} _ {\max}(K_ i)} \ge 1, or equivalently,

λ~max⁡(Ki)λmax⁡(Ki)≤ci.\frac{\tilde{\lambda} _ {\max}(K_ i)}{\lambda_ {\max}(K_ i)} \le c_ i.

The relative ratio λ~max⁡(Ki)/λmax⁡(Ki)\tilde{\lambda} _ {\max}(K_ i) / \lambda_ {\max}(K_ i) produced by warm-started Lanczos with 1010 iterations is consistently close to 11, rather than significantly below 11. Therefore, for a pathological set of weights to trigger the fallback mechanism, optimization would simultaneously need to push cic_ i arbitrarily close to 11, which naturally does not happen for two reasons:

  • (i) Safety Buffer at Initialization: We initialize ui=0u_ i = 0 (ci=0.5c_ i = 0.5), meaning that at epoch 00 (before the eigenvector cache warms up), 1010-step Lanczos would have to underestimate λmax⁡(Ki)\lambda_ {\max}(K_ i) by more than 5050\\% to violate positive definiteness, which is far larger than the approximation error of a 1010-step Krylov subspace even on matrices with an unfavorable distribution of eigenvalues.

  • (ii) Desirable Vanishing Gradient Near ci→1c_ i \to 1: Because ci=σ(ui)c_ i = \sigma(u_ i), the gradient with respect to the unconstrained variable uiu_ i is ∂J∂ui=∂J∂cici(1−ci)\frac{\partial J}{\partial u_ i} = \frac{\partial J}{\partial c_ i} c_ i(1 - c_ i). As cic_ i increases toward 11, the factor (1−ci)(1 - c_ i) vanishes, acting as a natural brake that prevents cic_ i from approaching the boundary 11 over finite optimization horizons (in early implementations, we included an explicit cap ci=cmax⁡σ(ui)c_ i = c_ {\max}\sigma(u_ i) with cmax⁡=0.999c_ {\max} = 0.999, but have since removed it because this vanishing-gradient property rendered it completely unnecessary).

Consequently, in practice, even unfavorable weight matrices do not simultaneously induce a severe eigenvalue under-approximation and push cic_ i close enough to 11 to trigger the fallback.

We thank the reviewer again for their time and constructive feedback, and we would be happy to address any further questions during the discussion period.

I thank the authors for their detailed response, complementary experiments and revisions to the manuscript. After considering their clarifications and the other reviewers' comments, I have decided to maintain my original score.

Reviewer_3r9pOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes ScaLip, an unconstrained reformulation of SDP-based Lipschitz constant estimation that preserves the tightness of the original SDP while enabling efficient optimization with scalable first-order methods. Experiments show that ScaLip substantially reduces computational cost and scales to larger networks, including convolutional architectures, while maintaining tight Lipschitz bounds.

Critical strengths
  1. The theory is solid and correct.
Critical weaknesses
  1. SDP-based Lipschitz constant estimation has been an important research direction for certified robustness of deep ResNets, MLPs, and CNNs. However, its practical significance has arguably diminished with the development of scalable parameterizations of Lipschitz-bounded neural networks. In particular, Refs. [1,2] demonstrate that networks with millions or even billions of parameters can be directly trained with tight Lipschitz bounds and strong certified robust performance. In contrast, SDP-based verification methods remain limited to relatively small neural networks due to their computational cost.
  2. Modern SOTA architectures are based on attention mechanisms, which are generally not globally Lipschitz without additional restrictions. To the best of my knowledge, the SDP framework considered here does not directly extend to estimating local Lipschitz constants of attention-based architectures over compact domains.
  3. The proposed method builds on the approach of Xu & Sivaranjani (NeurIPS 2024), which can be interpreted as exploiting a chordal decomposition of a band-structured LMI. Closely related ideas have previously been investigated in Ref. [3] and subsequently played an important role in scalable parameterizations of Lipschitz-bounded networks [2,4]. In particular, the diagonal scaling introduced around line 266 appears closely related to the parameterization in Eq. (9) of Ref. [2]. Moreover, similar constructions to those around lines 172–173 have been used in Ref. [4] for constructing Lipschitz-bounded layers.

Refs:

[1] Araujo et al. A unified algebraic perspective on lipschitz neural networks. ICLR 2023.

[2] Wang and Manchester. Direct parameterization of Lipschitz-bounded deep networks. ICML 2023.

[3] Xue et al. Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks. IEEE CDC, 2022.

[4] Pauli et al. LipKernel: Lipschitz-bounded convolutional neural networks via dissipative layers. Automatica, 2026.

Questions for authors

see the weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 3r9p (Part 1/2)

We thank the reviewer for pointing out the relevant references [1-4]. We have included all four references in the Introduction of the revised manuscript to improve our literature review and better clarify the contributions of our work. Below is a detailed response to the points raised by the reviewer. We have also summarized all updates to the revised manuscript in the General Response and Summary of the Revision, which we kindly invite the reviewer to check.

Weakness 1: SDP-based Lipschitz constant estimation has been an important research direction for certified robustness of deep ResNets, MLPs, and CNNs. However, its practical significance has arguably diminished with the development of scalable parameterizations of Lipschitz-bounded neural networks. In particular, Refs. [1,2] demonstrate that networks with millions or even billions of parameters can be directly trained with tight Lipschitz bounds and strong certified robust performance. In contrast, SDP-based verification methods remain limited to relatively small neural networks due to their computational cost.

Response: We thank the reviewer for this comment. We completely agree that SDP-based methods for Lipschitz estimation of neural networks have historically been computationally bottlenecked. In fact, this was precisely the motivation behind our research and the very challenge we aimed to address in this work. We also agree that studies such as [1, 2] are able to train Lipschitz-bounded networks from scratch by devising specialized parameterizations for the training routine. However, they cannot bound the Lipschitz constant of an already trained network. In fact, constrained parameterizations like [1, 2, 4] require specialized layer parameterizations during training (which, although yielding more robust networks, can restrict model capacity and clean accuracy while adding computational overhead during training) and cannot be applied to standard pre-trained networks deployed in practice. In contrast, standard models are trained without per-step parameterization overhead, and ScaLip or other Lipschitz constant estimation methods are only executed once post-hoc to certify the final trained network. Therefore, our work tackles the problem of computing the Lipschitz bound of pre-trained networks and effectively mitigates the exact bottleneck the reviewer mentioned for SDP-based verification methods. For example, on the largest network in our Experiment 2, which has more than 80 million parameters, our method (ScaLip-GPU) computes the Lipschitz bound in approximately 2.5 minutes, whereas SDP-based methods struggle even on much smaller architectures (see Table 3 in Appendix B.4). We have clarified this distinction between Lipschitz-by-construction training and post-hoc verification in the Introduction of the revised manuscript.

Weakness 2: Modern SOTA architectures are based on attention mechanisms, which are generally not globally Lipschitz without additional restrictions. To the best of my knowledge, the SDP framework considered here does not directly extend to estimating local Lipschitz constants of attention-based architectures over compact domains.

Response: We agree with the reviewer that, similar to existing SDP-based baselines, our method does not support attention mechanisms. Indeed, as the reviewer correctly recognizes, due to their multiplicative terms, attention mechanisms are not globally Lipschitz and therefore cannot be included in a global Lipschitz verification framework. Furthermore, as the reviewer rightly pointed out, estimating the local Lipschitz constant of attention-based architectures over compact sets fundamentally changes the underlying optimization problem in Eq. (2), which prevents a straightforward extension of SDP-based methods and places architectures with attention mechanisms outside the scope of our work. Nevertheless, we thank the reviewer for highlighting this important topic, which we will pursue as a direction for future work. We have highlighted this in the Conclusion and Future Work section of the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer 3r9p (Part 2/2)

Weakness 3: The proposed method builds on the approach of Xu & Sivaranjani (NeurIPS 2024), which can be interpreted as exploiting a chordal decomposition of a band-structured LMI. Closely related ideas have previously been investigated in Ref. [3] and subsequently played an important role in scalable parameterizations of Lipschitz-bounded networks [2,4]. In particular, the diagonal scaling introduced around line 266 appears closely related to the parameterization in Eq. (9) of Ref. [2]. Moreover, similar constructions to those around lines 172-173 have been used in Ref. [4] for constructing Lipschitz-bounded layers.

Response: As the reviewer correctly points out, and as was already mentioned in our initial submission, we build upon Eq. (4), the main theorem of EclipsE [5], which, similar to [3], leverages the sparsity structure of LipSDP and decomposes the single LMI into several smaller LMIs. However, although the chordal decomposition in Chordal-LipSDP [3] is insightful from a theoretical perspective and influenced subsequent studies including EclipsE and ours, it does not directly bring practical computational speedups. As the first author of [3] reported in their later work [6, Table 3.1], Chordal-LipSDP not only fails to improve the total runtime of LipSDP [7], but also severely degrades it (which is expected, as it introduces many dense matrix decision variables into the problem). We have added Chordal-LipSDP to Experiment 2 of our revised manuscript and similarly observed that it severely degrades the computational performance of the original LipSDP. EclipsE unlocked the practical utility of [3], and building upon EclipsE, we derive our method that produces tighter Lipschitz bounds via a much faster first-order method. Regarding the similarities with [2] and [4], we agree that related concepts have been used in the literature to train Lipschitz-bounded networks from scratch, as all of these works also build upon the SDP-based framework of LipSDP; however, as noted in our previous answer, none of these works can compute a Lipschitz bound for an already trained network. Regarding Eq. (9) of [2], we agree that they similarly leveraged the intuition of weight rescaling to construct their parameterization. Regarding Lines 172-173 of the original submission vs. [4], as we had already acknowledged in the initial version of our manuscript, we directly adapted the decompositions in Lines 172-173 from the EclipsE framework, and these derivations were not presented as a contribution of our work (our contribution instead lies in obtaining tighter Lipschitz bounds through a substantially faster first-order method). We have clarified these connections and citations in the Introduction, Related Work, and Section 3.2 of the revised manuscript, and added the empirical comparison with Chordal-LipSDP to Section 4.2 and Appendix B.4.

We thank the reviewer again for their time and effort in evaluating our work. We would be happy to address any further questions during the discussion period.

References:

[1] Araujo et al. A unified algebraic perspective on Lipschitz neural networks. ICLR, 2023.

[2] Wang and Manchester. Direct parameterization of Lipschitz-bounded deep networks. ICML, 2023.

[3] Xue et al. Chordal sparsity for Lipschitz constant estimation of deep neural networks. IEEE CDC, 2022.

[4] Pauli et al. LipKernel: Lipschitz-bounded convolutional neural networks via dissipative layers. Automatica, 2026.

[5] Xu and Sivaranjani. EclipsE: Efficient compositional Lipschitz constant estimation for deep neural networks. NeurIPS, 2024.

[6] Xue. Trustworthy Machine Learning: Specification, Verification, and Explanation. Ph.D. Dissertation, University of Pennsylvania, 2025.

[7] Fazlyab et al. Efficient and accurate estimation of Lipschitz constants for deep neural networks. NeurIPS, 2019.

Thanks for the authors' response, which partially addresses my concerns. However, I tend to maintain my original score.

  • One major motivation for Lipschitz constant estimation is certified robustness. If an application requires a neural network with a small Lipschitz bound, it may be more effective to encode it as prior knowledge during training rather than relying on post-training verification. If the Lipschitz constant of a trained model is large (e.g., ≥100\geq 100; see Table 3), a faster bound estimation method merely confirms that the network is not robust, without providing a mechanism to improve its robustness in subsequent training. Moreover, computationally cheaper methods, such as PGD-based attacks, may already be sufficient to demonstrate the lack of robustness in such cases.

  • I agree with Reviewer fJKT's comment in W1 that SDP-based verification methods typically require convolutional layers to be unrolled into dense matrices, which can be highly memory-inefficient. This limitation is particularly relevant given that the experiments in this work are restricted to relatively small datasets, such MNIST and CIFAR-10. Moreover, the considered architectures exclude several widely used components, such as normalization and pooling layers, further limiting the demonstrated practical applicability of the proposed method.

AuthorsOpenReview ↗

Follow-up Response to Reviewer 3r9p

Thanks for the follow-up discussion. We respectfully disagree with the reviewer that enforcing a Lipschitz constant during training can simply replace post-hoc Lipschitz verification and eliminate the need for existing state-of-the-art NN verification methods.

1. Post-Hoc Verification vs. Direct Parameterizations, Context of LL, and PGD

  • Limitations of Lipschitz enforcement methods: Direct parameterizations to enforce a Lipschitz constant [1, 2, 4] require prescribing a fixed Lipschitz bound prior to training, which is rarely known in advance. As an example, [2] trains models for different Lipschitz constants (e.g., 0.5,1,…,16\\{0.5, 1, \dots, 16\\} in one case) and picks the model with the best empirical robust accuracy. This shows the costly retraining sweeps needed to balance clean accuracy and robustness in such methods. Moreover, certified classification depends on the Lipschitz constants of pairwise logit differences (margins) fy(x)−fj(x)f_y(x) - f_j(x) [8]. However, direct parameterizations must either enforce an end-to-end Lipschitz bound on the full network f(x)f(x) that does not reflect these margins (yielding bounds substantially larger than the logit-difference Lipschitz bounds [8, Table 2]), or enforce the bound up to the pre-final layer and rely on conservative modifications such as multiplying the pre-final bound by the naive last-layer norm; in either case, they do not provide a tight margin Lipschitz bound. Even for networks trained via parameterizations such as [2], ScaLip can provide a scalable and accurate method for calculating the tighter Lipschitz bounds on pairwise logit differences for the trained network, potentially certifying samples that were left uncertified. The same holds for many other applications where prior Lipschitz bounds are not known.

  • Why post-hoc Lipschitz estimation is essential: In many safety-critical domains, such as reinforcement learning, imitation learning, and system identification, models are typically trained with standard pipelines, as enforcing specialized Lipschitz-by-construction layer parameterizations during training can restrict policy exploration, value-function expressivity, or clean performance. In formal control and verification of neural feedback loops (e.g., certifying closed-loop stability via the Small-Gain Theorem, Integral Quadratic Constraints, or Lyapunov/barrier certificates), the required threshold for the Lipschitz constant LL is dictated by the safety constraints, not by a value chosen before training. The tightness of a guaranteed upper bound then decides whether a certificate exists. For example, in grid-based verification, tightening LL by a factor kk widens the admissible grid spacing by kk in every dimension.

  • Comparison with PGD: PGD and ScaLip answer complementary questions: PGD can falsify robustness at single specific input points but can never certify it, while certification requires a guaranteed upper bound. Since the certified radius scales with margin/L\text{margin}/L, a tighter bound directly certifies more samples. On trained models in Table 2, ScaLip is up to ∼19×\sim 19\times tighter than the best scalable baseline, EclipsE-Fast, while LipSDP and EclipsE run out of memory on most examples.

2. Normalization, Pooling, and CNN Scope

  • Batch normalization: We would like to clarify that our framework natively supports batch normalization. At inference time, batch normalization is a fixed affine map. It folds exactly into the adjacent linear/convolutional layer (Wi,bi)(W_i, b_i), so the method needs no changes.
  • Pooling: Average pooling is linear and is absorbed into the (unrolled) weight matrix of the adjacent layer, like the stride-2 convolutions already used in our CNNs. Non-overlapping max-pooling is 1-Lipschitz in ℓ2\ell_2. It can be handled compositionally (since max-pooling layers are 1-Lipschitz by themselves, ScaLip can be used compositionally and the final bound is the product of the Lipschitz bounds of all partitions).
  • CNN Unrolling and Benchmarks: While we have acknowledged the path for future work to make our method more memory-efficient on CNNs, we emphasize that our method significantly outperforms the state of the art on CNNs. We believe that methods should be evaluated against established baselines, and we improve performance significantly across the SDP Lipschitz verification literature (LipSDP, Chordal-LipSDP, LipDiff, EclipsE).

References: [8] Fazlyab et al. Certified robustness via dynamic margin maximization and improved Lipschitz regularization. NeurIPS, 2023.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response and Summary of the Revision

We thank all three reviewers for their time, constructive feedback, and insightful suggestions, which have helped us clarify and improve our manuscript.

We have uploaded a revised version of the manuscript with all major additions and modifications highlighted in blue, along with the updated supplementary code. Please note that all section, proposition, equation, table, and appendix numbers referenced in our individual responses correspond to the revised manuscript unless mentioned otherwise. Below, we summarize the main updates in the revision:

  • 1. Optimization Landscape Guarantee (Proposition 1 in Section 3.1 and Proof in Appendix A.3): To establish why first-order optimization reliably converges to the global LipSDP bound, we added Proposition 1 (and its three-step proof in Appendix A.3), which proves that our unconstrained formulation has no non-global (spurious) local minima and no saddle points.

  • 2. Empirical Validation of the Cholesky Guardrail Fallback (Section 4.1 and Table 1): We conducted a forced-fallback stress test (FF columns in Table 1) by setting the number of WarmLanczos iterations to 11 on both CPU and GPU to intentionally trigger the Cholesky guardrail at every step, confirming that the converged bounds remain identical and the runtimes closely match the non-accelerated exact version.

  • 3. Expanded Formulation and Discussion for Convolutional Layers (Section 3.3, Section 5, and Appendix B.3): We expanded Section 3.3 and added an illustrative doubly block-Toeplitz unrolling example in Appendix B.3, while explicitly discussing the memory limitations of dense unrolling on very large CNNs and outlining future directions (including local Lipschitz estimation over compact domains for attention-based architectures) in Section 5.

  • 4. Expanded Literature Review and Chordal-LipSDP Benchmark (Sections 1, 1.2, 3.2, 4.2, and Appendix B.4): We incorporated all references suggested by the reviewers, clarified the distinction between Lipschitz-by-construction training parameterizations and post-hoc verification, discussed the role of diagonal weight rescaling in Section 3.2, and added an empirical comparison with Chordal-LipSDP to Experiment 2 (Section 4.2 and Appendix B.4).

We have also provided detailed point-by-point responses to each reviewer below.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.