acceptodds
Under review as a conference paper at ICLR 2027

Learning Recourse from Data: Sharp Cost Rates and Limits of Optimal-Action Recovery

Abstract

Counterfactual recourse identifies admissible changes that lead to a favorable prediction. It is usually computed for a fitted predictor treated as fixed, yet that predictor is itself estimated from finite data. We study recovery of the minimum recourse cost and the complete optimal-action set defined by an unknown population decision score. In smooth nonparametric binary regression with Euclidean cost and known translated convex action sets, we give design and boundary–action conditions under which score estimation error controls cost error uniformly over queries. We establish matching minimax bounds on explicit full-action and binding-box families, including cases where constraints change the minimizing action and its cost. The two targets nevertheless have different statistical limits: on a fixed regular family with full observational coverage, minimum cost is uniformly consistently estimable, but the complete exact optimal-action set is not. Arbitrarily small score perturbations can break ties between distant optima while barely changing cost. Uniqueness and uniform quadratic growth provide a positive counterpart through an upper bound for action-location recovery. Controlled experiments demonstrate finite-query Euclidean recovery and show that changing action constraints can amplify cost error for the same fitted score. These results distinguish estimating the minimum required change from recovering every minimum-cost choice.

Primary area:
learning theory
Keywords:
algorithmic recourse, counterfactual explanations, statistical learning theory, minimax estimation, nonparametric regression

Reviews

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

This paper studies whether recourse estimated from finite data can be used for population recourse. It proposes a nonparametric plug-in estimator and proves sharp rates for minimum-cost recovery under regularity conditions. The paper shows that the complete exact action set may be unrecoverable, while unique actions can be recovered under quadratic growth. Experiments show that binding constraints amplify errors and that cost and action recovery improve with more data.

Critical strengths

The separation between minimum recourse cost and the complete optimizer menu is conceptually useful. The explicit dependence of the stability constant on boundary slope and feasible-direction alignment also provides a description of how action constraints amplify score-estimation error.

Critical weaknesses

1: The assumptions seem to be too strong. The result assumes an injective normal tube, a positive crossing slope, off-tube separation, boundary-action coverage, radial crossing through a feasible segment of common positive length whose normal alignment is bounded below by τ>0\tau>0, and feasible depth. I feel that these assumptions are too strong, and the authors should check whether they can be weakened.

2: Theorem 7 establishes only an O(∥g^−g∥∞)O(\sqrt{\|\hat g-g\|_\infty}) upper bound for action-location recovery. The paper provides neither a perturbation lower bound showing that the square-root dependence is tight nor a minimax lower bound. Its optimality therefore remains unresolved.

3: Theorem 2 obtains cost stability indirectly by proving the stronger Hausdorff stability of the entire feasible set. This requires radial crossing at every boundary-action intersection, including components irrelevant to the minimum. Indeed, Proposition 3 removes a tangential but nonoptimal feasible component: feasible-set recovery fails, while the minimum cost remains unchanged. Thus, I wonder whether the assumptions are for full feasible-set recovery rather than just cost recovery. I feel the paper does not characterize the sufficient and necessary conditions for cost recovery.

Questions for authors

See the weakness part.

4 comments
AuthorsOpenReview ↗

Response to aQKs (1/2): Cost-Specific Conditions and Sharp Rates

Thank you for separating scalar-cost stability from full feasible-set stability. Your observation about Proposition 3 is correct: the lost tangential component is nonoptimal, so cost remains unchanged. The revision now gives cost-specific conditions and rates in Appendix I. Our second comment addresses the two location lower bounds requested in W2.

W1/W3 — A local sufficient condition with a direct cost proof.

Let gg have an L1L_1-Lipschitz gradient on the compact domain, and let each A(x)A(x) be nonempty and compact. Suppose an anchor ax∈A(x)a_x\in A(x) satisfies g(ax)≥η>0g(a_x)\ge\eta>0. Define

Dx=z∈A(x):∥z−x∥≤∥ax−x∥.D_x=\\{z\in A(x):\lVert z-x\rVert\le\lVert a_x-x\rVert\\}.

