PaperlayerView exact revision on arXiv

Source-linked AI summary

The Signed Geometry of One-Shot Recourse: On-Path Validity and the Signed-Curvature Criterion

Hazar Yueksel

arXiv:2609.36252v2cs.LGstat.ML

TL;DR

The paper asks when a one-shot gradient recourse step reaches the favorable side and what limited extra model queries can guarantee. It analyzes signed path curvature and query-limited corrections, finding a strong association between curvature sign and endpoint validity across shallow models, while identifying settings where the criterion or training gains remain limited.

  • Problem

    A one-shot gradient step reaches zero only in the linearized score, leaving open when it actually reaches the favorable side and what query-limited rules can ensure recourse.

    Source: §1 · p. 1

  • Method

    The paper analyzes recourse along the fixed gradient ray and studies curvature-based corrections, one-query rules, conformal calibration, training penalties, and ray line search.

    Source: §1 · pp. 1–2

  • Results

    Across 80 models, endpoint validity and P(κ ≥0) correlate at r = 0.985, while their mean absolute difference on F-MNIST is 8.2 points.

    Source: §10 · p. 7

  • Takeaways & Limitations

    When per-user search is affordable, ray line search is valid by construction and is the paper's preferred choice, despite costing 189 forward evaluations per user in its implementation.

    Source: §11 · p. 8

    The signed-curvature criterion is not established for deep networks, and the CIFAR-10 gains are not attributed to curvature sign because it was untested there.

    Source: §11 · p. 8

Abstract

from arXiv · show

Closed-form recourse moves a rejected user along the unit gradient $\hat g$ of the classifier score $f$ by the promised distance $d_p=|f(x)|/\|\nabla f(x)\|$, at which the linearized score reaches zero. We ask when this one-shot step succeeds and what additional model queries change. To leading order the step ends on the favorable side exactly when the path curvature $\kappa=\hat g^\top\nabla^2 f(x)\,\hat g$ is nonnegative. Across 80 shallow models, the fraction of rejected users whose step ends there and the fraction with $\kappa\ge0$ correlate at $r=0.985$, although on Fashion-MNIST the first falls below the second by 8.2 points on average. No rule that uses only the score value and gradient can be valid for every score with path curvature bounded by $K$ without overshooting some by order $Kd_p^2/\|\nabla f(x)\|$. When the curvature is also Lipschitz and the step is short, one evaluation of $f$ at the promised point attains the minimax rate among deterministic one-query rules that know the curvature bound and its Lipschitz constant, and split-conformal calibration makes such a rule reach the first crossing or abstain with probability at least $1-\delta$. Training with an asymmetric curvature penalty lets 99-100% of paths cross within the promised step on undershoot-prone shallow data, at about 4-22 times the overshoot of symmetric penalties (Fashion-MNIST, COMPAS). Because $\kappa$ and $d_p$ depend on how the score is scaled, part of this gain can be a longer promised step, and at matched validity a smaller audit of briefly trained models finds no uniform advantage over tuned inflation. Where a per-user line search along the ray is affordable, it is exact to grid resolution and preferable.

1 Introduction

The paper studies when a one-shot gradient recommendation succeeds and how limited model queries can improve it. Its analysis connects success to signed path curvature and compares rules that trade query cost against failed recourse and overshoot.

1 Introduction

  • The one-shot step can undershoot and leave a rejected user rejected, or overshoot and demand more change than necessary.It moves along the score gradient by the distance at which the linearized score reaches zero.Source: §1 · p. 1
  • The paper fixes the closed-form step's path to compare curvature penalties, step inflation, calibrated corrections, and ray line search under limited query budgets.For iterative generators that re-linearize, the results describe single steps only.Source: §1 · p. 1
  • To leading order, the step succeeds exactly when path curvature is nonnegative, while score-and-gradient-only rules cannot guarantee validity economically across bounded-curvature scores.With Lipschitz curvature and a short step, one extra function value at the promised point attains the minimax rate among deterministic one-query rules; split-conformal calibration gives first-crossing coverage or abstention.Source: §1 · pp. 1–2
  • The signed-curvature analysis differs from nearest-boundary robustness: recourse asks whether the prescribed step crosses along its chosen direction, which depends on curvature's sign.Related work also connects the one-query forward probe to Ostrowski's two-step method and frames its guarantee as a finite-scale, one-sided counterpart.Source: §1 · p. 2

2 On-Path Recourse

The section distinguishes success along the prescribed gradient ray from proximity to any decision boundary. It also explains that score rescaling can change the promised distance and curvature without changing the boundary or ray crossing.

2 On-Path Recourse

  • The promised distance d_p, first-crossing distance d_ray, and nearest-boundary distance d⋆ describe different aspects of recourse geometry.The nearest-boundary distance is no greater than the first-crossing distance along the chosen ray.Source: §2 · p. 2
  • Endpoint validity means the recommended point is favorable, while a ray hit means the first boundary crossing occurs within the recommended length.Endpoint validity implies a hit by continuity, but not conversely if the path crosses and then becomes unfavorable again.Source: §2 · p. 2
  • Unless an action set is specified, the gradient rays are continuous feature-space relaxations rather than implementable or causal actions.For a convex cone of feasible directions, specified results transfer up to the first binding constraint when a feasible ascent direction exists.Source: §2 · p. 2
  • A strictly increasing score rescaling that preserves the decision boundary can change the promised distance and curvature while leaving the first crossing fixed.The paper therefore treats its results as properties of the deployed score, not the boundary alone.Source: §2 · p. 3

3 Nearest-Boundary Distance as a Diagnostic

