acceptodds
Withdrawn from ICLR 2027

Certificate Tightness Is a Training Property

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

A deterministic robustness certificate rests on a global Lipschitz bound, usually the product of the layers’ spectral norms. On a standard network under standard training, that bound exceeds the sensitivity the network exhibits by orders of magnitude. We study the ratio of the two, the gap. The bound certifies the true constant from above, and any exhibited Jacobian certifies it from below. So the gap is the factor between the two ends of a certified enclosure. No verifier returning a global constant can improve the certified radius by more than that factor. This paper characterizes what sets the gap. It does not build a certified system. Its one intervention leaves the architecture and the loss fixed. We track the gap along training over 380 runs on four datasets. At a fixed convolutional architecture, training sets it. At learning rates fixed in advance, the gap grows 3× under SGD, 60× under AdamW and 2,300× under Muon. Tuned rates compress that spread to one order, SGD still mildest and Muon below AdamW. At those fixed rates on ImageNet-64, the spread widens to ten orders. Every quantitative prediction was registered before its test run, with two marked exceptions, and every miss is printed. The gap factors exactly into misalignment between layers and slack from units the activations switch off. Projecting each layer onto a spectral-norm cap after every step removes the slack term. Under Muon it moves the gap from 3.2 million to 7.4, at 0.55 clean accuracy against 0.88. The product bound is then within a factor of about seven of the best radius any global-constant verifier could grant. Repair after training recovers a factor of two to six, against five orders. Under the cap the optimizers’ roles invert. At the operating budget and the rates fixed in advance, SGD and AdamW collapse toward rank one and stop learning. Muon, which inflates the gap most when free, keeps training. We name this the constraint inversion. The cap moves only the bound, and verified accuracy also needs a trained margin. On four published 1-Lipschitz constructions at one fixed bound, Muon verifies more than SGD, with disjoint seed ranges. Training decides how much of a tight bound is usable.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Lipschitz constant, certified robustness, spectral norm, Muon, optimizer geometry, training dynamics, stable rank, 1-Lipschitz networks, pre-registration

Reviews

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

This paper studies how training affects the gap between the product of spectral norms Lipschitz bound and empirical Jacobian lower bounds. It analyzes the effect of different optimizers and spectral-control methods, reporting observations on gap growth and rank collapse, and explores remedies like post-training repair and optimizer switching.

Critical strengths

The paper systematically investigates tightness across training settings and datasets, providing empirical evidence while acknowledging tuning sensitivity and accuracy costs.

Critical weaknesses
  1. Limited theoretical novelty. Proposition 1 directly applies the standard margin-based certificate. Equation (4) gives an algebraic factorization, and Propositions 2–3 use familiar homogeneity and rescaling arguments. The paper should distinguish its new contributions from existing work, including Kuang et al. (2026).

  2. Limited generalizable guidance. Optimizer ordering changes after learning-rate tuning, while collapse depends on architecture, temperature, and learning rate. The update-rank discussion in §3.3 does offer a partial explanation based on known properties of orthogonalized updates, but gives little guidance beyond experimental tuning.

  3. Unclear practical benefit. The gap reduction from approximately 3.2 million to seven accompanies a clean-accuracy drop from approximately 88% to 55%, with only 0.15% certified accuracy at the reported radius. Practical claims need comparisons at similar accuracy and training budgets.

  4. Some conclusions not sufficeintly justified. For example, “Never pay for post-hoc repair” rests on restricted rescaling arguments and selected experiments, without reporting clean accuracy after weight-only repair in the main text. Optimizer switching also lacks a clear comparison with using the destination optimizer from initialization. "Tightness alone is insufficient, as expected." The certificate depends on both margin and the Lipschitz bound. Even an exact global Lipschitz constant may give a conservative local classification certificate. The experiments should better separate limitations from bound estimation, the certificate itself, and weak robustness.

Questions for authors
  1. Does optimizer switching improve clean accuracy, gap, and certified accuracy over training with either optimizer from initialization under comparable budgets? Is the benefit consistent across seeds and switching times?

  2. How do clean and certified accuracy change after weight-only capping? Can repair preserve useful classification performance?

  3. Beyond the known geometry of Muon updates, what new mechanism explains rank collapse? Can it predict when collapse occurs or tuning prevents it?

  4. What supports the broad recommendation against post-training repair?

Reviewer_fi2FOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The authors attempt to delve into the downstream impact of training time choices (particularly optimizer choice) on certified robustness performance.

Critical strengths

The authors are motivated by an interesting problem - attempting to understand, qualify, and explore the drivers behind certification under-performance. Exploring this space is important for understanding the theoretical and practical limits of certified systems under deployment.

The authors have presented a detailed set of additional ablation experiments within the appendices which, at times, covered interesting ground.

Critical weaknesses

