acceptodds
Under review as a conference paper at ICLR 2027

Finite-Sample Guarantees for Convex Neural Preference Learning

Abstract

Pairwise preference data are commonly used to train reward models. Yet existing statistical analyses of pairwise preference learning often assume linear reward heads, leaving finite-sample guarantees for nonlinear heads less developed. We study a Bradley–Terry estimator that fits a two-layer ReLU reward head on fixed representations through a convex activation-pattern formulation. The estimator jointly fits the preference likelihood and selects among retained activation patterns using a block-sparsity penalty. Conditioning on the representations and retained patterns, we analyze squared error in reward differences on the observed comparisons. For rewards supported on at most of patterns in dimension with samples, we establish a minimax lower bound of order under a sparse design condition. We further derive a prediction error bound of order for the convex estimator under standard conditions. When is known, a sharper calibration of the same estimator achieves the minimax lower bound rate under a stronger restricted eigenvalue condition. Experiments with synthetic rewards, language-model representations, and five preference datasets assess reward recovery and held-out preference prediction.

Primary area:
learning theory
Keywords:
Preference learning, Reward modeling, Convex neural networks, Minimax rates, Structured sparsity

Reviews

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

This paper studies the preference learning sample complexity with a two-layer ReLU network. Previous work needs to estimate on full dictionaries, which is unefficient. They provide tight bounds using a sparse-recovery estimator under some assumptions such as the ground truth reward function is sparse with respect to activation patterns. The basic idea is that they only have to sample several patterns, which is inherited from Pilanci & Ergen, under the assumption that these sampled patterns are enough to recover the ground truth reward function. They also conduct some basic experiments using last-layer features of LMs, and the preference learning results of their proposed convex optimization is better than two convex baselines and worse than the nonconvex baseline.

Critical strengths

This paper studies the sample complexity of preference learning with a two-layer ReLU network, which is a relatively novel topic. The established estimation rates are systematic.

Critical weaknesses
  • The theoretical contributions look marginal. The proof ideas are largely built on [1,3] and their combinations, and thus it is unclear what new statistical insight the paper provides beyond existing results [1,2,3].
  • The assumption this paper adopted is unjustified that the true reward margins admit an exact sparse representation over the randomly retained activation patterns, as stated at the beginning of Section 3. And the magnitude of Eapp\mathcal E_{app} is unjustified.
  • It is unconvincing that randomly sampled patterns can satisfy the coverage argument as stated in Remark 2, since the π⋆\pi_\star is unbounded. And the choice of only P=20 retained patterns in the experiments is not grounded.
  • The experimental results don't indicate improvement (even worse) over nonconvex baselines as can be seen from Table 1,2.

[1] Improved error rates for sparse (group) learning with Lipschitz loss functions. Dedieu.

[2] Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective. Yao et al. ICML 2025.

[3] Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer network. Pilanci & Ergen. ICML 2020.

Questions for authors

Please address issues listed in "Weakness". And the real-data regularization coefficient is much smaller than the theoretical value, please justify it.

4 comments

Thank you so much for your valuable feedback.

W1: Our main statistical contribution is to characterize how accurately pairwise comparisons determine the reward differences of a two-layer ReLU model when only ss of PP retained activation patterns are active. Pilanci and Ergen [3] provide the convex reformulation on which we build, but do not characterize this estimation risk. Yao et al. [2] establish minimax rates for coordinate-sparse linear rewards, whereas in our setting, sparsity is over activation patterns. Even if the active set were known, estimating the reward margins would still require estimating a dd-dimensional coefficient vector for each pattern. Our lower-bound proof makes the difference between [2] and ours explicit: varying coefficients on a fixed support gives the sd/nsd/n cost, while varying the support gives the slog⁡(P/s)/ns\log(P/s)/n cost. Moreover, the fundamental difference is that we extend the linear reward assumption in [2] to nonlinear reward assumption. This extension is nontrivial even on a fixed design because, for each ReLU activation pattern, the observed margins depend only on the difference between two cone-constrained coefficient vectors, while the regularizer depends on both vectors separately. Dedieu [1] is the source of the ordered-score argument we adapt in Theorem 3. The group-sparse rate itself has a precedent in [1], but its Group Lasso result does not directly cover our estimator: the observed margins depend on each pattern’s positive and negative ReLU coefficients only through their difference, and the penalty induced on this difference depends on the activation cone.