Nearest-boundary distance is used only as a diagnostic because it does not establish that the prescribed gradient step succeeds.

3 Nearest-Boundary Distance as a Diagnostic

  • Because d⋆≤d_ray, a small nearest-boundary distance cannot show that the recommended step crosses along its ray.The paper therefore does not use d⋆ for validity or first-crossing measurements.Source: §3 · p. 3
  • An unrefined DeepFool iterate moves by the alpha-1 step itself, making it unsuitable as an independent estimate of the quantity being audited.The paper instead estimates d⋆ with a Carlini–Wagner-style objective that does not use d_p.Source: §3 · p. 3
  • The nearest-boundary estimate is kept separate from the paper's ray-based validity and first-crossing quantities.This avoids using d⋆ as evidence for whether the prescribed step succeeds.Source: §3 · p. 3

4 Curvature Bounds the Nearest-Boundary Gap

The section bounds the nearest-boundary gap under local smoothness and gradient-flow assumptions, but that bound does not use curvature's sign.

4 Curvature Bounds the Nearest-Boundary Gap

  • The bound assumes a neighborhood containing both the alpha-1 endpoint and a closest boundary point, where the score is C2 and its gradient norm stays above γ.It also assumes a normalized gradient flow from the endpoint exists in that neighborhood for the specified interval.Source: §4 · p. 3
  • A bounded Hessian on the neighborhood is sufficient for the stated smoothness hypothesis, but the required gradient-flow reachability assumption is strong.The flow must reach the boundary from the endpoint while the gradient remains bounded away from zero.Source: §4 · p. 3
  • The nearest-boundary gap bound is blind to the sign of curvature, unlike the paper's on-path success criterion.The cited curvature bounds concern distance to the boundary rather than crossing within the prescribed step along one direction.Source: §4 · p. 3

5 The Signed-Curvature Criterion

The signed-curvature criterion links one-shot endpoint validity to the sign of curvature along the fixed ray, with a narrow remainder band left undecided. Under short-step conditions, the crossing error is asymmetric: concave paths can undershoot substantially, while convex paths are bounded by the remainder.

Endpoint identity

  • The endpoint Taylor identity yields the curvature thresholds by canceling the linear term at the promised distance.The threshold result assumes a Lipschitz constant M for the ray profile’s second derivative over [0, dp].Source: §5 · p. 3

Signed-curvature criterion

  • Alpha-1 is valid when κ > Mdp/3 and invalid when κ < −Mdp/3; only the band |κ| ≤ Mdp/3 is undetermined.Across rejected points, validity matches P(κ ≥ 0) up to the probability mass in that band.Source: §5 · p. 3

Quadratic model and conditions

  • If the Hessian is constant along the ray, the quadratic model’s first positive root equals the ray crossing distance.The theorem’s hypotheses require a Lipschitz second derivative and a step short relative to curvature scales.Source: §5 · pp. 3–4

Finite-scale error bound

  • Under the short-step regime, a concave path has undershoot at least |κ|dp^2/(2a) − 8Mdp^3/(3a), while a convex path’s undershoot is at most 8Mdp^3/(3a).Thus the leading error on concave paths is of order |κ|dp^2/a when the remainder is small.Source: §5 · pp. 3–4

6 The First-Order Barrier

With only the score and gradient at the user’s point, opposite-curvature paths can share the same inputs but have crossings on opposite sides of the promised distance. The section shows what one additional function query can guarantee under curvature regularity assumptions.

First-order barrier

  • Every first-order rule must either be invalid on the concave profile or overshoot the convex profile by at least the theorem’s gap.The two profiles share the starting value and gradient but bend in opposite directions along the ray.Source: §6 · p. 4

One forward query

  • A forward probe estimates κ with error at most Mdp/3 and supports a quadratic crossing estimate under the stated hypotheses.Adding the stated margin gives deterministic first-crossing validity when M is known.Source: §6 · p. 4

One-query minimax rate

  • The endpoint probe with an explicit margin attains the Θ(MK0dp^4/a^2) minimax error and overshoot rates among deterministic one-query rules.The theorem assumes K0dp/a ≤ 1/8 and Mdp^2/a ≤ 1/8.Source: §6 · p. 4

Scope

  • The minimax theorem settles rates, not close constants, and excludes randomized queries.Its estimation lower and upper constants, 1/2592 and 4, differ by more than 10^4.Source: §6 · p. 4

7 Signed-Quadratic Recourse and Conformal Calibration

Signed-quadratic recourse uses curvature information to adjust the promised distance, while a forward-probe variant estimates curvature from one endpoint evaluation. Split-conformal calibration adds a coverage-or-abstention guarantee, and the experiments compare overshoot at similar nominal targets.

Recourse rules

  • Signed-quadratic recourse uses one gradient and one HVP to adjust the step in opposite directions for concave and convex paths; the forward-probe variant uses one extra score evaluation instead.The bare signed-quadratic point estimate has mean ray-hit validity of 28.9% in the suite, so it needs a margin.Source: §7 · p. 4

Calibration

  • Split conformal calibration adds a residual quantile to a fixed base rule and guarantees first-crossing coverage or abstention with probability at least 1 − δ under exchangeability.The base rule must be fixed independently of calibration data.Source: §7 · pp. 4–5

Calibration scope

  • Coverage is marginal over calibration and test draws, and experiments measure crossings using a finite grid search followed by bisection.A finite recommendation requires n ≥ ⌈1/δ⌉ − 1; this is necessary but not sufficient when calibration rays are unbracketed.Source: §7 · p. 5

Implementation caveat

  • Validation-tuned inflation omits the finite-sample correction and caps α at 3.Source: §7 · p. 5