Fix s0>0s_0>0. At every z∈Dxz\in D_x with ∣g(z)∣≤η|g(z)|\le\eta, require a unit direction vv such that z+[0,s0]v⊆A(x)z+[0,s_0]v\subseteq A(x) and ∇g(z)⊤v≥γ>0\nabla g(z)^\top v\ge\gamma>0. Constants are common over queries and class members. Anchors and directions are population certificates; the estimator need not know them. The segment need not remain in DxD_x.

Theorem I.1 (p. 67) proves, for every continuous score ss,

\min\\{\eta/2,\gamma s_0/2,\gamma^2/(2L_1)\\} \quad\Longrightarrow\quad \sup_{x\in Q}|\rho_s(x)-\rho_g(x)|\le2\varepsilon/\gamma.$$ Omit the last threshold when $L_1=0$. The anchor is feasible for both scores, so both minimizers lie in $D_x$. Along an admissible direction, $$g(z+tv)\ge g(z)+\gamma t-L_1t^2/2\ge g(z)+\gamma t/2$$ for $t\le\min\\{s_0,\gamma/L_1\\}$. Starting at a population optimizer, either it is already $s$-feasible or its score lies in $[0,\varepsilon)$; a step $2\varepsilon/\gamma$ makes it $s$-feasible. Starting at an $s$-optimizer, either it is already population-feasible or its population score lies in $[-\varepsilon,0)$; the same step repairs feasibility. The triangle inequality gives each direction of the cost bound. This avoids normal-tube, off-tube, and boundary–action coverage assumptions in the deterministic cost theorem. It imposes no crossing condition on distant noncompetitive components. Proposition I.5 (p. 71) verifies these conditions for the disk example while global radial crossing fails. The relaxation therefore covers an example excluded by the full-set theorem. ### **Checkable conditions and statistical rates.** For logistic scores, a signed coordinate with box slack at least $s_0$ has derivative $(1/4-g(z)^2)|w_j|$. A common positive coefficient bound and such slack at every competitive near-zero point verify the condition directly. More generally, Proposition F.6 proves it for compact convex actions with uniformly favorable anchors and derives a root-$n$ logistic cost guarantee. For the nonparametric result, Theorem I.2 (pp. 67–68) retains the statistical coverage and smoothness assumptions, with $d\ge2$, $\beta\ge2$, and fixed query/action budgets. A uniform score event of radius $e_{n,\delta}$ gives cost error at most $2e_{n,\delta}/\gamma$. Choosing $\delta=n^{-2}$ and bounding failure loss by $\sqrt d$ yields expected error of order $(\log n/n)^{\beta/(2\beta+d)}$. The matching lower bounds concern specified fixed full-action and binding-box problems. Lemma I.3 checks ascent at *every* near-level box action, using coordinate slack and derivative margins, including near-level points whose boundary projections are not admissible. Proposition I.4 embeds the hard families without altering their cost separation, KL bounds, or active constraints. The construction's global geometry verifies these examples; it is not required of every member of the local class. ### **What is necessary, and for which notion of recovery?** Under compactness and common positive-threshold feasibility, define $$v_x(t)=\min_{z\in A(x),\\,g(z)\ge t}\lVert z-x\rVert, \qquad \Omega_g(\varepsilon)=\sup_x\max\\{v_x(\varepsilon)-v_x(0),v_x(0)-v_x(-\varepsilon)\\}.$$ Lemma B.9 (p. 23) gives the exact identity $$\sup_{s\in C(\mathcal X):\\,\lVert s-g\rVert_\infty\le\varepsilon} \sup_{x\in Q}|\rho_s(x)-\rho_g(x)|=\Omega_g(\varepsilon).$$ Threshold inclusions prove the upper bound; the two shifts $s=g\pm\varepsilon$ give equality. The condition $\Omega_g(\varepsilon)\to0$ exactly characterizes query-uniform continuity against all continuous uniform score perturbations. The ascent theorem supplies primitive sufficient conditions for its linear bound. The identity is not a necessity theorem for learning in every restricted statistical model, which may exclude these shifts. The revision separates this deterministic characterization from the statistical upper and lower bounds.
AuthorsOpenReview ↗

