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

Hazar Yueksel

cs.LGSep 28, 2026

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

Authors: Hazar Yueksel

Organizations: Google

Abstract

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 $κ=\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 $κ\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-δ$ . 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 $κ$ 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.

Figures & tables

Dataset	Method	Bal. Acc. (%)	$\|d_{\star}-d_{p}\|$ (nearest)	$\|d_{\text{ray}}-d_{p}\|$ (on-path)	Validity (%)
COMPAS	Unregularized	$66.83\pm 0.58$	$0.0543\pm 0.0111$	$0.0697\pm 0.0123$	$73.58\pm 3.34$
COMPAS	Spectral Norm	$65.41\pm 0.52$	$0.0199\pm 0.0087$	$0.0206\pm 0.0085$	$10.90\pm 29.72$
COMPAS	1-Lipschitz GP	$66.68\pm 0.56$	$0.0114\pm 0.0049$	$0.0141\pm 0.0046$	$31.65\pm 15.33$
COMPAS	Global Hutchinson	$66.59\pm 0.32$	$0.0123\pm 0.0031$	$0.0105\pm 0.0019$	$90.94\pm 4.32$
COMPAS	MW-Hutchinson	$66.60\pm 0.43$	$0.0134\pm 0.0030$	$0.0151\pm 0.0019$	$84.12\pm 2.95$
German	Unregularized	$73.38\pm 0.79$	$0.0249\pm 0.0059$	$0.0220\pm 0.0057$	$100.00\pm 0.00$

Table 1: Symmetric regularizers: nearest-boundary gap and on-path validity (10 seeds; mean

\pm

population standard deviation). Ray metrics use all rejected test points;

d_{\star}

is a C&W-style solver estimate on a seeded random subset of at most 128 rejected points per seed. Validity is ray-hit validity,

d_{\text{ray}}\leq d_{p}+10^{-6}

. The gap columns are seed means; Theorem 4.1 bounds the first pointwise, and Theorem 5.2 the second after its leading term is removed. Spectral Norm validity is bimodal across seeds (Section 10 ).

Queries	Rule	$n$	Val. %	Oversh.
none	alpha-1	80	76.6	0.041
none	tuned inflation	80	98.2	0.061
1 HVP	signed-quadratic	80	28.9	0.005
1 HVP	conformal-quadratic	80	95.5	0.025
1 forward	conformal-probe	80	96.0	0.0016
189 forward	ray line search $=d_{\text{ray}}$	80	100.0	0.000

Table 2: Rules by the model queries they need per user beyond the gradient, mean over

n

models of the five-seed suite (4 datasets

\times

4 training methods

\times

5 seeds) at target

0.95

: ray-hit validity and mean overshoot. Tuned inflation needs a validation set and the conformal rules a calibration set. Rows differ in realized validity; the last row, alpha-1 on the 20 asymmetric-penalty models among the 80, is a training-time intervention and not comparable with the others.

Data	med. $\hat{M}$	screen pass	p90 stress	slab cont.	crit. err. pass/reject
COMPAS	0.018	93.8%	75%	99.1%	0.021 / 0.000
German	0.024	100%	97%	97.9%	0.000 / –
Adult	0.61	68.2%	60%	99.3%	0.000 / 0.035
COMPAS (MW)	0.008	98.5%	89%	99.3%	0.041 / 0.000
CelebA depth (unreg)	138	7.8%	3.9%	99.6%	0.123 / 0.423
CelebA depth (Asym)	42	10.5%	7.7%	99.4%	0.171 / 0.366

Table S1: Finite-grid directional-

M

screen on real models (unregularized unless noted; tabular rows: 2 seeds except COMPAS-MW (seed 0),

\leq\!400

rejected points; CelebA depth rows: ResNet-18, 3 attributes

\times

5 seeds, 256 points/model, pooled; the same eleven-point ray grid on

[0,2d_{p}]

throughout). “p90 stress” substitutes the measured p90 of

\hat{M}

for every point as a sensitivity analysis, not an upper-bound certificate. Slab containment is the empirical fraction with

