Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies procedures for quantifying uncertainty in a regression setup, focussing on the full quantile function as a form of interpretable output. The main contributions of the paper include 1) exhibiting that optimizing the pinball loss can lead to poor quantile functions, and 2) proposing new quantile methods which work in an agnostic manner.
main_review: The problem studied in the paper seems quite relevant in the context of current large-scale deep learning models being mis-calibrated, for regression as well as classification tasks. 
- Overall, I enjoyed reading this paper and it is in general well-written. With the limited space though, I would urge the authors to go into a bit more detail about some of the proposed methods rather than listing all of them in Section 3.
- While the MAQR method seemed to perform well on the UCI datasets, it was not tried on the fusion dataset due to compute issues. I would be interested in seeing some simulation experiments for problems with varying samples (n) and dimensions (d). This would allow us to understand the breakdown point of the MAQR method in some more detail and provide a comparison with the other baselines. 
- Since one of the key contributions of the paper is proposing new methods, I am a bit worried about the choice of the benchmark datasets from UCI. In particular, why were these particular set of 8 datasets  chosen from all the available ones? Can the authors provide evaluation on some other larger scale datasets?
- Choice of network architecture: the results were obtained with a single two-layer ReLU network. This seems quite limiting, and it would be interesting to see consistent trends across a variety of depths (even going to larger depths to showcase trends). Given the particular choice, I am not particularly convinced that the method works well in the extreme over-parameterized regime.
- Algorithm 1 (MAQR) uses residuals instead of directly working with the y values. Is there an advantage in doing so? Can you perhaps performa an ablation over these two choices to showcase why this particular form was chosen?


The authors have addressed my concerns and I have updated my rating accordingly.
limitations_and_societal_impact: The authors provide a discussion on this and relate their work to the literature on fairness in ML.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work is motivated by some shortcomings of the classical pinball loss used to learn quantile models, like the required differentiability of the models and miscalibration issues.
The pinball loss is also not naturally suited to build centered intervals.
This work proposes alternatives ways for learning quantile models, addressing these shortcomings.
Four methods are proposed:
- Model Agnostic QR: it is a generic method based on conditional density estimation and standard regression. Therefore it is not particularly tied to differentiable models and doesn't use the pinball loss.
- Combined calibration loss: a loss to be used instead of the pinball one, with the advantage of explicitly balancing  sharpness and calibration of the predictions.
- Centered intervals: an alternative loss based on the Winkler score is proposed to train models providing centered intervals.
- Group batching: a heuristic replacing uniform sampling for batch-based based methods, aiming at better individual calibration.
main_review: ## General aspects

**Originality** 

As far as I know, Proposition 1 is a new result that shows that the pinball loss doesn't guarantee calibration on a finite dataset.
Four methods are proposed, with different degree of originality:
- MAQR is a new quantile method leveraging existing conditional density methods like KDE and standard (mean) regression methods. 
- The combined calibration loss combines two new objectives addressing sharpness and calibration respectively. A new theoretical result shows that calibration objective is well founded (it is minimized by the true quantile function).
- The centered interval  method leverages the existing interval (or Winkler) score. The novelty is in using it as training loss---instead of an evaluation metric---and in averaging it over all interval widths.
- The group batching is a heuristic that consists in using some non-uniform batching criterion with the goal of approximating adversarial group calibration that is closer to the ideal individual calibration.


**Quality**

The theoretical results are useful and the proofs seem correct.  
The experiments properly illustrate the benefits of the methods proposed.

The methods are interesting. The two first methods (MAQR and combined calibration loss) are treated in more depth and rigor  than the last two. In particular, the group batching method (Section 3.4) is vaguely described (some elements are given in the appendix but still in an informal way).


I found the relationship with regularization not properly discussed. In particular, the assertion "While this may seem like an issue that can simply be addressed with regularization, we demonstrate in Appendix F.2 how that is not the case." is too strong, since appendix F.2 shows  it  experimentally for SQR only, which has the particularity of taking the quantile level as input.
A discussion of previous work relating regularization and calibration would be desirable :

*I. Takeuchi, Q. V. Le, T. D. Sears, and A. J. Smola. Nonparametric quantile estimation. JMLR, 2006.*

*I. Steinwart et al. Estimating conditional quantiles with the help of the pinball loss. Bernoulli, 2011*

It would be also interesting to compare with the following recent work that addresses the coverage problem:

*Romano, Y., Patterson, E., & Candes, E. (2019). Conformalized quantile regression. Advances in Neural Information Processing Systems, 32, 3543-3553.*


**Clarity**

The paper is well organized and well motivated. The group batching method not properly described, with some important elements being described in the appendix only. Algorithms 1 and 2 seem to contain some errors that make them confusing (see detail below).