Response to aQKs (2/2): W2 on Location Lower Bounds

W2 — Action-location lower bounds. Proposition J.2 (p. 73) gives a fixed-query displacement lower bound cεc\sqrt\varepsilon for sup-norm score error ε\varepsilon. Theorem J.3 (p. 74) proves the matching minimax rate (log⁡n/n)1/(d+4)(\log n/n)^{1/(d+4)} on a fixed full-action class at β=2\beta=2. Both use unique optimizers.

1. One fixed class, with global optimizer guarantees.

For d≥2d\ge2, Lemma J.1 constructs uniform design, full actions, and a fixed query strip Q∗=UQ×v0−s0Q_\ast=U_Q\times\\{v_0-s_0\\}. In a protected chart, g0(u,v)=κ(v−v0)g_0(u,v)=\kappa(v-v_0), with u∈Rd−1u\in\mathbb R^{d-1}. The alternatives are

gj,h−g0=αh2ϕ((u−uj)/h)χ((v−v0)/h),g_{j,h}-g_0=\alpha h^2\phi((u-u_j)/h)\chi((v-v_0)/h),

where the nonnegative smooth profiles are compactly supported, have maximum one, and χ=1\chi=1 near zero. The amplitude α>0\alpha>0 and upper scale h0>0h_0>0 are chosen before sample size. All 0<h≤h00<h\le h_0 and centers in a fixed interior rectangle belong to the same class.

The zero graph is exactly v=v0+f(u)v=v_0+f(u), where f(u)=−(α/κ)h2ϕ((u−uj)/h)f(u)=-(\alpha/\kappa)h^2\phi((u-u_j)/h). For x=(w,v0−s0)x=(w,v_0-s_0), squared boundary distance is

Fw(u)=∥u−w∥2+(s0+f(u))2,I⪯D2Fw⪯5I.F_w(u)=\lVert u-w\rVert^2+(s_0+f(u))^2,\qquad I\preceq D^2F_w\preceq5I.

Small fixed amplitude controls the second-derivative term. The chart has −s0/2≤f≤0-s_0/2\le f\le0 and ∥Df∥≤1\lVert Df\rVert\le1. Strong convexity gives one chart minimizer; its displacement bound keeps it inside the protected region. Vertical monotonicity identifies the favorable region there with the epigraph. Every favorable point outside the chart retains cost at least s0+Δactives_0+\Delta_{\rm active}, whereas the chart optimum costs at most s0s_0. This fixed exterior gap makes the optimizer globally unique.

Growth is checked for all feasible points, not only on the boundary. Write a feasible chart point as z=(u,v0+f(u)+t)z=(u,v_0+f(u)+t), t≥0t\ge0, and the optimizer as z∗=(u∗,v0+f(u∗))z_\ast=(u_\ast,v_0+f(u_\ast)). Then