|(d_{\text{ray}}-d_{p})+\kappa d_{p}^{2}\rho/(2a)|\leq 8\hat{M}d_{p}^{3}/(3a)

Suite (driver)	Data, epochs, seeds	Weights $\lambda$ ; curvature target $\delta$
Main comparison, main-paper Table 1 ( exp.py )	COMPAS, German, Adult (20k); 50 epochs; seeds 0–9	COMPAS/German/Adult: gradient penalty 0.5/0.05/0.5; MW-Hutchinson and Global Hutchinson 0.2/0.05/0.05; Spectral Norm none
Five-seed suite: signed-curvature criterion and common cohort, signed-quadratic and conformal rules, endpoint and clipping audits, score gauge, sign isolation, deployment shift, mask audit ( run_sig.py )	COMPAS and German 50 epochs, Adult (8k) 30, F-MNIST 15; seeds 0–4	MW / Global / Asym $(\lambda,\delta)$ : COMPAS 0.2 / 0.2 / (2, 0.1); German 0.05 / 0.05 / (1, 0.05); Adult 2.0 / 1.0 / (10, 0.05); F-MNIST 0.1 / 0.1 / (10, 0.05). Sign isolation: twin at the Asym $(\lambda,\delta)$ ; sign-blind $\kappa^{2}$ at $0.1$ , $1$ , and $10$ times the Asym $\lambda$
Adult penalty sweep ( final_adult.py )	Adult (8k); 30 epochs; seeds 0–4	MW and Global $\lambda\in\{0.05,1.0\}$ ; Asym $\lambda=10$ , $\delta\in\{0,0.05,0.1,0.2\}$
FaiR-N comparison ( fairn2.py , fairn_adult.py )	COMPAS 50 epochs, seed 0 (sweep) and seeds 0–4; Adult (8k) 30 epochs, seeds 0–1; plain accuracy	FaiR-N adds $\lambda_{f}$ times the squared difference of the two groups’ mean $d_{p}$ in each minibatch: $\lambda_{f}\in\{0.02,0.05,0.1,0.3\}$ (COMPAS sweep), $\{0.02,0.1\}$ (COMPAS, five seeds), $\{0.02,0.1,0.5\}$ (Adult); Asym $(2,0.1)$ on COMPAS, $(10,0.05)$ on Adult
COMPAS penalty suite ( compas_asym.py )	COMPAS; 50 epochs; seeds 0–2; ray metrics on the first 200 rejected test points in split order; plain (not balanced) accuracy	MW 0.2; Asym $\lambda=2$ , $\delta\in\{0.05,0.1\}$
F-MNIST, Table S3 ( fm_final.py )	15 epochs; seeds 0–4; unweighted loss	MW 0.1; Global 0.1; Asym (10, 0.05)

Table 4

Dataset	Best sym. validity	Asym validity	Asym acc.	Asym overshoot
Adult (sweep, $\delta{=}0.05\text{--}0.2$ , $d{=}100$ )	70.9% (MW)	99.4–100.0%	81.4–81.5%	0.038–0.092
F-MNIST	74.7% (MW)	99.9%	88.5%	0.22
CIFAR-10 ( $V_{1}$ , ten seeds)	95.4% (Global)	91.6%	92.0%	1.003

Table S2: Asymmetric penalty vs. best symmetric curvature penalty (within-run comparisons). Validity is exact alpha-1 ray validity; overshoot is mean

[g]_{-}

for the asymmetric penalty. “Best sym.” is the stronger of Global/MW-Hutchinson in that run.

Method	Acc.	Under	Over	Validity
Unreg	88.40	0.0082	0.0516	$52.2\pm 4.9$
MW-Hutch	88.92	0.0065	0.0653	$74.7\pm 10.2$
Global	89.05	0.0108	0.0546	$68.8\pm 11.0$
Asym	88.53	0.0017	0.2203	$99.9\pm 0.1$

Table S3: Fashion-MNIST MLP results (5 seeds; balanced accuracy; all rejected test points; mean

\pm

population standard deviation).