**Significance**
 
The methods and the theoretical properties presented in this work should be of interest for the statistical and machine learning communities working on quantile regression and uncertainty quantification in general, and for practitioners requiring predictions with uncertainty estimation.

## Specific comments about the methods

**MAQR**

I think I got the idea from the text, but Algorithms 1,2 and 3 are confusing to me.
The idea seems to be (please correct me if I'm wrong):
- Learn a standard regression model $\hat{f}:x\rightarrow y$, compute residuals $\epsilon=y-\hat{f}(x)$
- Learn an empirical conditional CDF of the residual $\epsilon$ for each $x_k$ using its neighbors (KDE)
- Use it to compute the cumulative density $p$ of each neighbor $x$ and build a new observation $\\{x, p, \epsilon\\}$
- Learn a regression model $\hat{g}: x,p \rightarrow \epsilon$ , which can be interpreted as quantile regression model since it takes the quantile level $p$ as input. 
- Use $\hat{f}+\hat{g}$

Algorithms 1 and 2:
For i=1 in Algo 1, the dataset D that is passed to Algo 2 seems to be empty.
The dataset of pairs that is taken as argument of Algo 2 seems to be the union of sets returned by itself on previous calls, but it is confusing that Algo 2 returns a set made of triplets .

Algorithm 1: why does it output k = 1, …, m ? What is m?

Line 6 : why the preceding " D: " ?   (also in Algo 2) 

Maybe I am wrong because of the previous confusions, but it seems to me that the dataset that is used to train $\hat{g}$ can be larger than the original dataset (because of the overlapping neighborhoods). This should be discussed.

Algorithm 3 looks simpler and it is not obvious how Algo1+2 is an instance of it.
Line 5 of Algo 3: what does " KDE estimate of Q(xi; pk)" mean? Q is not a density.

The statement "residuals … which produces more accurate empirical CDFs" should be justified.


**Combined Calibration loss method**

The empirical loss should be introduced and explained in the main text. 
It would be interesting to report the values of lambda selected by the cross-validation procedure to see what kind of tradeoff is best for the considered datasets.


**Centered Interval method**

Expectation over alpha uniform on [0,1] can make  $\hat{l}>\hat{u}$  (lower bound > upper bound). Does it make sense?

This loss also combines sharpness and calibration by taking  into account the width of the interval $u-l$ and penalizing the points outside the interval. In the light of the previous section, I would expect some discussion on how these objectives are weighted.


**Group batching**

 This is an interesting heuristic to add on previous methods and other batch based methods, by modifying how batches are built. Nevertheless, I found it not properly described. It is essentially described by the following sentence in the main text:
"Instead, deliberately grouping the datapoints based on input features, and then batching and taking
gradient steps based on these groups, induces better adversarial group calibration."
Appendix gives more information but remains very informal.

Moreover: in appendix (lines 692-694), it is said that uniformly sampled batches are alternated with the adversarial ones without justification.


## Minor comments

"Proper scoring rules" should be formally defined in Section 2.

Theorem 1: the random variable E deserves a more explicit definition.

Eq. 5 $\hat{p_p}$ seems a duplicate notation for $p^{obs}_{avg}$.

Line 215: occur -> occurs

Line 347: "While sharpness tends to increase with group batching, higher sharpness is desirable if
there is high noise in the true data distribution. "
I think this refers to the width of the 95% centered interval: higher = less sharp.
However, "higher sharpness" sounds like the opposite.

Line 592:  I found the following notation confusing :

$$\hat{p}^{obs}_{avg}(D,\tau) \text{ of } g - \tau$$ 

Maybe it would be clearer to define $\hat{p}^{obs}_{avg}(D,\tau)$ of $g$ and $f$ before, using different symbols.

Last part of the proof of Prop 1 (generalization to any tau ): The step from line 592 to 593 is clear since tau is part of the set {p_j} defining ECE and therefore the inequality compares  terms of each ECE. 
lines 599-601: you should explain more explicitly how you get to the same inequality between ECEs when tau is not part of {p_j} .

Line 637: state -> stated
Line 810: shrink -> shrinks


## Summary of suggestions

I would be glad to increase my score if the following aspects are addressed :
- a discussion on previous work relating pinball loss, calibration and regularization is added
- the description of Algorithms 1,2,3 is improved
- the group batching method is more precisely described 

## UPDATE AFTER REBUTTAL

My suggestions have been addressed. Therefore I increase my score to 7.
limitations_and_societal_impact: The authors discussed the limitations of MAQR related to high-dimensional data. 
It would be desirable to discuss limitations of the other methods (i.e. combined calibration loss, centered intervals and group batching).

The potential negative societal impact is adequately addressed in the appendix.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a new quantile method called MAQR for uncertainty quantification. This method is based on estimating empirical CDFs for residuals locally and therefore suffers from the curse of dimensionality. To address the issue, the authors further propose an NNs based solution, where the proposed loss consists of a convex combination of two terms. The first term encourages average calibration and the second term encourages sharpness. Thus allowing the user to control the balance between the two. The paper also provides a theoretical result stating that the first term is indeed minimized by the true quantile function. The authors also propose a version of the method for estimating centered intervals as well.

The paper is concluded with a rather extensive empirical evaluation.

main_review: The proposed methods are interesting and can be of interest to both researchers and practitioners interested in uncertainty quantification. The proposed methods are novel to the best of my knowledge - although I am not completely up to date with the literature.  The paper is dense, but overall well-written. However, some important definitions are not stated anywhere in the paper (see comments below). The claims of the paper are reasonably justified using a combination of theoretically motivated arguments and an extensive empirical study. The authors are comparing and evaluating the methods using several evaluation metrics. The main paper is also accompanied by a rather thorough appendix providing the details of the theoretical results as well as the experimental settings. 


- It is not entirely clear to me, why eq. (6) is a good way to encourage sharpness. In my opinion, the authors should elaborate on this.

- Line 252: What is meant by: "all expected probabilities p ∈ (0, 1)" in line 252. Can the authors elaborate on that?

- What is the exact definition of sharpness used in the paper? Sharpness is both for motivating the work as well as an evaluation metric, but the authors do not provide an explicit definition.

- The MAQR method has a hyperparameter controlling bandwidth or locality, $d_N$, and one might suspect that the results can be quite sensitive to perturbations in this parameter. It would be nice if the authors would include a small discussion of the robustness of the methods.

- The objective in eq. (7) has the hyperparameter lambda balancing sharpness and calibration. It is state that lambda is estimated using cross-validation based on the adversarial group loss. I am curious to know what were the optimal values for the different experiments? 

- The y-labels are missing for Figures 7 and 13 in the appendix.

# After rebuttal
I've updated my score from 6 to 7
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents four alternatives to training quantile regressors with the vanilla pinball loss:

(1) a specific conditional density estimator, from which the quantiles are derived

(2) a new loss function that balance calibration and sharpness

(3) centered intervals

(4) group calibration to enforce conditional coverage

Experiments are shown to compare these methods with SQR, a neural network that optimizes the pinball loss.

main_review: The paper is well written and the methodology is sound. In particular, I think that the new loss function (point 2) is very interesting, as well as the idea of group calibration (point 4).

The idea of deriving quantile estimators from conditional density methods (CD; point 1) has been around for some time. Thus, I miss comparisons of the conditional density estimator the authors propose to other conditional density estimators available in the literature. This is particularly relevant because, in almost all UCI datasets, MAQR was the best performing method, but it is also the only CD-based method. Thus, it is not clear to me that the good performance comes from using this specific conditional density estimator or if it is because of the fact that the problem of estimating the quantiles was being tackled in another way (namely estimating the whole distribution). 

I also have two concerns with the CD method:

- The same data is being used twice: (i) to fit the regression and (ii) to model the distribution of the residuals. I wonder if regression methods that lead to overfitting (e.g., a neural network that interpolates the training points) would harm the quality of the estimator.

- The methods depend on the Euclidean distance between the features, which not good in general (especially if isotropic): It is often the case that some covariates are independent of the Y conditional on the remaining ones. This is especially true in high-dimensions. Thus, I don't agree with the authors that all nonparametric conditional densities fail in high-dims (some methods do variable selection, for instance), but instead that this specific method is not appropriate.


I also miss comparisons to other quantile estimators that don't directly target the pinball loss, such as quantile regression forests.


Minor comment:

- The results on the appendix for the Fusion datasets indicate that the Check score is minimized by SQR, so I don't really with the last statement from Section 4.1.
limitations_and_societal_impact: 
Yes, limitations have been addressed.
review_title: null

Meta-review: In this study, the authors are concerned with the problem of estimating the full quantile function of the responses in a regression setting. This task can be typically realized by performing quantile regression on all quantiles. However, the authors pointed out a drawback of pinball loss, which is usually used in quantile regression, and a new method that can overcome this drawback is proposed. Both the problem and the setting discussed in this paper are important, and the theoretical validity of the proposed method and the demonstration of its performance through experiments are properly done. All reviewers found the paper useful for the ML community. The authors are encouraged to consider updating the paper based on the reviewers' comments and suggestions.
Decision: Accept (Poster)