\ge\tfrac12\lVert u-u_\ast\rVert^2+t^2,\qquad \lVert z-z_\ast\rVert^2\le3\lVert u-u_\ast\rVert^2+2t^2.$$ The cube diameter bounds the sum of the two costs by $2\sqrt d$. Inside the chart, excess cost is therefore at least $\lVert z-z_\ast\rVert^2/(12\sqrt d)$. Outside it, the fixed gap gives the paper's truncated quadratic-growth condition with common $r_\ast=1$ and $\lambda=\min\\{(12\sqrt d)^{-1},\Delta_{\rm active}\\}$. Common normal tubes require a separate check. Construction D.1 and Propositions D.2–D.4 provide positive baseline reserves. Lemma J.1 bounds the tube-map displacement by $E_0\le\sigma_{\rm tube}/4$ and its derivative defect by $E_1\le m_{\rm tube}/2$. Within a chart, the lower Lipschitz constant is $m_{\rm tube}-E_1>0$; pairs outside a common chart retain $\sigma_{\rm tube}-2E_0>0$. The derivative defect contains an $O(\alpha)$ term at $\beta=2$, controlled by choosing amplitude first, not merely shrinking $h$. Crossing, range, and off-tube margins are common as well. ### **2. A fixed-query perturbation lower bound.** Choose a profile point $v_\dagger$ with nonzero gradient. At $w_j=u_j+hv_\dagger$, we have $\lVert\nabla F_{w_j}(w_j)\rVert\ge ch$. The gradient's Lipschitz constant is at most five, so the optimizer moves at least $ch/5$, while $\lVert g_{j,h}-g_0\rVert_\infty=\alpha h^2$. Fixing $w_\ast$ and taking $u_h=w_\ast-hv_\dagger$ keeps the query fixed. Setting $h=\sqrt{\varepsilon/\alpha}$ proves displacement at least $c'\sqrt\varepsilon$ within the same unique-optimizer class. ### **3. Minimax lower and upper bounds in the same loss.** Pack $M_h\gtrsim h^{-(d-1)}$ separated centers. At each matched query, its own bump moves the optimizer by order $h$; every other bump leaves that query's optimizer exactly at baseline. The maximum Hausdorff distance over these finite witnesses separates all targets by order $h$ and is bounded by the query-uniform loss $L_{\Pi,Q_\ast}$. The bump has amplitude $h^2$ and support volume $O(h^d)$, so the common Bernoulli margin gives sample KL at most $Cnh^{d+4}$. Taking $h=c(\log n/n)^{1/(d+4)}$ makes average KL a small fraction of $\log M_h$. A nearest-target decoder and Fano yield expected location loss at least a constant times $h$ for every estimator. For the upper bound, the uniform score radius at $\beta=2$ is $e_n=O((\log n/n)^{2/(d+4)})$. Theorem 7 gives $O(\sqrt{e_n})$ on the event; bounded loss and failure probability $n^{-2}$ give the same expected rate. Together these bounds prove $$\inf_{\widetilde\Pi_n}\sup_{\theta\in\Theta_\ast}\mathbb E_\theta L_{\Pi,Q_\ast}(\widetilde\Pi_n,\Pi_\theta) \asymp(\log n/n)^{1/(d+4)}.$$ Here $\Theta_\ast$ is the fixed full-action class at $\beta=2$. Higher-smoothness and binding-action location rates remain open. Figure J.1 illustrates local scaling; the class-membership and minimax claims are proved analytically.

I thank the authors for the detailed responses. I will take the responses into my final consideration. Thank you very much!

AuthorsOpenReview ↗

Sincere thanks for your careful consideration

Thank you very much for taking the time to carefully consider our responses. We truly appreciate your thoughtful and constructive feedback. If there is anything we can clarify further, we would be grateful for the opportunity.

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

The paper studies the statistical estimation of the recourse function --- the optimal value solution map for an individual's optimization problem in decision-making under unknown Bayes classifier decision rules. In particular, the paper models the recourse function as the minimal cost of feasible actions that an individual can take to achieve a desired outcome. The algorithm observes (Xi,Yi)(X_i, Y_i) pairs sampled from the data distribution and estimates the recourse function using a nonparametric approach. The paper provides optimal rate of convergence for the recourse value under Hölder smoothness assumptions; while estimation of the set of maximizing actions is not possible in general, the paper identifies sufficient conditions where this is possible. The paper also provides experimental studies to demonstrate the performance of the proposed algorithm.

Critical strengths

The statistical estimation framework for the recourse function appears to be novel and interesting, and the paper provides a rigorous theoretical analysis of the convergence rates under certain smoothness assumptions.

Critical weaknesses
  • The paper focuses on classical Hölder class and local polynomial estimation methods, which limit the applicability of the results to modern settings where flexible machine learning methods are more preferred. It also seems that the current analysis depends heavily on the smoothness class.
  • The problem is reduced to a variant of the classical level-set estimation problem, and not too many new technical ingredients are introduced. The paper could benefit from a more detailed discussion of the technical challenges and how they are addressed in the proposed approach.
