- 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
-
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 certificates and the information from the next layer, improving the tightness.
-
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.
-
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
-
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.
-
Equivalence of optimal values does not guarantee convergence of the first-order procedure. The recursive dependence on 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
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 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 of the decomposed problem (4) is convex, and its objective is a convex function on .
-
(ii) In the second step, we show that if we augment this problem with a few redundant scalar decision variables as , our unconstrained formulation becomes a bijective one-to-one change of variables. The augmented objective preserves the convexity of on , and our change of variables (and via element-wise and ) forms a continuous one-to-one mapping with a continuous inverse (given explicitly in Eq. (8) of Appendix A.3). Because a continuous bijection with a continuous inverse preserves local minima, our unconstrained objective cannot have any non-global local minima.
-
(iii) Finally, we prove the absence of saddle points. Because is directionally differentiable everywhere (since is convex), applying the chain rule to shows that at any differentiable point where , the directional derivative of the convex objective vanishes in every direction. By the convexity of , 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 , since would make the Lipschitz constant of the network zero). Furthermore, to ensure continuous differentiability of the objective so that every stationary point () 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 , 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.
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.
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] 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) together with the layer-wise margins (ci) 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.