acceptodds
Under review as a conference paper at ICLR 2027

Beyond Static Embeddings: Finite-Query Certificates for Local Representation Stability

Abstract

The geometry of finitely observed embeddings does not determine the local stability of the representation map. We investigate this information gap using a finite-query framework. Within the class of continuously differentiable functions, identical activation observations can correspond to arbitrarily large local sensitivity. Moreover, perturbation queries can leave directions outside their span unidentified. Using a classical anchored interpolation operator, we can recover the Jacobian restricted to the covered subspace, accounting for a curvature-conditioning error that relies on an independently provided local smoothness bound. This analysis yields two-sided sensitivity estimates, finite-scale displacement bounds, and a prediction-invariance condition that accounts for the readout and decision margin. We present a 1D construction that meets the recovery bound for a one-sided endpoint query. This operator analysis leads to Secant-Frame Regularization (SFR), an input-Jacobian-free objective that targets the largest reconstructed logit response. Through experiments, we instantiate the conditional bounds. On the CIFAR-10 dataset, SFR demonstrates improved robustness in evaluated covered transformations compared to matched-query pairwise consistency. Our findings link finite-representation observations to a defined local stability analysis and distinguish conditional certification from empirical regularization.

Primary area:
learning theory
Keywords:
local representation stability, finite-query identifiability, secant frames, subspace robustness certification, Jacobian approximation, operator-norm regularization

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_26NfOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies what finite representation observations can establish about local stability, identifying the limitations of static activations and incomplete perturbation coverage. It derives sensitivity bounds and prediction-invariance conditions on covered subspaces under independently established smoothness bounds, and proposes Secant-Frame Regularization (SFR) to penalize the largest reconstructed logit response without explicitly computing input Jacobians. Experiments demonstrate conditional certification on controlled functions and trained smooth models, while CIFAR-10 experiments show improved robustness to selected transformations compared with matched-query pairwise consistency.

Critical strengths
  1. The analysis clearly identifies what finite observations can and cannot certify, providing a rigorous framework connecting perturbation coverage, smoothness, and prediction margins to local stability.
  2. SFR improves evaluated transformation robustness over matched-query pairwise consistency across all five seeds, achieving a 2.46-point average gain with a 0.30-point clean-accuracy decrease and demonstrating practical value.
Critical weaknesses
  1. The certificates require independently established curvature bounds, and their application to trained networks is demonstrated only on shallow smooth models in PCA coordinates, limiting the demonstrated practical scope of the theoretical guarantees.
  2. Using the same regularization weight for SFR and pairwise consistency does not account for their different penalty scales, leaving it unclear whether the reported advantage persists after independently tuning both methods.
Questions for authors
  1. How costly and conservative are the required curvature bounds, and how does this requirement limit the applicability of the certificates beyond the shallow smooth models evaluated?
  2. Were the regularization weights tuned independently for SFR and pairwise consistency, and does SFR retain its robustness advantage when both methods achieve comparable clean accuracy?
4 comments
AuthorsOpenReview ↗

Rebuttal - W1W2

Thank you for recognizing the rigor of the finite-observation analysis and the consistent improvement in robustness across all five seeds. We also appreciate the concerns about practical certification and the strength of regularization. To clarify the relationship between our contributions: finite perturbation queries reveal a restricted response operator; an independently justified smoothness bound controls the uncertainty between these queries; and a prediction margin turns the resulting displacement bound into a conditional certificate. The SFR approach directly regularizes the empirical response operator and can be trained without a curvature bound.

1. Weakness 1

The trained-model experiment has a specific purpose: to instantiate the complete certification argument on learned classifiers while making its assumptions verifiable. Theorem 4.3 and Corollary 4.5 apply whenever the stated coverage, smoothness, and readout conditions hold. Their statements do not impose a one-hidden-layer architecture or PCA representation. The independently supplied bound is the information that allows finite secants to support a neighborhood-wide guarantee. Making this requirement explicit is central to the paper’s account of what finite observations can establish.

Experiment 7 demonstrates that this conditional result can be instantiated on trained models and real data. Appendix E.8 evaluates certificates on all official MNIST test examples, with PCA and standardization fitted on the optimization-training split. The experiments include coordinate dimensions 8, 16, and 32. These coordinates define the declared perturbation domain and provide complete directional coverage, and the guarantees hold within that domain. The analytic weight-based curvature bound and the resulting positive certified radii provide a concrete test of the full argument.

The CIFAR-10/ResNet-18 experiment addresses the complementary question of whether the finite-query objective helps train a standard image classifier. It evaluates SFR empirically without requiring a curvature bound. Thus, the practical scope demonstrated for formal certification and the scope demonstrated for empirical regularization are different and identified. The scope of the trained certificate experiment does not restrict where SFR can be evaluated as a regularizer. We give the bound’s cost and measured conservatism.

2. Weakness 2

The existing comparison establishes a consistent benefit under a controlled, specified training protocol. Pairwise consistency and SFR share the architecture, data splits, optimizer schedule, perturbation setup, forward-query budget, and validation-based checkpoint-selection rule. Under that protocol, SFR improves covered joint robust correctness in every seed, with a mean gain of 2.46 percentage points and a mean clean accuracy decrease of 0.304 points (Tables 18-22). This supports the practical value of the proposed objective at the reported operating points.