Fundamentally, I assess a paper in terms of two key areas - how interesting the idea is, and how well the authors convey that idea. To me, unfortunately, this work appears primarily to be an experimental exploration of robustness gaps. This is not necessarily a bad thing - experimentally derived works are important. But in an experimental work there's a need for there to be something that the reader can take away from the work, to generalize to their own approaches. In this work, I really struggle to see how anyone would do this. The experimental evaluation is relatively limited (focusing resources on 3 optimizers and limited datasets), is built upon an unclear set of tested hypothesis, and really fails to articulate the implications of the results, and the why of them.

This inability to articulate also speaks to just how hamstrung the manuscript is by the poor quality of the authors prose. Subjects are ambiguous, ideas are presented in a staccato manner, and concepts are introduced as a "what" but without a "why". Complicating all of this is that I do not think that the authors have a clear idea about who their audience is. I've been working in the certification space for a long time (although primarily branch & bound and Cohen style certs), and even I was having to pause to think through what the authors were trying to communicate at times. My read on this would be that a reader who is less familiar with this space would truly struggle to understand what was going on at times.

Further notes on this exist below, and are presented in the hope that they help the authors improve the quality of their manuscript.

Foundations

  • The Lipschitz constant "is what a certificate needs and is intractable to compute" - this is one form of what an L2 norm certification may need, but there are other norms, and other forms. For classifiers for example, certifications are based upon the argmax/softmax output of f_theta, and changes to that are more important than to the L2 norm difference across the final layer.
  • Mathematical detail is poorly presented (see below for more comments on writing quality). See for example the definition of G - is G defined strictly as a measure of the ratio? It's defined without discussing why it's defined.
  • "It is computed exactly, so L_Linear <= L_global holds by construction (Appendix B)" - this seems like a relatively important point for understanding the overall mechanism, which would suggest it should be in the main body, rather than App B. But then when looking at App B, it's not even clear where this is formally defined.
  • The authors define G >= 1, and M >= 1, but they say there's no possible guarantee on A, but yet A = G / M so inherently A >= 0. This isn't wrong, and it's incredibly minor, but still, what else is a review for if not for occasionally devolving into scientific pedantry?
  • "The grid holds 380 training runs across 358 unique configuration-seed cells." 1) The grid is completely undefined. 2) This in no way follows on from the previous sentence. 3) There's no explanation for the close-but-not-exact 380 vs 358. I assume this is referencing the grid in Figure 1 - but it's both a) too small, and b) very odd to present results in a place where a teaser figure would usually be. It makes these read like they're indicative numbers, not real results.
  • Figure 2 - it seems like these properties rapidly asymptote, rather than being a function of the training step. But the length of the asymptote, and the lack of markers, makes one wonder how much of the effort was placed into resolving things at high training steps. Also the lack of log scale makes one wonder how close to 0 this goes, and how arbitrary the everything-approx-60 value as training -> 0 is.
  • Literature review is somewhat sparse - for example, the gap was not just considered by Khromov & Singh and Ma. Cullen et al's "Et Tu Certifications: Robustness Certificates Yield Better Adversarial Examples" is one example off the top of my head. There's also some of the earlier CR papers like Salman's work for example that attempted to decrease the gap, at least implicitly. Obviously these are probabilistic CR approaches, rather than Lipschitz, but fundamentally this is a broader space than is being presented here.
  • I'm not exactly sure what someone would take from this work. For example, take the statement in the conclusion that developers sholud "Choose the optimizer with the care given to the architecture". But there's not much detail as to what drives this choice, or what are the factors that are promoting these changes.

