- 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 is unjustified.
- It is unconvincing that randomly sampled patterns can satisfy the coverage argument as stated in Remark 2, since the 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
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 that suffice for their respective high-probability bounds. However, these choices need not minimize prediction error on a given dataset. We therefore use , where multiplier lets us adjust the overall penalty strength to the dataset while retaining the scaling prescribed by the theory. We can select empirically without knowing the underlying reward parameters. In the experiments, we calibrate the multiplier 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 issue is not fully resolved. As a theoretical result, the magnitude of is not well understood, and even though the can be increased to make the exponent large enough, 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 , where the -th term in the fitted reward is . Since , two different decomposition of the same 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 prediction error rate on new comparisons as in our standard in-sample bound.
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 s of P 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 d-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/n cost, while varying the support gives the slog(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 d and P 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 π⋆, which governs the probability of sampling the patterns needed for this extension. The stated condition assumes that π⋆ is a fixed positive constant, however small; this ensures that the success probability converges to one as P grows. We agree that this condition is sufficient but not necessary. More generally, π⋆ may decay with P, provided that Pπ⋆→∞.
In the revised experiments in Section 4.1, we extensively examine sensitivity to the pattern budget by varying P from 20 to 110 and reporting both approximation and estimation errors. The results support the use of P=20 in the subsequent experiments as a computationally tractable baseline that nevertheless delivers strong empirical performance.