Dataset	Method	Probe val. %	Probe overshoot	HVP val. %	HVP overshoot	Overshoot ratio
COMPAS	asym	94.5	0.0020	94.8	0.0120	6 $\times$
COMPAS	glob	95.3	0.0000	93.3	0.0058	133 $\times$
COMPAS	mw	94.1	0.0001	95.3	0.0077	70 $\times$
COMPAS	unreg	95.7	0.0023	95.2	0.0203	9 $\times$
German	asym	95.5	0.0003	94.8	0.0027	10 $\times$
German	glob	99.0	0.0000	97.6	0.0035	127 $\times$

Table S4: Zero-HVP conformal-probe vs. HVP-conformal at

\delta=0.05

, target

0.95

(means over five seeds). Probe matches HVP coverage at markedly lower overshoot on every cell. The overshoot ratio (HVP over probe) is computed from the unrounded means; several probe overshoots round to

0.0000

Inference-query budget	Rule	Validity %	Overshoot
none (training-time only)	asymmetric $\alpha{=}1$	99.6	0.103
validation only (closed form)	tuned inflation	98.2	0.061
one forward eval, no HVP	conformal-probe	96.0	0.0016
one HVP	conformal-quadratic	95.5	0.025
per-user ray search	ray line search (oracle)	100.0	0.000

Table S5: Deployment map (descriptive; the conformal rows carry the coverage-or-abstention guarantee of Proposition 7.1): for each inference-query budget, a fitting rule and its measured validity and overshoot, pooled over the

\delta=0.05

, target-

0.95

suite (the asymmetric row over its 20 models, the other rows over all 80).

Setting	$r$	models
Shallow common cohort (COMPAS/German/Adult/F-MNIST)	0.985	80
Adult only ( $\delta=0.05$ suite)	0.996	20

Table S6: Signed-curvature criterion. The shallow row uses direct alpha-1 endpoint success and

\mathbb{P}(\kappa\geq 0)

on identical held-out IDs; the Adult row correlates alpha-1 ray-hit validity with

\mathbb{P}(\kappa\geq 0)

over the 20 Adult models of the

\delta=0.05

rule suite. No deep-network test of the criterion is included: an earlier CIFAR-10 check was withdrawn because its evaluation pipeline was not retained, and the historical CelebA scale suite at the end of S4 is not used as evidence.

	one-shot		signed-quad		conformal-quad		tuned inflation
Data	$V$	$O$	$V$	$O$	$V$	$O$	$V$	$O$
COMPAS	0.867	0.035	0.447	0.004	0.946	0.011	0.970	0.071
Adult ( $d{=}100$ )	0.456	0.011	0.322	0.001	0.954	0.027	0.983	0.023
F-MNIST	0.739	0.098	0.157	0.015	0.959	0.060	0.975	0.130
German	1.000	0.020	0.229	0.000	0.960	0.003	1.000	0.020

Table S7: Per-dataset recourse rules at

\delta=0.05

: validity

V

and mean overshoot

O

, each the mean over all models of a dataset (every training method and seed). Conformal-quadratic lands at the

0.95

target on every dataset (COMPAS

0.946

, the others above target). On COMPAS and F-MNIST it does so at far lower overshoot than tuned inflation. On Adult its mean overshoot is higher than that of tuned inflation, and it loses in the unregularized cell, although its median per-model overshoot reduction is positive (Table S8 ). signed-quad alone undershoots (it is the base predictor). German is the method-not-needed control.

Setting	median reduction
COMPAS	78%
F-MNIST	40%
Adult (full UCI)	32%
pooled (above three, $n{=}60$ )	54%

Table S8: Median overshoot reduction of conformal-quadratic vs. tuned inflation at

\delta=0.05

(positive

=

lower overshoot), taken over the per-model reductions of all models of a dataset, or of the three datasets for the pooled row. A median can be positive where the mean overshoot of Table S7 is higher, as on Adult. German excluded (method not needed; alpha-1 already

\approx 100\%

valid, so a

0.95

target only trades validity down).

