{'fraction_non_alphanumeric': 0.040695272383875346, 'fraction_numerical': 0.008764681579413326, 'mean_word_length': 4.40721238232009, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Discriminative Learning of Prediction Intervals

In this work we consider the task of constructing prediction intervals in an inductive batch setting. We present a discriminative learning framework which optimizes the expected error rate under a budget constraint on the interval sizes. Most current methods for constructing prediction intervals offer guarantees for a single new test point. Applying these methods to multiple test points results in a high computational overhead and degraded statistical properties. By focusing on expected errors, our method allows for variability in the per-example conditional error rates. As we demonstrate both analytically and empirically, this flexibility can increase the overall accuracy, or alternatively, reduce the average interval size. While the problem we consider is of a regressive flavor, the loss we use is of a combinatorial nature. This allows us to provide PAC-style, finite-sample guarantees. Computationally, we show that our original objective is NP-hard, and suggest a tractable convex surrogate. We conclude with a series of experimental evaluations.


Introduction
Constructing an interval which contains some point of interest with high probability is a fundamental task in statistics. In contrast to point predictions, intervals provide some measure of confidence, and can be used to reason about the reliability of a prediction. In this paper we focus on prediction intervals (PIs). For some predetermined significance level α, the classic task of PI estimation is to construct an interval [ℓ, u] which will contain a point y ∈ R sampled from some distribution D with probability of at least 1 − α. PIs are hence similar in spirit to confidence intervals, but are designed to contain future sampled points rather than population parameters such as the mean or variance.
In this paper we consider non-parametric PI estimation in a regressional setting. Let D = D XY be an unknown joint distribution over examples x ∈ X and labels y ∈ Y = R, where X, Y denote random variables and x, y their instantiations. In the classic PI task, we are given a training set of m pairs sampled i.i.d. from D XY , and an additional test example x m+1 sampled from the marginal D X . Then, for a given confidence level α, the goal is to construct an interval [ℓ, u] ∈ R 2 which will contain the true label y m+1 ∼ D Y |X=x with probability of at least 1 − α. The classic approach to this task is to first estimate the conditional D Y |X=xm+1 , and then infer the smallest interval which covers 1 − α of the probability mass. In the case of a Gaussian conditional distribution, this leads to simple closed form solution for computing PIs, and provides asymptotic guarantees when the data is indeed Gaussian (see also Sec. 2). There are many variations on this parametric two-step approach [10,11], as well as other direct and non-parametric methods [24,9,23].
Methods such as the above are designed for the classic setting which concerns only a single new test example. In many realistic cases, however, the task is to predict intervals for a set of future test points, given only the training data. This setting is known as inductive batch learning and has been extensively studied in machine learning. As we later discuss in detail, applying single test-point methods to the batch setting is rarely straightforward, and often comes at the cost of a significant computational overhead and/or the loss of statistical guarantees [14,15,3]. This is also true for the recently popular methods based on conformal prediction designed in the online learning setting [2,13].
Our goal in this paper is therefore to provide a general framework for PI estimation in the batch setting.
The approach we present models PI estimation as a discriminative learning task, where the goal is to learn an interval predictor with high expected accuracy. To this end, we design a learning objective which takes into account the natural tradeoff between accuracy and interval size. Our analysis provides computational guarantees on training such predictors, as well as statistical guarantees on their generalization. This means that, with enough samples, an interval predictor which achieves an error of α on the training set will have roughly the same error on the test set.
The method we present differs from the standard single-point approach in several important ways. First, the learning objective we consider relaxes the classic α-confidence requirement to hold in expectation. Focusing on expected errors allows our method to predict intervals with different error rates for different examples. Second, a model-free discriminative framework separates the task (predicting accurate intervals) from the model (Gaussian, linear, etc.). To this end, we first identify an appropriate combinatorial loss function, and then suggest a tractable convex surrogate. This allows for trading off guarantees on optimization (in the linear case) with potentially higher accuracy (via more expressive predictor classes). Third, our approach reverses the classic roles of accuracy and interval size: instead of fixing an error rate of α and predicting tight intervals, we seek to minimize the error under a fixed budget constraint on the mean interval size. Intuitively, allowing for variability in individual interval sizes enables the overall accuracy to be boosted by "sacrificing" some points for the sake of others. Overall, the formulation we present is geared towards maximizing expected accuracy, rather than providing (asymptotic) worst-case guarantees.
For the analysis, we partition the significance level α into a confidence term δ (over S ∼ D m XY ) and an accuracy term ǫ (over y ∼ D Y |X ), thus promoting PACstyle results. Fixing a base class B of real functions, we show how the VC dimension of interval predictors based on B can be expressed in terms of the VC dimension of thresholds over B. This covers several wellestablished classes of binary classifiers. Our results show that the VC of intervals grows only linearly in that of the threshold class. While classic methods typically offer only algorithm-specific asymptotic guarantees, our framework provides finite-sample results that depend only on the function class.
The paper is structured as follows. In Sec. 2 we review related work on prediction intervals. We then compare the single-point and batch settings in Sec. 3, and present our discriminative method in Sec. 4. Sec. 5 contains a theoretical analysis of both the statistical complexity (Sec. 5.1) and computational hardness (Sec. 5.2) of our approach. Finally, Sec. 6 contains a detailed experimental evaluation of our method on a collection of benchmark datasets. We conclude with a discussion of our results in Sec. 7.

Related Work
The simplest approach for constructing PIs includes two steps. In the first step, as in standard regression, a point-predictor f : X → R is trained. Then, intervals [ℓ, u] are constructed around the predictionsŷ = f (x). In the parametric setting, the conditional distribution D Y|X is assumed to have some parametric form (for a comprehensive review, see [6]). Given a new example x, the interval boundaries ℓ and u are then set to contain 1 − α of the probability mass. Many parametric forms of D Y|X lead to closed form solutions for [ℓ, u]. For example, assuming y ∼ N (µ(x), 1) gives: where Φ −1 (·) is the inverse normal cdf, and the conditional mean estimatesŷ =μ(x) can be learned via simple regression [20].
In Eq. (1), the interval boundaries are in effect set to be the α/2 and 1 − α/2 quantiles of the (assumed) conditional distribution. This suggests that the above two-stage process can be replaced with a direct estimation of the conditional quantiles q τ (x). Quantile regression can then be used to predict PIs [9], circumventing the need to explicitly state a distributional assumption. This can either be done by minimizing a tilted version of the absolute loss over a parametric hypothesis class [10,11], or by using non-parametric empirical quantile estimates using bootstrapping [24] or leave-one-out sampling [23].
Methods such as the above are often justified by asymptotic guarantees. These, however, do not always lead to good performance in practice. Some methods offer corrections for finite-sample biases [19,17], but are often based on further assumptions, and general sample complexity results are typically hard to obtain.
In a set of comprehensive papers on conformal prediction, the authors expand the classic single test-point setting to an online setting where a set of new examples are given in sequence [5,21]. The goal is then to minimize regret, namely predict intervals which will be good in hindsight compared to the best fixed alternative. Based on this, recent work [12] introduces flexible extensions to the basic conformal method, as well as additional finite-sample and distribution-free asymptotic guarantees. While several works on conformal prediction discuss the batch setting [2,14,15], the implicit goal in these is still to achieve a per-example error of at most α. This typically induces a large computational overhead in the inductive setting, since every new point effectively requires fitting a new model. The split-conformal method in [13] fits a single model, but at the cost of larger intervals [3]. Our method, in contrast, focuses on an inductive batch setting where the goal is to minimize the expected error, and a predictor is trained only once on a fixed training set.
Several works consider a learning setting that is similar to ours, most of which are motivated by specific applications. In [8], the authors design a multi-criteria loss and train a neural network to explicitly predict the interval boundaries. Several extensions of this approach have been suggested as well [25,7]. In contrast to our method, the above methods balance accuracy and interval size heuristically, use a discontinuous (and non-convex) objective, offer no statistical guarantees, and are applied only to small datasets.

Single-point vs. Batch
Before presenting our method, it will be useful to formally discuss the subtle but crucial distinctions between the single test-point and inductive batch settings. Let f : X → R × R be an interval predictor.
In the single test-point setting (as well as in the online learning setting used in conformal prediction [21]), the requirement is to guarantee that: where D m+1 denotes the joint probability over both S and (x m+1 , y m+1 ). In this setting, and in order for Eq. (2) to hold, the algorithm for constructing f is typically given access to both S and x m+1 . In contrast, in the batch setting, the algorithm is allowed access to S alone. To highlight this distinction we use the notations f ( · | S, x m+1 ) and f ( · | S) accordingly.
Methods which are designed to satisfy Eq. (2) can in principle be applied to the batch setting. This, however, often comes at either a computational or a statistical cost. One popular and straightforward approach is to compute a new predictor f x = f (· | S, x) for every new test point x. For example, this idea lies at the core of conformal prediction, and is used to provide regret-type guarantees for the online learning settings. While feasible, such an approach carries a significant computational overhead. To circumvent this, other approaches partition S into effective 'train' and 'test' subsets [2,13,3]. This allows them to work with a single predictor, but can result in the downgrading or loss of statistical guarantees.
One way to restore some guarantees in this setting is to tighten the condition in Eq. (2), and require that the probability of success conditionally holds for all 1 examples [15], namely: Here, the probability is over the joint distribution of sample sets S and conditional new labels y. This means that for every x ∈ X , the predicted intervals should contain the labels with probability of at least 1 − α, and is in effect what methods such as quantile regression [10,9] aim for.
Due to its worst-case nature, the performance of predictors constructed to satisfy Eq. (3) is dominated by the difficult instances. Here we argue that such worstcase requirements can be overly demanding. In accordance, we propose an objective which modifies Eq. (3) in two important ways. First, we relax the worst-case requirement over x ∈ X to hold in expectation over the marginal D X . Second, in the analysis (Sec. 5), we partition α into a confidence term δ over the training set and an accuracy term ǫ over new examples. Overall, our aim is to guarantee that, with probability of at least 1 − δ over S ∼ D m XY , we have: Intuitively, this means that when the training set is representative of the distribution, we'd like f to generalize well to new examples. In the next section, we show how this can be achieved by minimizing an appropriate loss function.

Method
Our approach considers the task of generating PIs from a model-free, discriminative learning perspective. Given a training set S = {(x i , y i )} m i=1 sampled i.i.d. from D XY , our goal is to learn an interval predictor f with a low expected loss: The loss function L (y, f (x)) should quantify how well the predicted interval f (x) fits the label y. Since a good interval is one which contains the true label, a natural choice is the following interval 0/1-loss: Under this loss, Eq. (5) can be rewritten as: Hence, a good mapping is one which produces good intervals in expectation. Specifically, a mapping f with L (f ) = α guarantees that predicted intervals will contain the true labels with probability 1 − α, on average.
When comparing the above discriminative criterion with the standard PI criterion in Eq. (3), it becomes clear that they differ only in their requirement over x. Specifically, while Eq. (3) requires that labels be covered with probability 1 − α for all x ∈ X , Eq. (7) requires this only in expectation. The discriminative objective in Eq. (7) can therefore be seen as a relaxation of the classic criterion, one which allows for variability in the probability of covering the true label. This gives our approach some flexibility, which as we show, can boost predictive performance.

Learning Objective
When considering how to train a predictor over S, it might at first be tempting to solve the following ERM: is the predicted interval, and F is a class of interval predictors. However, it quickly becomes apparent that without constraining the size of the predicted intervals, the loss can be arbitrarily low for any input. This is because, for any reasonable F , intervals can be made large enough to always contain the true labels. This emphasizes a fundamental tradeoff between error and interval size, and motivates the addition of a global budget constraint: Thus, for a given budget B, our hypothesis class is effectively restricted to include only predictors f which generate intervals with an average size of at most B. Of these, our objective is to choose one with minimal error. Note that thel ≤û constraints are always feasible when F includes functions with a bias term.
The idea of fixing a budget and minimizing error in some sense reverses their roles when compared to that of classic PI methods. In these, the first step is to predetermine and fix the amount of tolerated error α. Then, for a new point x, the interval is set to the tightest lower and upper bounds which contain 1 − α of the (estimated) conditional density of Y given X. 2 Still, for cases where a fixed-error approach is more suitable, a "reversed" variant of Eq. (9) can be solved: When L (·) is convex (such as in the surrogate we consider in next section), Eqs. (9) and (10) (9), and using cross-validation to guarantee an expected error of approximately α.

Convex Surrogate
Since the labels and predictions in our setting are real, the problem we consider may appear to be one of regression. Nonetheless, it is in essence a classification problem, and the combinatorial nature of the 0/1 loss in Eq. (19) makes it NP-hard to solve (see Sec. 5.2). Due to this, we turn to learning with tractable surrogates. In what follows we suggest a convex surrogate to the 0/1 loss, and discuss its properties.
Our surrogate loss is inspired by the ε-insensitive loss used in Support Vector Regression Machines [26,22]: Here, a point-predictionŷ ∈ R incurs no penalty if it is within distance ε of the true label y; otherwise, the penalty is linear. For the special case of ε = 0, the ε-insensitive reduces to the standard mean absolute error loss. For ε = 1, the lossL can be thought of as a symmetrized variant of the popular hinge loss used in SVMs, in which both under-and over-estimates of y are penalized. This motivates the idea that, just as the hinge loss serves as a proxy to the binary 0/1-loss, the ε-insensitive loss can be used as a surrogate to the interval 0/1-loss.
Recall that our learning goal is to produce a low-error interval predictor under a budget constraint on the average interval size (Eq. (9)). For a given budget B, one way to achieve this is to set ε = B and learn a point-predictorf : X → R withL. Then, predicted intervals are constructed vial =f (x) − ∆/2 andû = f (x) + ∆/2, for ∆ = ε. Note that for every x, the interval size is exactly ∆ =û −l = B. Under this approach, the training loss and test-time predictions are calibrated: a predicted interval is penalized only if it does not contain the true label.
Clearly, fixing all interval sizes ∆ to B is sufficient for satisfying the budget constraint. This, however, is not necessary, as the constraint requires only that the intervals be of size B on average. Hence, interval sizes can vary, and solutions with varying interval size can in principle give lower error.
The idea of varying interval sizes lies at the base of our approach. To allow for variation, we parametrize the interval size ∆, and jointly learn a point predictor y = f (x; w) and an interval-size predictor∆ = g(x; v). For learning, we use a parametrized ε-insensitive loss, with a per-example insensitivity scale ε(x) = g(x; v).
The learning objective can be written as follows: where in practice f and g are additionally regularized. For a liner parameterization, namely f (x; w) = w, x + b and g(x; v) = v, x + a for w, v ∈ R d and b, a ∈ R, the loss and constraints in Eq. (12) become convex in both w and v. Finding the global optimum can therefore be done efficiently using standard convex solvers. Note that whileŷ lies at the center of ∆, the quantiles which correspond to the interval endpointsl,û are not necessarily symmetric, and can vary across examples. This is in contrast to most methods which use fixed symmetric-tail quantiles.
Note that a possible alternative parametrization is to directly model the interval boundaries vial = f ℓ (x; w ℓ ) andû = f u (x; w u ). In the supplementary material we show that for linear predictors both parameterizations are equivalent (up to, perhaps, regularization).
The objective in Eq. (12) allows for variability in the size of predicted intervals. As in other approaches, this can be used to account for conditional heteroskedasticity. But, more importantly, a differential allocation of the budget allows for variability in the conditional probability of errors, namely: Intuitively, this allows our method to boost the overall accuracy by "sacrificing" the accuracy of some points (by reducing the size of their interval) in favor of others (by allocating them more of the budget).
Without restricting the form of∆, solving Eq. (12) would most likely result in overfitting. Intuitively, in this scenario, intervals would either be allocated just enough budget to cover the labels exactly, or allocated no budget at all. Clearly, highly is undesired as it can lead to unstable predictions. It therefore remains to show that learning parametrized interval predictors via Eq. (12) can lead to good generalization. In the next section, we analyze the sample complexity of learning in our setting , and show that the VC dimension of a class of interval predictors is linear in the VC dimension of a corresponding class of threshold functions.

Theoretical Analysis
In this section we consider three theoretical aspects of our approach: the asymptotic properties of the interval constraints in Eq. (9), the sample complexity of our approach, and the computational hardness of ERM over the 0/1-interval loss in Eq. (19).
Constraints: Eq. (9) requires that the average interval size does not exceed the budget B, and that each predicted interval is consistent (that is,l i ≤û i ). For the budget constraint, let D be a random variable specifying the size of predicted intervals, 3 with instances denoted by d. The distance between the average and expected interval sizes | 1 | can therefore be bounded using standard concentration bounds. For consistency, note that if functions in F include a bias term, then the constraint can always be satisfied. This means that given an empirically consistent predictor f , its expected consistency can be estimated using sample complexity bounds for the realizable case. In practice, inconsistent predicted intervals can simply be replaced by point predictions. Alternatively, both constrains can be replaced by a single convex constraint of the form 1 m i max{0,û i −l i } ≤ B.
Sample complexity: As noted in Sec. 1, classic PI methods consider a single confidence term α defined the joint distribution of training set and a new example. For our analysis, we separately consider the training set and new examples. We use PAC theory to determine, for every ǫ, δ ∈ [0, 1], the minimal number of examples m that guarantee an expected error of at most ǫ (over the test distribution) with probability of at least 1 − δ (over the train set). To this end, in the following Sec. 5.1 we analyze the VC dimension of learning a class of interval predictors F .
Computational hardness: Many of the discontinuous losses in machine learning lead to combinatorial optimization problems which are hard to optimize. In Sec. 5.2 we prove that this is also the case for the interval 0/1 loss in Eq. (19). To this end, we show a reduction from the NP-hard problem MAX FS, which motivates the use of the convex proxy loss in Eq. (12).

VC Dimension
In this section we analyze the VC dimension of batch interval prediction. The difficulty in analysis lies in the fact that the function classes we consider are not binary, as both labels and predictions in our setting are real. Albeit the regressive nature of the learning setup, the loss is binary, and as a result, the complexity of learning is combinatorial. To overcome this difficulty, the main modeling point here is that we consider both x and y (and not just x) as the input to an hypothesis. This allows us to express the VC dimension of a class of interval predictors in terms of the VC dimension of some base class of threshold functions.
Let B = {b : X → R} be a base class of real functions (e.g., linear functions). Denote by F (B) the class of interval predictors whose interval boundaries are set by functions in B, namely function of the form Our goal here is to bound the VC dimension of F (B). We show that this can be done by first considering the VC dimension of threshold functions over the base class B.
In binary classification, a conventional way of using real functions b ∈ B for classification is to consider the corresponding classes of threshold functions:  F (B). Formally, with a slight abuse of notation, we analyze the VC dimension of the binary class: It should be noted that analyzing the complexity of a class under a loss function is in fact the true (though sometime implicit) goal in standard binary classification as well. We prove the following result in the supplementary material: where L 0/1 is appropriately defined over the standard binary 0/1 loss guven by L 0/1 (y,ŷ) = 1 {y =ŷ} .
The main difference in the analysis of these classes lies in the input and output of the functions they include. Proof. For some f b ℓ ,bu ∈ F (B), we have: Consider a set S = {(x i , y i )} m i=1 of size m that L(F ) shatters. On the one hand, the m pairs have 2 m assignments under L(F ). On the other hand, due to Eq. (15), the number of assignments is at most that of H ≤ (B) times that of H ≥ (B), namely: where Π m (· ) denotes the maximal number of assignments of an hypothesis class over m points. Using the Sauer-Shelah Lemma and our assumptions on the VC dimension of H(B), for k ≤ m/3 we have: Solving for the maximal m satisfying Eq. (16) gives m ≤ 10k. Hence, VC(F (B)) under L is at most 10k.

NP-hardness
In this section we establish the computational hardness of minimizing the empirical risk over the interval 0/1loss as in Eq. (9). We focus on the linear case where x ∈ R d and the interval class is: Proof. We show a reduction from the NP-hard problem Max-FS [18]. In this problem, given a (not necessarily feasible) linear system Az = d of M equations over N variables, the goal is to find the maximal feasible subsystem. 4 Given an instance of Max-FS, namely A ∈ R M×N and d ∈ R M , we will construct a training set S = {(x i , y i )} m i=1 and budget B with corresponding optimal solutions. W.l.o.g. we will assume that rows in A are distinct and that M ≥ 2.
Our construction is as follows. Let m = 2M + 1.

Experiments
In this section we evaluate the performance of our method on a collection of benchmark datasets. We compare our method to several baselines on data from the UCI repository [16]. We used all dense-featured regression datasets with between 1,000 and 10,000 samples, giving a total of 8 datasets. All of our experiments use a 80:20 train-test split. For each considered setting we set all meta-parameters via 5-fold crossvalidation on the training set over a tight grid. We report average results over 100 random data splits. For datasets with less than 25 features, we augment each example with pairwise interaction terms.
At its core, our method offers a general means for exploiting the variability in interval size for reducing error. While applicable to virtually any base class of real functions, our evaluation focuses on linear functions. This is because linear functions can be plugged into almost any method, provide computational guarantees for our method as well as the other baselines, and in many cases works well in practice. By using a linear base class in all methods, we allow for a fair comparison, where results express the statistical power (rather than computational traits) of the different methods.
In accordance with the above, we compare our method (IntPred) to several baselines, some of which are designed for the fixed-error setting (and take as input a significance lever α), and some, likes ours, which are designed for the fixed-budget setting (and take a budget B as input). Our fixed-error baselines include quantile regression (QuantReg) with symmetric tails, and batch-mode conformal prediction with the absolute loss (AbsConf) and squared loss (SqrConf). We use the efficient split-conformal inference method suggested in [13,12], since other conformal methods are computationally infeasible for the datasets we consider. Our fixed-budget baselines include regressing with the absolute loss (AbsReg) and squared loss (LinReg) and adding a fixed symmetric interval of size B, as well as the fixed-budget method discussed in Sec. 4.2, which minimizes the ε-insensitive loss with ε = B (SVR). We use L 2 regularization in methods where this is possible.
Our main evaluation criterion is the test error, namely the probability that a predicted interval does not contain the true test label. Since errors can be reduced simply by enlarging the intervals, for a fair comparison we evaluated all methods over a fixed set of average interval sizes {B i }, and compared for each B i separately. This is easily achieved for the fixed-budget methods (as they take budget inputs), but not neces- sarily so the fixed-error methods, which do not offer a direct way to control interval sizes. To include these in the comparison, we first evaluate them over a tight set of confidence levels α j ∈ [0, 1]. Then, we interpolate errors from the interval size outputs, and compute approximate errors for the budgets B i . For interpolation, we used 3 rd -order monotonically-increasing concave splines with 5 knots over 30 points. This gave average R 2 values of 0.996 for QuantReg, 0.855 for AbsConf, and 0.901 for SqrConf. Furthermore, due to the difference in the scale of label values and variance across datasets, we present results for normalized budgets, where a normalized B = 1 corresponds (approximately) to an error of 0.1.
Our results are presented in Fig. 1. In the spirit of classic PI methods, we focus on the high-confidence regime with errors in the range [0, 0.2]. 5 Fig. 1 (A) presents an evaluation across all datasets. For each dataset, we show results for the B i under which the test accuracy of our method was roughly 0.1. As can be seen, IntPred outperforms all other baselines for all but one dataset (where it ranks a close second). Across all evaluations, IntPred is statistically significantly better than the other methods (Friedman test [4], P < 10 −10 ). While other methods perform well over some datasets, their performance is in general inconsistent. This is demonstrated in Fig. 1 (B) which displays errors averaged over all datasets for a range of (normalized) budgets. As the plot shows, the volatility of some baselines (especially of the fixed-error methods) results in high average errors.
Recall that, in effect, SVR optimizes over the same interval loss as IntPred, but is constrained to fixedsize interval predictions. Hence, comparing IntPred to SVR quantifies the added value (in terms of er-5 Both approaches present some difficulty when targeting very low test errors. For the fixed-budget methods, a higher budget leads to lower train errors. Hence, budgets which give a train error of 0 may be prone to overfitting. For most fixed-error methods, as there are typically no finite-sample guarantees on test error, even setting α = 1 does not guarantee an arbitrarily low test error. ror) of allowing for variability in interval size. Fig. 1 (C) therefore presents a direct comparison between the average error of IntPred and that of other methods, where each point on the plot corresponds to a different budget B i . The relative performance of SVR demonstrates that interval-size flexibility reduces the error by roughly 20% across most of the focal error region.

Discussion
In this paper we presented a method for constructing prediction intervals in an inductive batch setting. Our framework views PI estimation as a discriminative learning task, where the goal is to minimize the probability of error under a budget constraint. The algorithmic, computational, and statistical results we presented were made possible due to our suggested modification of the classic PI objective: focusing on expected errors, allowing for error variability, and separating accuracy from confidence.
While the statistical properties we presented are general, the computational guarantees we discussed hold mostly for the convex surrogate loss in Eq. (12) over linear functions. In practice, however, our method can be applied to any function class, as well as other potential non-conex loss surrogates. It will therefore be intriguing to explore the empirical performance of our method when used with non-linear predictors (such as neural networks) over non-convex losses (such as an L p -based loss with p < 1).
The experimental evaluation we presented demonstrates the empirical potential of allowing for variable errors across examples. However, our method achieves better overall accuracy at the price of explainability, as our method does not offer any guarantee on the confidence associated with each individual example. For example, a predicted interval can be small either because the confidence is high (and there is no reason to waist budget), or because it is low (and allocating budget is justified in terms of the loss). In interesting direction to explore is therefor to augment prediction with an estimate of confidence, namely the probability of the true label falling within the interval. We leave this for future research.

Nir Rosenfeld
Yishay Mansour Elad Yom-Tov Harvard University and Microsoft Research Tel Aviv University Microsoft Research

Equivalence of Parameterization
There are two natural parameterizations of intervals.
The first is to model the interval boundaries via: The second is to model the interval center and size: Here we show that for linear predictors, both parameterizations are equivalent. Specifically, we show that for every (w ℓ , w u ) there exist some (w,ṽ) whose predictions coincide on all x, and vice versa.
Let w ℓ , w u ∈ R d , and consider some x ∈ X . Note that: Similarly, for w, v ∈ R d , we have: We note that the only practical difference here would be when each component is regularized separately (e.g., with a different regularization constant).

VC of Functions and Losses
Recall that for a loss function L and a function class F , we define their composition as: we denote the by L 0/1 (H) the composition of the binary 0/1-loss function L 0/1 (·) with a binary function class H, where: Here we prove the following claim: L 0/1 (0, h z (x i )) = 1 = z i Now, assume the VC dimension of L 0/1 (H) is m. Then there exist some (x 1 , y 1 ), . . . , (x m , y m ) which shatter L 0/1 (H). This means that for every z 1 , . . . , z m , there exists some h z ∈ H such that L 0/1 (y i , h z (x i )) = z i . Consider the set x 1 , . . . , x m . For any y 1 , . . . , y m , set z i = 0 for all i. Hence, the corresponding h z is such that L 0/1 (y i , h z (x i )) = 0 for all i, which means that h(x i ) = y i as needed.