Writing quality

  • Look at the abstract as an example - the presentation is highly staccato, the length is significantly longer than the accepted academic style (~28 sentences, as compared to the usual <10 sentence abstracts), and I'd suggest that it really doesn't efficiently communicate what the authors are trying to say. Speaking of the abstract "it" is often used without a clearly established subject.
  • This staccato presentation persists across the document. Sentences don't flow from their preceding sentences. The same goes for paragraphs. To really underscore the issues with this staccato presentation, look at the conclusion, and the limitations statement.
  • "is a promise built from one number" - this reads as an attempt to be poetic in presentation, but it fails to convey any meaning. What is this promise? How is it built? What is the one number? And then going into "no input change is amplified by more than a factor L." What is the audience for this? I've been reading certification papers for 7+ years, and while I can understand it, I struggle to believe anyone who is not deeply immersed in the literature would get what the authors are saying. This same pattern is repeated with the discussion of the sqrt(2) factor, and again, and again, and again. A paper should be accessible to more than just the authors. It should be able to stand somewhat self contained, at least with regards to its prose.
  • The subject ambiguous "it" anti-pattern continues beyond the abstract. It refers to certification gaps, certifications themselves, and I'm sure a bunch of other things, but it's subject is never clearly established.
  • Font size on Figure 1 is way too small - it's orders of magnitude smaller than the body text.
  • "We therefore work with one certified bound on each side of it, EQN, EQN, the product bound and the witnessed sensitivity over a witness set D of data points." This isn't a sentence. And the it is ambiguous again - it could be the true Lipschitz contstant, the evaluation process, that evaluation is NP-hard, or two-layer networks.
  • Undefined terms - exhibited / exhibited Jacobian is used 3 times, yet it's not defined, yet it's "proof of sensitivity".
  • "The certificate prices its worst end". What is the it? And pricing is used as a concept repeatedly, but is never defined. This isn't an E-values based certification mechanism, so there's no natural concept of price or value as a part of the certificate.
  • "Verified accuracy at a radius is the share of test inputs classified correctly and certified there". Someone from within the certification community would understand this. But outside of it, the "there" not clearly referring to the the radius in question is going to be difficult to parse. There's a reason most papers discussing CA will just define it mathematically, because it's quite a clear and intuitive process to grok mathematically, and, I'd argue, far clearer than this presentation.
  • "up to six orders of certified radius may be recoverable". I have absolutely no clue what the authors are trying to say here, nor why "G \approx 7" is defined so differently ("within a factor 7 of what any sound verifier could grant"). Close proximity changes to the verbiage of how you discuss a single concept invites confusion rather than clarity - because the reader suddenly is asking if there's a reason why the verbiage is changing, and if that means anything.
  • "The gap has exactly two places to live." - perhaps to say that it could originate from two places might be a little clearer.
  • Structuring is odd. It would appear to make more sense to just define G, M, A in the one space, rather than discussing G, then going into M, A later.
  • "only one handle acts on the numerator" - handle reads as being a technical device, but it appears to just be semantics.
  • "Later registered blocks add runs outside it"....what?
  • "These are geometric means over seeds" - are the these 3, 60, 2300? It seems unlikely, as they're highly even numbers.
Questions for authors
  1. How would this generalize beyond the strictly feed-forward ReLU networks you've considered here?
  2. What were you thinking about when you introduced transformers into the limitations section? I ask because they would, as an artchitecture, appear to be completely detached from the approaches you have described, and perhaps this speaks to a point that I have misunderstood while reading the paper.