Rule	HVP	queries	$V$	$O$
one-shot ( $\alpha{=}1$ )	0	0	0.766	0.041
tuned inflation	0	0	0.982	0.061
signed-quadratic	1	0	0.289	0.005
conformal-quadratic	1	0	0.955	0.025
conformal-quadratic (Mondrian)	1	0	0.951	0.020
ray line search	0	many	1.000	0.000

Table S9: Query-budget cost curve (tabular,

\delta=0.05

): validity

V

and overshoot

O

against per-user Hessian-vector products and model queries. Tuned inflation additionally requires a validation set and conformal a calibration set (one-time, offline). The Mondrian row pools the 40 COMPAS and Adult models only (German abstains; F-MNIST has no protected group); on those 40, conformal-quadratic has

V=0.950

O=0.019

Dataset / shift	Rule	$\Delta\mathbb{P}(\kappa{\geq}0)$	Src $V$ %	Tgt $V$ %	Drop%	Tgt $O$
COMPAS (cov., priors)	VT inflation	$-0.351$	$100.0$	$66.4$	$33.6$	$0.012$
	conformal stale		$96.7$	$86.0$	$10.7$	$0.008$
	conformal recal.		$100.0$	$95.2$	$4.8$	$0.023$
	asym. training		$100.0$	$99.3$	$0.7$	$0.142$
COMPAS (subpop.)	VT inflation	$+0.183$	$95.3$	$99.3$	$-4.0$	$0.134$
	conformal stale		$95.4$	$99.6$	$-4.2$	$0.023$

Table S10: Recourse under deployment shift (means over five seeds; target validity

95\%

\delta=0.05

). “Drop” is source minus target validity (lower is more robust; negative means the target slice was easier). Drop is computed from the unrounded means, so it can differ by

0.1

from the difference of the displayed columns.

Method	Acc.	$V_{1}$	$V_{1.05}$	$V_{1.10}$	$U_{1}$	$O_{1}$
Unreg	$94.4\pm 0.3\%$	$79.2\pm 4.7\%$	$82.8\pm 3.9\%$	$84.9\pm 3.0\%$	$4.455\pm 0.862$	$1.036\pm 0.458$
MW	$93.2\pm 0.7\%$	$89.8\pm 0.0\%$	$97.4\pm 1.2\%$	$98.2\pm 0.5\%$	$2.333\pm 3.046$	$3.165\pm 2.745$
Global	$92.9\pm 0.6\%$	$93.8\pm 0.8\%$	$98.4\pm 0.8\%$	$98.4\pm 0.8\%$	$1.942\pm 0.427$	$3.771\pm 0.961$
Asym	$93.9\pm 0.3\%$	$95.1\pm 2.4\%$	$96.9\pm 2.8\%$	$97.1\pm 2.4\%$	$0.728\pm 0.524$	$1.129\pm 0.713$

Table S11: CIFAR-10 automobile-vs-truck exact and small-inflation audit. Entries are mean

\pm

sample standard deviation over three CUDA seeds.

V_{\alpha}

is ray validity for recommendation

\alpha d_{p}

Method	$\alpha_{.95}$	$V_{.95}$	$O_{.95}$	$\alpha_{.99}$	$V_{.99}$	$O_{.99}$
Unreg	$2.000\pm 0.000$	$90.6\pm 2.8\%$	$3.667\pm 1.143$	$2.000\pm 0.000$	$90.6\pm 2.8\%$	$3.667\pm 1.143$
MW	$1.032\pm 0.038$	$95.8\pm 2.7\%$	$3.428\pm 3.123$	$1.408\pm 0.514$	$98.2\pm 0.5\%$	$6.625\pm 7.852$
Global	$1.028\pm 0.041$	$97.1\pm 2.3\%$	$3.987\pm 1.263$	$1.680\pm 0.554$	$98.7\pm 0.9\%$	$8.491\pm 4.440$
Asym	$1.100\pm 0.173$	$95.8\pm 1.6\%$	$1.352\pm 0.663$	$1.833\pm 0.289$	$98.2\pm 1.8\%$	$3.447\pm 1.981$

