acceptodds
Under review as a conference paper at ICLR 2027

The Price Of Diagonal Multipliers In Neural Network Certificates

Abstract

Many semidefinite Lipschitz certificates for neural networks use diagonal multipliers on activation slope inequalities. We study their conservatism relative to a stated certificate class, using classical polytopic vertex-LMI ideas. For discrete-time neural dynamics, we derive necessary and sufficient vertex conditions for one-step quadratic incremental ℓ2-gain certificates over the independent-slope abstraction (class-exact). We connect this characterization to robustness margins; its layerwise counterpart is NP-hard to compute. A valid block-multiplier hierarchy contains the diagonal level and reaches the reference under strict quadratic-stability assumptions. For equilibrium models, fixed-point certificates dominate storage-based ones, and their diagonal level contains LBEN. For stability, the stated Lur’e–Postnikov-type Lyapunov family is at least as powerful as quadratic functions. We characterize its full strength over sector-bounded or monotone classes by necessary and sufficient vertex conditions with a constructive, decrease-preserving reduction; slope restrictions can permit strict improvement. Exact witnesses enclose the maximum diagonal/reference class price over 72 feedforward networks in [1.049355, 1.049357], and the maximum diagonal/full-block static class price over 828 equilibrium-model targets in [1.067848, 1.122833]. These are class-optimum enclosures; the separate 4.14% reduction from blocks of four compares returned feasible gains. Complete audits of twelve two-layer ReLU networks separate losses, with abstraction loss above 72% in one model. On two width-80 MNIST models, under a 60-second per-target budget, the original block policy loses to diagonal in certified accuracy at ϵ = 0.3.

Primary area:
optimization
Keywords:
semidefinite programming, neural network certification, robustness certificates

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_S8shOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This work studies one particular method for neural network certification, namely SDP. It studies various theoretical properties of the diagonal multiplier of SDP. It then demonstrates its theoretical results with empirical studies.

Critical strengths

SDP is one of the major methods in verifying ℓ2\ell_2 robustness, therefore, understanding and improving it is an important problem.

Critical weaknesses
  1. The paper is extremely badly written. I tried hard to read it and still find it confusing. It rarely has intuitions well-explained, and the proof sketch is also weak and abstract. Explaining the intuition and sketch via minimal examples or plots would have been better. I do not think any reader can reasonably understand the current manuscript without significant difficulty.

  2. The empirical result is very weak. The main result uses networks with up to hundreds of neurons, while SDP-CROWN which also uses SDP for ℓ2\ell_2 robustness, has scaled to millions of parameters. At radius 0.3, this work achieves up to 56.6% on MNIST, while SDP-CROWN reports more than 80%. This might be due to the model scale, but if the method proposed is not scalable at all, what will be the credit?

Questions for authors

See weakness

6 comments

Thank you. The general comment lists the changes. As you suggested, Figure 1 is now a minimal example with three neurons and a plot (exact values in App. E). §4–§6 start with intuition, and the proof ideas after Theorem 2, Theorem 5 and Proposition 6 go step by step.

Scale and SDP-CROWN. The paper is a measurement study, not a new verifier (§1, "Scope"). It asks how much tightness diagonal multipliers cost in SDP Lipschitz certificates. Measuring this from both sides needs the reference value, the best bound this certificate type can prove. Computing it takes 2m2^m LMIs for a layer of mm neurons and is NP-hard already for one hidden layer, so two-sided results are limited to small models. One-sided bounds scale further: new App. K certifies that the price is at most 19.3% on 27 feedforward networks (up to six hidden layers and 768 neurons) and at most 11.0% on 9 convolutional networks; for 18 residual networks the bounds are inconclusive.

The 56.6% is the mean certified accuracy at radius 0.3 of three width-40 monotone DEQs on MNIST (Table 2). It comes from Lipschitz bounds that hold for all inputs, with four-neuron block multipliers. SDP-CROWN computes bounds for each input separately, on different and larger models, so the two numbers are not comparable. §2 now cites SDP-CROWN and says this.