Beyond these, we have also extended our theoretical analysis to out-of-sample prediction in this revision, which is challenging and, to our best knowledge, new in existing literature. Specifically, we establish a new, independent prediction error bound for unseen comparisons, following the same distribution as training comparisons. This result complements our existing fixed-design guarantees and strengthens the practical relevance of the theoretical framework. The new theorem and its proof are provided in Section 3.4 and Appendix I of the revised manuscript. We believe this provides additional theoretical contribution to the literature.

W2: We acknowledge that exact sparse realizability is a substantive modeling assumption, which is precisely why we developed Corollary 1 to cover settings in which the true reward margin does not admit an exact sparse representation. Specifically, Corollary 1 bounds the prediction error by the best sparse approximation error plus a statistical estimation term.

We agree that the magnitude of the approximation error was not adequately investigated in the original manuscript. We have therefore revised Section 4.1 to examine the decomposition into approximation and estimation errors quantitatively. In the settings considered, the approximation error remains relatively small and exhibits expected decay toward zero as dd and PP increase, holding all other parameters fixed. Please see the revised Section 4.1 for further details.

W3: Indeed, Remark 2 extends the theoretical guarantees for the proposed method from a particular retained set of activation patterns to the full collection of activation patterns, which requires additional conditions. Thank you for raising an insightful question about the interpretation of π⋆\pi_\star, which governs the probability of sampling the patterns needed for this extension. The stated condition assumes that π⋆\pi_\star is a fixed positive constant, however small; this ensures that the success probability converges to one as PP grows. We agree that this condition is sufficient but not necessary. More generally, π⋆\pi_\star may decay with PP, provided that Pπ⋆→∞P\pi_\star\to\infty.

In the revised experiments in Section 4.1, we extensively examine sensitivity to the pattern budget by varying PP from 20 to 110 and reporting both approximation and estimation errors. The results support the use of P=20P=20 in the subsequent experiments as a computationally tractable baseline that nevertheless delivers strong empirical performance.

W4: Thank you for this observation and we are glad to have the opportunity to clarify the expected outcome of comparisons with the nonconvex baseline. Our main contribution is a finite-sample theory for estimating nonlinear reward differences from pairwise preferences through a convex formulation. Accordingly, the comparison evaluates how closely the estimator covered by our theory performs relative to a directly trained two-layer ReLU network. Comparable performance is expected because both methods fit Bradley–Terry reward models using the same input representations, although the convex estimator is restricted to the retained activation patterns. The nonconvex baseline may perform better in many settings because it can adapt its activation patterns during training. When it performs slightly worse, we believe that optimization variability may be one contributing factor.

Unlike the nonconvex baseline, our estimator enjoys finite-sample theoretical guarantees while remaining empirically competitive and occasionally outperforming the baseline. Specifically, in Table 1, the nonconvex baseline achieves a lower mean MSE, whereas our estimator achieves higher mean directional accuracy and AUC under all three nonlinear data-generating processes. In Table 2, the methods differ in mean held-out accuracy by at most 0.40 percentage points on four of the five datasets, with a larger difference of 2.02 percentage points on WebGPT.

Q1: Theorem 2 and 3 give explicit choices of λ\lambda that suffice for their respective high-probability bounds. However, these choices need not minimize prediction error on a given dataset. We therefore use cλthmc \lambda_{\text{thm}}, where multiplier cc lets us adjust the overall penalty strength to the dataset while retaining the scaling prescribed by the theory. We can select cc empirically without knowing the underlying reward parameters. In the experiments, we calibrate the multiplier cc using a held-out validation split on an independent dataset. Such an approach that giving a theoretical tuning parameter and using cross-validation to tune the hyperparameter in practice is commonly used in statistical literature.