Questions for authors
  • On the modelling side, since the Bayes classifier is unknown and not directly implemented by the decision-maker, why is it reasonable to assume that the individual aims to optimize their actions based on the Bayes classifier's decision rules?
  • If we use other modelling assumptions on the unknown decision score function gg, to which extent can the proposed estimation framework be generalized? For example, what if we assume gg is a linear-logistic function or other generalized linear models?
4 comments
AuthorsOpenReview ↗

Response to U1bK (1/2): Population Benchmark and Model Scope

Thank you for the questions about the population benchmark, model scope, and the relation to level-set estimation. We address these below. Our accompanying comment gives the assumptions and derivation of the logistic-regression guarantee in Proposition F.6 (pp. 54–55).

Q1 — The individual acts on the fitted model. Why study a population target?

The operational recommendation is computed from the fitted score g^\widehat g. We do not assume that an individual observes or optimizes an unknown Bayes rule. The population score g(z)=Pr⁡(Y=1∣X=z)−1/2g(z)=\Pr(Y=1\mid X=z)-1/2 defines the benchmark for measuring sampling error in the minimum-cost function induced by the fitted predictor.

As with population risk, an unknown target can quantify uncertainty in a data-dependent decision. Here the learner targets the conditional probability, and we ask how sampling error affects the induced recourse cost. We have clarified this interpretation in the Introduction and Appendix F.6.

It also has a concrete refitting consequence. With the same population, queries, and action constraints, write Ei=sup⁡x∈Q∣ρg^i(x)−ρg(x)∣E_i=\sup_{x\in Q}|\rho_{\widehat g_i}(x)-\rho_g(x)|. Then

sup⁡x∈Q∣ρg^1(x)−ρg^2(x)∣≤E1+E2.\sup_{x\in Q}|\rho_{\widehat g_1}(x)-\rho_{\widehat g_2}(x)|\le E_1+E_2.

If Ei≤riE_i\le r_i with marginal failure probability δi\delta_i, cost disagreement is at most r1+r2r_1+r_2 with probability at least 1−δ1−δ21-\delta_1-\delta_2, without independent refits. This controls minimum costs across fits targeting the same population score. It does not ensure that a particular action stays valid after retraining or establish causal effects. For a permanently fixed classifier, validity under that classifier remains the operational question.

Q2/W1 — The framework is not tied to local-polynomial fitting.

The deterministic transfer accepts any continuous fitted score with a uniform error guarantee. Local-polynomial regression supplies the sharp rate for our nonparametric class; it is not built into the recourse functional.

Proposition F.6 gives a complete logistic calculation: correct specification, bounded parameters, a positive feature Gram bound, and convex actions with uniformly favorable anchors imply a query-uniform root-nn cost bound at fixed dimension, confidence, and constants. Neither a design-density lower bound nor a global normal tube is required. Our accompanying comment gives the derivation.

For a GLM score gϑ(z)=h(ϑ⊤u(z))−1/2g_\vartheta(z)=h(\vartheta^\top u(z))-1/2, a continuous feature map bounded by BB and an LhL_h-Lipschitz inverse link give

\le L_hB\lVert\widehat\vartheta-\vartheta\rVert.$$ A parameter bound for that model can then be combined with appropriate population/action geometry (Proposition F.5, p. 53). Continuous flexible fits, including ReLU networks, can enter the same interface when a uniform score-error event is established. Under misspecification, estimation and uniform approximation errors add and must meet the activation threshold. Average prediction accuracy alone does not supply this event. Rates remain specific to the statistical class. Model structure can also improve location rates: full-action affine-logistic recourse has root-$n$ location recovery under nonzero slope, a uniform unfavorable-query margin, and uniformly interior projections (F.8, p. 55). ### **W2 — What must be proved beyond level-set estimation?** For each query, the favorable region is intersected with a different action set before minimizing distance. Boundary accuracy alone does not control these intersections: Proposition 3 exhibits a disappearing tangential component. For scalar cost, the revised Theorem I.1 avoids controlling irrelevant components by correcting only competitive near-threshold actions. The binding-box lower bound in Theorem 4 addresses a separate difficulty. Its alternatives must remain statistically close while their *constrained minimum costs* separate. Appendix D.2 preserves an active face, localizes the optimizer, and excludes cheaper actions at competing bumps. The constraints change the population optimum and its cost throughout the retained family. Boundary separation by itself would not prove this claim. Finally, Theorem 6 realizes cost learnability and failure of complete-menu recovery in one fixed, fully covered statistical family. We credit classical estimation and stability tools; the contribution is the resulting distinction between constrained cost and action recovery. Table 1 (p. 8) now separates the targets, assumptions, and guarantees.
AuthorsOpenReview ↗