What the measurement offers. We measured how much looser diagonal multipliers make the bound than the best bound of the same certificate type: on the networks with certified two-sided bounds, at most 4.94% for feedforward networks and 12.29% for DEQs (against the static full-block certificate). A much larger gap comes from using only slope ranges: in one ReLU network, every bound that uses only slope ranges, including ours, exceeds the true Lipschitz constant by over 72%. So, on these networks, richer static multipliers can tighten the bounds only slightly, and designers of SDP certificates are likely to gain more from information that slope ranges discard.

If any point that affects your assessment remains open, please tell us and we will address it.

Dear authors,

Thanks for the effort, especially the improved writing. However, I am still unconvinced about the novelty of this work. In particular, the authors try to say it is unnecessary to compare against SDP-CROWN, which I believe to be super weak, as all theoretical results ultimately want to guide the practice. Especially when this work also presents a new algorithm, even though it does not claim sota.

Part 1. Thank you for the follow-up and for noting the improved writing

It does present a new, provably valid certificate family, the block-multiplier hierarchy, but we do not propose it as a verifier (§1, "Scope"): used as one, it gives a modest gain at a higher cost, so we do not claim state of the art. The paper is a measurement study. Its credit is twofold: methods that make the cost of diagonal multipliers measurable with certified bounds, and the certified findings they produce.

Terms, as used in the paper.

  • Multiplier: the weights an SDP certificate puts on the conditions that each activation's slope stays in a known range (for ReLU, between 0 and 1). A diagonal multiplier gives each neuron its own weight; a block multiplier also couples the neurons within a group; the full block is one group with all neurons of a layer.
  • Storage function: an energy-like quadratic function that some certificates use to track how the difference between two inputs changes over time steps (for a feedforward network, a time step is a layer).
  • Static: a static multiplier acts at a single time step. A static fixed-point certificate for deep equilibrium models (DEQs) works directly on the fixed-point equation, with no storage function.
  • Reference value: the smallest bound that a quadratic storage function can prove from the slope ranges alone, with each neuron's slope free to vary over time (one storage per layer for feedforward networks). No certificate that combines such a storage with a static multiplier, diagonal or not, can prove less.
  • Price: the diagonal bound divided by the reference value; 1.05 means the diagonal bound is 5% above it. For DEQs, certificates without storage are never worse (Proposition 6(v)), so there both bounds are static fixed-point certificates: the diagonal one divided by the best one with the full block.
Reviewer_Kf2WOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper is motivated to measure what makes certificates loose. Authors construct a reference and intermediate certificates to analyze where the conservatism enters SDP-based neural-network certificates. The crucial conclusions supported are: improving multipliers addresses only one source of conservatism, and its practical value depends on computation and model structure. The main contribution is the measurement of losses; and its practical improvements are the more comprehensive validation on various models at different scales.

Critical strengths

Strong points:

  1. The problem formulation evidently reveals why a tighter multiplier need not solve the dominant source of looseness.
  2. The numerical evidence distinguishes feasibility from optimality: they combine the verified upper bounds with exact moment, covariance-flow, and slope-response lower witnesses.
  3. The stability results are well supported by explicit proof with counterexamples.
Critical weaknesses

Weak points:

  1. On page 3, 5 and 6, much of the central framework builds upon control theory. The vertex characterization and strict full-block equivalence build directly on classical results; the paper acknowledges this. Its novelty therefore rests primarily on the neural-network formulation, the particular hierarchy, the restricted Lyapunov-family result, and the certified audits.
  2. On page 4 and 6, the reference remains restricted. For DEQs, equality between the static full-block reference and the independent-slope fixed-point gain is explicitly unresolved. Consequently, the reported DEQ interval measures a certificate-class penalty, not total robustness conservatism.
  3. On page 7-9, empirical generality is limited. The forward neural networks are mainly shallow and small-scale, failing to validate the performance on deep convolutional, residual, and transformer architectures.
  4. On page 6, There is little predictive understanding of when blocks help. The paper measures conservatism carefully, but offers no validated structural rule for selecting worthwhile blocks or anticipating a large diagonal penalty.