You are correct that a shared numerical coefficient does not equalize effective regularization strength. Proposition 4.6 makes the distinction precise. In its orthonormal-frame setting, let A=J^f(x;V)A=\widehat J_f(x;V) denote the reconstructed response operator and let rr be the number of orthonormal directions. With ζ=0\zeta=0, the per-example penalties are Rpair=1r∥A∥F2R_{\mathrm{pair}}=\frac{1}{r}\Vert A\Vert_F^2 and RSF=∥A∥op2R_{\mathrm{SF}}=\Vert A\Vert_{\mathrm{op}}^2. Pairwise consistency penalizes the average squared singular response, and SFR penalizes the largest squared response. Their ratio depends on the singular-value distribution. When multiple singular modes are possible, no single constant rescaling makes the two objectives equivalent across all response operators. This establishes a substantive difference in how they penalize directional sensitivity.

At the same time, that mathematical distinction does not establish that the measured improvement is caused exclusively by spectral emphasis, or that SFR dominates an independently tuned pairwise baseline. The finite-query information limits, conditional guarantees, and distinction between average and worst-direction control remain valid independently of this hyperparameter-comparison limitation.

AuthorsOpenReview ↗

Rebuttal - Q1Q2

3. Question 1

How the reported bound is obtained. For the trained models in experiment 7, Appendix D.8, Lemma D.6 proves a global sufficient bound for the unthresholded Softplus classifier. The bound follows analytically from the activation’s derivative bounds and the trained weights. ''Independently supplied'' means justified separately from the finite secant observations, and it can depend on the learned parameters. Appendix E.8 evaluates this bound in float64 with an upward safety factor. Sampled Jacobian differences serve as diagnostics, rather than as the basis for its neighborhood-wide validity.

Computational cost. Obtaining this particular bound requires two weight-matrix spectral norms and a maximum row norm. Because it is global, it can be computed once for a fixed checkpoint and reused at all test anchors. Secant queries and margins are still evaluated per example. The manuscript does not report separate wall-clock timings for bound acquisition, so we do not claim a measured speed advantage for this step. Its cost is separate from SFR training, which does not use β\beta.

Observed conservatism. Appendix E.8 reports a maximum sampled Jacobian-difference quotient divided by the analytic bound of 0.3240. This measures slack relative to the observed variation, and it does not identify the unknown exact neighborhood-wide curvature constant. The certificate calculation nevertheless yields positive radii (Table 15). These radii are in standardized PCA coefficient-space units. SFR and exact-Jacobian regularization attain the same reported median radius in this experiment. The dependence on conservatism is in Theorem 4.3: a larger valid β\beta increases both the secant-reconstruction error bound and the quadratic displacement correction, which can reduce the certified radius.

Beyond the evaluated architecture. Independent bounds also exist for deeper smooth networks. For instance, [1] derived compositional curvature bounds for smooth sequential and residual networks. Their global bounds offer a route to supplying the required assumption when the map, domain, and norms match. Layer-based estimates can become conservative as depth and layer gains increase, so obtaining a useful radius for a particular deep model remains dependent on the quality of that independent bound. This requirement also explains the separation of our experiments: a ReLU network or transformation pipeline crossing nonsmooth boundaries does not automatically satisfy the smoothness assumption. Accordingly, the CIFAR-10 results support empirical robustness to covered transformations. The formal certificate results are reported for the settings in which the assumptions are established.

4. Question 2

The primary CIFAR-10 protocol in Table 18 specifies λSF=λpair=0.01\lambda_{SF}=\lambda_{pair}=0.01 and ζ=0\zeta=0. The results of this experiment concern these fixed coefficients and do not establish superiority over independently optimized clean-robust trade-off curves. Checkpoint selection is performed on validation data: each regularized method is selected by covered robustness subject to the seed-matched ERM clean accuracy floor, and the final test metrics are reported afterward. This rule controls model selection and incorporates clean accuracy (Table 18).

At the reported operating points, pairwise consistency and SFR achieve 95.5% and 95.2% clean accuracy, respectively, with 82.6% and 85.1% evaluated joint robust correctness (Table 19). The paired robustness gain is 2.46 percentage points, and the paired clean accuracy change is −0.304 points (Table 21). The accuracy and prediction-invariance differences quoted above are in Table 22. All differences are SFR minus pairwise consistency. The covered robustness endpoint uses the evaluation protocol described in Table 18. These show that SFR produces a consistent robustness improvement with a modest clean accuracy trade-off under the documented protocol. The reported experiments do not resolve the outcome after independently tuning both methods to equal clean accuracy. We respectfully argue that this qualification preserves the demonstrated empirical contribution while keeping its scope precise, alongside the paper’s information-theoretic and conditional-certification results.

We appreciate the opportunity to make clarifications and hope our responses address your concerns. Thank you again!

Reference:

[1] Entesari, T., Sharifi, S., & Fazlyab, M. (2024). Compositional curvature bounds for deep neural networks. ICML’24: Proceedings of the 41st International Conference on Machine Learning.

Reviewer_26NfOpenReview ↗

Thank you for the detailed responses and for clarifying the scope and limitations of the results.

Thank you for the detailed responses and for clarifying the scope and limitations of the results. These clarifications have addressed my concerns, and I will raise my rating accordingly.

