- 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 , 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 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
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 for sup-norm score error . Theorem J.3 (p. 74) proves the matching minimax rate on a fixed full-action class at . Both use unique optimizers.
1. One fixed class, with global optimizer guarantees.
For , Lemma J.1 constructs uniform design, full actions, and a fixed query strip . In a protected chart, , with . The alternatives are
where the nonnegative smooth profiles are compactly supported, have maximum one, and near zero. The amplitude and upper scale are chosen before sample size. All and centers in a fixed interior rectangle belong to the same class.
The zero graph is exactly , where . For , squared boundary distance is
Small fixed amplitude controls the second-derivative term. The chart has and . 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 , whereas the chart optimum costs at most . 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 , , and the optimizer as . 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!
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.
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 g have an L1-Lipschitz gradient on the compact domain, and let each A(x) be nonempty and compact. Suppose an anchor ax∈A(x) satisfies g(ax)≥η>0. Define
Dx=z∈A(x):∥z−x∥≤∥ax−x∥.
Fix s0>0. At every z∈Dx with ∣g(z)∣≤η, require a unit direction v such that z+[0,s0]v⊆A(x) and ∇g(z)⊤v≥γ>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 Dx.
Theorem I.1 (p. 67) proves, for every continuous score s,
\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.