Questions for authors

Questions:

  1. On page 6, can the static DEQ full-block exactness question be resolved under additional assumptions, or illustrated with a counterexample? This would clarify what portion of the remaining gap belongs to the multiplier class versus the fixed-point abstraction.
  2. On page 7, can you provide stronger guidance on when the diagonal price becomes large? Controlled changes in depth, width, conditioning, or coupling—and matched comparisons of alternative partitions—would help turn the diagnostic findings into a useful selection rule.
6 comments

Thank you for the careful reading and the accurate summary.

  1. We agree that the vertex characterization and the full-block equality rest on Boyd et al. (1994) and Scherer (2001), and we cite them where they are used. §1 now states what is new for networks: (i) on small ReLU models the true Lipschitz constant can be computed, so we also measure how far the best certificate is from it; (ii) for feedforward networks the reference value uses one storage function per layer, which adds a third source of looseness, the storage loss; for DEQs, fixed-point certificates, which Scherer's argument does not cover, are never worse than storage-based ones; (iii) a family (cone) of block multipliers that can be checked exactly at finitely many vertices, is valid for increments (differences between two inputs), and contains LipSDP-Neuron (and, for DEQs, the LBEN condition) as special cases. With all neurons of a layer in one block, it reaches the storage-based reference value; this needs strict stability for recurrent updates and storage-based DEQ certificates, and no condition for feedforward networks (new Proposition 11(iv)); (iv) intervals that provably contain the price, although computing the reference value is NP-hard already for one hidden layer. We also added Noori et al. (2024a) (Remark 22, App. I).

  2. The DEQ reference and Q1. We agree. The abstract, §3 and §6 now state that for DEQs the price is measured against the best static fixed-point certificate that couples all neurons in one block. So the DEQ interval is a price within static certificates, not the total looseness of the bound. We removed the appendix sentence that conjectured that, under a rank condition, this certificate gives the best possible bound under the fixed-point abstraction (describing the DEQ only through slope ranges at its fixed points), and the paper makes no claim about it: the equality argument we adapt from Scherer covers certificates with a storage function, not static fixed-point ones. The paper does not certify how much of the DEQ gap comes from this abstraction. Table 9 gives an uncertified indication on MNIST: mean diagonal bounds of 40.4 (contractive) and 26.2 (monotone), against sampled lower estimates under the fixed-point abstraction of 38.2 and 24.4. These ratios, about 1.06 and 1.07, overestimate the price and that gap combined; they do not separate the two.

  3. For two of the three architectures, the limit is computation, not the theory: a convolution without max pooling is a feedforward layer with structured weights, and a residual block is one step of (1) with A=IA=I (§3). What does not scale is measuring the price from both sides: computing the reference value uses one LMI per corner of each layer's slope box (2m2^m for a layer of mm neurons), and it is NP-hard already for one hidden layer. One-sided upper bounds do scale: new App. K certifies that the price is at most 19.3% on 36 feedforward and convolutional networks with up to 768 neurons; for 18 residual networks the bounds are inconclusive. Attention does not act on each neuron separately, so transformers are outside our setting.

  4. Q2 (when the price is large). We have no validated rule, and the paper says so. We tried a predictor based on how strongly the weights couple neurons, chosen before testing; on twelve held-out models it did no better than predicting the average for each DEQ type (App. J). One certified comparison: the largest DEQ price is at most 1.018 and 1.013 on two width-8 MNIST models, but at least 1.033 on one of the six width-40 MNIST models (App. J, Table 15). The models differ in more than width and there are few seeds, so this suggests, but does not show, that the price grows with width. The worked example (Figure 1) also shows that an intuitive block (two neurons that are never active together) can give no improvement, because block multipliers use only the slope ranges, not which neurons can be active together. Controlled studies of depth, width, conditioning and coupling are future work (§8).

If any point that affects your assessment remains open, please tell us and we will address it.

Thank you again for your review. As the discussion period ends on November 18, we would like to check whether our response and the revised PDF address your concerns. If anything is still unclear, we would be glad to clarify before the deadline. If the response resolves your concerns, we hope this can be reflected in your final assessment.