Dear Reviewer 26Nf,

Thank you again for taking the time to review our paper and for raising the score! If you have any follow-up questions or comments, we would be happy to clarify further.

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

This paper studies what can and cannot be inferred about local representation stability from finitely many activation and perturbation queries. It first proves two information-theoretic limitations: activation values on a finite dataset do not provide a uniform upper bound on local sensitivity, and perturbation queries leave directions outside their span unconstrained. For a queried subspace, the paper constructs an anchored secant operator that estimates the restricted Jacobian and derives two-sided sensitivity bounds and finite-scale displacement bounds under an independently supplied local Jacobian-smoothness bound. It then propagates representation bounds through a Lipschitz readout and a prediction margin to obtain conditional prediction-invariance certificates. Based on the largest reconstructed logit response, the authors propose SFR, an input-Jacobian-free objective that targets worst-direction rather than average queried response. Experiments include synthetic identifiability and recovery audits, analytic and trained-model certificate tests, and CIFAR-10 experiments with ResNet-18. SFR improves covered-transformation robustness over matched-query pairwise consistency, while subspace TRADES remains slightly stronger on the main robust-correctness metric.

Critical strengths
  1. The paper clearly identifies the information limits of finite representation observations. The non-identifiability results for activation-only statistics and under-spanning perturbation queries are conceptually important and prevent overclaiming stability from static embedding geometry or sparse probes.

  2. The theory is carefully connected to an implementable regularizer and audited across multiple settings. The anchored secant operator, conditioning-aware recovery error, readout Lipschitz factor, and prediction margin are combined into an explicit conditional certificate. The synthetic sharpness and recovery experiments, trained-model audits, and CIFAR-10 evaluation make the distinction between certification and empirical regularization concrete.

Critical weaknesses
  1. The certificates depend on independently established smoothness and coverage assumptions that are difficult to verify for general neural networks. Finite queries alone do not establish the required neighborhood-wide Jacobian bound, and the guarantee applies only to the span of the queried directions. Thus, the main certification result may be difficult to instantiate beyond specially structured models or prescribed low-dimensional transformations.

  2. The empirical evidence for SFR is limited and does not establish superiority over stronger robustness objectives. The main learned-model result uses CIFAR-10 with ResNet-18 and covered transformations; SFR improves over pairwise consistency but is slightly worse than subspace TRADES on evaluated joint robust correctness. Broader datasets, architectures, perturbation families, and comparisons would be needed to support claims of general utility.

Questions for authors
  1. How can the independently supplied local smoothness bound be obtained or validated for practical deep networks? Please clarify whether the reported certificates use analytic, data-dependent, or empirically estimated bounds, and quantify how loose the resulting bounds are compared with the actual local Jacobian variation.

  2. How sensitive are the certificates and SFR to query-frame design? Please report controlled experiments varying the number of queries, probe radius, conditioning and redundancy of the frame, and the choice of transformation subspace. It would be useful to compare random frames, orthogonal frames, PCA frames, and transformation-specific frames, while reporting coverage, conditioning error, certified radius, clean accuracy, and robust correctness.

  3. How well does the framework transfer across data modalities, dimensions, resolutions, and architectures? Experiments on additional vision datasets such as CIFAR-100, Tiny-ImageNet, and ImageNet subsets, with multiple input resolutions and ambient dimensions, would help assess scalability. Comparisons among CNNs, ResNets, U-Nets, Vision Transformers, and MLP-style architectures would clarify how architectural inductive bias affects the finite-query information gap and the effectiveness of SFR.

  4. Can the authors provide stronger comparisons with existing robustness regularizers and certification methods? In addition to pairwise consistency and subspace TRADES, comparisons with input-gradient or Jacobian regularization, virtual adversarial training, randomized smoothing, and transformation-specific certification would help determine whether SFR offers a distinct advantage after matching clean accuracy, query budget, and computational cost.

  5. How robust are the conclusions to the choice of representation and output scale? Since SFR is applied to logits and can penalize class-independent logit shifts, please evaluate whether the observed gains persist under logit normalization, temperature scaling, alternative readouts, or direct application to intermediate representations with an explicitly controlled readout.

5 comments
AuthorsOpenReview ↗

Rebuttal - W1W2

Thank you for the careful evaluation and for recognizing the importance of the finite-observation information limits and the connection between the theory, conditional certificates, and an implementable regularizer. The central contribution is to characterize the local stability information supported by finite observations and to translate that characterization into a learning objective. This paper makes a specific empirical claim: SFR improves evaluated covered-transformation robustness over matched-query pairwise consistency. We address each concern below.

1. Weakness 1

We agree that establishing a valid neighborhood-wide smoothness bound is the principal practical requirement for deterministic certification. The paper makes that requirement in Assumption 3.6, Theorem 4.3, and Corollary 4.5. Its contribution is to determine what finite observations establish once this independent information is available, including accounting for the directions and scales for which the conclusion holds.

Coverage and smoothness have different verification requirements. For a prescribed subspace EE and probes lying in EE, coverage is checked directly by rank⁡(V)=dim⁡(E)\operatorname{rank}(V)=\operatorname{dim}(E). Conditioning is inspected through the singular values. Proposition 4.2 shows why the coverage restriction is necessary: an affine modification can preserve all queried responses and the same Jacobian-variation bound while introducing arbitrarily large sensitivity in an omitted direction. Therefore, restricting the certificate to the covered span reflects the information available from the queries.