Thank you again for your careful review. We hope these revisions address your concerns, and we would be grateful if you would consider updating your assessment. We would also be happy to clarify any remaining questions or respond to further comments.

Thank you for your rebuttal. My concerns regarding to W4, Q1 are resolved. W2 is also somehow resolved by empirical supports. For other concerns:

  • My concern regarding to the theoretical contribution as stated in W1 is not fully resolved, as the same-distribution result is truly technically nontrivial yet I still cannot see distinct insights. The technical correctness of the newly added results cannot be easily verfied during the discussion. However, I think the major idea is still that this setting can be reduced to a simple regression problem after correctly handling the nonlinear activation patterns, which is not an original idea.
  • My concern regarding to the π⋆\pi^\star issue is not fully resolved. As a theoretical result, the magnitude of π⋆\pi^\star is not well understood, and even though the PP can be increased to make the exponent Pπ⋆P\pi^\star large enough, PP would also increase the estimation error. However, the empirical supports for approximation error can somehow relieve this issue. So W3 should not be viewed as a big issue.

To conclude, most soundness issues are resolved, though I still think this paper is more like a borderline result, and am personally not interested in the results. I cannot confidently recommend acceptance, though I'm ok with this paper being accepted. I hope the AC can provide their insights on this.

We are happy to know that some concerns are addressed. However, we would like to clarify that the out-of-sample theory cannot be reduced to a simple regression problem. Specifically, the challenge appears on a new input xx, where the pp-th term in the fitted reward r^(x)\widehat r(x) is (vp⊤x)+−(wp⊤x)+(v_p^{⊤} x) _ {+} - (w_p^{⊤} x) _ {+}. Since up=vp−wpu_p = v_p - w_p, two different decomposition of the same upu_p can give identical training margins but different predictions. Our out-of-sample analysis bounds the angular diameters of the training activation cones and uses the fitted path norm to control how much these predictions can differ. Under the stated assumptions, this geometric control allows the reconstructed network to achieve the same O(s(d+log⁡P)/n)\mathcal O\left(s(d+\log P)/n\right) prediction error rate on new comparisons as in our standard in-sample bound.

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

The paper studies an estimator for a Bradley-Terry loss on pairwise preferences via a convex formulation. The convex estimator is fitted as a two-layer ReLU network on activation patterns extracted from fixed representations. The authors derive the minimax rate for the proposed estimator and evaluate their formulation in a set of experiments, including on synthetic and human-generated preference datasets.

Overall, while the contribution feels a bit incremental, the paper seems well-executed. I would encourage the authors to answer some of my raised questions, mostly connected to the empirical evaluation.

Critical strengths
  • The paper is quite dense, but still comprehensible and well-written
  • Empirical results are nice to support the formal contribution in general, even though the results could be even stronger to showcase the derived guarantees
  • The derivations of bounds and formal definitions seem correct
  • The method performs well against the direct precursor and linear baseline, though it performs a bit worse than the non-convex baseline
Critical weaknesses
  • The contribution feels pretty incremental over COALA; it combines the existing convex reformulation with a Bradley-Terry loss and applies the same ADMM solver.
  • I feel some of the assumptions seem quite strong compared to the initial framing, e.g., the bounds partially rely on distinct coefficient vectors generating well-separated margins, but with an increasing number of activation patterns P this separation seems hard to ensure, i.e., activation patterns may only differ on a single training point, and constants seem to trend towards zero, particularly when working with full pattern sets.
  • Some issues currently exist in the experiments of Section 4; see questions.