Thank you for the response and for revising the claims and providing additional experiments. These clarifications improve the presentation and help delineate the scope of the contributions. However, my main concerns remain:

  1. Limited methodological novelty. The theoretical framework largely specializes established results from control theory to neural-network certification. Although this application is useful, the response does not sufficiently establish a substantial methodological advance beyond that specialization.
  2. Limited evidence of scalability. The computational cost remains a significant constraint. The additional MNIST experiments extend the evaluation, but the tested networks remain relatively small and shallow. These results therefore do not establish applicability to substantially larger or deeper architectures.
  3. Lack of a validated criterion for practical benefit. The paper still lacks a reliable criterion for predicting when richer multipliers will meaningfully improve certificates relative to their computational cost. The authors acknowledge this limitation, but deferring it to future work leaves the practical guidance incomplete. Given these unresolved concerns, I maintain my original assessment. I appreciate the authors’ efforts and would welcome a substantially strengthened revision that demonstrates clearer methodological advances, broader scalability, and more actionable guidance.
Reviewer_LmRKOpenReview ↗
Rating
2
Confidence
2(+1)
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates how much tightness is lost by the use of a diagonal multiplier in SDP-based neural network certificates. The authors propose a reference value based on LMI to measure the loss. With the reference, the authors measure three types of losses, replacing joint activation behavior with elementwise independent slopes, modeling activation constraints using quadratic constraints, and combining activation constraints using diagonal multipliers.

Critical strengths

This paper propose a reference value based on LMI to measure the loss of the use of a diagonal multiplier in SDP-based neural network certificates, which can be extremely useful in the tightness analysis of SDP-based relaxation.

Critical weaknesses

The writing of this paper needs improvement, this paper is extremely technical and hard to follow. The authors should place more emphasis on the motivation and intuition behind developing the technical result in the paper.

I believe there is novelty in this paper; however, the writing of this paper needs significant improvement in order to be accessible to general readers of the ICLR.

Questions for authors

None

5 comments

Thank you for recognizing the novelty and for the clear advice. The revision now puts motivation and intuition first:

  • §1, "Why the multiplier matters" explains that SDP certificates use only the slope ranges of the activations and weight each neuron's slope condition by one number (the diagonal multiplier); why the tightness lost this way matters; and why measuring it is hard.
  • Figure 1, for a network with three neurons, shows on one axis the true Lipschitz constant, the best bound any certificate of this type can prove, and the bound with diagonal multipliers. The gaps between them are the two losses the paper measures: the looseness from using only slope ranges, and the looseness from diagonal multipliers (the price).
  • §3 defines all notation before it is used, and §4–§6 each start with a short paragraph of intuition.

If any part is still hard to follow, please tell us which, and we will revise it.

Thank you again for your review. As the discussion period ends on November 18, we would like to check whether our response and the revised PDF address your concerns. If anything is still unclear, we would be glad to clarify before the deadline. If the response resolves your concerns, we hope this can be reflected in your final assessment.

Thank you again for your review and for recognizing the novelty. Since our first reply, we have uploaded a further revision that continues the clarity work you asked for (all discussion-phase additions are in blue). New in this revision:

  • §3–6 now define each remaining term and symbol where it is first used, for example what a linear matrix inequality (LMI) is, how each kind of network fits the common form (1), and what a level of the multiplier hierarchy is.
  • The abstract and §1 define the reference value precisely, and long sentences are split.
  • §7 states a practical consequence: on the MNIST monotone DEQs, multipliers that couple groups of neurons can certify at most 64.0% of test inputs at radius 0.3 (mean of three seeds), against 55.5% for diagonal multipliers (Table 9). On these models, larger gains need information beyond the slope ranges.

The changes from the first revision that you suggested are kept: the motivation in §1, the worked example of Figure 1, and the intuition paragraphs and proof ideas of §4–6.

We hope the revision addresses your suggestions.

Reviewer_vs2bOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2(+1)
Read review
Paper summary