The certificates also have a trained-model instantiation. Experiment 7 uses MNIST Softplus classifiers with an analytically established curvature bound derived from the learned weights (Appendices D.8 and E.8). On PCA-16, SFR attains a median certified radius of 0.336 in standardized coefficient units, compared with 0.253 for pairwise consistency and 0.231 for ERM (Table 15). Finally, the introduction and Section 4.4 separate certification from regularization. SFR can be trained using finite evaluations and ordinary parameter backpropagation without obtaining a certified smoothness constant. The CIFAR-10 ReLU experiments evaluate this empirical use, and we do not claim smoothness-based certificates for that pipeline. Thus, this paper instantiates both conditional certification and empirical regularization.

2. Weakness 2

Our primary comparison tests the mechanism established in Proposition 4.6: whether controlling the largest reconstructed response is useful relative to averaging squared responses from matched queries. Therefore, pairwise consistency is a direct mechanistic comparator, and subspace TRADES provides a stronger adversarial-training reference. Tables 2 and 19-22 report that SFR improves evaluated joint robust correctness by 2.46 percentage points over pairwise consistency and prediction invariance by 2.85 points. All five paired seeds favor SFR on both metrics. The clean accuracy difference is −0.304 points. These are decision-based improvements in addition to reductions in the raw sensitivity diagnostics.

We also report that subspace TRADES achieves higher joint robust correctness: 85.8% vs. 85.1% for SFR, with a paired SFR-minus-TRADES difference of −0.734 points. This result is consistent with the theory: robust correctness depends on margins and finite-radius behavior as well as operator gain. A smaller raw gain does not necessarily indicate higher robust accuracy, and this paper does not claim such a connection.

The evidence extends beyond this primary table: Experiment 7 compares SFR with exact-Jacobian regularization on trained MNIST models, and Experiment 9 studies diagnostics across ResNet-18 and CompactViT checkpoints. These studies support complementary aspects of the framework. Broader benchmarks would establish broader empirical generality, and the present results support the specific claims made in the abstract, Section 5, and the conclusion.

AuthorsOpenReview ↗

Rebuttal - Q1Q2

3. Question 1

The constants used for the reported certificates are analytic. Their validity is not inferred from sampled Jacobian differences. Analytic experiments. For the quadratic map used in experiments 3 and 6, Appendix D.8, Lemma D.4 gives the exact global constant β⋆=∥b∥2,∥Q+Q⊤2∥op\beta^{\star}=\Vert b\Vert_2\\,\left\Vert\frac{Q+Q^{\top}}{2}\right\Vert_{\mathrm{op}}. With the symmetric matrices used in those experiments, this becomes ∥b∥2,∥Q∥op\Vert b\Vert_2\\,\Vert Q\Vert_{\mathrm{op}}. Lemma D.5 gives the exact global readout constant Lg=max⁡c∥Wc,:∥2L_g=\max_c\Vert W_{c,:}\Vert_2 for g(z)=Wz+cg(z)=Wz+c. An exact global constant can still be conservative for a particular restricted subspace.

Trained neural certificates. For the unthresholded Softplus logit map f(a)=W2sτ(W1a+b1)+b2f(a)=W_2s_{\tau}(W_1a+b_1)+b_2, where sτ(t)=τ−1log⁡(1+eτt)s_\tau(t)=\tau^{-1}\log(1+e^{\tau t}), Lemma D.6 proves βˉf=τ4∥W2∥op∥W1∥op∥W1∥2→∞\bar{\beta}_f=\frac{\tau}{4}\Vert W_2\Vert_{\mathrm{op}}\Vert W_1\Vert_{\mathrm{op}}\Vert W_1\Vert_{2\to\infty}. This bound is globally valid for the specified smooth model and is calculated from its learned weights. It is model-dependent analytic information, rather than a curvature estimate fitted from input samples. Appendix E.8 documents float64 evaluation with an upward safety factor and strict radius rechecks. PCA and standardization are fitted on the training split, and the probe scale is selected on validation data. The certificates concern the standardized PCA coefficient space.

Measured conservatism. Appendix E.8 presents a maximum sampled Jacobian-difference quotient divided by its analytic bound, which is 0.3240. This value quantifies the slack against observed variation. However, it does not represent the tightness ratio to the unknown neighborhood-wide supremum. Table 15 reports the analytic bounds as follows: 5.770 for ERM, 5.158 for pairwise consistency, 4.115 for exact-Jacobian regularization, and 4.112 for SFR. The corresponding median certified radii are 0.231, 0.253, 0.336, and 0.336, respectively. These sufficient bounds provide meaningful certificates for trained models, despite their conservative nature. Additionally, Table 17 indicates that no certificate violations were observed during the attack audit. The guarantee derives from the analytic bound and the sufficient inequality.

For deeper continuously differentiable networks, compositional curvature bounds provide an established route to supplying this independent information [1], as discussed in Appendix B.5. For example, βF∘ϕ≤βFLϕ2+LFβϕ\beta_{F\circ\phi}\le\beta_F L_\phi^2+L_F\beta_\phi when the constituent Jacobian norm and curvature bounds are valid throughout the relevant domains. Therefore, we must also include transformation and preprocessing regularity. This is a possible source of bounds for further instantiations, not a procedure we claim to have applied to the CIFAR-10 ReLU models.