Questions for authors
  • Can you share some additional results like training curves for the non-convex baseline? How was the number of epochs chosen?
  • Can you give a runtime comparison of the presented methods? For practical applicability, it would be interesting to compare, e.g., the non-convex baseline with the proposed method.
  • Figure 1: I am not sure what to take away from here. I see the dependency on „n“, and also an initial increase in „s“, however, increasing d and log P does not seem to indicate any notable pattern, and " s „saturates“ quite quickly at a value of 3 instead of increasing approximately linearly. Could you maybe comment on it? What could be the reason? Otherwise, I would probably qualify the sentence „consistent with the qualitative dependence predicted by our theory“/„provide empirical support for the main scaling behavior“
  • Can you give some details on the regularization multipliers „c“ used in the training experiments? In Theorem 2, we choose lambda according to the given formula (also reported below Table 4). Why is „c“ included as a multiplier within the formula? Was its value tuned/ablated?
3 comments

Thank you so much for your valuable feedback.

W1: We agree that COALA is closely related to our work and provides important motivation. Nevertheless, our method differs from COALA in several substantive aspects. COALA employs a two-stage estimator: it first trains a convex neural network under the squared loss, then freezes the first-layer weights and fine-tunes only the output layer using the Bradley–Terry loss. Although COALA does not provide a statistical analysis of this estimator, such an analysis could build on standard theory for fixed-feature models. In contrast, our method jointly estimates the coefficients associated with the retained activation patterns under the Bradley–Terry loss and a sparsity-inducing penalty through a single convex program. To our knowledge, a rigorous statistical analysis of this joint formulation has not been developed in the existing literature. Providing such an analysis constitutes our main theoretical contribution: we establish finite-sample guarantees and a minimax characterization of reward-difference estimation, going beyond the optimization-convergence guarantees established for COALA. Finally, ADMM is only one generic solver for the resulting convex problem; other optimization algorithms could also be used in practice.

W2: Assumptions 1–4 are motivated by standard regularity conditions in high-dimensional statistics, including the sparse- and restricted-eigenvalue conditions commonly used in minimax analysis and Group Lasso theory (Raskutti et al., 2011; Lounici et al., 2011; Negahban et al., 2012). Conditions of this type are close to necessary for establishing oracle inequalities and related theoretical guarantees (van de Geer and Bühlmann, 2009)[2]^{[2]}.

Your question regarding Assumption 1 is particularly insightful. This assumption characterizes a fundamental trade-off between the number of sampled activation patterns and the sparsity imposed on the coefficient vector uu. As the number of sampled patterns increases, the coefficients must be concentrated on a sufficiently small set of active patterns; conversely, a less sparse coefficient vector requires a smaller collection of candidate patterns. An analogous trade-off arises in high-dimensional linear models, where the admissible sparsity level depends on the ambient dimension, typically through a complexity term such as slog⁡(P/s)s\log(P/s).

Q1: Yes, we do have the training curves for the nonconvex baseline. We have added the training curves in Appendix M. All of them used 200 epochs. The curves show that the training loss decreases and stabilizes by the end of training, with little further improvement in the final epochs. These results support the adequacy of the training budget used in our comparisons.

Q2: Across our semi-synthetic and real-preference experiments, the proposed convex method took longer to train than the nonconvex baseline. The convex solver samples activation patterns once at initialization and spends most of its runtime in the subsequent ADMM iterations. We do not claim the proposed method is computationally efficient. However, it does not prevent it from being practically useful. Because the benefit of convexity, as proposed in this paper, mostly lies in that it enables rigorous theoretical characterization of our estimator.

Q3: We agree that the original Figure 1 did not provide sufficient information to interpret our theoretical results. In the revision, we have expanded Section 4.1 to report the decomposition of prediction error into approximation and estimation errors, with the latter further decomposed to reveal the bias–variance trade-off under different reward oracles as the model parameters vary. The remaining simulation settings, including the designs and models, are largely unchanged. For completeness, we have moved the original Figure 1 and its accompanying experimental description to Appendix B.

The revised synthetic experiment illustrates the decomposition established in Corollary 1: the MSE consists of approximation and estimation errors, with the estimation error further decomposed into variance and squared bias. We consider four settings with increasingly complex true comparison functions: sparse ReLU, for which the approximation error is zero; linear; symmetric ReLU; and interaction ReLU. Across all four settings, we observe a consistent pattern: holding the other parameters fixed, the approximation error decreases as PP and dd increase. The experiments also exhibit the expected bias–variance trade-off. We believe these new results provide a clearer interpretation and empirical validation of the principal scaling behavior predicted by our theory.