Empirical comparison

  • At δ = 0.05, conformal-probe has lower mean overshoot than conformal-quadratic in all 16 dataset×method cells at similar pooled validity (96.0% versus 95.5%).Conformal-quadratic has lower mean overshoot than tuned inflation in 15 of 16 cells, but pooled validity differs: 95.5% versus 98.2%.Source: §7 · p. 5

8 Penalties

The penalty section distinguishes sign-blind penalties on the full Hessian from an asymmetric penalty targeted at curvature along the recourse ray. It also cautions that raising curvature can change score scale and lengthen the promised step, so validity gains must be read alongside overshoot.

Implementation

  • The margin-weighted Hutchinson implementation estimates the squared Hessian Frobenius norm with one Rademacher-vector HVP per example and step.The paper uses Softplus activations because input Hessians vanish almost everywhere in piecewise-affine ReLU networks, making HVP penalties vacuous there.Source: §8 · pp. 5–6

Penalty design

  • A full-Hessian Frobenius or Hutchinson penalty is sign-blind, while the asymmetric penalty targets κ on the fixed ray and penalizes curvature below a nonnegative target.The asymmetric penalty computes κ with one input HVP per example and weights the penalty toward rejected points.Source: §8 · p. 6

Ablations

  • The matched sign-twin penalty matches the asymmetric penalty except on Adult, where the hinge changes validity from 93% to 99.4%.The sign-blind κ^2 ablation is reported as unstable and harmful on COMPAS.Source: §8 · p. 6

Scale and interpretation

  • The score-scale effect can make a curvature penalty act partly like point-dependent step inflation, so alpha-1 validity alone does not distinguish changed path geometry from changed scale.Any such inflation also grows overshoot, making overshoot relevant when interpreting validity gains.Source: §8 · p. 6

9 Experimental Setup

The experiments use shallow neural models across four tabular or image datasets, with separately trained suites for the main comparisons, criterion audits, and additional analyses. Validity is measured by whether the recommended step reaches the ray crossing.

9 Experimental Setup

  • The study covers COMPAS, German Credit, Adult, and Fashion-MNIST, with protected attributes specified for the first three datasets.The data vary in size and dimensionality, from 1,000 German Credit examples to 20,000 Adult rows and 784-dimensional Fashion-MNIST.Source: §9 · p. 6
  • Most experiments use two-layer Softplus MLPs trained with Adam; Fashion-MNIST uses a larger network and a shorter training schedule.The suites include different seeds, resplits, penalty sweeps, and CIFAR-10 experiments.Source: §9 · p. 6
  • Ray-hit validity counts a recommendation as successful when the first crossing is within the recommended length, up to a 10^-6 tolerance.Endpoint validity is used for the criterion and score-gauge audits; the two validity measures agree on 99.55% of audited points in the 80-model suite.Source: §9 · p. 6

10 Results

Across the experiments, curvature-based validity tracks one-shot endpoint success closely, while asymmetric curvature training can raise validity at increased overshoot. Results also show dataset-specific gaps, group differences, and sensitivity to deployment shift.

Signed-curvature criterion

  • Across 80 models, endpoint validity and P(κ ≥ 0) correlate at r = 0.985, but their mean absolute gap reaches 8.2 points on Fashion-MNIST.Pointwise curvature sign agrees with endpoint success on 94.7% of held-out points; the criterion is systematically optimistic on Fashion-MNIST.Source: §10 · p. 7

Main comparison

  • No method leads on every dataset: spectral and gradient penalties achieve high Adult validity but have larger nearest-boundary gaps and fail on COMPAS.Margin weighting does not outperform its unweighted ablation; seed outcomes can split into low and high clusters.Source: §10 · p. 7

Asymmetric penalty

  • At α = 1, the asymmetric penalty reaches 99.4–100.0% Adult validity, 99.9% on Fashion-MNIST, and 99.5% on COMPAS, with higher overshoot.On Fashion-MNIST mean overshoot rises to 0.22 from about 0.05–0.07; on COMPAS it is 0.111 versus 0.005 for MW-Hutchinson.Source: §10 · p. 7

Deep networks

  • On CIFAR-10, Global Hutchinson raises validity from 81.0% to 95.4%, while the asymmetric penalty reaches 91.6% with lower overshoot than Global Hutchinson.A forward-probe training penalty produced chance-level classifiers in the tested full-length runs.Source: §10 · p. 7

Case study: a group gap on COMPAS

  • On unregularized COMPAS models, validity is 67% for African-American defendants and 89% for Caucasian defendants; the group gap remains a single-case finding.The analysis does not establish a general fairness claim, and curvature is not isolated as the cause of the gap.Source: §10 · pp. 7–8

Case study: deployment shift

  • Source-tuned inflation loses 34 points of validity on the COMPAS prior-offense split, while asymmetric training stays above 98% across the examined splits, usually with higher overshoot.The shift also changes score scale, so the match between validity loss and curvature change does not isolate curvature.Source: §10 · p. 8

11 Discussion

The audits support an on-path account of the recourse gap and show that rules trade validity, overshoot, and query cost. The theory is local, and its signed-curvature criterion is not established for deep networks or tree ensembles.

11 Discussion

  • No rule is best across validity, overshoot, and query budget; inflation recovers validity by spending overshoot, while conformal-probe has the smallest overshoot among qualifying no-search rules.Ray line search is valid by construction but costs 189 forward evaluations per user, making it preferable where that cost is affordable.Source: §11 · p. 8
  • The signed-curvature theory is local, and its theorem requires regime (⋆), which only some audited rejected points satisfy under the stated enclosure conditions.The criterion is not established for deep networks; tree ensembles lack a gradient ray, and a smoothed surrogate did not track ensemble validity.Source: §11 · p. 8