Table S12: CIFAR-10 validation-tuned inflation audit.

\alpha

is selected on rejected validation examples, then evaluated on rejected test examples. Entries are mean

\pm

sample standard deviation over three CUDA seeds.

Method	Acc.	$V_{1}$	$V_{1.05}$	$U_{1}$	$O_{1}$
Unreg	94.5	81.0	85.3	3.487	1.102
MW	93.3	92.5	98.1	1.635	3.129
Global	93.1	95.4	98.6	1.299	4.644
Asym	92.0	91.6	95.3	0.549	1.003

Table S13: CIFAR-10 automobile-vs-truck audit, means over ten seeds. Acc.: test balanced accuracy (%);

V_{\alpha}

: ray validity (%) at

\alpha d_{p}

;

U_{1},O_{1}

: alpha-1 under- and overshoot (

L_{2}

, standardized pixels); all on the first 128 rejected test images. A ray with no crossing within

\max(8d_{p},10^{-3})

is invalid and enters

U_{1}

at that length. Seeds 0–2 and 3–9 ran on two GPU types; rerunning all ten Unreg and Global seeds on one type gives

V_{1}

of 81.4 and 95.9 (ten-seed expansion paragraph).

Data	Meth.	$V_{1}$	$\alpha_{95}$	$O_{95}$	$\alpha_{99}$	$O_{99}$	$\alpha_{100}$	$O_{100}$	S100
compas	asym	$100.0\pm 0.0$	1.000	0.139	1.000	0.139	1.000	0.139	3
compas	glob	$34.6\pm 56.6$	1.033	0.040	1.033	0.040	1.033	0.040	3
compas	mw	$34.6\pm 56.6$	1.033	0.039	1.033	0.039	1.033	0.039	3
compas	unreg	$35.4\pm 56.0$	1.033	0.041	1.033	0.041	1.033	0.041	3
german	asym	$97.8\pm 3.7$	1.017	0.031	1.017	0.031	1.017	0.031	3
german	glob	$53.0\pm 49.8$	1.033	0.038	1.050	0.056	1.050	0.056	3

Table S15: Fixed-inflation summary from three-seed CSVs.

V_{1}

is alpha-1 ray validity.

\alpha_{q}

is the first grid alpha whose validity reaches level

q