[2]^{[2]}: van de Geer, Sara A., and Peter Bühlmann. “On the Conditions Used to Prove Oracle Results for the Lasso.” Electronic Journal of Statistics 3 (2009): 1360–1392.

Q4: Theorem 2 and 3 give explicit choices of λ\lambda that suffice for their respective high-probability bounds. However, these choices need not minimize prediction error on a given dataset. We therefore use cλthmc \lambda_{\text{thm}}, where cc is data-adaptive. The multiplier cc lets us adjust the overall penalty strength to the dataset while retaining the scaling prescribed by the theory. We can select cc empirically without knowing the underlying reward parameters. In the experiments, we calibrate the multiplier cc using a held-out validation split on an independent dataset. For example, for the real-preference experiments, we tested different multiplier candidates on the new dataset HelpSteer3\texttt{HelpSteer3}, selected the optimal one c=5×10−5c = 5 \times 10 ^{-5}, and fixed this multiplier across all other five evaluation datasets. Such an approach that giving a theoretical tuning parameter and using cross-validation to tune the hyperparameter in practice is commonly used in regularization.

Thank you again for your careful review. We hope these revisions address your concerns, and we would be grateful if you would consider updating your assessment. We would also be happy to clarify any remaining questions or respond to further comments.

Thanks to the authors for providing the additional results and clarifications.

Thanks for addressing the raised weaknesses and questions. I still feel the contribution is incremental, but the reasoning given for W1 is fair. The addition of the training curves (Q1) is well appreciated. Q4 is also resolved. However, some concerns remain:

W2: I agree that the basic assumptions are necessary and justified. But i feel the specific point is not fully addressed (i.e. K, ϕ_ going towards zero).

Q2: I am still missing some quantification for the runtime/compute spend. Even for a theoretical contribution, the expected compute for implementation is still relevant.

Q3: The new figure is definitely clearer. Thanks! However, most of the plotted curves still remain very flat (especially for Sparse ReLU), so i still do not really see the predicted patterns.

Given that the authors address the remaining issues (like the missing compute demand) for the camera ready, i do not have strong objections against publication, and thus will update my score.

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

This paper studies the statistical complexity of learning a nonlinear reward model from pairwise preferences under a Bradley–Terry model and develops a convex method with finite-sample guarantees. The authors fit the reward with a two-layer ReLU network on fixed representations through a convex formulation over retained activation patterns, with a penalty that encourages few active patterns. When the true reward differences have a sparse representation in these patterns, the authors derive lower and upper bounds on the squared error between fitted and true reward differences over the observed comparisons, conditional on the representations and retained patterns. The bounds’ leading terms grow with the number of active patterns, the representation dimension, and the number of retained patterns, and shrink with the number of comparisons. With known sparsity, the authors report that the proposed convex method attains the minimax rate. Finally, when the sparse representation is only approximate, the authors provide a further bound that separates approximation error from estimation error.

Critical strengths

Strengths

  1. The paper addresses a well-motivated question about the statistical complexity of preference learning. The authors connect the complexity of the reward model to estimation accuracy and relate the number of active patterns to the number of neurons the chosen representation needs. This relation gives the bounds a concrete interpretation and shows what makes estimation difficult within the studied model class. This strength is the main positive consideration in my score.

  2. The proposed theory accounts for approximation error. The authors extend their guarantees to cases where the sparse model only approximates the true reward differences. Separating approximation error from estimation error makes the theory more complete and strengthens the contribution.

Critical weaknesses

