Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies distribution-free multi-valid coverage in the batch setting. They provide two algorithms to achieve multi-valid coverage, which is a stronger notion than regular marginal coverage. In a brief summary, they design their algorithm based on a theoretical argument that patch operation such that a postprocessing and make sure coverage guarantee when conditional on x\in B  for a set B can decrease pin-ball loss, which is the a key loss for quantile control.
strength_and_weaknesses: Strength. This paper is technically sound. Conditional on group membership has important application.

Weakness. I am a bit confused about the writing. I am generally familiar with a conformal prediction on the statistics side, but this paper is a bit hard for me to parse. I think it mainly follows a line of literature in CS, which I am not familiar with, and a terminology explanation is missing. For instance, I cannot understand what is the difference between the batch setting in this paper and the setting studied in standard literature, though the paper clearly says ``it is different from the sequential setting because the labels are not applicable when the set is deployed".  The algorithms are based on s, which involves y, does it mean they can only observe s and x? And the sequential setting I think it means online learning, but most of the standard conformal settings are just offline, what is the difference between those literature and batch settings? I also could not understand why a criterion needs to hold for all tau when conditional on f(x)=tau, this is a bit too strong. Also by replacing tau to f(x) is not novel, it is widely considered in the literature such as ``conformal quantile regression" by Romano. Besides, the lipchitiz on distribution basically needs the density to be bounded, which is not applicable on many real examples in practice, such as applications in learn then test paper by Bates etc.

Some minor comments, the set of distribution on \mathcal X should use \Delta_{\mathcal X} instead of \Delta \mathcal X, which looks weird.

I would raise my score if the author can provide more detailed explanation.
clarity,_quality,_novelty_and_reproducibility: Hard for me to understand parts of it. 
summary_of_the_review: See commentes above.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper looks at a novel way to investigate batch conditional coverage in the setting of conformal prediction. CP is known to be unable to provide conditional coverage guarantees and hence this paper proposed two methods to relax these assumptions but taking a closer look at batch conditional coverage and hence propose batchGCP and batchMVP.

The key insight is that their threshold contrary to CP is now a function of X which in turn is now to be learnt.

By adding this extra degree of freedom they are able to obtain interesting results regarding batch conditional coverage and show that their proposed method is superior compared to standard CP and other baselines.
strength_and_weaknesses: I will start with the strengths of this paper:
- The authors propose a novel way to understand batch conditional coverage by utilizing the pinball loss in a specific way.
- They also analyse the fact that the pinball loss might not always be well optimized and hence provide an iterative algorithm that sequentially improves the quantile computation.
- They theoretically analyze the proposed algorithms and provide further theoretical analysis of how their method can achieve the guarantees (I am not familiar with the theory and hence I will be leave this part to be scrutinized by the other reviewers)
- The experiments are mostly convincing and show that their proposed method is superior to current baselines

In terms of weaknesses and clarifications:
- First of all I would like the authors to clarify what $f(x) = \tau$ actually signifies. I am a little confused because wouldn't that mean f is a constant function? I just don't get the intuition on what the point of $\tau$ is. Could the authors please give a concrete example of what tau signifies and why f(x) is constant? 
- In algorithm 1, I am confused to why you are computing the pinball loss wrt to y shouldn't it be the scores? maybe I am completely misunderstanding this part here but isn't f(x) supposed to be the quantiles for the scores? in that case, why are we minimizing the loss wrt to y the output? Sorry if I misunderstood sth.
- I would suggest the authors to create a figure on how the patching works on a simple 1-2D example. I think that would illustrate the algorithm much easier. I get the general gist. My confusion also comes into algorithm 2. Isn't g(x) supposed to be fixed? i.e. these are the subgroups that we predefined. Now that we are optimizing over them how can we ensure that the groups that come out at the end reassemble the groups that we are interested in dealing with when all training is done? Also, what is the form of g?
-  I am not familiar with PAC Bayes but a constant that big in 90k+ in theorem 4.2 seems not to be very useful. Even if it works in practice the theorem seems kind of useless. Please correct me if I am wrong here.
- Could you please point me to the experiments where you increased the group size? I am confused to what breaks in your theory if each group is just an individual datapoint i.e. each group is just a 1-2 datapoint. Is there something that breaks in your theory or does that mean the bounds will become useless? I am just trying to get a more intuitive understanding on how the group size affects the overall bounds as in standard CP.
- This is more like a clarification question: In the Barber et al 2020 paper do they do the following: split the calibration data for each subgroup and then compute a different threshold for each group. Then for testing time, they first check which group it is in and then sue the corresponding threshold for that new datapoint. If the answer is yes then please just reply with a yes, if no, please tell me why this is a  valid baseline if the calibration data is reasonably big for each group.