4. Question 2

This paper already includes controlled experiments for the principal quantities in the recovery bound. Experiment 3 evaluates 24192 valid frame settings (see Appendix E.4 and Tables 6-7; page 33 – Implementation). The experiment records no recovery-bound violations or two-sided interval misses beyond numerical tolerance. Experiment 2 separately compares orthonormal, redundant tight, and duplicated imbalanced frames, including a positive control in which the missing direction is appended. Experiment 4 compares one-sided and symmetric probes and shows that the latter recover the derivative exactly, up to numerical precision, for the particular quadratic construction studied.

The theory explains these sensitivities through ηβ(V)=β2σmin⁡+(V)(∑j∥vj∥24)1/2\eta_{\beta}(V)=\frac{\beta}{2\sigma_{\min}^{+}(V)}\left(\sum_j\Vert v_j\Vert_2^{4}\right)^{1/2}. For V=hUV=hU with rr orthonormal columns, this reduces to ηβ(hU)=βhr2\eta_\beta(hU)=\frac{\beta h\sqrt r}{2}. With exact evaluations, smaller probes reduce the curvature allowance, while poor conditioning can amplify reconstruction error. Noise and finite precision introduce a separate small-probe trade-off, as noted in Section 4.2. Coverage is a separate issue: duplicating existing directions cannot reveal an omitted direction. More queries do not automatically improve this deterministic allowance, and equal-length tight redundant frames have the same expression βhr/2\beta h\sqrt r/2.

The real-data study also reports clean accuracy, recovery uncertainty, certified radius, and certified correctness at PCA ranks 8, 16, and 32 (Table 16). SFR’s median certified radii are 0.255, 0.336, and 0.422, compared with 0.175, 0.231, and 0.281 for ERM. This is a study of different PCA-coordinate models. Random, orthogonal, PCA-derived, and transformation-specific designs should also be distinguished according to whether they span the same EE.

AuthorsOpenReview ↗

Rebuttal - Q3Q4

5. Question 3

The mathematical framework applies to maps between any finite-dimensional Euclidean spaces that meet the specified assumptions. The concept of architecture is important because it relates to the map's sensitivity, curvature, and evaluation cost. The statements regarding non-identifiability apply to the specified function classes, and they do not claim that every counterexample can be realized within every given architecture.

This paper includes complementary aspects that present a broad range of empirical evidence:

  • The recovery audit varies input dimensions 8, 32, and 128, output dimensions 4, 16, and 64, and frame rank and conditioning independently within valid settings.
  • Experiment 7 trains MLP-style Softplus classifiers on MNIST in PCA-coordinate dimensions 8, 16, and 32 and reports certificates and predictive performance.
  • Experiment 8 gives the primary five-seed CIFAR-10 ResNet-18 comparison.
  • Experiment 9 includes both ResNet-18 and CompactViT, with 266 eligible checkpoints from 50 training runs, including 40 primary architecture–method–seed runs (Appendix E.10; Table 23). Its pooled results are observational diagnostic evidence.

There is also a precise computational distinction between ambient dimension and the dimension of the claimed perturbations. If a rank-rr frame is factored as V=URV=UR, with UU orthonormal, then ∥YV†∥op=∥YR†∥op\Vert YV^{\dagger}\Vert_{\mathrm{op}}=\Vert YR^{\dagger}\Vert_{\mathrm{op}}. For logit outputs, the right-hand side is the norm of a C×rC\times r matrix. This permits operator evaluation without constructing a dense input Jacobian. It does not remove the cost of network evaluations, which grows with architecture and resolution, or the requirement for at least rr independent directions to cover an rr-dimensional space. In transformation coordinates, rr can remain fixed as image resolution increases, although curvature and computational costs may change.

CIFAR-100, Tiny-ImageNet, subsets of ImageNet, and comparisons involving controlled resolution or U-Nets evaluate broader empirical transfer and are not included in the current evidence. The results presented in this paper support the corresponding information and recovery statements, as well as their demonstrated training applications.

6. Question 4

This paper already includes exact-Jacobian regularization in two settings: the learned stress test in experiment 5 (Table 12) and the trained MNIST certificate study in experiment 7 (Table 15). The results show that the finite-query objective can closely match the behavior of the direct derivative-based reference in that setting. For CIFAR-10, Table 18 specifies the shared architecture, training schedule, seed-specific splits, transformation domain, and evaluation protocol. Pairwise consistency and SFR each use 7 conceptual forward queries per example, and the protocol reports a common target of 12 effective conceptual forwards. Checkpoint selection uses validation-covered robustness subject to a seed-matched ERM clean-accuracy floor. Evaluation includes 50 attack steps, 10 restarts, cross-entropy, margin, and DLR losses, and 3 step-size multipliers. These controls support the targeted comparison.