12 Conclusion

The paper concludes that one-shot recourse succeeds to leading order when the score bends upward along the recommended path, while additional queries and calibration improve what recourse rules can guarantee. It also reports the use and verification of generative AI tools in research and manuscript preparation.

12 Conclusion

  • To leading order, the closed-form gradient step succeeds exactly when the deployed score bends upward along its recommended path.The paper states that a one-query evaluation can attain the best deterministic rate under the specified curvature bounds, and calibrated rules can reach the first crossing or abstain.Source: §12 · p. 8

AI use statement

  • Generative AI tools assisted with code, experiments, proof drafting, result interpretation, and manuscript editing; the authors report reviewing the assisted work.AI-generated or refactored code was tested and used to rerun experiments and check printed numbers against committed results.Source: AI use statement · pp. 8–9

Checklist

The checklist reports that theoretical assumptions and proofs, experimental materials, and reporting details are documented, alongside asset and ethics information.

Checklist

  • Algorithmic costs are counted in model queries, but the paper makes no wall-clock comparison.The listed ray line search uses 189 forward evaluations in the implementation.Source: Checklist · p. 12
  • Theoretical results include their hypotheses and complete proofs, with plain-language explanations of assumptions.The paper also explains its regime and query model where introduced.Source: Checklist · p. 12
  • Reproduction materials include code, prepared data, scripts, result files, commands, and checks of headline numbers; one historical scale suite is unreproducible and excluded as evidence.CelebA reruns may agree with retained results only in distribution because the local image copy lacked some aligned images.Source: Checklist · pp. 12–13
  • Experimental reporting specifies training settings, evaluation measures, seed dispersion where reported, and a cluster-bootstrap interval for the signed-curvature correlation.Some tables report no seed dispersion.Source: Checklist · p. 13
  • Compute resources are described, although device detail is incomplete for some GPU experiments.CIFAR-10 result files record CUDA but not the GPU model; CelebA result files do not record the device.Source: Checklist · p. 13
  • Dataset sources and terms are documented, and ethics materials discuss contested COMPAS and CelebA labels; the work involved no human-subject research.The released COMPAS copy excludes names, dates of birth, and case numbers.Source: Checklist · p. 13

Overview

The supplement collects proofs, supplemental-only results, further experiments, and reproducibility material. It maps results to code and files, while noting that reviewers cannot verify the timing of when pass criteria were fixed.

Supplement overview

  • The supplement contains proofs and derivations, results stated only there, additional experiments, and reproducibility material.Its sections cover proofs, distance-estimator diagnostics, experimental setup, full empirical results, negative results, and an additional figure.Source: Overview · p. 14
  • Supplement S10 maps every result to its code and result files, but reviewers cannot verify when pass criteria were fixed because that timing is recorded only in private repository history.Source: Overview · p. 14
  • Supplement S11 covers data and ethics, and supplemental results use separate numbering unless they also appear in the main paper.Source: Overview · p. 14

S1. Proofs and Derivations

This section develops criteria, bounds, and guarantees for ray-based recourse, relating endpoint success to first crossing and examining score representation, curvature, promised distance, and limits of recourse rules. It also analyzes the drift screen’s error and ambiguity, distinguishing certification of endpoint validity from ray-hit validity, which additionally depends on early-hit/endpoint-failure mass.

Notation

  • For rejected points, endpoint success and ray-hit validity are distinct events, and their difference captures paths that cross before the recommendation but end on the unfavorable side.The global nearest-boundary distance is a diagnostic quantity, not the first-crossing distance along the action ray.Source: Notation · p. 14

Proof of Proposition 2.1: Score Gauge and Action Map

  • A convex score gauge preserves the classifier and ray while raising relative curvature and promised length; only positive affine zero-fixing gauges preserve promised length globally.The same classifier and ray can be assigned either curvature sign, so κ and dp depend on score representation.Source: Proof of Proposition 2.1: Score Gauge… · p. 15

Proof of Theorem 4.1

  • Under the local Hessian and gradient conditions, the theorem bounds global nearest-boundary distance, but this diagnostic does not imply ray validity, undershoot, or overshoot.The neighborhood must contain the one-shot point and a closest boundary point, with the normalized gradient flow remaining inside it.Source: Proof of Theorem 4.1 · pp. 16–17

Proof of Theorem 5.2

  • Under regime (⋆), first-crossing validity and endpoint success coincide; outside it, the conformal recommendation is not generally bounded by a fixed multiple of dp.The endpoint fallback clips recommendations to 2dp, with a 1.9% pooled fallback rate; it does not inherit the conformal coverage-or-abstention guarantee.Source: Proof of Theorem 5.2 · pp. 17–18

Derivation of the Leading-Order Fixed-Alpha Observation

  • At fixed scale, alpha-1 validity differs from the sign test κ ≥0 only within |κ| ≤ Mdp/3, while its leading-order expected overshoot increases under a rightward curvature shift.The monotonicity claim is local, leading-order, specific to alpha-1, and assumes the d²p/a scale is held fixed.Source: Derivation of the Leading-Order… · p. 18