The paper studies the strength of diagonal-mulitplier certificates for discrete-time Lur'e systems and various special cases, including feedforward neural networks, deep equilibrium models, and models with recurrent updates. Several classes of reference values are introduced for discrete-time Lur'e systems (as well as several special cases) that are then compared with values obtained by diagonal multipliers. Finally, computational experiments are performed where the reference values and diagonal-multiplier values of several models are computed and compared.

Critical strengths

The underlying questions that are studied in this paper, such as quantifying the looseness of relaxations for computing Lipschitz constants of neural networks, are certainly interesting, and the results could be of interest to the machine learning community if the mathematical claims are made precise and if the paper presents its results in a clearer and more understandable way (see the Weakness section).

Critical weaknesses

I recommend rejecting the paper because it lacks clarity in its presentation and is mathematically imprecise in many parts.

My first main concern is with the readability of the paper. The writing of the paper is very compressed and the paper makes frequent use of non-standard high-level terminology, which makes it extremely hard to follow the paper. Here are some examples for this (this is a non-exhaustive list):

  • Line 14-16: "vertex conditions for one-step quadratic incremental ℓ2\ell_2-gain certificates over the independent-slope abstraction (class-exact)". Even if these terms are eventually defined in the paper at a later point, one should not use this terminology already in the abstract.
  • Line 73: "gain-to-margin chain"
  • Line 80-81: "Certificates on the fixed-point relation are never worse than storage-based ones at any level". It has not been defined what stoage-based certificates are.
  • Line 194: "Vertex characterization of quadratic incremental dissipativity". The paper does not define what "quadratic incremental dissipativity" means.
  • Line 204: "dynamic multipliers"
  • Line 260: "Strict top-level losslessness"
  • Line 338: "printed rational certificates"
  • Line 368: "historical population maximum"
  • Line 372-374: "Iris (Fisher, 1936), two moons, and PCA-50 MNIST (LeCun et al., 1998) and Fashion-MNIST (Xiao et al., 2017)(gains in PCA coordinates); widths (8), (16), (8,8); ReLU and tanh; three seeds; 72 networks." The writing is compressed to such an extent that I do not understand what this sentence is supposed to mean. The same applies to lines 374-376, 425-430.
  • Line 454: "multiplier headroom", "population-wide gap"

One reason for the lack of readability might be that the authors try to convey too much information within the page limit of 9 pages, leading to the compressed writing and overloaded paper. Therefore, to improve readability in a potential revision of the paper, I would suggest that the authors decide on which contribution(s) are the most interesting and central one, present only these contribution in the main paper in much more detail than currently, and move the less interesting ones to the appendix. This would also include revising the writing of the proof ideas, which are currently very short and not very understandable, using only standard terminology or properly defining non-standard terminology in the paper, and making the writing in the experiments section less compressed and more readable.

My second concern is with the mathematical precision of the paper and its results. In many cases, the mathematical objects and terms used in the paper have not been properly defined in the preliminary section, so in the later parts of the paper it is unclear what the objects that are being considered and discussed actually represent (especially for readers not completely familiar with the topic). Besides the comments above, here are some more examples for this:

  1. Line 45: It is not defined what increments are, and the term "incremental" is used many times afterwards.
  2. Line 140-144: The dimensions of zz, xx, and wkw_k are not defined. It is also not clear how the functions computed by recurrent updates are.
  3. Line 161: It is not formally defined what it means for a function to be "time-varying".
  4. Line 169: It is not defined what a "result" is and therefore it is unclear what a "robustness" certificate is supposed to represent.
  5. Line 173: The value γdiag\gamma_{\rm diag} is introduced as "the infimum of the gains certifiable with diagonal multipliers". The paper does not rigorously state what "the gains certifiable with diagonal multipliers" are. I do not understand what this is supposed to represent, since the paper neither introduces what "gains" are, nor what diagonal multipliers are in the context of their setting. This should be properly introduced (e.g. by rigorously stating the model, what diagonal multipliers are in this context, and what the "gain").
  6. Line 187 (Equation (2)): It is not defined what Δx+\Delta x^+ is.
  7. Line 221: The paper does not define what "activation patterns" are in their context. The claim that every activation pattern is realized on an open set of inputs is not generally true for ReLU networks and common definitions of activation patterns. For example, for the ReLU network that computes f:R→R,  x↦max⁡(0,x)−max⁡(0,−x)f:\mathbb{R}\to\mathbb{R},\; x\mapsto \max(0,x)-\max(0,-x), both neurons are inactive (attain zero) only if x=0x=0, so this activation pattern is not realized on an open set of inputs. Since the authors seem to use a different definition of activation patterns, they should properly introduce and define this term in the "Preliminaries" section.
  8. Line 234: It is not defined what FyF_y or FjF_j are.
  9. Line 313: It is not clear where the ∑jθj∫…\sum_j\theta_j\int\dots terms come from and how it relates to the model considered in the paper.