The other proposed comparisons are relevant, and their relationship to the contribution is discussed in Appendices B.4-B.9:

  • Input-gradient and Jacobian penalties control derivatives directly. SFR reconstructs a restricted vector-valued operator from finite evaluations and exposes its coverage and conditioning. Input-Jacobian-free training still uses ordinary parameter gradients; we do not claim a measured runtime advantage over all derivative-based implementations.
  • VAT and TRADES already pursue local adversarial robustness of predictive distributions [2,3]. SFR’s distinction is its specified secant operator and spectral aggregation, with an explicit recovery analysis. Worst-direction regularization by itself is not claimed as new.
  • Randomized smoothing and transformation-specific smoothing, such as TSS, certify smoothed decision rules and address their own perturbation and sampling models [4,5]. Our sufficient condition concerns the specified original map on its covered subspace, supplied with a valid smoothness bound.
Reviewer_hoRTOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper investigates how finite perturbation queries can provide certificates of local representation stability beyond static embeddings. It introduces an anchored interpolation operator to estimate local sensitivity within the queried subspace and derives associated error bounds and prediction-invariance conditions. Building on this analysis, it proposes Secant-Frame Regularization (SFR), which penalizes large logit responses without explicitly computing input Jacobians. The theoretical results are validated through numerical experiments, while CIFAR-10 experiments show that SFR improves robustness and prediction invariance over pairwise consistency, though it slightly underperforms Subspace TRADES on these metrics.

Critical strengths
  1. The paper provides a useful theoretical perspective on the limitations of static embeddings for characterizing local representation stability, explicitly clarifying what can be inferred from finite perturbation queries and what remains unobserved outside the queried subspace.

  2. The proposed framework establishes formal bounds on local sensitivity and prediction invariance, offering a principled connection between finite-query observations and representation stability.

Critical weaknesses
  1. I really appreciate the rigorous theoretical setup, particularly Theorem 4.3. However, a practical limitation arises because ensuring tight recovery requires the query frame to fully cover the target subspace (EV=EE_V = E). For standard ambient image spaces where dd is massive, requiring dd independent queries becomes computationally prohibitive. The authors elegantly sidestep this by evaluating on low-dimensional charts (like PCA spaces or 5D transformations), but it would be helpful to clarify more explicitly in the text that this is currently a transformation-specific tool rather than a general local robustness certificate for raw pixel spaces

  2. The theoretical pipeline relies heavily on an externally provided local smoothness constant β\beta via Assumption 3.6. While mathematically sound, deriving a tight, non-vacuous β\beta for standard deep non-convex networks (especially those with ReLU activations) is known to be highly challenging. The use of a single-hidden-layer Softplus network in Experiment 7 to compute an analytic bound is a nice proof-of-concept, but it leaves me wondering how this framework scales to realistic architectures like ResNet. Discussing this gap more explicitly would manage practical expectations better.

  3. The motivation for Secant-Frame Regularization (SFR) via operator-norm control is theoretically elegant (Proposition 4.6). However, looking at the CIFAR-10 results (Table 2), SFR achieves an 85.1% robust accuracy, which is slightly behind the Subspace TRADES baseline (85.8%). Since SFR is proposed as a novel regularizer, its practical adoption would be much more compelling if it could either consistently match SOTA baselines or offer a distinct computational advantage. Adding more context on why a practitioner might choose SFR over TRADES despite the slight performance drop would strengthen the empirical section.

  4. Definition 4.7 applies the SFR penalty directly to the raw, unnormalized logits. One potential issue here is that uniform shifts across all class logits (which do not change the softmax distribution or the final classification decision) will inflate the operator norm and be penalized by SFR. I suspect this might lead to unnecessary over-regularization, potentially hurting clean accuracy. Has the team considered applying the penalty to margin differences (e.g., fc−fc∗f_c - f_{c^*}) instead? A brief discussion or an ablation on this design choice would be very insightful.

Questions for authors
  1. First, exact recovery in Theorem 4.3 requires full subspace coverage (EV=EE_V = E). Could the authors clarify the computational roadmap for scaling this certificate beyond low-dimensional charts (like 5D transformations or PCA)? How severe is the computational bottleneck of requiring q≥dim⁡(E)q \ge \dim(E) queries in high-dimensional ambient spaces?

  2. Also, the theoretical guarantees depend heavily on the local smoothness constant β\beta (Assumption 3.6). Are there tractable methods to estimate a non-vacuous β\beta for standard deep networks with non-smooth activations (e.g., the ResNet-18 used in Exp 8)? Does this imply the formal certificate is currently restricted to shallow or smooth models?

  3. Meanwhile, in Table 2, Subspace TRADES slightly outperforms SFR on covered joint robust correctness (85.8% vs. 85.1%). To help me assess its practical impact, could you elaborate on the core advantages of SFR over TRADES? For example, does SFR offer significant reductions in wall-clock training time or memory footprint that justify the slight performance drop?

  4. Lastly, the SFR penalty targets raw logits (Definition 4.7), which might over-regularize decision-invariant uniform logit shifts. Is this choice strictly necessary for the proofs, or could applying the penalty to margin differences (e.g., fc−fc∗f_c - f_{c^*}) be a viable variant? Understanding your design rationale would be very helpful (no new experiments expected).

4 comments
AuthorsOpenReview ↗

Rebuttal - W1Q1W2Q2

Thank you for your careful review and for acknowledging the value of our information-theoretic approach and sensitivity bounds. We appreciate the chance to clarify our guarantees and the role of SFR. Our contribution includes a characterization of finite observations, conditional stability guarantees for perturbation spaces, and an empirical regularizer based on this analysis. We address your 4 concerns below.