Proof of Theorem 6.1 (First-Order Barrier)

  • No rule using only the first-order jet can be valid for every score with curvature bounded by K without overshooting some score by order Kdp²/a.The proof constructs two scores with the same value and gradient but separated first crossings.Source: Proof of Theorem 6.1 (First-Order… · p. 19

Proof of Corollary 6.2 (One-Query Root-Estimation Upper Bound)

  • One forward evaluation at dp estimates curvature well enough for a root estimate with the same order as an exact-curvature rule; collocation sharpens its error bound.The bare rule need not cross; adding a known margin gives deterministic first-crossing validity, while split conformal calibration provides coverage-or-abstention.Source: Proof of Corollary 6.2 (One-Query… · pp. 19–20

The Drift Screen: a Per-Point Validity Certificate Without Regime (⋆)

  • The endpoint-validity indicator equals 1{κ̂ ≥0} identically, because κ̂ is a weighted mean of directional second derivatives over the promised segment.This probe identity requires no regime condition or assumption that a crossing exists.Source: The Drift Screen: a Per-Point Validity… · p. 20
  • If ϕ'' is M-Lipschitz on [0, dp], |κ̂−κ| ≤ Mdp/3, so endpoint validity equals 1{κ ≥ 0} whenever |κ| > Mdp/3.The screen requires no smallness condition; replacing M with an upper bound only shrinks the certified unambiguous set.Source: The Drift Screen: a Per-Point Validity… · pp. 20–21
  • Ambiguity mass bounds the population gap between endpoint validity and P(κ ≥ 0), while ray-hit validity adds early-hit/endpoint-failure mass r, which is not bounded outside regime (⋆).Under Theorem 5.2’s regime (⋆), strict increase makes r = 0 for recommendations up to 2dp; outside it, r must be measured.Source: The Drift Screen: a Per-Point Validity… · p. 21
  • A 200-point scan detected 0/1787 early-hit/endpoint-failure cases, but finite-grid scanning cannot certify their absence or bound the event.The sample is smaller than the endpoint audit; a tolerant validity flag additionally marked 3 Adult points whose crossings were 2 × 10^-8–5 × 10^-7 past dp, not early hits.Source: The Drift Screen: a Per-Point Validity… · p. 21
  • On shallow suites, measured validity-gap and ambiguity-mass pairs were 1.25 ≤ 4.00, 0.00 ≤ 0.00, and 1.12 ≤ 6.50; the deep-row comparison 35.2 ≤ 81.3 is diagnostic only.At depth, only a finite-grid lower bound on M is available, and the ray-hit correction r is not bounded outside regime (⋆).Source: The Drift Screen: a Per-Point Validity… · p. 21
  • Float64 endpoint recomputation left 0/768 violations on COMPAS’s certified-unambiguous set, resolving a float32 near-boundary artifact.The same point’s float32 crossing appeared 9.1 × 10^-8 past dp; float64 made its endpoint +4.8 × 10^-9, as κ > 0 predicts.Source: The Drift Screen: a Per-Point Validity… · pp. 21–22
  • At depth, ambiguity mass rose from 0–6.5% on shallow suites to 81.3% on ResNet-18/CelebA, where sign-disagreement was 44.5% on ambiguous versus 5.7% on unambiguous points.The depth screen is diagnostic, not a certificate: its lower-bound M estimate makes the unambiguous set optimistic, and the association does not establish why the criterion degrades.Source: The Drift Screen: a Per-Point Validity… · p. 22

A Matching Deterministic One-Forward-Query Converse

The section establishes matching minimax rates for deterministic one-forward-query root estimation and uniformly first-crossing-valid recommendation under curvature and curvature-Lipschitz bounds. Its converse uses indistinguishable profiles, and the rates persist in a segment-capped class.

Theorem 6.3

  • Θ(MK0d^4/a^2 + M^2d^5/a^2) is the rate for both deterministic one-query root estimation and uniformly first-crossing-valid overshoot over the stated class.The probe rule attains an upper bound within a constant factor, while the converse supplies a matching-order lower bound.Source: A Matching Deterministic… · p. 22

Converse

  • A deterministic rule sees identical transcripts on the constructed profile pair, so valid advice must clear the later root and overshoot the earlier one by their full gap.The same indistinguishability forces absolute estimation error of at least half the root gap.Source: A Matching Deterministic… · pp. 23–24

Segment-capped class

  • On the segment-capped class, estimation and valid overshoot both have rate Θ(MKd^4/a^2), while zero-query valid overshoot retains the Kd^2/a lower bound.The probe upper bounds are (13/3)MKd^4/a^2 for estimation and (28/3)MKd^4/a^2 for valid overshoot; the converse gives matching-order bounds.Source: A Matching Deterministic… · p. 24

Pointwise sharpness

  • For the fixed probe at d, neither the curvature-bound term nor the curvature-Lipschitz term in the collocation upper rate is an artifact of the proof.A constructed profile pair shares the probed value and yields root separation with both terms represented in the expansion.Source: A Matching Deterministic… · p. 24

Query-budget comparison

  • The zero-query rate is Θ(W), and one forward value improves it by a factor of order Md^2/a; randomized and noisy converses remain open.The section also notes that query placement matters more than query count at larger budgets, contrasting fixed locations with adaptive ones.Source: A Matching Deterministic… · p. 24

Curvature–collocation oracle

  • With zero or one exact forward value, the minimax rates have the same order for estimation and valid overshoot, whether curvature is hidden or revealed first.The rate-sharp lattice distinguishes hidden κ from revealed κ; the upper and lower constants differ.Source: A Matching Deterministic… · pp. 24–25

Many Queries: an Adaptivity Separation

For fixed query locations, the paper proves a q^-3 minimax rate for first-root error and valid overshoot. It contrasts this with an adaptive procedure whose error decays faster than any power of q, while leaving adaptive optimality unproved.

Rate separation

  • For q ≥ 3 fixed query locations, first-root error and uniformly valid overshoot have minimax rate Θ((M/a)(W/q)^3), whereas adaptive error is o(q^-k) for every k.For adaptive queries, the stated valid-overshoot bound is 8X·2^(1−q); the fixed-location result is a Θ(q^-3) rate.Source: Many Queries: an Adaptivity Separation · pp. 26, 28

Batch procedure

  • The batch upper bound places q ≥ 3 equispaced queries across an enlarged root band and interpolates locally around the sign change.A deterministic radius added to the interpolated estimate makes the recommendation uniformly first-crossing-valid.Source: Many Queries: an Adaptivity Separation · pp. 26–27

Scope and loss

  • The recovered quantity is the first root localized by the origin jet and curvature bounds, and the one-sided valid-recommendation loss has the same minimax order as absolute error.The root band has width Θ(W), where W = K0d^2/a + Md^3/a.Source: Many Queries: an Adaptivity Separation · p. 28

Conjecture

  • The successive-collocation rule and its certified radii are conjectured, not proved in the paper.The proposed iteration queries d, then successive estimates, and interpolates from recent values.Source: Many Queries: an Adaptivity Separation · p. 28

Adaptive procedure

  • An adaptive rule queries d, then bisects a root-containing interval using the sign at its midpoint, leaving interval length at most 8X·2^(1−q).The initial interval lies where the ray profile is increasing, so its midpoint sign identifies which half contains the root.Source: Many Queries: an Adaptivity Separation · p. 28

Limitations

  • No adaptive minimax-optimality is claimed, and randomized, noisy, and finite-precision oracles fall outside the stated results.The matching adaptive converse remains unproved; the batch bounds are rate-sharp but their constants differ by about eleven orders of magnitude.Source: Many Queries: an Adaptivity Separation · pp. 27–28

Leading-Order Average-Case Companion to Theorem 6.1

This section develops curvature-based bounds and conformal recourse rules, then audits their empirical scope alongside curvature-aware training and recourse repairs. It also examines matched-validity baselines, constrained directions, deployment and group differences, and reproducibility and feasibility limits, qualifying how the results should be interpreted or used.

Leading-Order Average-Case Companion to Theorem 6.1

  • For fixed-scale scale-only rules, matching or exceeding P(κ ≥ 0) validity entails a leading-order overshoot bound only under a curvature-density assumption and finite-remainder qualification.The COMPAS and Adult measurements illustrate where the threshold may lie but do not verify the density envelope or a positive population lower bound.Source: Leading-Order Average-Case Companion… · p. 29

Proof of Proposition 7.1 (Conformal First-Crossing Coverage-or-Abstention)

  • Under exchangeability, conformal calibration guarantees first crossing or abstention with probability at least 1 − δ, but favorable endpoint classification additionally requires no intervening recrossing.The endpoint implication applies to in-regime recommendations no longer than 2dp; the segment-safe fallback makes no conformal-coverage claim on fallback cases.Source: Proof of Proposition 7.1 (Conformal… · pp. 29–30

Proofs of the Distributional Consequences (Theorem S1.28, Remark 8.1)

  • At fixed scale, inflation validity is determined by a curvature threshold exactly for quadratic profiles and up to boundary-layer mass at finite curvature-Lipschitz constant.The curvature-CDF shift does not isolate the effect when dp and gradient scale vary together; the COMPAS covariate-split agreement is descriptive, not identifying.Source: Proofs of the Distributional… · pp. 30–31
  • On a shared ray with a common first-order jet and directional curvature, first crossings differ by at most twice the Theorem 5.2 slab, so leading-order dependence is through κ.Instantaneous full-Hessian penalties are even under H → −H and constrain off-ray curvature, unlike the directional one-sided penalty; this local comparison does not establish trained-model performance.Source: Proofs of the Distributional… · p. 31

Staleness Monitoring and Zero-Search Repair

  • Measured validity rises from 66.4% for stale inflation to 98.8–99.7% with the zero-search repair, at overshoot 0.28–0.40 versus 0.023 for conformal recalibration.The measured validity is on the full target; no certificate covers those full-target figures. A separate finite-cohort guarantee applies only to the screened cohort under the stated screen and enclosure assumptions.Source: Staleness Monitoring and Zero-Search… · p. 32

S2. Metric Audit and Estimator Diagnostics

  • Endpoint success and first-crossing validity agree 99.55% pooled, and the 109 disagreements are boundary-coincident; curvature sign correlates with endpoint success at r = 0.985.For conformal recommendations, endpoint and first-crossing coverage match in every cell; 98.1% of test points satisfy dconf ≤ 2dp, while the segment-safe fallback abstains from correction for 1.9%.Source: S2. Metric Audit and Estimator… · p. 33

S3. Experimental Setup

  • The experiments use shallow Softplus MLPs with deterministic seeds, while Fashion-MNIST uses a larger network trained for 15 epochs and line searches cover rejected test points unless capped.Real-data nearest-boundary estimates use a seeded random cap of 128 rejected points per seed and are diagnostic rather than exact.Source: S3. Experimental Setup · p. 33

S3.1. Measured Directional-Curvature Variation and Regime Screening

  • The finite-grid screen leaves 94–100% of COMPAS and German points unrejected but only 68% of unregularized Adult points, where 8M̂dp^2 ≤ a is binding.The screen can reject points but cannot certify regime eligibility; at depth, only 7.8% of ResNet-18/CelebA points pass, and the observed degradation is consistent with—but does not prove—the remainder mechanism.Source: S3.1. Measured Directional-Curvature… · pp. 34–35
  • 93.8%, 100%, and 68.0% of COMPAS, German, and Adult points pass the directional-curvature screen, within 0.3 points of the estimated screen fractions.At most two points per dataset change decisions; a naive global weight-norm cascade yields only about 5% and is uninformative. The conditional floating-point enclosure exceeds dense-grid values under stated evaluation-accuracy assumptions, but does not enclose stored jet inputs.Source: S3.1. Measured Directional-Curvature… · p. 35

S3.2. Implementation Specification

  • Ray validity is assessed against the first crossing found by a uniform 160-point scan followed by 30 bisection steps, with rays lacking a grid crossing counted invalid.The described conformal suite uses a 0.05 miscoverage target and calibration residuals based on crossing distance minus the chosen base distance.Source: S3.2. Implementation Specification · p. 37

Asymmetric Penalty vs. Best Symmetric Penalty

  • On COMPAS, asymmetric regularization raises validity from 86.5% to 99.5% at δ = 0.1 and reaches 96.3% at δ = 0.05 against MW-Hutchinson.The best symmetric penalty reaches at most 70.9% on Adult in the reported sweep; Adult paths are concave and undershoot-dominated, while COMPAS and German are mostly convex and high-validity. Over ten CIFAR seeds, the best symmetric penalty leads, reversing the three-seed ordering.Source: Asymmetric Penalty vs. Best Symmetric… · p. 38
  • Asymmetric regularization beats the best symmetric penalty by 13.3 points on COMPAS, 17.5 on Adult, and 12.9 on F-MNIST across 20 repeated splits.It wins all 20 splits on those datasets and 13/20 on German, where the gain is 2.1 points; the authors caution that overlapping resamples and non-significant Holm-adjusted tests do not establish population superiority.Source: Asymmetric Penalty vs. Best Symmetric… · p. 39

Sign-Isolation Ablation: the Positive Target versus the Hinge

  • The sign-blind curvature penalty never exceeds 54% mean validity across three λ decades and reaches 30.2% on COMPAS versus 73.9% unregularized.On COMPAS and F-MNIST, the sign twin without the hinge matches the asymmetric arm within +0.3 and −0.7 points; on Adult, the hinge yields 99.4 ± 0.3 versus 93.0 ± 5.3 and reduces seed standard deviation 20-fold.Source: Sign-Isolation Ablation: the Positive… · pp. 39–40

Signed-Quadratic and Conformal Recourse: Full Tables (δ = 0.05)

  • Conformal-quadratic has lower overshoot than tuned inflation in 15 of 16 dataset×method cells, and in 8 of the 9 below-target cells, with unregularized Adult the sole loss.This is a common nominal-target comparison, not a matched-realized-validity comparison: pooled validity is 95.5% for conformal-quadratic and 98.2% for tuned inflation.Source: Signed-Quadratic and Conformal… · p. 40
  • At δ = 0.05, the one-forward-evaluation conformal-probe matches HVP-conformal coverage cell by cell while reducing pooled overshoot about 16×, from 0.0253 to 0.0016.Probe cell means are 94.1–99.2% and pooled validity is 96.0%; its overshoot is lower in every cell, including unregularized Adult (0.0059 versus 0.0705).Source: Signed-Quadratic and Conformal… · p. 40, Table S4 · p. 41
  • With one forward query, conformal-probe meets the target at the lowest overshoot among target-meeting rules without per-user search (96.0%, 0.0016); per-user ray search reaches 100% validity and zero overshoot.With one HVP, conformal-quadratic measures 95.5% validity and 0.025 overshoot; neither conformal rule abstains on the 80 models, and both carry the stated coverage-or-abstention guarantee under exchangeability.Source: Signed-Quadratic and Conformal… · p. 41, Table S5 · p. 41

Deployment-Shift Robustness (Full Table)

  • Under deployment shift, asymmetric training keeps target validity above 98% in all seven cells, while conformal-quadratic recalibrated on target averages 95.1% validity (range 91.7–97.3%).Validation-tuned inflation drops 33.6 points on the COMPAS priors-count shift; curvature marginals do not generally predict validity drops, as illustrated by F-MNIST and Adult.Source: Deployment-Shift Robustness (Full Table) · pp. 42–43, Table S10 · p. 43

Real CIFAR-10 Binary Deep-Image Recourse Rules

  • Across seven added CIFAR-10 seeds, Global and MW improve exact alpha-1 validity over unregularized training by 14.3 and 11.8 points, respectively, while Asym is unstable.Asym’s improvement is not significant when its collapsed seed is included; the collapse is reproducible, and the ten-seed audit concludes MW and Global are the reliable choices.Source: Real CIFAR-10 Binary Deep-Image… · p. 44, Table S13 · p. 45

Deep Forward-Probe Penalty: a Negative Result; Historical Note (Not Used as Evidence): ResNet-18 Scale Suite on CelebA

  • The deep forward-probe training experiment fails all three preregistered success criteria: probe arms collapse, and the HVP arms do not retain unregularized validity.Only 2/10 Softplus and 5/10 GroupNorm–ReLU seeds have finite validation-validity candidates. The historical CelebA scale suite is not used as evidence because its results cannot be regenerated and lack retained provenance.Source: Deep Forward-Probe Penalty: a Negative… · pp. 45–46, Historical Note (Not Used as… · p. 48

Comparison to FaiR-N; Disparity Tests on Two Additional Real Datasets

  • FaiR-N does not fix curvature-driven validity failure in the reimplementation: COMPAS validity falls from 73.9% to 51.7% at its highest five-seed fairness weight.On two additional datasets, the protocol finds no material disparity: ACSIncome groups are both at the all-concave floor, while Taiwan credit-default has a 4.3-point gap below threshold; the COMPAS disparity does not recur there.Source: Comparison to FaiR-N · p. 46, Disparity Tests on Two Additional Real… · p. 47

Group-Conditional versus Matched-Uniform Training on COMPAS; Channel Attribution and the Criterion-Implied Identity

  • On COMPAS, matched-uniform training reduces the residual validity gap by 19.16 points (20.73 to 1.57), whereas the conditional allocation criterion is not met.The criterion-implied curvature-channel closure is 87.9%, but the authors identify it as a consistency corollary, not independent mediation; curvature and remainder scale are correlated (−0.72 pooled), making attribution order-dependent.Source: Group-Conditional versus… · p. 46, Channel Attribution and the… · p. 47

Historical Note (Not Used as Evidence): ResNet-18 Scale Suite on CelebA

  • Across 57 smoothed CelebA models, P(κ ≥0) and alpha-1 ray-hit validity correlate at Pearson r = 0.76, while most models have overall accuracy below 0.60.On unregularized models, the alpha-1 step denies recourse to 90% of attractive, 55% of heavy-makeup, and 72% of smiling rejected users; heavy-makeup denial is 81% for women versus 38% for men. Ray search brackets 91% of evaluated rejected images; the 60 repeated ReLU rows represent 15 distinct models.Source: Historical Note (Not Used as… · p. 48

S5. Extended Inflation and Validation-Tuned Baselines

  • At matched validity, Asym has no blanket overshoot advantage; validation-tuned inflation wins on overshoot and both costs in several COMPAS and F-MNIST settings.The comparison reuses stored three-seed results from shorter, smaller-data training runs and does not establish how the main-paper models would compare; once tuned, validation-tuned inflation remains closed-form at inference, while line search requires per-user search.Source: S5. Extended Inflation and… · p. 49, Table S17 · p. 51

Constrained-Action Geometry (the masks are a special case)

  • The constrained-action transfer replaces gradient-ray curvature with curvature along the feasible direction; when Kdp,A < aA/2, gradient-only rules must be invalid or overshoot by at least Kd2p,A/aA.Constraints can only increase promised distance, dp,A ≥ dp; over 2×10^5 synthetic random jets, κA and κ differ in sign in 31.7% of cases, and feature-freezing is the coordinate-projection case.Source: Constrained-Action Geometry (the masks… · pp. 50–51

Empirical Mask Audit

  • 97–100% projected-ray validity on COMPAS with the protected-only mask contrasts with 86–90% on strict German masks for non-asymmetric methods and 99.6% for Asym.German protected-only validity is 100% for every method; COMPAS strict masking leaves no first-order movable dimension, and F-MNIST is excluded because its masks freeze no features.Source: Table S18 · p. 52, Empirical Mask Audit · p. 52

S7. Cost-Model Audit Details

  • With travel-error cost CU/CO = 5, Asym is strongest on binary-denial cost among closed-form alpha-1 rules, while validation-tuned inflation is strongest on effort cost and can also win binary-denial cost.Oracle line search wins every modeled cost setting when a crossing is bracketed, with validity 1 and overshoot 0, but query and search costs are omitted.Source: S7. Cost-Model Audit Details · p. 53

S8. Failed Attempts and Negative Results

  • For smoothed tree ensembles, P(κσ ≥0) does not track ray validity (Pearson r = −0.53 over 33 cells), and Adult validity stays near zero even at P(κσ ≥0) ≈0.98.The authors attribute this failure to smoothing making the surrogate’s promised distance a poor predictor of the jagged boundary, and limit the criterion to locally smooth boundaries; the tested training-time attempts do not establish an impossibility result.Source: S8. Failed Attempts and Negative Results · p. 53

S9. Extended Figures

  • At the COMPAS-unregularized median (M̂, dp, a) = (0.018, 0.75, 1.00), the finite-grid slab is an empirical diagnostic, not a certified remainder.The figure reports the quadratic-model gap, its leading-order approximation, and a two-sided slab that contains 99% of points per point in regime (⋆).Source: Figure S1 · p. 54, S9. Extended Figures · p. 54

S10. Reproducibility and Provenance

  • The supplement maps results to code and files, and claims manifest.py checks headline numbers against their result files or, for some entries, stored printouts.Historical CelebA aggregates cannot be exactly rerun from the archive because the curvature-helper variant and image-list order were not retained; GPU determinism was requested but not enforced.Source: Historical Note (Not Used as… · p. 48, S10. Reproducibility and Provenance · pp. 54–55
  • Table S22 maps reproducibility-checklist areas to documentation, and the provenance inventory identifies scripts and result files for recourse and audit analyses.The historical CelebA aggregates are not reproduced by the public producer, which instead defines and checks records for future runs.Source: S10. Reproducibility and Provenance · p. 56, Table S22 · p. 57

S11. Data and Ethics

  • COMPAS and CelebA measure whether prescribed recourse steps reach claimed boundaries, not whether their contested, historically biased prediction targets are legitimate decision variables.No new human-subject data was collected, and the released COMPAS copy excludes direct identifiers and custody metadata.Source: S11. Data and Ethics · p. 57
  • Reported group differences are descriptive; the curvature-channel decomposition is a reweighting, the preregistered conditioning-benefit test failed, and dataset-specific results do not establish broad fairness.The paper makes no group-conditional allocation or equivalence claim.Source: S11. Data and Ethics · p. 58
  • Unconstrained score-space rays can yield unactionable or misleading advice without an action map, so denied recourse and disparities are framed as harms to measure before deployment.The constrained-action experiment is only a feature-freezing diagnostic; under the strict COMPAS mask, no first-order actionable dimension remains.Source: S11. Data and Ethics · p. 58
Loading 2609.36252v2…