, averaged over the seeds that reach it (S100 counts the seeds that reach

q=1

Data	Target	Meth.	Sel. $\alpha$	Test $V$	Gap	Under	Over	$n$
compas	0.90	asym	1.000	$98.4\pm 2.7$	-0.013	0.000	0.038	128–128
compas	0.95	asym	1.003	$99.7\pm 0.5$	-0.005	0.000	0.042	128–128
compas	0.99	asym	1.007	$100.0\pm 0.0$	0.000	0.000	0.046	128–128
compas	0.90	glob	1.017	$96.6\pm 3.0$	0.000	0.001	0.021	128–128
compas	0.95	glob	1.020	$97.9\pm 2.4$	0.005	0.000	0.025	128–128
compas	0.99	glob	1.032	$99.7\pm 0.5$	0.003	0.000	0.039	128–128

Table S16: Validation-tuned inflation summary.

\alpha

is selected on rejected validation examples. Gap is validation minus test validity.

Data	Target	Group/method/rule	Valid.	Over	Bin. cost	Eff. cost
compas	0.95	Asym asym VT	0.984	0.038	0.116	0.039
compas	0.95	non-Asym glob VT	0.979	0.025	0.129	0.027
compas	0.99	Asym asym VT	0.997	0.042	0.055	0.042
compas	0.99	non-Asym unreg VT	0.997	0.036	0.049	0.036
compas	100%	Asym asym VT	1.000	0.046	0.046	0.046
compas	100%	non-Asym mw CI	1.000	0.059	0.059	0.059

Table S17: Matched-validity selected rows. VT denotes validation-tuned inflation and CI denotes constant inflation. For each dataset, target, and group (Asym, or any of the other three methods) the row is the candidate (CI at a grid

\alpha

, or VT at any tuning target) with the lowest mean overshoot among those whose validity reaches the target on all three seeds; the 100% row uses target 0.999. Costs use

C_{U}/C_{O}=5

Data	Method	Mask	Dims	Valid.	Under	Over	$n$
compas	unreg	protected_only	6	97.3	0.013	0.113	470
compas	unreg	strict	0	–	–	–	470
compas	mw	protected_only	6	99.5	0.000	0.052	473
compas	mw	strict	0	–	–	–	473
compas	glob	protected_only	6	99.5	0.000	0.040	476
compas	glob	strict	0	–	–	–	476

Table S18: Feature-freezing coordinate-projection audit. Validity is ray-hit validity on the projected score-space path, not causal or fully feasible recourse. Dashes indicate zero movable dimensions or excluded metrics.

Data	Cost	Best	$\alpha$	Cost
compas	binary	asym VT	1.007	0.046
compas	effort	unreg VT	1.017	0.024
fmnist	binary	unreg VT	1.078	0.294
fmnist	effort	unreg VT	1.050	0.153
german	binary	asym VT	1.020	0.023
german	effort	asym VT	1.007	0.011

Table S19: Best non-oracle winners at

C_{U}/C_{O}=5

. The last column is the mean cost over the three seeds, with sample standard deviations (ddof

=1

) 0.022, 0.006, 0.055, 0.051, 0.014 and 0.001 in row order.

Attempt	Intended mechanism	Observed outcome
Calibrated curvature target	Replace the fixed target $\delta$ of the asymmetric penalty by a per-point target $\min(2m/d_{p}^{2},\text{cap})$ , meant to clear the alpha-1 boundary with less excess curvature.	On COMPAS, Adult, and F-MNIST every calibrated point of the two-seed frontier run has lower validity and higher overshoot than some fixed- $\delta$ point, and all six three-seed configurations cost more than the fixed- $\delta$ penalty in both travel-error costs at $C_{U}/C_{O}=5$ .
Steepness penalty	Add $\lambda_{d}$ times the mean $d_{p}^{2}$ of rejected minibatch points to the asymmetric penalty ( $\delta=0.05$ ) to change the fixed-scale tradeoff.	For every $\lambda_{d}\in\{0.1,0.5,2\}$ , accuracy falls from $67$ / $80$ / $89\%$ at $\lambda_{d}=0$ to $53$ / $23$ / $49\%$ (COMPAS/Adult/F-MNIST), and at least one of three seeds rejects no test point.
Adult symmetric penalty sweep	Give MW/Global Hutchinson penalties larger regularization budgets on an undershoot-dominated dataset.	Validity remains far below the asymmetric penalty even when the diagnostic gap shrinks.

Table S20: Negative results of training-time attempts. The first two rows were regenerated with the current code; accuracy is plain accuracy and validity is ray-hit validity. S10 lists the scripts.

Figure S1: Quadratic-model gap $d_{\text{ray}}^{q}-d_{p}$ of Lemma 5.1 (equal to $g$ when $\phi^{\prime\prime}=\kappa$ on $[0,d_{\text{ray}}^{q}]$ ), its leading-order approximation, and the measured two-sided slab $\pm 8\hat{M}d_{p}^{3}/(3a)$ versus $\kappa$ , at the COMPAS-unregularized median $(\hat{M},d_{p},a)=(0.018,0.75,1.00)$ ( $n{=}800$ points). As $\hat{M}$ is a finite-grid lower bound, the slab is an empirical diagnostic, not a certified remainder; per point it contains $99\%$ of the points in regime $(\star)$ (certified enclosure in S3.1).

Result (section)	Code	Result, protocol and other files
Score-gauge audit (S1)	score_gauge_audit.py	results/score_gauge/
Probe bounds and collocation cancellation (S1)	verify_probe_escape.py : exact recovery on quadratic profiles, the $Md_{p}/3$ bound, the equivalence on trained models, the symbolic cubic case, and non-polynomial and kinked $C^{2,1}$ profiles
Segment-safe fallback (S1)	endpoint_segment_fallback.py recomputes the upper-tail fallback and checks the branch invariant	endpoint-audit files (S2 row)
Drift screen and ambiguity mass (S1)	verify_drift_screen.py ; float64 recomputation and grid scan: verify_drift_float64.py	criteria: DRIFT_SCREEN_FALSIFIER.md
Theorem 6.3 and Corollary Pointwise sharpness of the $d_{p}$ probe. (S1)	verify_one_query_lower_bound.py ; verify_oracle_lattice.py ; their result files check exact transcripts, regularity, first roots, finite margins and the separate parameter scalings	criteria: ONE_QUERY_LOWER_BOUND_FALSIFIER.md ; ORACLE_LATTICE_FALSIFIER.md
Adaptive radii (conjecture) and Theorem Many Queries: an Adaptivity Separation (S1)	verify_adaptive_q_query_bounds.py , which also asserts that no matching adaptive converse is claimed; its summaries are rechecked by claims_manifest.py	results/theory_audit/adaptive_q_query_bounds.csv ; criteria: ADAPTIVE_QUERY_LOWER_BOUND_FALSIFIER.md ; written argument for the conjecture, not part of this supplement: ADAPTIVE_Q_QUERY_FINDING.md

Table S21: Code and files behind each result. “Criteria” marks a protocol file committed before the run.

Checklist area	Where documented
Problem and assumptions	Main-paper definitions, theorem statements, and limitations.
Algorithms and training	Main setup, S3.2, and the scripts of the code archive.
Data and preprocessing	Main setup, S3.2, the data notes and instructions of the code archive.
Evaluation metrics	Main definitions and S2.
Compute and runtime	Main-paper checklist and the runtime and progress output of the scripts.
Randomness and seeds	Main setup, S3.2, the seed columns of the result files, and the commands of the code archive.

Table S22: Where the areas of the main paper’s reproducibility checklist are documented.

Explore similar work

Algorithmic Recourse Under Competition
Sep 30, 2026Shahin JabbariAlgorithmic Cores Trade-Off
Drexel University
The Curvature of Regret in Contextual Linear Optimization
Oct 1, 2026Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. SmithLinear Programming Regret
Auburn University Auburn, AL, USA · University of Alabama Tuscaloosa, AL, USA
The Role of Causality in Algorithmic Recourse
Jul 30, 2026Srikanth Avasarala, Varun Gupta, Shahin Jabbari +2Causal Reasoning High-Stakes Domains
Georgia Institute of Technology · Vector Institute · Drexel University +1

Sep 30, 2026, cs.LGJ/K move · Enter open · S save

Algorithmic Recourse Under Competition

Shahin Jabbari

Drexel University

Algorithmic Cores Trade-Off Decision Thresholds Competition

Open paper AskPDF arXiv

Algorithmic recourse provides individuals who have received undesirable outcomes from machine learning models with suggestions for minimum-cost improvements to achieve the desired outcome. A central assumption when computing recourse is that the decision rule remains fixed throughout the recourse implementation phase. We challenge this assumption in settings where individuals compete for limited resources. In such settings, widespread recourse implementation can change the acceptance threshold even when the scoring model that is used to evaluate individuals remains the same. This change in acceptance threshold can, in turn, invalidate the original recourse recommendations (i.e., following the recourse may not lead to the desired outcome). To address this problem, we introduce a framework called recourse under competition that jointly optimizes for recommendation recipients and the recommended score target they need to satisfy to balance the recourse cost and post-shift validity among initially rejected individuals. We develop an algorithm based on the Implicit Function Theorem and empirically analyze its performance. Experiments on synthetic and real datasets show that personalized score targets can achieve higher validity, albeit at a higher cost. In contrast, common score targets generally offer favorable cost-validity trade-offs for lower to medium validity values.

Abstract

Explore similar work

Algorithmic Recourse Under Competition

The Curvature of Regret in Contextual Linear Optimization

The Role of Causality in Algorithmic Recourse