Response to U1bK (2/2): Logistic Recourse Guarantee and Proof

This comment provides the logistic-regression result requested in Q2 and addresses W1 about dependence on the nonparametric model. Proposition F.6 (pp. 54–55) verifies the statistical and action conditions together.

1. Model, estimator, and action assumptions.

Let z∈[0,1]dz\in[0,1]^d, u(z)=(z,1)u(z)=(z,1), p=d+1p=d+1, B=pB=\sqrt p, and

\vartheta_0=(w,b),\qquad \lVert\vartheta_0\rVert\le R.$$ Assume i.i.d. correctly specified logistic observations and $\mathbb E[u(X)u(X)^\top]\succeq\nu I_p$ for $\nu>0$. Fit empirical logistic loss over the radius-$R$ parameter ball, with $R>0$. Each known action set $A(x)$ is compact, convex, and contained in the cube. For a fixed $0<\eta<1/4$, require an anchor $a_x\in A(x)$ with $g(a_x)\ge2\eta$ at every query. Constants are uniform over the fixed query set $Q$. ### **2. Why these action conditions give feasible ascent.** Define $\ell(r)=\log[(1/2+r)/(1/2-r)]$, $\Delta_\ell=\ell(2\eta)-\ell(\eta)$, and $$s_0=\Delta_\ell/R,\qquad \gamma=(1/4-\eta^2)\Delta_\ell/\sqrt d,\qquad L_1=R^2/4.$$ At any admissible $z$ with $|g(z)|\le\eta$, the anchor satisfies $w^\top(a_x-z)\ge\Delta_\ell$. For $v=(a_x-z)/\lVert a_x-z\rVert$, the bounds on $w$ and the cube diameter imply $$\lVert a_x-z\rVert\ge s_0,\qquad \nabla g(z)^\top v =(1/4-g(z)^2)\frac{w^\top(a_x-z)}{\lVert a_x-z\rVert}\ge\gamma.$$ Convexity makes $z+[0,s_0]v$ admissible. The gradient is $L_1$-Lipschitz because $|\sigma''|\le1/4$. This verifies ascent on the entire near-zero band, including all competitive actions. An empty band makes this directional condition vacuous. For a box, maximize $w^\top z+b$ by choosing each coordinate endpoint according to the sign of $w_j$. The anchor condition is that this maximum is at least $\ell(2\eta)$, uniformly over queries. The box may still change the minimum-cost action. These are population conditions; a fitted-model grid check is a diagnostic, not their statistical certification. ### **3. Parameter concentration and uniform score error.** Put $m_R=\min_{|t|\le RB}\sigma'(t)>0$. For $\delta\in(0,1)$, assume $$n\ge\frac{8p^2B^4}{\nu^2}\log\frac{4p^2}{\delta}.$$ For $G_n=n^{-1}\sum_i u(X_i)u(X_i)^\top$, entrywise Hoeffding bounds give $G_n\succeq(\nu/2)I_p$ with failure probability at most $\delta/2$. The empirical Hessian is then at least $(m_R\nu/2)I_p$ throughout the parameter ball. A second Hoeffding bound controls the loss gradient at the true parameter by $B\sqrt{2p\log(4p/\delta)/n}$, again with failure probability at most $\delta/2$. Constrained optimality and strong convexity give, on their intersection, $$\lVert\widehat\vartheta-\vartheta_0\rVert \le R_{n,\delta}:=\frac{2B}{m_R\nu}\sqrt{\frac{2p\log(4p/\delta)}n}.$$ This also covers a true parameter on the ball boundary. The sigmoid's $1/4$-Lipschitz property gives uniform score error $e_{n,\delta}=BR_{n,\delta}/4$ on the same event. ### **4. From score error to minimum cost.** Require $$e_{n,\delta}\le\varepsilon_{\rm a} :=\min\\{\eta/2,\gamma s_0/2,\gamma^2/(2L_1)\\}.$$ The anchor remains feasible for the fitted score and bounds both optimal costs. From either optimizer, feasible ascent repairs any disagreement in feasibility by moving at most $2e_{n,\delta}/\gamma$. Taylor's inequality supplies score gain at least $\gamma t/2$ along this step. Applying the triangle inequality to both corrections gives, with probability at least $1-\delta$, $$\sup_{x\in Q}|\rho_{g_{\widehat\vartheta}}(x)-\rho_g(x)| \le\frac{BR_{n,\delta}}{2\gamma} =\frac{B^2}{\gamma m_R\nu}\sqrt{\frac{2p\log(4p/\delta)}n}.$$ There is no additional union bound over queries. Empty fitted feasible sets receive the bounded fallback cost $\sqrt d$; they cannot occur on this event. This is a complete query-uniform root-$n$ guarantee at fixed dimension, confidence, and constants, with explicit sample and activation thresholds. The feature Gram bound replaces the density requirement of local-polynomial regression, and the favorable-anchor argument replaces global tube and intersection assumptions for this cost result. Correct specification, Gram nondegeneracy, and a uniform favorable margin remain substantive requirements. Uniformity over a model family requires common constants; optimal dimension dependence is not claimed.