In a potential revision, the "Preliminaries" section should be substantially extended, with more detailed definitions of the mathematical objects and a more detailed problem statement (including rigorous definitions for quantities such as γdiag\gamma_{\rm diag}). I recommend revising and more carefully preparing a clear exposition of the results and conveying the conceptual ideas behind the proofs.

Other comments

  • Line 11-31: The abstract is hard to decipher. For example, it is not clear what (class-exact) or what the intervals are supposed to mean, since they are properly introduced only much later in the paper. I would recommend to not use non-standard terminology in the abstract.
  • Line 141: It is not clear whether the activation functions ϕℓ\phi_\ell can be different or if they are assumed to be the same for each layer.
  • Line 157: The paper should mention what dimensions the matrices in B have.
  • Line 172: It is not clear what a quadratic inequality "on the fixed-point relation" is. This should be made more precise.
  • Line 174: It would be helpful to mention what a "certificate type" is before defining γref\gamma_{\rm ref} using this term.

Minor comments

  • Line 138: The organization of proofs in the appendix should not be mentioned in the "Notation" paragraph (e.g., one could mention this after listing the contributions).
  • Line 158: Using V\mathfrak{V} as the set of vertices of B\mathfrak{B} is not a good notational choice, since they are very easy to confuse visually.
  • Line 378-390 (Figure 1 (Middle/right)): The entries at 1.0 are barely legible.
Questions for authors

Besides providing clarifications for the mathematical definitions and terminology discussed in the Weaknesses section which are the main reason for the score, I have the following additional questions:

  1. Line 151: Could you please clarify how exactly a DEQ becomes (1) in the coordinates σ\sigma?
  2. Line 225-230: Could you please clarify how the NP-hardness result for ReLU networks with one hidden layer and scalar output differs from existing NP-hardness results for computing the Lipschitz constant, e.g., Scaman & Virmaux (2018) and Jordan & Dimakis (2020)?
8 comments

Thank you for the detailed list. We agree that the submission used terms before defining them. We moved secondary material to the appendix and used the space for definitions, intuition and an example.

  • Increments; dimensions; recurrent updates; activations (ll. 45, 140–144): §3, "Notation and increments" and "Three kinds of networks". Activations may differ across neurons and layers.
  • B\mathfrak B, time-varying maps, robustness certificates (ll. 157–169): §3, "Slopes and the abstraction" (B⊂Rm×m\mathfrak B\subset\mathbb R^{m\times m}), "One form for all three" and "Incremental gains and robustness certificates".
  • Gains, diagonal multipliers, γdiag\gamma_{\rm diag}, dissipativity, storage-based and fixed-point certificates (ll. 80, 172–174, 194): §3, "Certificates and multipliers" (Eq. (2)) and "Problem statement", which writes out the inequality that defines γdiag\gamma_{\rm diag} and names the reference for each kind of network.
  • Symbols in Eq. (2) and Prop. 4 (ll. 187, 234): Δx+\Delta x^+ is defined after Eq. (2); FiF_i (the ii-th logit) and the class labels cc, c′c' are defined before Prop. 4. If you meant other symbols, please tell us.
  • Lur'e–Postnikov terms (l. 313): explained in App. C.
  • Other terms you listed: removed from the main text or defined where they first appear. The E2 and E3 setups are rewritten in full sentences.
  • Abstract and proofs: the abstract avoids non-standard terms, and the proof ideas after Theorem 2, Theorem 5 and Proposition 6 go step by step.