clarity,_quality,_novelty_and_reproducibility: The paper is nicely written however there are certain parts when it comes to intuition on what the theorems mean that are still none intuitive to me. The experiments are quite well laid out with the exception of the questions raised above.
Overall the novelty is there and I quite like the angle they tackle the problem. The experimental results also back up their claims however I have not run the code myself.
summary_of_the_review: I have detailed all my concerns above and I am happy to increase my score if the above misunderstandings have been clarified.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper extends the scope of conformal prediction techniques from marginal validity to conditional validity with respect to a subset of the feature space. This allows for example to quantify the uncertainty of predictions conditional on the race or gender of the subpopulations. The main novelty lies in the fact that instead of thresholding the score functions by a constant to satisfy the prescribed coverage, the authors propose to learn a threshold function under coverage validity constraints. This is very similar to what is done in learning under fairness constraints. The authors present a series of numerical experiments illustrating the performance of their method, a clear improvement over the alternative method.
strength_and_weaknesses: The idea of learning a threshold function is very innovative and can certainly be applied in other contexts. The numerical demonstration is very convincing and the subject in general is relevant for the AI/ML community.

The major weakness of the paper is that it is very hard to read. The proof does not seem to be written to be read at all. Same expressions are repeated several times, making it very messy, and very difficult to understand. The authors would benefit from reducing this clutter in the proofs. An example is the proof of Lemma C4, where the core tool is just the application of classical remarkable identities to bound $|(q - a)^2 - (q - b)^2 |$. 

Also, it is very difficult to understand under which hypotheses the proposed algorithms work, so much the article is convoluted with additional (sub)-constraints on the distributions. And this, from lemma to lemma, one gets lost and even after reading it multiple times, I have trouble extracting a clear setting where the algorithms are guaranteed to work.
clarity,_quality,_novelty_and_reproducibility: Can do better in terms of clarity, see my remarks above and below.

I could not check the proofs given the time delay, and length of the paper.

summary_of_the_review: Some comments/questions:

1) By construction, Conformal Prediction is distribution free. The propositions of this paper are not, since they significantly restrict the CDF with some regularity assumptions, that in-fine, cannot be verified because the distribution of the data is unknown. Can the authors comments on that?

2) A core assumption, all around the paper, is that the scores functions are $\rho$-Lipschitz. However, the latter depends on the distribution, which is also unknown, Even more, the scores are constructed from the data eg as prediction errors of a neural net. How do one verify this assumption? More annoying, the proposed algorithms do not even use the regularity constants in play, which suggests, with a bitter taste, that the theoretical analysis is not connected to the proposed algorithm. The authors might want to discuss this a bit more.

3) Considering the context of the article, the exchangeability assumption is perhaps a bit too strong. It would be surprising if the population of the considered subgroups follow the same distribution nonetheless being independent. When considering age or gender, can the authors present any example where such assumption is realistic?

4) When conditioning on an under-represented group (ie where very low number or none of examples is observed), the conditional event becomes a rare event. How does it affect the length of the conformal set proposed?
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a conformal prediction algorithm that obtains multivalid converge on exchangeable data in the batch setting. Multivalid coverge guarantees mean that the target coverage level holds conditionally on membership in each group or/and the threshold value. They provide theoretical analysis to clarify the reliability of the proposed algorithms under some regularity conditions. Extensive experiments have been conducted to compare the performance of the proposed method and other comparative methods.
strength_and_weaknesses: Strength:

Theoretical analysis of the proposed method explains why it works.

Adequate experiments are conducted.

Weaknesses:

-- The first sentence in the last paragraph on page 3, "that on each input x output a value f(x) that is", output should be outputs.

--Please provide some examples that satisfy the Lipschitz condition in Definition 2.2.

-- what is the meaning of this sentence "To facilitate learning models f with guarantees conditional on their output values, ..."?  Please give some examples of such f. Is m here the same as m in Algorithm 2? In general regression settings, finite cardinality seems unrealistic. In Section 5, please state clearly what f you have used, does it satisfy the finite cardinality condition? How do you choose m in practice (in Section 5, you use different m)?

--From theoretical results, the sample size should be large enough for the results to hold (with high probability). For a comprehensive understanding of the sample size requirement, It will be helpful to provide more experimental results for different sample sizes (especially for small sample sizes).

-- Is it possible to theoretically analyse the (average) size of predictive sets of the proposed algorithms (smaller compared to previous conformal methods)? Please provide some discussions.

-- Please explain the parameters alpha, rho, m in Algorithm 2 and their connection. Are these parameters pre-specified by users or tuned in some way?

-- The meaning of Figures 2 and 4 is not very clear. Please clarify this.

-- From experimental results (e.g., Figures 1&3), the method, BatchMVP, might obtain predictive sets that undercover in some groups. Can you explain this?
clarity,_quality,_novelty_and_reproducibility: See above.
summary_of_the_review: This paper proposes a novel method that has multivalid coverage guarantees. They theoretically analyse the properties of the proposed method.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work extends the scope of conformal prediction from marginal validity to conditional validity with respect to a subset of the feature space.  Two algorithms to achieve multi-valid coverage (a stronger notion than regular marginal coverage) are provided.
The main novelty lies in the fact that instead of thresholding the score functions by a constant to satisfy the prescribed coverage, the authors propose to learn a threshold function under coverage validity constraints.
justification_for_why_not_higher_score: The paper is very hard to read. Expressions are often repeated several times, making it very messy, and very difficult to understand.
justification_for_why_not_lower_score: The idea of learning a threshold function is innovative and can be applied in other contexts. The numerical demonstration is convincing and the subject in general is relevant for the community.
Decision: Accept: poster