Thanks for the response and the new results. They addressed some of my concerns, and I increased my score accordingly.

Thank you very much for reconsidering our paper and updating your rating. We sincerely appreciate your time and thoughtful feedback.

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

The paper studies how accurately recourse can be learned when the decision score is estimated from finite labeled data. It considers two targets: (a) Minimum recourse cost: What is the smallest change needed to obtain a favorable prediction? Here, “cost” measures distance between the original and modified features; and (b) Optimal-action set: What are all the ways to obtain that favorable prediction with the smallest possible cost? There may be several equally good options. Both are evaluated against an unknown population score, uniformly over a fixed query set.

The key contributions of this paper are three-fold. (1) Statistical formulation and geometric error transfer: Under suitable observational coverage, smoothness, and boundary–action geometry conditions, the authors show that score-estimation error controls the minimum recourse cost error. (2) Sharp learning rates under binding action constraints: They establish the rate (log⁡nn)β2β+d\left( \frac{\log n}{n} \right)^{\frac{\beta}{2 \beta + d}}, with matching minimax lower bounds on explicit families with unrestricted actions and binding box constraints. (3) Statistical distinction between estimating recourse cost and recovering optimal actions: They also construct a regular family where cost is consistently estimable but the complete optimal-action set cannot be recovered uniformly: small score changes can break ties between distant optima while barely changing cost. Uniqueness and quadratic growth provide sufficient additional conditions for action-location recovery.

Validation combines controlled simulations with analyses of Banknote and HTRU2 data. The simulations show decreasing cost and action-location errors as sample size grows, and isolate how binding constraints amplify cost error while holding the fitted score fixed. The public-data experiments examine whether geometric diagnostics help explain action displacement after model refitting, with benefits varying across configurations.

Critical strengths

(S1) The paper establishes a meaningful statistical benchmark for constrained recourse. The upper bound explains how the score estimation error translates into recourse cost error. The matching minimax lower bounds show that this difficulty remains in examples where action constraints genuinely change the optimum. Preserving binding constraints throughout the statistically difficult alternatives seems to be substantive. Together with the uniform upper bound, this establishes a sharp statistical benchmark for the constrained recourse problem. This strengthens the contribution by showing how estimation accuracy and action geometry jointly determine what can be learned from data.