Activation patterns (l. 221). The claim assumes, in the same sentence, that W0W_0 has full row rank. Then the pre-activations W0x+b0W_0x+b_0 can take any value, so every on/off pattern of the hidden neurons occurs on an open set of inputs. Your example is most likely ∣x∣=ReLU(x)+ReLU(−x)|x|=\mathrm{ReLU}(x)+\mathrm{ReLU}(-x); there W0=[1;−1]W_0=[1;-1] has rank 1, so the assumption does not hold. §4.1 now states the assumption wherever it is used, and Figure 1 is an example without full row rank. The claim therefore holds as stated; we hope this answers your soundness concern.

Q1 (DEQ as (1)). Take σ=Wz+Ux+bz\sigma=Wz+Ux+b_z as the state. Then z=ϕ(σ)z=\phi(\sigma) and σ=Wϕ(σ)+Ux+bz\sigma=W\phi(\sigma)+Ux+b_z, which is (1) at a fixed point with A=0A=0, B=WB=W, C=IC=I, E=UE=U, w=xw=x, Cy=0C_y=0, Dy=VD_y=V, Dw=0D_w=0. Fixed points of the two forms correspond one-to-one (Lemma 12). This is now in §3.

Q2 (NP-hardness). The reduction of Scaman & Virmaux (2018, App. A) uses one-hidden-layer networks whose first layer has full row rank; for these, our reference value equals the true Lipschitz constant. The result is now Remark 3, credited to them, and no longer a contribution; our MaxCut proof is kept as an alternative in App. B.2. Jordan & Dimakis (2020) prove that the ℓ1\ell_1 and ℓ∞\ell_\infty Lipschitz constants are hard even to approximate, a different setting. Both are cited in §2.

If any point that affects your assessment remains open, please tell us and we will address it.

Thank you again for your review. As the discussion period ends on November 18, we would like to check whether our response and the revised PDF address your concerns. If anything is still unclear, we would be glad to clarify before the deadline. If the response resolves your concerns, we hope this can be reflected in your final assessment.

I thank the authors for responding to my questions and their revised manuscript.

Although the revised version is more readable compared to the previous version, my concerns regarding the readability and mathematical precision of the paper are still largely unresolved. There are still several undefined mathematical terms and I still find the paper very difficult to follow (in particular, the mathematical sections 3 to 6).

This comment only concerns the revised main paper (all 10 pages contain significant changes). I did not go through the revised appendix in detail (over 20 pages in it contain changes compared to the prior version).

Comments on the paper

2 comments

We thank the reviewers. Main finding: we measured how much looser diagonal multipliers, the standard choice (e.g. LipSDP-Neuron), make SDP Lipschitz bounds than the best bound of the same certificate type. On the networks where we certified two-sided bounds, this is at most 4.94% for feedforward networks and 12.29% for DEQs (against the static full-block certificate). A much larger gap comes from using only slope ranges: in one ReLU network whose true Lipschitz constant we computed exactly, every bound that uses only slope ranges, including ours, exceeds the true constant by over 72%. So, on these networks, richer static multipliers can tighten the bounds only slightly; larger improvements need more information than slope ranges.