Weaknesses

  1. The guarantees do not cover error in reward differences on new comparisons, even comparisons from the same distribution. The theory bounds error only on the observed comparisons, conditional on the representations and the retained patterns. The experiments also do not measure squared error in reward differences on new comparisons. Section 4.3 reports preference accuracy and AUC on new comparisons, but these metrics measure how well the model predicts preferences, not the error in reward differences. Although the authors acknowledge this limitation, the connection between their guarantees and prediction on new comparisons remains unresolved. This limitation is the main reason for my score.

  2. The paper does not show when its conditional guarantees are useful. The guarantees require that a few retained patterns approximate the true reward differences well and that the design conditions hold. The paper does not show when a practical number of retained patterns meets these requirements, and Corollary 1 allows for approximation error without showing when that error is small. The synthetic and semi-synthetic experiments are appropriate, but they mainly describe trends in error and compare methods. The experiments do not test the design assumptions or separate approximation error from estimation error. This gap weakens the case that the theory guides reward learning in practice.

Questions for authors

Questions

  1. Do the authors have theoretical or experimental evidence on the squared error in reward differences on new comparisons from the same distribution? If not, which additional assumptions would extend the guarantees from the observed comparisons to new ones?

  2. Do the representations and retained patterns in the synthetic and semi-synthetic experiments (Sections 4.1–4.2) satisfy Assumptions 2–4? Please report these checks and explain how Corollary 1 accounts for the errors in these experiments.

  3. In Section 4.2, the authors attribute the lower mean squared error (MSE) of the nonconvex method to approximation error from restricting the activation patterns. Table 1 does not isolate this cause. Could the authors test the explanation directly, for example by showing whether the gap shrinks as the number of retained patterns grows?

  4. Theorem 1 bounds the expected minimax risk, while Theorem 3 gives a high-probability bound under different design assumptions. Do the two bounds hold under common conditions that support the claim of minimax optimality, or do they only match in rate under separate conditions? Which design and curvature constants are treated as fixed?

  5. The text before Corollary 1 identifies a limitation and explains why the next result is needed. To improve clarity, could the authors give the same motivation before the assumptions in Sections 3.1–3.2, make the interpretations after the theoretical results more explicit, and connect these interpretations to the paper’s research questions? In particular, what does the lower bound say about unavoidable estimation error, what does the convex estimator achieve, and how does Corollary 1 change these conclusions? Please also separate conclusions about the chosen pattern representation from conclusions about learning nonlinear rewards in general.

3 comments

Thank you so much for your valuable feedback.

W1 & Q1: We agree that developing an out-of-sample prediction theory is an important extension. In the original manuscript, the experiments in Sections 4.1 and 4.2 were designed to evaluate our fixed-design estimation bounds; accordingly, we reported in-sample performance metrics in those sections. In the real-data application in Section 4.3, the true reward differences are unobserved, making it impossible to evaluate the out-of-sample MSE directly. We therefore used alternative criteria to assess predictive performance on the test data.

We appreciate the your comment, which motivated us to address the more challenging problem of deriving an out-of-sample bound. In the revised manuscript, we have added Section 3.4, which establishes an out-of-sample prediction error bound of order s(d+log⁡P)/ns(d+\log P)/n. This rate matches the in-sample rate established in Theorem 2. We also discuss the additional conditions required for the bound, which are relatively standard in out-of-sample prediction theory.

W2 & Q2: Assumptions 2–4 are motivated by standard regularity conditions in Group Lasso theory (Lounici et al., 2011; Negahban et al., 2012). In our simulations, Assumption 2 can be enforced during the sampling procedure by discarding activation patterns that violate the assumption and retaining only those that satisfy it. Assumptions 3 and 4 hold with constants κ\kappa and κ~\widetilde{\kappa} that are small but strictly positive. Similarly small constants have been observed for related design conditions in high-dimensional statistics literature. For example, in numerical experiments for the Lasso, Hirose (2025)[1]^{[1]} found that the constant associated with the weaker compatibility condition can be close to zero when the dimension is large relative to the sample size.

Corollary 1 decomposes the MSE into approximation and estimation errors, with the estimation error further decomposed into variance and squared bias. We revised the synthetic experiment in Section 4.1 to explicitly demonstrate this error decomposition. Holding the other parameters fixed, we find that the approximation error decreases as dd and PP increase.