(S2) The paper clearly separates two different learning problems. Estimating how much change is necessary can be statistically easier than recovering every optimal action to make that change. The fixed-family impossibility result makes this distinction precise under the full observational coverage and common regularity conditions. The positive result under uniqueness and quadratic growth also identifies additional structure that allows the optimal-action recovery. Together, these results give the paper a clear message with consequences for how recourse guarantees should be interpreted.

Critical weaknesses

(W1) I have some concerns about the independent novelty of the geometric and action-recovery results. The rate exponent comes from the familiar non-parametric estimation theory literature, the menu impossibility result exploits instability near tied optima, and the positive location bound follows from the quadratic growth. The binding-constraint lower bound is the strongest contribution, but several other results formalize familiar principles in the recourse setting. This limits how much weight I place on them as separate theoretical advances.

(W2) It seems that prior work also studies the statistical validity and distance-based robustness of counterfactual explanations [1]. The contribution of this paper therefore rests on the precise statistical formulation, uniform guarantees, and constrained lower-bound constructions.

(W3) The assumptions also limit practical reach: the framework uses smooth scores, strong coverage and geometric conditions, and known full-dimensional convex action sets. Immutable features, discrete changes, and causal interventions require further development. Also, the impossibility result specifically concerns preserving the complete optimal-action menu; it does not establish that useful approximate recommendations are impossible.

[1] Emilio Carrizosa and Antonio Navas-Orozco, "Building robust counterfactual explanations with statistical guarantees", EURO Journal on Computational Optimization (2026).

Questions for authors

No specific questions whose answers could materially affect my overall assessment.

1 comment
AuthorsOpenReview ↗

Response to Reviewer DENe: Contribution and Binding-Constraint Lower Bound

Thank you for recognizing the binding-constraint lower bound and the distinction between cost and complete-menu recovery. We agree that the contribution should be assessed through these statistical conclusions, with classical estimation and stability arguments credited as their foundations. We have clarified this positioning and added a compact map of targets, assumptions, and guarantees (Table 1, p. 8).

W1 — What is new, and what uses established principles?

The Hölder rate exponent, instability near tied optima, and the quadratic-growth conversion are familiar ingredients. Our claim concerns what can be recovered from data under action constraints.

The binding-box lower bound in the submission remains central. Theorem 4 constructs statistically difficult alternatives for which the constraints change both the population optimizer and its cost. The proof localizes perturbed optima, preserves a genuinely active face, and excludes cheaper competing bumps, all within a fixed regular class. Boundary separation alone would not establish the required cost separation after constrained minimization (Appendix D.2, pp. 37–44).

The cost–menu separation also concerns a fixed statistical family. Theorem 6 shows that cost can be uniformly consistently estimated while the minimax error for the complete exact menu stays bounded away from zero. The family has full observational coverage and common regularity constants. The tie-breaking mechanism is familiar; the contribution is its realization together with cost learnability in this statistical setting.

W2 — Relation to statistical validity guarantees

We have clarified the comparison with Carrizosa and Navas-Orozco (2026) in Section 2. Their statistical guarantees for counterfactual explanations address validity under an unknown ground-truth model and its relationship to parameter robustness. Our targets are the population minimum-cost function and exact optimizer correspondence, with uniform estimation losses and minimax bounds. Whether a recommendation is valid and how accurately the population minimum cost can be estimated are distinct questions, even when both use a distance objective.

W3 — Scope and the complete-menu target

We agree that Theorem 6 does not rule out useful approximate recommendations. The complete menu matters when a later preference selects among equally costly actions: Proposition 5 identifies its Hausdorff loss with worst-case distortion of the best attainable Lipschitz secondary utility. Approximate menus and preference-specific choices remain separate targets; Section 5 now makes this distinction explicit.

The revision also weakens the geometry needed for scalar cost. Theorems I.1–I.2 (pp. 67–68) require feasible ascent only at competitive near-threshold actions and establish sharp rates on specified full-action and binding-box families. This removes global intersection regularity from the cost-only result. Smoothness and coverage remain in the nonparametric statistical class; discrete, immutable-feature, and causal action models still require separate analysis.

We have organized the revision around these distinctions so that the assumptions and conclusions for each target can be read together.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.