The main changes:

  1. Readability. The abstract and introduction are rewritten in plain language. §3 ("Setting, certificates and the problem") now defines all notation, the three kinds of networks, the certificates and the three quantities we compare: the diagonal bound γdiag\gamma_{\rm diag}, the reference value γref\gamma_{\rm ref} (the best bound this certificate type can prove) and the true Lipschitz constant γtrue\gamma_{\rm true}. Figure 1 is a worked example with three neurons (exact values in App. E). §4–§6 each start with a paragraph of intuition, and the proof ideas go step by step. To make room, the stability results and experiment E1 moved to App. C.
  2. Credit and prior work. That computing the reference value is NP-hard, already for one hidden layer, follows from Scaman & Virmaux (2018). It is now Remark 3, credited to them, and no longer claimed as a contribution. §1 ("Relation to control theory") states what we take from Boyd et al. (1994) and Scherer (2001) and what is new. We added Noori et al. (2024a), who describe all valid incremental quadratic constraints for ReLU; Remark 22 (App. I) shows that, with a storage function, these constraints never certify a bound below our reference value.
  3. Scope. §1 ("Scope") states that the paper measures what diagonal multipliers cost; it does not propose a new verifier. §8 lists the limitations the reviewers raised. For DEQs, the abstract, §3 and §6 now state that the price is measured against the best fixed-point certificate that couples all neurons in one block (the full block).
  4. Larger networks (new App. K), for the scale questions of Reviewers Kf2W and S8sh. As a limited check of whether the price stays small on larger networks, we certify upper bounds on it for 54 newly trained MNIST networks with up to 768 neurons. The price is at most 19.3% for 27 feedforward networks (up to six hidden layers) and at most 11.0% for 9 convolutional networks. For 18 residual networks the upper bounds (up to 39.2%) are inconclusive: without the reference value, they also contain the storage loss (from the quadratic storage functions) and the gap left by our search over slope patterns.
  5. Notation. Symbols that had two meanings within a section are renamed; for example, the slope vector is now κ\kappa, so kk only indexes time. Terms are explained in words where they first appear, and each concept has one name (e.g. full block for the block of all neurons). Renamed symbols are not marked separately; inside revised passages they are blue with the surrounding text.

We removed one appendix conjecture on DEQs.

We thank the reviewers and the AC. After the follow-ups of 15–16 Nov, we uploaded a second revision (discussion-phase changes in blue; the main text is still 10 pages) and replied to each follow-up. In brief:

  1. Clarity (vs2b, LmRK). Terms and symbols in §3–6 are now defined where they first appear (e.g. LMI, time-varying activation maps, the σ-coordinates of a DEQ, levels of the hierarchy, feasibility, and γdiag\gamma_{\rm diag} and γref\gamma_{\rm ref} for each kind of network). §4–6 open with intuition; Theorems 2 and 5 and Proposition 6 have proof ideas. No result changed in content in this revision.

  2. Novelty (Kf2W, S8sh). We agree that the vertex test and, for recurrent updates, the full-block equality specialize Boyd et al. (1994) and Scherer (2001); the paper credits both. What is new: certified two-sided bounds on the price of diagonal multipliers on trained networks, through exactly checked witnesses, although the reference value is NP-hard to compute; a block-multiplier hierarchy valid for increments and checked at 2∣b∣2^{|b|} corners per block; the full-block result for feedforward networks with no stability condition (Scherer's result applied per layer); and the separation of three losses on networks whose true Lipschitz constant we compute exactly.

  3. Scale (Kf2W, S8sh). We agree that our models are small. Two-sided measurement needs the reference value (2m2^m vertex checks for a layer of mm neurons), so it is limited to small models. Block certificates need only 2∣b∣2^{|b|} checks per block (cost: Table 12). App. K certifies one-sided bounds on 54 networks of up to 768 neurons.

  4. Practical guidance (Kf2W, S8sh). We have no validated rule that predicts from the weights when blocks help; the predictor we tested failed (App. J). A certified test, needing no block SDP, bounds in advance how much any block can gain (App. K). Price bounds also cap the accuracy gain: on the MNIST monotone DEQs, no block level can certify more than 64.0% at radius 0.3 (mean of three seeds), against 55.5% for the diagonal certificate and 56.6% for four-neuron blocks (§7, Table 9).

  5. SDP-CROWN (S8sh). The current numbers are not directly comparable: global Lipschitz bounds versus per-input bounds on different, larger models. In the final version we will add a direct comparison on the raw-pixel feedforward MNIST models of App. K, at the same radii.

We are grateful for the reviewers' detailed comments

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.