1. Weakness 1 and Question 1

The coverage requirement is central to this paper. Proposition 4.2 demonstrates that a large affine response can be added in an unqueried direction while maintaining observed values and the same Jacobian-smoothness bound. Therefore, within the observation model and function class, few probes cannot create an unrestricted deterministic pixel-space certificate. This issue also arises with affine maps of zero curvature. Specifying the covered perturbation space ensures meaningful guarantees and prevents unsupported extrapolation from sparse observations.

We would also like to clarify the recovery statement. Theorem 4.3 gives an error-bounded estimate of the Jacobian restricted to the observed span: ∥J^F(x;V)−JF(x)PEV∥op≤ηβ(V)\Vert \widehat{J}_F(x;V)-J_F(x)P_{E_V} \Vert_{\mathrm{op}} \leq \eta_{\beta}(V). It applies to EVE_V even when that span is smaller than a prescribed target EE. Full coverage is required to make the claim over all of EE. Moreover, full coverage alone does not imply exact recovery at a finite probe scale: the curvature-conditioning term remains, and Proposition 4.4 demonstrates an attained 1D error. These distinctions are stated after Proposition 4.2 and Theorem 4.3 (page 5). The operator norm can be computed from the output-by-query secant matrix without materializing the ambient input Jacobian. Batching and small matrix factorizations can reduce implementation overhead, but they cannot remove the coverage requirement.

The roadmap is to define a relevant perturbation space, use a well-conditioned covering frame, and expand claims only when additional structure or an independently justified bound addresses unobserved directions. Our framework is subspace-specific and does not rely on low-dimensional observations to validate remaining pixel directions. Computational limitations are discussed in Section 6 and Appendix F.

2. Weakness 2 and Question 2

The formal certificate is conditional on a valid neighborhood-wide smoothness bound, and the experiments respect that condition. Assumption 3.6 treats this bound as independently supplied. The text following Theorem 4.3 also distinguishes a certified bound from curvature estimates obtained by sampling (pages 5-6). A maximum observed Jacobian-difference quotient would be a diagnostic, not a justified upper bound over the entire neighborhood.

The theorem has no restrictions on network depth. For smooth deep models, derivative bounds can be propagated through compositions. The challenge is obtaining constants sufficiently tight to yield useful radii. For example, if H=G∘FH = G \circ F, the relevant Jacobian norms are bounded by LFL_F, LGL_G, and the Jacobians have Lipschitz constants βF\beta_F, βG\beta_G on a convex input neighborhood and its image, respectively. The chain rule gives βH≤LGβF+βGLF2\beta_H \leq L_G \beta_F + \beta_G L^2_F. This provides a route to valid bounds at greater depth, while also showing why naive composition may be conservative. We do not claim that such bounds are automatically non-vacuous for an arbitrary trained architecture.

For ReLU networks, neighborhoods that cross genuine Jacobian discontinuities typically do not meet Assumption 3.6, since almost-everywhere differentiability does not satisfy the condition. A neighborhood confined to a single activation region is affine with zero curvature in raw-input coordinates, proving that such a region requires verification. The complete composite also needs to consider transformation and preprocessing in transformation coordinates, as nonlinear charts may not exhibit zero curvature even when the network branch is affine, as stated in Assumption 3.6.

This highlights the differing roles of Experiments 7 and 8. Experiment 7 uses a trained Softplus classifier, allowing for an analytical establishment of premises. Appendix D.8 derives the curvature bound, and Table 15 shows the median certified radius. Experiment 8 evaluates SFR on ReLU ResNet-18 as an empirical regularizer without requiring a certified smoothness constant. Hence, we do not provide a formal certificate for this experiment. We mention this distinction in the abstract, introduction, experiment descriptions, and limitations. The theory applies beyond shallow networks, but extending certificates across nonsmooth regions requires further analysis. The current experiments uphold both claims under their specified assumptions.

AuthorsOpenReview ↗

Rebuttal - W3Q3W4Q4

3. Weakness 3 and Question 3

Thank you for this question and comment. We agree with your reading of Table 2. The central experimental question for SFR follows directly from Proposition 4.6: does controlling the largest reconstructed response help compared with averaging fixed-frame pairwise responses under matched queries? Experiment 8 supports this hypothesis. Relative to pairwise consistency, SFR improves covered joint robust correctness and prediction invariance. This tests the specific distinction the theory establishes.

Other existing experiments also show a practical tradeoff with Subspace TRADES. Table 19 reports 85.1% CIFAR-C mean accuracy for SFR vs. 79.1% for Subspace TRADES, across the evaluated 15 corruptions and severities 1-5. This is a secondary corruption-transfer endpoint and supports a different empirical ranking from the primary covered-attack endpoint. A practitioner prioritizing the latter would prefer TRADES in this comparison. One also concerned with corruption transfer has evidence favoring SFR. We do not infer universal superiority from either endpoint. SFR also achieves lower measured secant operator norm and empirical finite-radius worst gain, consistent with its sensitivity-control objective (Tables 2 and 20). As the paper explains, these raw-logit quantities must be interpreted alongside margins and logit scale, and their reduction alone does not imply higher classification robustness.