Q3: We agree that Table 1 alone does not explain why the nonconvex estimator achieves a lower MSE, and we have revised the discussion to remove this attribution. To investigate the underlying mechanism more directly, we have incorporated your suggestion into the revised Section 4.1. Specifically, using a controlled synthetic design, we examine how the approximation and estimation errors vary with the number of retained activation patterns.

Q4: Theorem 1 characterizes the overall difficulty of the estimation problem, with Assumption 1 specifying the conditions that define the problem class. By contrast, Theorem 3 concerns the performance of the proposed estimator and therefore requires additional conditions on the particular design under consideration.

Although Theorem 1 is stated in expectation, a similar argument yields the following minimax lower bound in probability: inf⁡η~sup⁡η⋆∈Gs,MPη⋆(∥η~−η⋆∥n2≥cs[d+log⁡(P/s)]n)≥14.\inf_{\widetilde\eta}\sup_{\eta^\star\in\mathcal G_{s,M}}\mathbb{P}_{\eta^\star}\left(\|\widetilde\eta-\eta^\star\|_n^2\ge c \frac{s[d+\log(P/s)]}{n} \right)\ge \tfrac14.

We treat M,ϕ−,ϕ+,κ~,δ,M, \phi_-, \phi_+, \widetilde \kappa, \delta, and μM=σ(M)[1−σ(M)]\mu_M=\sigma(M)[1-\sigma(M)] as fixed.

Q5: We have added a brief discussion at the beginning of Section 3.2 explaining the motivation for Assumptions 2 and 3. All the other motivations and interpretations are behind each assumption and theorem. Specifically, Assumption 2 controls the scale of each pattern block, and Assumption 3 limits cancellation among blocks. Assumption 4 strengthens Assumption 3 by requiring errors in the ss largest blocks remain detectable in the observed margins. For the retained pattern class, the lower bound separates the unavoidable cost of estimating ss coefficient vectors, sd/nsd/n, from the cost of selecting their support, slog⁡(P/s)/ns\log(P/s)/n. The convex estimator nearly attains this rate under Assumption 2 and 3, and exactly attains this rate under Assumption 2 and 4. Corollary 1 adds the cost of approximating a reward outside that sparse class.

Thank you again for your careful review. We hope these revisions address your concerns, and we would be grateful if you would consider updating your assessment. We would also be happy to clarify any remaining questions or respond to further comments.

[1]^{[1]}: Hirose, Kei. "Numerical optimization for the compatibility constant of the lasso." arXiv preprint arXiv:2512.03321 (2025).

Reviewer_7riAOpenReview ↗

Response to the Authors

Thank you for your response. I really appreciate your detailed rebuttal. I found it informative (e.g., the out-of-sample result). I will maintain my score since it already reflected my positive view of your paper.

We are pleased that you found our newly added out-of-sample results informative. Deriving these results was technically challenging, and we appreciate your comment, which motivated us to pursue this important extension.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We thank all the reviewers for their valuable feedback. We have uploaded the revised version of the manuscript. Substantial changes are highlighted in blue. Here is the summary for the major changes:

1. Out-of-sample theory: We extended our theoretical analysis to out-of-sample prediction. Specifically, we establish a new prediction error bound for unseen comparisons under standard conditions. This result complements our existing fixed-design guarantees and strengthens the practical relevance of the theoretical framework. The new theorem and its proof are provided in Section 3.4 and Appendix I of the revised manuscript.

2. Approximation and estimation error decomposition with synthetic experiment: We revised Section 4.1 to measure approximation and estimation error separately under different reward oracles and moved the original scaling experiment to Appendix B for record. The revised synthetic experiment shows variance increases and approximation error decreases as dd and PP increases while holding other parameters fixed.

We thank the reviewers for their time and constructive feedback. We would welcome any further questions or concerns regarding our responses and revisions, and would be happy to provide additional clarification before the discussion period ends.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.