- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper deals with the problem of estimating the regression function given i.i.d. observations . As opposed to many results in the literature, the quality of the estimator is measured by the integrated absolute error , where is the distribution of the feature vector . This contrasts with standard settings where performance is evaluated via the squared integrated error, or where the mean absolute error is computed with respect to the conditional median rather than the conditional mean. The paper is mainly theoretical, and its main contribution is a high-probability upper bound on the error of the sign-betting estimator introduced by Maillard and Baraud. Additionally, it demonstrates that existing upper bounds for classic estimators, such as Empirical Risk Minimization (ERM) under squared and logarithmic losses, lead to suboptimal risk bounds, with the sub-optimality residing specifically in the approximation error.
Critical strengths
The paper is well-written and provides a clear motivation for the problem under consideration. The main results are stated with all the necessary rigour. All relevant results I am aware of are adequately cited. I did not check the supplementary material for the proofs and other additional material, but all the statements are highly plausible.
Critical weaknesses
The main weakness is the level of novelty. As the authors honestly mention, the paper builds on the prior work by Maillard and Baraud, who considered the same problem for regression with a deterministic design. I agree that, from a technical point of view, the case of random design is different from the case of deterministic design, and there is no direct conversion between the two. However, it is already well understood in the statistical and ML communities that, up to some extra work, the risk bounds established for deterministic design carry over to the random design.
The second weakness is the condition that the response is in , and the same is true for the values of all the functions.
A minor remark is that the bibliography, probably generated by an LLM, has not been correctly checked. In particular, the book "Introduction to nonparametric estimation" has only one author: A. Tsybakov.
Another minor remark is that both the abstract and the introduction mention empirical results. However, the main body of the paper contains only mathematical results. In such a situation, it would be more appropriate to free up some space in the main body for including at least one page of empirical results.
Questions for authors
I have only one, very general question. Is there a case where the oracle inequality established in this paper leads to optimal rates in some sense (for instance, minimax) whereas the inequality that upper bounds the mean-absolute error by the MSE and then applies the risk bound on the MSE leads to sub-optimal rates?
2 comments
acknowledgment of reading the reply
Thank you for your reply. The last example is clear; in simple words, it says that L2->L1 conversion is suboptimal in cases where the O(n^(-1/2)) term in eq (17) vanishes. This means that it essentially happens only in the noiseless setting. I find that this is an interesting observation.
I maintain my score, and find that the paper deserves acceptance.
We thank the reviewer for the thoughtful comments and questions. We address each point below.
[W1] We agree that extending fixed-design results to random design itself is not the main novelty of our work. Beyond establishing high-probability guarantees for population error, our analysis introduces the comparator-dependent approximation quantity BP(f0) and second-order quantity v(f0), which are not ingredients provided by the fixed-design result of Baraud and Maillard and yield finer guarantees. Together with our lower bound, our results provide a sharp characterization of the optimal universal approximation factor for proper learning under our learning criterion.
[W2] We agree that boundedness is an assumption of our analysis. The specific range [0,1] is only a matter of normalization, and the results extend directly to responses and predictors taking values in any bounded interval by affine rescaling. This boundedness assumption is naturally satisfied in many of our motivating applications, for example, when rewards are bounded in bandit or RL, or when responses are human ratings on a bounded scale. Extending the high-probability population guarantees to unbounded or heavy-tailed responses is an interesting direction beyond the scope of the current work.
[W3] We thank the reviewer for pointing out the bibliographic error. We will correct the entry for "Introduction to nonparametric estimation" and carefully check the bibliography in the final version. For clarification, we did not use an LLM to generate or modify the bibliography. The BibTeX entry for "Introduction to nonparametric estimation" was copied from Google Scholar. We acknowledge that we did not independently verify the correctness of the Google Scholar BibTeX entry, which led to this error.
[W4] We agree that the empirical results should be more visible in the main paper. We will move a subset of the experimental results from the appendix to the main text in the final version.
[Q] Yes. A simple realizable noiseless example shows that converting an MSE guarantee to L1 via Cauchy-Schwarz can lose the optimal rate. Consider F={f0,f1}, where f0≡0 and f1=1{x∈A} for a set A with PX(A)=p=1/n, and let Y=fj(X) deterministically for some j∈{0,1}. If none of the n samples falls in A, which occurs with constant probability (1−1/n)n=Θ(1), the two regression problems are indistinguishable to any learner. On this event, for any output g,
\ge \lVert f_0-f_1\rVert_1 =p,$$ so at least one of the two problems has $L_1$ error at least $p/2$. Similarly, $$\frac{1}{2}\bigl(\lVert g-f_0\rVert_2^2+\lVert g-f_1\rVert_2^2\bigr) \ge \frac{p}{4}.$$ To see this, on $A$ we have $f_0=0$ and $f_1=1$, and hence $$\frac{1}{2}\bigl(g(x)^2+(g(x)-1)^2\bigr) =\left(g(x)-\frac{1}{2}\right)^2+\frac{1}{4} \ge \frac{1}{4}.$$ Integrating over $A$, which has probability $p$, gives the inequality above. Since the indistinguishable event occurs with constant probability, this gives minimax lower bounds of $\Omega(p)$ for both $L_1$ risk and MSE. For the upper bound, consider an estimator that outputs the identified regression function if a sample from $A$ is observed, and otherwise outputs $f_0$. Its risk under either metric is at most $p(1-p)^n=O(p)$. Hence $$\inf_{\widehat f}\sup_{j\in\lbrace 0,1\rbrace} \mathbb E_j\lVert\widehat f-f_j\rVert_1 \asymp \frac{1}{n},$$ $$\inf_{\widehat f}\sup_{j\in\lbrace 0,1\rbrace} \mathbb E_j\lVert\widehat f-f_j\rVert_2^2 \asymp \frac{1}{n}.$$ Our realizable noiseless guarantee in Corollary 10 also gives $L_1$ error $O(1/n)$ for this two-function class with constant probability. In contrast, even starting from a minimax optimal MSE guarantee of order $1/n$, upper bounding $L_1$ error by the square root of MSE and applying the error bound on the MSE only yields an $O(n^{-1/2})$ $L_1$ bound. To summarize, in this example, directly analyzing the $L_1$ error achieves the optimal $1/n$ rate, whereas converting an MSE bound via Cauchy-Schwarz inequality loses a square root and gives a suboptimal rate.