Regarding computation, SFR uses a fixed query frame and ordinary parameter backpropagation, without adversarial inner maximization. We do not claim a measured wall-clock or memory advantage: those quantities are not benchmarked in the current submission. The supported reasons to consider SFR are direct finite-query operator control, consistent improvements over the matched pairwise baseline, and the observed robustness-transfer tradeoff. The existing results substantiate those reasons without requiring an efficiency claim.

4. Weakness 4 and Question 4

The current choice controls the full reconstructed logit response and gives a sufficient route to prediction stability. Its rationale is to anchor the objective at the predictor, avoiding ambiguity from rescaling an intermediate representation and inversely rescaling its readout (Section 4.4). Recovery theory does not require raw logits, and margin-based variants are compatible with it. An input-independent common offset cancels in the anchored differences f(x+vj)−f(x)f(x+v_j)-f(x). An input-dependent common shift a(x)1a(x)\mathbf{1} can affect the penalty while preserving probabilities and decisions. Our paper acknowledges this in Section 4.4. This reflects the conservativeness of the chosen regularization target and does not invalidate the recovery bound or the sufficient prediction condition.

A shift-invariant formulation follows by centering the logits: P=IC−1C11⊤P=I_C-\frac{1}{C}\mathbf 1\mathbf 1^\top, S~θ(x;V)=∥P,Yfθ(x;V)V†∥op\widetilde{S}_{\theta}(x;V)=\left\Vert P\\,Y_{f_{\theta}}(x;V)V^{\dagger}\right\Vert_{\mathrm{op}}. Centering preserves every pairwise class margin, softmax probability, and prediction. Since PP is a fixed orthogonal projection, S~θ≤S^θ\widetilde S_{\theta} \leq \widehat S_{\theta}, and any valid smoothness bound for fθf_{\theta} also bounds PfθPf_{\theta}. Therefore, Theorem 4.3 and the prediction stability argument apply to the centered map under the same coverage and regularity conditions. This construction needs no additional model queries.

Margin differences are also viable. Fixing the anchor’s winning class yy, one can apply the framework to (fy−fj)j≠y(f_y-f_j)_{j \neq y}, with the corresponding output norm and smoothness constant. In fact, if DD contains all unordered class-difference rows, then D⊤D=CPD^\top D=CP. Hence, for A=YfV†A=Y_fV^\dagger, ∥DA∥op=C,∥PA∥op\Vert DA\Vert_{\mathrm{op}}=\sqrt{C}\\,\Vert PA\Vert_{\mathrm{op}}. Centered-logit control is equivalent, up to a fixed normalization, to operator control of all pairwise margin responses.

Thank you again, and we hope these clarifications answer your questions and resolve your concerns!

Dear Reviewer hoRT,

We noticed that our response to your review may not have received a follow-up. If you have any questions or need further clarification regarding our response, we would be happy to provide additional information.

Thank you for your time and consideration!

Thank you for the detailed response. The discussion of subspace coverage and the centered-logit formulation addresses my main theoretical questions. The CIFAR-C results also clarify the trade-off between SFR and Subspace TRADES. Obtaining useful certified radii for deep ReLU networks remains a practical limitation. Taking the response into account, I have raised my rating from 2 to 3.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal Summary

We thank the reviewers, the AC, and the PC for their careful reading and constructive feedback. With one day remaining in the rebuttal period, we summarize our contributions and rebuttal below.

  • We establish why directional coverage is necessary. Models can agree on every embedding in a finite dataset but have arbitrarily different local sensitivities. Even for affine maps, identical responses to every perturbation query can conceal arbitrarily large sensitivity in a direction outside the queried span.
  • We derive a finite-radius prediction guarantee on the covered subspace. We bound the error in reconstructing the restricted Jacobian using probe scale, frame conditioning, and an independently justified neighborhood-wide curvature bound. The readout sensitivity and class margin then determine a radius within which the prediction is guaranteed to remain unchanged.
  • We demonstrate certification on a trained model. For MNIST Softplus classifiers, we derive the curvature bound directly from the learned weights. In 16 standardized PCA coordinates, Secant-Frame Regularization (SFR) matched exact-Jacobian regularization at a median certified radius of 0.336, compared with 0.253 for pairwise consistency (Table 15).
  • We introduce SFR to control the largest reconstructed logit response. SFR captures sensitive combinations of probe directions that pairwise averaging can obscure. Training requires neither an input Jacobian nor a certified curvature bound. In the rebuttal, we also showed how centering logits removes decision-irrelevant common shifts while preserving every class margin, with no extra queries.
  • We quantify the empirical trade-off on CIFAR-10/ResNet-18. With matched queries and a shared regularization weight, SFR improved robust correctness under the tested transformations over pairwise consistency in all five seeds. The mean gain was 2.46 percentage points, with a 0.30-point decrease in clean accuracy. Subspace TRADES led on this robustness measure (85.8% vs. 85.1%), while SFR led on mean CIFAR-10-C corruption accuracy (85.1% vs. 79.1%). Whether the pairwise comparison holds after independently tuning both methods remains open (Tables 19–21).

We believe this paper deserves publication because it identifies the conditions under which finite perturbation queries can certify local prediction stability within their span. Moreover, it turns this analysis into a regularizer that improves robustness to the tested transformations, outperforming matched-query pairwise consistency.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.