Reviewer_hWWPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the gap G between the product of layer spectral norms (an upper bound on a ReLU network's Lipschitz constant) and the largest Jacobian norm observed on 64 test inputs (a lower bound). By Proposition 1, no verifier returning a global constant can enlarge the certified radius by more than G. Across 380 runs on four datasets, mostly a six-convolution CIFAR-10 network without normalization layers, the authors report:

  • G grows 3×, 60× and 2,300× under SGD, AdamW and Muon at pre-set learning rates (about one order of magnitude apart when tuned);
  • an exact split G = M × A into cross-layer misalignment and activation gating;
  • capping each layer's spectral norm after every step takes Muon's G from 3.2 × 10⁶ to 7.4, at 0.55 clean accuracy against 0.88, while post-hoc repair recovers a factor of 2 to 6;
  • under the cap, SGD (at every budget tried) and AdamW (at the operating budget) collapse toward rank one and stop learning, while Muon keeps training;
  • on four published 1-Lipschitz constructions, Muon verifies about 3.5 to 4.5 points more than SGD (Table 27).

Nearly all quantitative predictions were written down and timestamped before the corresponding experiments (two exceptions are marked), and failed predictions are reported alongside successful ones.

Critical strengths
  • The experimental practice is careful and transparent. Predictions were registered before the runs, misses are reported in the main text, the instruments are cross-checked (stronger witness sets, LipSDP on a dense network, an exhaustive 2-D check), and seed variation is reported.
  • Measuring the ratio rather than the bound itself is a sensible choice. Together with Proposition 1, it gives a cheap diagnostic for whether a better global-constant verifier could help at all.
  • The decomposition G = M × A is exact by construction and makes the source of looseness measurable. The gating-entropy check in Section 3.6 rules out the trivial explanation that the cap simply makes the network linear.
  • The rank collapse of SGD and AdamW under hard projection, with Muon unaffected, is an interesting observation. The temperature × learning-rate factorial (Appendix J) is a good attempt to separate the candidate causes.
  • The result that Muon improves verified accuracy over SGD on four existing 1-Lipschitz constructions, with disjoint seed ranges, is the most directly usable finding.
Critical weaknesses

1. The headline optimizer effect depends heavily on the learning rate.

The abstract leads with G growing 3×, 60× and 2,300× under SGD, AdamW and Muon. These numbers come from one learning rate per optimizer, fixed in advance. Table 8 shows that this choice matters a lot:

  • Within one optimizer, a higher learning rate gives a much larger G. For Muon, G goes from 1.3 × 10⁴ at rate 0.005 to 1.7 × 10⁹ at rate 0.05.
  • Muon's fixed rate is not its best rate. Muon reaches its best accuracy at rate 0.005 (0.898), not at its fixed rate of 0.02 (0.875). At its best rate, its G is 1.3 × 10⁴, about 250× lower than the 3.2 × 10⁶ the paper headlines.
  • At each optimizer's best rate, the difference largely disappears:
OptimizerBest rateClean accuracyG
SGD0.050.8524.4 × 10³
Muon0.0050.8981.3 × 10⁴
AdamW10⁻³0.8647.6 × 10⁴

The spread falls from about 700× to about 17×, and Muon is no longer the loosest.

The main grid runs each optimizer at only one pre-chosen learning rate. The authors should report G across a range of learning rates for each optimizer, and compare optimizers at matched clean accuracy, to show whether the ranking still holds. Table 8 already has this sweep for the unconstrained network, but it is not used in the main argument.

2. Suggestions for understanding G better.

The paper measures G carefully, but leaves open why it grows and how readers should interpret it. I would like to see the following explored:

  • Why does G grow during training, and why faster under some optimizers? The two explanations the authors registered were both rejected by their data (Table 26), which they report honestly. Stable rank (roughly, the number of directions the weights use) fell under Muon rather than rising, and it fell most under SGD, whose G grew least. What is the authors' current best explanation?
  • Is step size the driver? Weakness 1 shows that a larger learning rate gives a larger G. One direct test: make each optimizer change the weights by the same amount per step, and check whether G still differs between optimizers.
  • What does G tell the reader, and how can it be used? G measures how informative the certificate is, not how robust the network is. A reader could take "G falls from 3.2 million to 7" as a robustness gain, yet verified accuracy is unchanged (Section 3.7). Two things would help:
    • State the limits of G in one place. They are now mentioned in different sections: G applies only to verifiers returning a single global constant; a small G means nothing for a network that has stopped learning; and G is measured on 64 inputs, so it is an upper estimate.
    • Show how G can be used. The paper's main suggested use is to measure G before investing in a better verifier (Section 5). The paper does run LipSDP on a dense network (Table 21), but to check that the gap is not an artifact, not to test this use. A direct demonstration would show that networks with small G gain little in certified radius from a tighter verifier, while networks with large G gain more. It would also help to know whether G can guide other decisions, such as choosing an optimizer, learning rate or cap budget, or detecting during training when the certificate starts to become uninformative.

3. The training setup is not "standard training".

The abstract frames the results as holding for "a standard network under standard training", but the main grid uses no normalization layers, no learning-rate schedule and only 8,000 steps. The paper itself says the collapse under the cap is "a property of our protocol" (Appendix A). Either narrow the claims, or repeat the main results with batch normalization and a learning-rate schedule.

4. The novelty feels limited.

  • The main contributions are measurements. The paper reports how G changes with the optimizer, under a hard cap and after post-hoc repair, but offers no explanation or new method built on these observations.
  • The theory is light. Proposition 1 follows in one line from the definitions, and the paper presents Propositions 2 and 3 as resting on a known rescaling symmetry of ReLU networks (Section 3.4).
  • The directions in weakness 2 would add the missing depth: an explanation of why G grows, a test of whether step size drives it, and a demonstration of how G can be used in practice.

5. Minor: the paper is hard to read, and the information is dense.

  • The main text contains no tables. All 27 tables are in the appendices, so the numbers behind most results (for example, Tables 6, 8, 9 and 11) cannot be checked without leaving the main text.
  • Some sentences can only be understood with the paper's own vocabulary in mind. Examples are "Within every optimizer the routes harden in the registered order" (Section 3.3), "Only the total budget is physical" (Section 3.4) and "Propositions 2 and 3 close profile search and covariant projection" (Section 5).
Questions for authors
  1. At matched clean accuracy, how large is the optimizer effect on G? Can you plot G against clean accuracy along the learning-rate sweep for each optimizer?
  2. Do the main results (the optimizer effect on G and the cap reducing G by orders of magnitude) hold with batch normalization and a standard learning-rate schedule? If batch normalization prevents the collapse under the cap, how should the "constraint inversion" be read?
  3. Section 3.3 argues that the rank collapse comes from a persistent dominant update direction at c = 2, but says why that direction persists "stays open". Can you separate the update geometry from the effective step size, for example by running SGD or AdamW with update norms matched to Muon's?
  4. For the Muon vs. SGD comparison on the four 1-Lipschitz constructions, rates were chosen by a 1,000-step screen, but four of the six screens peaked at the edge of their grid (Appendix S). Would the advantage survive a wider rate search and full-length tuning?
  5. How does G relate to the certified radius from a local verifier on the capped networks? This would show how much of the remaining slack global-constant verifiers cannot reach.

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

Related papers

Discussion (0)

Sign in to comment.