Learning from Interval Targets
Authors: Rattana Pukdee
Ziqi Ke
Chirag Gupta
Venue: NeurIPS 2025 poster ()
Keywords: Interval regression
Weak supervision
Learning theory
Primary area: general_machine_learning

Abstract: We study the problem of regression with interval targets, where only upper and lower bounds on target values are available in the form of intervals. This problem arises when the exact target label is expensive or impossible to obtain, due to inherent uncertainties. In the absence of exact targets, traditional regression loss functions cannot be used. First, we study the methodology of using a loss functions compatible with interval targets, for which we establish non-asymptotic generalization bounds based on smoothness of the hypothesis class that significantly relaxing prior assumptions of realizability and small ambiguity degree. Second, 
  we propose a novel min-max learning formulation: minimize against the worst-case (maximized) target labels within the provided intervals. The maximization problem in the latter is non-convex, but we show that good performance can be achieved with the incorporation of smoothness constraints. Finally, we perform extensive experiments on real-world datasets and show that our methods achieve state-of-the-art performance.

Learning from Interval Targets
Rattana Pukdee
Ziqi Ke Bloomberg zke 7 @bb holloomberg.noe net
Chirag Gupta Bloomberg
Carnegie Mellon University
rpukdee@cs. cmu. edu
cgupt 61 61 10100lllombbee net
Abstract
We study the problem of regression with interval targets, where only upper and lower bounds on target values are available the form of intervals. This problem arises when the exact target label is expensive or impossible to obtain, due to inherent uncertainties.
the absence of exact targets, traditional regression loss functions cannot be used. First, we study the methodology of using a loss function compatible with interval targets, for which we establish non-asymptotic gener- alization bounds based on smoothness of the hypothesis class that significantly relax prior assumptions. Second, we propose a novel minmax learning formulation: minimize against the worst-case (maximized) target labels within the provided intervals. The maximization problem in the latter is non-convex, but we show that good performance Finally, we perform extensive experiments on real-world datasets and show that methods achieve state-of-the- performance.
be achieved by incorporating smoothness constraints.
Introduction
Supervised learning has achieved significant empirical success, largely due to the availability of extensive labeled datasets. However, in many real-world tasks, obtaining target labels is challenging, which hampers the performance of these methods. This difficulty arises either from high labeling costs-for example, certain medical measurements are expensive- or from practical limitations, such as sensors that only record target values discrete intervals (e.g., every hour), leaving intermediate values unobserved. Prior work has addressed this issue by incorporating additional information into the learning pipeline. For instance, some approaches encourage model outputs to be smooth over unlabeled data [Zhu 22055] [Chapelle et al.), while others enforce models satisfy constraints derived from domain knowledge, such as physical laws [Willard et al. 2020 Swischuk et al. 2019).
In this work, we focus on regression tasks where only the lower and upper bounds of the target values (intervals) are available. Our setting relates to both weak supervision and learning with side information. Learning with interval targets generalizes supervised learning, which corresponds to the special case where the lower and upper bounds are equal. On the other hand, for many tasks, it easier and more practical for human labelers to provide interval targets instead of precise single values; thus, these intervals can be viewed as form of weak supervision. Additionally, in various settings, such intervals are readily available for unlabeled data, either from domain knowledge or inherent properties of the data, serving side information e.g., in bond pricing.
A natural strategy for learning from interval targets is to learn hypothesis whose outputs always lie within the provided intervals. Despite its simplicity, previous work [Cheng al., 2023a] has shown that this method leads to hypothesis that converges to the optimal one under two assumptions: (i) the true target function belongs the hypothesis class, and (ii) the intervals have an ambiguity degree
This work conducted during internship Bloomberg.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

smaller than I (Section 2). However, these assumptions are unlikely to hold in practice, In particular, (ii) is often violated; for example, even in the simple case where the interval is a ball of radius e around the target value y, the ambiguity degree equals 1. It is important to understand whether this approach can be effective under more relaxed assumptions.
1.1 Summary of contributions
First, we study the approach of modifying the typical regression loss to make it compatible with interval learning. This setup was first studied by Cheng et al. [2023a], and our result improves upon theirs. We show that for any hypothesis class J. with Rademacher complexity decaying as ((1/vn) such as for class of two-layer neural networks with bounded weights, we prove that, with high probability. the error decomposes into an irreducible term depending on the quality of the intervals and the Lipschitz constant of the hypothesis class, plus terms that vanish at (1/ Vn) (Theorem 4.1) Compared to the previous bound by [Cheng et al., [202aa], our result: (1) applies even when a so-called "ambiguity degree" is large (this roughly corresponds to going from the well-specified case to the agnostic case), (2) provides non-asymptotic guarantees, and (3) reveals how hypothesis class structure affects the learning guarantee. The key insight is that, when the hypothesis class is smooth, the outputs for two close inputs cannot differ significantly. As result, portions of the original intervals can be ruled out, leading to much smaller valid intervals (Theorem 3.6 and Figure
Second, we explore an alternative approach that learns a hypothesis minimizing the loss with respect to the worst-case labels within the given intervals. Since we assume that the true target values lie within these intervals, the worst-case loss serves as an upper bound on the regression loss. We consider two variants of the second approach: i) we allow the worst-case labels to be any points within the intervals, ii) we restrict the worst-case labels to be outputs of some hypothesis in our hypothesis class, thereby incorporating the smoothness property. We show that there are scenarios where the second variant performs arbitrarily better than the first (Proposition (.4), indicating that constraining the worst-case labels to the hypothesis class is preferable in the worst-case scenario.
We complement the theory with experiments that demonstrate the effectiveness of both methods on real-world datasets.
1.2
Related work
Our problem is closely related to partial-label learning, where each training point is associated with
of candidate labels instead of single target label [Cour et al., 2011 [shida et al., 2017 Feng
jet al. 2020a [shida et al. 22019] Yu et al., 2018). In classification with finite label sets, common
approaches include minimizing the average loss over the label set (Jin and Ghahramani 2002 Zhang
iet al. 2017 Wang et al. 2019 Xu et al. |021 Wu et al. [202]] Gong ct 2022| and identifying the true label from the candidate set [Lv et al. 2020 Zhang et al. 2016 Yu and Zhang 2016
Theoretical work has established learnability conditions Liu and Dietterich] 2014 Cour et al. 2011
and statistically consistent estimators [Lv et al. 2020 Feng et al. 2000b) Wen et al. 2021 based on the small ambiguity degree assumption or specific label set generating distributions.
The regression setting has received less attention. While Cheng et al. (023b) introduced partial- label regression with finite label sets and Cheng et al. 2023a] extended it to intervals, both rely heavily on the small ambiguity degree assumption. However, this assumption ooriiittiiooooiiiaallllll proposed for classification Cour et al. [201T] not be suitable for regression tasks. In classification, a hypothesis either correct or incorrect, and a small ambiguity degree ensures that, with enough observed label sets, we can recover the true label. However, in regression, we are often satisfied with predictions that are sufficiently close to the target-for for example, within an error tolerance of c-making the concept of ambiguity degree less applicable. We explore natural extension of the ambiguity degree to ambiguity radius for the regression task in Section F and argue that our theoretical analysis not only is applicable to this extension but do also provide a stronger result. In our work, we study projection loss, which is equivalent to the partial-label learning loss (PLL loss) in [n et al. [2020] for the classification, and generalizing the limiting method in Cheng et al. 2023a We provide nommasympo error bound that does not rely on the ambiguity degree and extend our analysis to the agnostic setting, Additional related work appears in Appendix

---

Figure 1:
One dimension example of learn- ing from interval targets
Figure 2: Smooth hypothesis leads to a smaller interval
Figure 3: ( An example of learning from intervals where the input is one dimension. The intervals are shown as gray boxes. natural method to learn a hypothesis that always lies within these intervals. Here, we illustrate two such hypotheses that are both valid but have different levels of smoothness. (2) When the hypothesis smooth (blue linc). it lies within intervals much smaller than the original ones, depicted by the green region (Proposition 3.4 We can extend this result to hypotheses that approximately lie within the intervals (Theorem 3.6
1.3 Preliminaries and notation
Let X' be the feature space and ) be the label space. Let f*: X' + Y denote the target function. We use uppercase letters (e.g., X) to represent random variables and lowercase letters (e.g., a) for deterministic variables. We consider regression problem where our goal is to learn function f: X + y from hypothesis class F that approximates the target function f* in the deterministic label setting. Let D be the distribution over X x y where, for each æ E X' the label y is determinis- tically given by = (x). Our goal is to learn a function ff that minimizes the expected loss err(f) = E y<D [e(s(X),)) Y)] for some loss function E: y x y + IR, satisfying the following,
Assumption 1. The loss function E 3 x y + I can be written as Ely sf (ly y for some non-decreasing function 4i, and satisfies Ely, (y,,y')
if and only if
y
Interval targets. We assume that we have access only to interval samples of the form {(z,, 4, u4) } where 4 and u, are the lower and upper bounds of yi. respectively. While we assume that the label is fixed to f (x:), we allow the intervals that is, the bounds (4,, (:))::t) to be random and assume that each tuple (Is; 14, u.) is sampled from some distribution D,, To deal with singular events of measure zero, we assume that DD, is a nonatomic distribution i.e. it does not contain point mass (see Appendix D for a full definition). We also use p to refer to the probability density function.
2 Learning from intervals using a projection loss
Since the target label y always lies within the interval 11 u], natural strategy learn hypothesis E F such that f(r E [t, u] for all E X' (Figure 1 In previous work, Cheng et al. [2023a] analyzed the following strategy.
Learn f that minimizes the empirical risk of the 0-1 loss: (o-
(1)
where lo (f 1ff(x) = 1[f()) > u]. Using l loss as the surrogate (equation (12)), they showed that of converges to f as - oa if two assumptions are satisfied, (i) Realizability, that is, f E F. (ii) Ambiguity degree is smaller than 1. Ambiguity degree is the maximum probability of specific incorrect target y', belonging to the same interval [7, u] as the true target y:
Ambiguity degree (D, Dr) = sup
{ Prrv'' E [T.UU] X =x) pp((, v) O, 1/ # # Dz
(2)
These assumptions can be impractical and restrictive. First, our hypothesis class may not contain f Second, an ambiguity degree smaller than implies that for any fixed x, if we keep sampling the interval [4, u), the intersection of such intervals (in the limit) would only be the set of the true
3

---

target fy ; that is, we can recover the true y given an infinite number of intervals. However, this assumption is unlikely to hold in practice because there usually a gap between the upper and lower bounds and the target y. For example, in the simple case where [7, u. = [y y + e] (a ball with radius 6 > around the true target y), the assumption fails since y + e/2 always lies within the interval at the same time with the true y-
We begin by defining a suitable learning objective. Since the 0-1 loss above is not continuous, it is not suitable for gradient-basse optimization techniques. To address this, we relax the loss by considering projection
mee (f() == min ((f(z).)) sElt.a]
(3)
for any general loss function E. The following proposition shows that Te is a meaningful proxy for the 0-1 loss, and can be evaluated efficiently by only considering the boundaries of the interval.
Proposition 2.1. Suppose that E y y + IR is loss function that satisfies Assumption 7 then Te(f(z), ([(,)),,,,,) u) = 0 if and only if fzx) E [1, ui), and we can write
( u) (z) 1Je(f(z).1) + 1[f(x) > vl((f(x)...) w).
The proof is provided in Appendix C.1 In the rest of the paper, we refer to T. as the projection loss. Consequently, the informal goal given in equation I can be formalized as the following objective:
If((x,) < (J((f(x;). + 1[f(x;) u.(((f(z;))
(5)
3 Properties of hypothesis that lie inside the interval targets
We will derive key properties of a hypothesis that lie inside the interval targets which will provide an essential setup for our main theoretical results in the next section. We denote F,, := {f e F (f L, U)] I 7) as class of hypotheses with the expected projection loss is smaller than This is an interesting hypothesis class to study because as we minimize the projection objective equation 5 a uniform convergence argument (e.g. |Mhrri (2018) would guarantee that the result hypothesis f belong to F,,. The value of r depends on the number of data points and the complexity of F. In particular, with probability at least 1 å over the draws (I,, 42, u,) ~ D,, for all, f E F,
1 Σ Te(((x)) + 2R, (II(F) + M
In(1/8)
Elxe(((X),
(6)
Y2
Here. R2 (IFF)) is the Rademacher complexity of the function class IIF) == (me(s + R f E F} and we assume that the Te is uniformly bounded by M. Thus, given n. M, and the empirical loss on observed data (first term in R.H.S.). we have an upper bound of which f F, which decreases with n. In the rest of this section, we will provide a property of a hypothesis f F, for any fixed > O. In particular, we show that for any v. f(x) belongs to an interval that is smaller than the original interval targets (Theorem 3.6) where the size of the reduced intervals depend on the Lipschitz constant of FF and 77. This leads to our main result: a generalization bound on the loss of w.r.t. actual labels y, thus showing that regression can be done using interval targets (Section
3.1 Effect of realizability and small ambiguity degree assumptions on F,,
We begin by examining the implications of the assumptions made in prior work (Section 2 The realizability assumption implies that f* E Fo since the projection loss of f is always zero. Second, the small ambiguity degree assumption implies that, for any x, the intersection of the intervals can only be the singleton set { As a result, we have Fo = (f E F err(f) = 0} + V.
With these assumptions, we can show that minimizing the projection objective will converge to hypothesis with zero error. The following informal argument summarizes the asymptotic analysis

---

of Cheng et al. [003b]]. Here is the high-level idea: let fn be the hypothesis that minimizes the empirical projection objective equation [5] Realizability implies that there exists f E F with an expected loss of zero. Since Jn achieves the empirical risk no larger than that of f", it must achieve empirical risk of zero. From equation we have fn E Fr,, with high probability, where
?n = 2R, (II(F) + My 1n(1/6) In general, for a hypothesis class with the Rademacher complexity decays O(1/Vn), we have 1/+2 O(1 Now as D0, have 7/. - 0 which means that Fr.. + Fo- Consequently, err(fa) -> 0 since any member of Fo has zero error.
However, when the realizability and ambiguity degree assumptions do not hold, there may be f Fo with err (f) > 0. Additionally, with a finite amount of data, we can only learn hypothesis f Fr for some 1 > 0. In the next section, we will analyze Fr, without relying on the small ambiguity degree assumption and in finite samples.
3.2 Properties of Fn
Although our results extend to the probabilistic interval setting, where multiple intervals [T, u] are drawn for each æ, we focus on the deterministic interval setting in the main paper for simplicity. In this case, each is associated with a fixed interval [L, Uz A detailed discussion of the probabilistic interval setting is in Appendix D Now, we start with the following characterization of f(x) for
E Fo and then later we will consider when f E Fn. First, we can see that when the expected projection loss is zero, f(x must lie inside the given interval.
Proposition 3.1. For any f E Fo, we have (xx E 11,, Mz) any x with p(x) > 0.
The proof is based on the Assumption and the fact that the expected projection loss zero. Next, we can further show that the interval in which f(r must lie can be made smaller than I. uz)) if we assume that the class contains only m mn-pischitz function.
Definition 3.2 (m-Lipschitz). A class F is m-Lipschitz when for any f E F and any x' E X
1f(x)) - f(=') S ml|x x'1)
We can rearrange the inequality into f(x') mm|1 x' $ f(x) f(x') ml|a - x'|l. For Fo. we can substitute f(x') with its lower and upper bound lx', tgy, which implies L. ml|a x' S
f(x < uy ml|a ='||- We denote this lower and upper bound of f(x) induced by x'.
Definition 3.3 (A lower and upper bound induced by x'). For any x, xf X, lower and upper bound of (x) induced by x' is given by
(m) 2' +-2 = lus - -mlla- - x' ||. uw'=z= := ug + ml|l - E'|1.
(m)
Furthermore, the intersection of such bound over all x' with p(x') is denoted by
((m)) ((m)))
(m))
N (((m)) baat m
(m)
(8)
p(x))>0
Following the argument above, we can derive reduced interval for any Fo- Proposition 3.4. Let FF be class of hypotheses that are m- m-Lipschitz and suppose that satisfies Assumption 1 Then for any I E Fo and.for each x with p(x:) >>
f(x) E (mm) (m)
First, we observe that (16m) ( is always smaller than [Tz, uz] because when we set x' = x, we have ((m) (m)
(m) u [L,, ug]. Second, if the hypothesis becomes more smooth, the interval p up gets smaller. This phenomenon can also be interpreted as implicitly "denoising" the original intervals by leveraging the smoothness of the hypothesis class.
5

---

May-i
Mayriz
Upper bound gap
Mxy-
ml/a xt'l
Mar
4
I
f(a))
Lg'-1
Lower bound gap
f(x)
Figure 4: An interval of x in-
Figure 5: Upper and lower bound gaps
duced by x'
Figure 6: 4 Based the smoothness property, the difference between f(x) and f(xx) cannot
exceed m x z'Il- As a result, the upper and lower bounds of f(x') imply the corresponding bounds for (xx) The lower bound gap of x' is defined the difference between the lower bound of
(a) induced by x' and the largest lower bound (DD=))): similarly for the upper bound gap. These gaps crucial in bounding the size of (2) and 8n (x) (how much we have to compensate when
Fr)) where larger gaps lead to larger values (Theorem 3.6).
Next, we extend Proposition 3.4 to F,,, The key technical challenge is that for f E F f(x) may lie outside the interval so we can't simply use Lz', Uu* as lower and upper bounds of f(x') anymore. This complicates the application of the Lipschitz property because f=²') can now be arbitrarily large or small for any x', as long as the expected projection loss is smaller than 1j. The following result uses new notion of bound gap of f(x induced by x' which is the difference between the lower and upper bounds induced by a given x' and the best lower and upper bounds from all x' (Figure 5).
Definition 3.5 (A lower and upper bound gap induced by x'). We uses the notation,
(m) mm) = 1D x'
(m)
- and ug -2
u
u 0' UD-+2:
to respectively denote the lower bound gap and upper bound gap for f(x) induced by x'.
Theorem 3.6. Let F be class of functions that are m-Lipschitz. and Ely, 1/) by y/ for any p 2 1. For any f E Fr, and for each x. with p(x) > O we have,
(m) (x) E [16m) rn,(x), up + (x:),, where,
(10)
(x) = r s.1. Ex((r 11 x { = 17. and (x) = s.1. Ex[(s ugx (m) 12) p21 1).
(11)
(12)
Proof. (Sketch) The proof leverages the smoothness property of f to establish bounds on how far the function values can deviate from their projected intervals. The key insight that (x)
significantly deviates from the reduced interval [1 D' ( then by Lipschitz continuity, f(x')
must also deviate from ugr) for nearby points x' However, such deviations are constrained
by the expected projection loss being bounded by 17. The proof proceeds in three main steps:
using the Lipschitz property, we show that fzx deviates below its lower bound f(m) by some amount then for all points x': f(x') < i (r (i - (lmma) ii) the projection loss bound ([X)( L, U)] S y) implies that such deviations cannot be too large. iii) the maximum possible deviation (x) is characterized by the equation: 7 [[[[g(z, X,r) < L)](g(x, x), L)] where g(x, x', r) represents the upper bound on f(x') derived in step i). We can also apply similar argument for the upper bound.
We compensate for f E F,, by adding buffer of size and to the interval derived in Proposition 3.4 the average lower and upper bound gap is large, then we would have a larger compensation f, S. When 17 = 0, we have Proposition 3.7. Under the conditions of Theorem 3.6 we can bound ry, (x) and s,(x), as
O. In general, we can bound the buffers r, s in terms of n
(x) < inf 8 + (n/ Pr((g(m) (m) - <0)) and s,(xx) inf 8 (n/ Pr(ug(-) (m) S /0) (13)

---

Main results
We present main theoretical results on learning with interval targets. Our analysis proceeds into three steps: first establishing a basic error bound for the realizable setting, then extending it to provide explicit sample complexity guarantees and finally extending it to the agnostic setting. We provide the sample complexity results and their interpretation here and provide the full analysis in Appendix E The following result also applicable Lp loss or a general loss function satisfying Assumption but we state the result for the (1 loss for simplicity.
Theorem 4.1 (Generalization bound, Realizable Setting), Let F be a hypothesis class satisfying i) Realizability and m- mn-Lipschirzness, ii) Rademacher complexity decays as O /n), iii) support of the distribution D, bounded, iv) loss function E(y. y') = 13/ 3²). With probability least 1 for any that minimize the objective equation for any > 0.
crr(f) S Ex (m)
(m)) D
+
D
+
In(1/0) MV
I(r),
(14)
vn
n
(a)
(b)
where D constants and [(r) Ex [1/minPrxx (1g x-X
(m))
S ST), Prx
Prx
(ug
X-8 STii]
(m)
is
decreasing in T.
Interpretation: Our error bound is divided into two parts.
(a) The first term represents an irreducible error term which depends on the smoothness property of our function class F and the quality of the given intervals (it does not decrease as n is larger). However, this term can be small. For example, in the case when the ambiguity degree is small, this error term would be zero, ensuring perfect recovery of the true labels.
(b) The second and third term capture how well we can Iearn a hypothesis that belongs to the intervals and these would decay as we have a larger sample size n. To see this, assume that have a fixed value of r, if one set n -> 3o then the third term would converge to zero. That is, (b) would converge to as n co. Since is arbitrary, we decay to zero as n - 30 and we are left with the first term (a). In addition, the function I(r) depends the distribution of intervals D,. In particular, when D, has small lower/upper bound gaps, (()) would also be small which leads to a better generalization bound for any fixed n.
to be small so that (b) would
Theorem 4.2 (Generalization Bound, Agnostic Setting). Under the conditions of Theorem 4. apart from realizability, with probability at least - for any f that minimize the empirical projection objective, for any 0,
err(f) S +x
Ex (m) - ((m) xxxx + 27 efT
D Vn
+ M
In(1/8)
+ OPT
r(r),
(a)
(15)
(m) where D,M are constants and (T()) Ex [1/min(Pxx (lg
x- S T), Prx Pug x S <)) is
(m)
decreasing function of T, prr (f) is an empirical projection error of f, and OPT is the expected ervor of the optimal hypothesis in F.
Interpretation: Our error bound for the agnostic setting is divided into three parts.
(a) The first term represent an error term of the optimal hypothesis in F, given by OPT.
(b) The second term represent an eтror term which depends on the smoothness property of our function class J and the quality of the given intervals similar the realizability setting.
(c) The third and the fourth term capture how well we can learn hypothesis that belongs to the intervals. The key difference between this agnostic setting and the realizability setting that this term would not decay to zero anymore as + do. In particular, for fixed we can see that as n - oc, we would have errpoo((] I OPT since we are minimizing the empirical projection loss and as result, this third part would converge to
27 + 20PT ((7).
(16)
7

---

Since this hold for any т, the optimal T would be the one such that 7 = OPT-I(()) and this value depends on the distribution p.
Overall, when n + 0o, the upper bound would converge to
OPT + [EExIuu00 (m) - xxxx + 2r + 20PT-
(17)
This can be small long the OPT is small, the expected lower/upper bound gaps are small and when the noise in the given intervals are small. Overall, our theoretical insight suggests that we can improve our error bound by (i) having smoother hypothesis class (smaller m) which would reduce
the interval size |u 2(m²) in the term (b) (ii) increasing the number of data points n which leads to a smaller bound in the term (c). However, if m is too small (our hypothesis is too smooth), F may not contain a good hypothesis, causing OPT to be large. Our theoretical results suggest that selecting appropriate level of smoothness to balance the terms lead improved performance in practice. In practice, we can find the right level of smoothness by treating m as a hyperparameter and tuning it on validation set.
5 Learning from intervals using minmax objective
In this section, we explore a different learning strategy: we aim to learn a function / E F that minimizes the maximum loss with respect the worst-case ÿ within the interval. We demonstrate that this approach yields a point-wise solution that can be evaluated efficiently. First, we define the worst-case loss as
(e(
= max e(f()),
(18)
sEllaa Proposition 5.1. Let be a loss function that satisfies Assumption 7 then
=
1 u "I((f()).)) + +)(f(()
+ff(x) (I(((()))))
u
(19)
2
2
Since y E [4, u.. this objective serves an upper bound on the true loss: (x( e(f()),
Consequently, if we have a hypothesis with a small expected value Efpe(f(x), err(f) will also be small. Based Proposition 5.1 we define the Minmax objective
(z), I. u)]. then the error
n 11((x,)) S
4 + [e(((x;)) I[f(x,,
4 2h
min Σ
(C((())))))
(20)
2
In particular, when E(y, v') = ly 1/1. we can show that minimizing is equivalent to performing supervised learning using the mid-point of each interval.
Corollary 5.2. Let Ely, 3/) = ly - s'l then (e(f(z), = lf(z)
4u
+ a-t and the solution of
2
equation 20 is equivalent to
1: + Ui
= arg min
(1xs)
(21)
2
This corollary establishes a connection between the heuristic of using the midpoint target and our approach of minimizing the maximum loss p. However, we note that p does not take the smoothness of the hypothesis class F into account and may lead to the worst-case labels that are overly conservative and not reflective of the target labels. Therefore, it would be beneficial to incorporate knowledge about certain properties of the true labels. In particular, in the realizable setting, f E Fu. so we may consider the worst-case labels that can be generated by some E Fo.
min max (X)( JEF FeFoo
(22)
In the realizable setting, this method also provides an upper bound for err(f), but it is stronger than p because we are comparing against the worst-case f' Fo rather than any possible ÿ E [1, u).
Proposition 5.3. In the realizable setting where f E Fo. for bounded loss e, for any f E F,
err(f) max f < (lp( L.)). Pe
(23)
8

---

We can conclude that when hypothesis has a small minmax objective, its expected loss would be small well. Moreover, we demonstrate that restricting the worst-case labels to those that could be generated by some f Fo can lead to better performance than using all possible worst-case labels. This is due worst-case labels being highly sensitive the interval size.
Proposition 5.4. For any constant e >> O and Eyy y') = by u--v v'l. there exists distribution Dj and a hypothesis class F and f E such that for fi arg minser max ([)(f(X), (X) and L, U),, err(fi) = while err(f2) >
f2 = arg
The proof is in Appendix C.8
An empirical Minmax objective using labels from Fo is given by
min max SEF P'EFo
Σ ((()))
(24)
However, there is closed-form solution for the inner maximization of objective in 24 making less efficient to optimize than equation 20) To address this, we propose alternative approaches by approximately learning f' E Fo to solve this objective.
5.1 Alternative approaches to solving a minmax objective with constraints
Recall that an empirical Minmax objective using labels from Fo is given by equation 24 However, there no closed-form solution for the inner maximization objective in 24 making it less efficient to optimize than equation 20 To address this, we propose alternative approaches by approximately learning f' e Fo solve this objective.
1) Regularization. We keep track of two hypothesis f, f' E F and introduce a regularization term based on the projection loss to ensure that f' is close Fo. We call this method Minmax (reg),
min mIX PEF PE
(((aa))
क. (.,
(25)
Here the regularization term is always non neae-positie and depends only on f'. We can use a gradient descent ascent (Korpelevich 1976, Chen and Rockafellar 1997 Lin et al. 2020) algorithm that updates f and f' with one gradient step at a time to solve this objective.
2) Pseudo labels. We could replace a hypothesis class Fo with a finite set of hypotheses f2, } where fj E F,, for some small 7). We can get fj by minimizing the empirical projection loss. We then relax our objective by learning that minimizes the maximum loss with respect to fj. We call this method PL (Max),
min
max Σ f((())))(())))))) JEF JE(L....
(26)
Since fj are fixed, learning í becomes a minimization problem, which is more stable to solve compared to the original minmax problem. Alternatively, to further stabilize the learning objective, we can replace the max over f with mean. We refer to this variant as PI (Mean).
(((r))
(27)
PEF
6 Experiments
We empirically validate our theoretical results with comprehensive experiments on five public datasets from the UCI Machine Learning Repository and 18 additional tabular regression datasets (Grinsztajn et al. 2022), where we vary our proposed interval-generatiigg algorithms to simulate different scenarios and convert regression targets into interval targets (see Appendix G for full details). To control the smoothness of our hypothesis as required by our theoretical results, we utilize Lipschitz ALPs-MLPs augmented with spectral normalization layers [Miyato et al.) 2018 that

---

abalone
12.
Projection (UIMMPP)
MAC
10-
Lpzchizz constant (Approx)
Projection (MLP)
1.6
10"4
105
30
104
302
1014
30F
30"
102
102
1014
307
10"
102
107
Usechttz
Lbschitzz
Upschitz constant
Figure 7: Test MAE of the projection method with Lipschitz MLP using different values of the Lipschitz constant. The vertical line is the Lipschitz constant approximated from the training set. The dashed horizontal lines are the test MAE of PL (Mean) and Projection approach with a standard MLP. Optimal smoothness level leads a performance gain.
ensure the Lipschitz constant is less than 1, then scaled by factor of m to control the hypothesis smoothness. We compare standard MLPs against these Lipschitz MLPs, where both model types projection losses, and we also compare with the minmax loss and proposed minmax loss variants PL(Mean) and PL(Max). We summarize our findings as follows. In terms of learning methods, the projection objective and proposed PL methods generally perform best in the uniform interval setting (where interval sizes and locations are uniformly sampled), while naive minmax excels when the target value is known to be the interval center (consistent with Corollary 5.2). More importantly, we demonstrate that smaller reduced intervals, predicted by Theorem [366 with average interval size decreasing the Lipschitz constant decreases. Our key theoretical insight about the relationship between smoothness and error bounds is supported by experiments showing that the optimal Lipschitz constant balances constraining the hypothesis class while maintaining enough capacity for low error. Finally, on 18 additional tabular regression benchmarks. Lipschitz MLPs significantly outperform standard MLPs on 14 datasets (Table I establishing smoothness as a simple yet effective method for enhancing learning with interval targets. Additional results and ablation studies are provided in Appendix L Our code is available at https: lelggittuuu thub. com/ www.bboooooobboobeeeeee wttpbeerrrginttttalll. targets
hypothesis classes indeed achieve
Comparison of the test MAE of LipMLP and MLP results on datasets from the tabular regression benchmark (with interval targets).
Table 1:
Dataset
LipMLP
MLP
Dutaset
LipMLP
MLP
Ailerons
3.278 + 0.034
4.323 0.098
Airlines Delay
38.974
0.005
39.077 1 0.008
Allstate Claims
86.547
86.542
Analcatdata Supreme
17.856 0.072
CPU Activity
1
10.560
0.087
Elevators
59.663 = 0.167
59.926 0.251
GPU
29.817
25.123 +: 0.888
House 16H
5.728 0.031
5.837 0.025
House Sales
76.607
76.716
Houses
31.515 0.332
Mercedes
8.791 0.187
11,207 0.218
Miami House
1.013 + 0.028
1.671 = 0.055
Sulfur
10.681 + 0.082
14.421 + 0.279
Superconduct
0.540 0.021
1.459 - 0.099
Topo 21
1.305 0.013
2.192
Visualizing Soil
15.803
17.898
Wine Quality
28.537 = 0.126
29.537 + 0.148
YProp 4
2.360 0.050
3.828 + 0.435
Conclusion
We theoretically investigated the problem of learning from interval targets, analyzing hypotheses that lie within these intervals and those minimizing the worst-case label loss. We derived a novel theoretical bound, providing crucial insight: understanding how smoothness such as smaller predictive intervals and a regularized worst-case label. This connection makes our theoretical findings directly applicable in practice. Future directions include challenging settings such as "noss' settings where targets might have small projection loss even outside the interval, and extend these methods non-i.i.d. settings e.g. time-series.
lead to benefits
Acknowledgments and Disclosure of Funding
Rattana Pukdee is supported by the Bloomberg Data Science Ph.D. Fellowship.
10

---

References
Dana Angluin and Philip Laird. Learning from noisy examples. Machine learning, 2:343-370, 1988.
Pranjal Awasthi, Maria Florina Balcan, and Philip Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
Jessa Bekker and Jesse Davis. Learning from positive and unlabeled data: A survey. Machine Learning, 109(4):719-700 2020.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papemot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach to semi-super learning. Advances in neural information processing systems, 32, 2019.
Thomas Brooks, D. Pope, and Michael Marcolini. Airfoil Self-Noise. UCI Machine Learning Repository, 1989, DOI:
Mathis Brosowsky, Florian Keck, Olaf Dünkel, and Marius Zöllner. Sample-specific output constraints for neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 6812-6821, 2021.
Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien. Semi-supervised learning.
George HG Chen and R Tyrelll Rockafellar Convergence rates in forward-backward splitting. SIAM Journal on Optimization, 7(2):421 444, 1997.
Pengfei Chen, Ben Ben Liao, Guangyong Chen, and Shengyu Zhang. Understanding and utilizing deep neural networks trained with noisy labels. In International conference on machine learning, pages 1062-1070. PMLR, 2019.
Xin Cheng, Yuzhou Cao, Ximing Li, Bo An, and Lei Feng. Weakly supervised regression with interval targets. In International Conference on Muchine Learning, pages $428-5448 PMLR, 2023a.
Xin Cheng, Deng-Bao Wang, Lei Feng, Min-Ling Zhang, and Bo An. Partial-label regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7140-7147, 2023b.
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 2011.
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution innputiiinn-neeeedeeetnt pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 32, 2019.
Marthinus C Du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. Advances in neural information processing systems, 27, 2014.
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 213-220, 2008
Gabriel Erion, Joseph D Janizek, Pascal Sturmfels, Scott M Lundberg, and Su-In Lee. Improving performance of deep learning models with axiomatic attribution priors and expected gradients. Nature machine intelligence, 3(7):620-633 631. 2021.
Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple complementary labels. International conference on machine learning, pages 4072-3084 PMLR, 2020a.
Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning. Advances in neural information processing systems, 33: 10948-10966 2020b.
Daniel Fu, Mayee Chen, Frederic Sala, Sarah Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. International conference machine learning, pages 3280-3291. PMLR, 2020.

---

Xiuwen Gong, Dong Yuan, and Wei Bao. Partial label learning via label influence function. In International Conference on Machine Learning, pages 7665-7678. PMLR, 2022.
Léo Grinsztajn, Edouard Oyallon, and Gael Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? Advances in neural information processing systems, 35: 507-520, 2022.
Cho-Jui Hsieh, Nagarajan Natarajan, and Inderjit Dhillon. Pu learning for matrix completion. In International conference on machine learning, pages 2445-2453, PMLR, 2015.
Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama. Learning from complementary labels. Advances in neural information processing systems, 30, 2017.
Takashi Ishida, Gang Niu, Aditya Menon, and Masashi Sugiyama. Complementary-label learning for arbitrary losses and models. In International conference on machine learning, pages 2971-2980. PMLR, 2019.
Rong Jin and Zoubin Ghahramani. Learning with multiple labels. Advances in neural information processing systems, 15, 2002.
Giannis Karamanolakis, Subhabrata Mukherjee, Guoqing Zheng, and Ahmed Hassan. Self-training with weak supervision. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 845-863, 2021.
Davood Karimi, Haoran Dou, Simon K Warfield, and Ali Gholipour. Deep learning with noisy labels: Exploring techniques and remedies in medical image analysis. Medical image analysis, 65:101759, 2020.
George Em Karniadakis, Ioannis G Kevrekidis, Lu Lu, Paris Perdikaris, Sifan Wang, and Liu Yang. Physics-informed machine learning. Nature Reviews Physics, 3(6):422-440, 2021.
Karthik Kashinath, M Mustafa, Adrian Albert, JL Wu, C Jiang, Soheil Esmaeilzadeh, Kamyar Azizzadenesheli, R Wang, Ashesh Chattopadhyay, A Singh, et al. Physics-informed machine learning: case studies for weather and climate modelling. Philosophical Transactions of the Royal Society A, 379(2194):0200093,, 2021.
Durk P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling, Semi-supervised learning with deep generative models. Advances in neural information processing systems, 27, 2014.
Ryuichi Kiryo, Gang Niu, Marthinus C Du Plessis, and Masashi Sugiyama. uusibiee-unlabeled learning with non-negative risk estimator. Advances in neural information processing systems, 30, 2017.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint arXiv:1610.02222,, 2016.
Xiaoli Li and Bing Liu. Learning to classify texts using positive and unlabeled data. In IJCAI, volume 3, pages 587-592. Citeseer, 2003.
Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In Proceedings of the IEEE international conference on computer vision, pages 1910-1918, 2017.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
Liping Liu and Thomas Dietterich. Learnability of the superset label learning problem. In Interna- tional conference machine learning, pages 1639.1637. PMLR, 2014.
12

---

Philip M Long and Rocco A Servedio. Random classification noise defeats all convex potential boosters. In Proceedings of the 25th international conference on Machine learning, pages 608 615, 2008.
Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identification of true labels for partial-label learning. In international conference on machine learning, pages 6500 6510. PMLR. 2020.
Tengyu Ma. Lecture notes from machine learning theory, 2022. URL WtRphtttt://wb..taaffeet
edd/class/stats22
Ron Meir and Tong Zhang. Generalization error bounds for bayesian mixture algorithms. Journal of Machine Learning Research, 4(Occ):839--5) 860, 2003.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference Learning Representations, 2018.
Mehryar Mohri. Foundations of machine learning, 2018.
Warwick Nash, Tracy Sellers, Simon Talbot, Andrew Cawthorn, and Wes Ford. Abalone. UCI Machine Learning Repository, 1994. DOI: htts://dbi.org11.2444/////
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances neural information processing systems, 26, 2013.
Rattana Pukdee, Dylan Sam, Zico Kolter, Flrii-Florina Balcan, and Pradeep Ravikumar. Learning with explanation constraints. In Proceedings of the 37th International Conference Neural Information Processing Systems, pages 49883-49926, 2023a.
Rattana Pukdee, Dylan Sam, Pradeep Kumar Ravikumar, and Nina Balcan. Label propagation with weak supervision. In The Eleventh International Conference on Learning Representations, 2023b.
Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the VLDB endowment. International conference on very large data bases, volume 11, page 269. NIH Public Access, 2017.
Alexander J Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data programming: Creating large training sets, quickly. Advances neural information processing systems, 29, 2016.
Laura Rieger, Chandan Singh, William Murdoch, and Bin Yu. Interpretations useful: penalizing explanations to align neural networks with prior knowledge. In International conference on machine learning, pages 1116-8126. PMLR, 2020.
Andrew Slavin Ross, Michael C Hughes, and Finale Doshi- Velez. Right for the right reasons: training differentiable models by constraining their explanations. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 2662-2670, 2017.
Salva Rühling Cachay, Benedikt Boecking, and Artur Dubrawski. End-to-end weak supervision. Advances in Neural Information Processing Systems, 34: 1845-1857, 2021.
Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala. Univer- salizing weak supervision. In The Tenth International Conference on Learning Representations, 2022.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk. Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi cemi-supervised learning with consistency and confidence. Advances neural information processing systems, 33:59--608, 2020.
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEFE transactions on neural networks and learning systems, 34(1344(1) 11188811551,33 2022.
13

---

Renee Swischuk, Laura Mainini, Benjamin Peherstorfer, and Karen Willcox. Projection-basee model reduction: Formulations for physies-based machine learning. Computers & Fluids, 179:704-717, 2019.
Pnar Tfekci and Heysem Kaya. Combined Cycle Power Plant. UCI Machine Learning Repository, 2014. DOL:
Ruth Urner and Shai Ben-David Probabilistic lipschitzness niceness assumption for deterministic labels. Learning Faster from Easy Data- Workshop@ NIPS, volume 2, page 1, 2013.
Jesper E Van Engelen and Holger H Hoos. A survey on sumi-supervised learning. Machine learning. 109(2):333-440, 2020.
Qian-Wet Wei Wang, Yu-Feng Li, and Zhi-Hua Zhou. Partial label learning with unlabeled data. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3755-3761, 2019.
Hongwei Wen, Jingyi Cui, Hanyuan Hang, Jiabin Liu, Yisen Wang, and Zhouchen Lin. Leveraged weighted loss for partial label learning. In International conference on machine learning, pages 11091-11100. PMLR, 2021.
Jared Willard, Xiaowei Jia, Shaoming Xu, Michael Steinbach, and Vipin Kumar. Integrating physics- based modeling with machine learning: A survey, arXiv preprint arXiv:2003.04919 1(1):1-34, 2020.
Dong-Dong Wu, Deng-Bao Wang, and Min-Ling Zhang. Revisiting consistency regularization for deep partial label learning. In International conference on machine learning, pages 24212-2422 24225. PMLR, 2022.
Jin-Long Wu, Heng Xiao, and Eric Paterson. Physics-informed machine learning approach for augmenting turbulence models: A comprehensive framework. Physical Review Fluids, 3(7): 074602, 2018.
Ning Xu, Congyu Qiao, Xin Geng, and Min-Ling Zhang. Instance-dependent partial label learning. Advances in Neural Information Processing Systems,
2021.
Wanqian Yang, Lars Lorch, Moritz Graule, Himabindu Lakkaraju, and Finale Doshi Velez. In- corporating interpretable output constraints in bayesian neural networks. Advances in Neural Information Processing Systems, 13:1222111 2020.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. International conference on machine learning, pages 40-48. PMLR, 2016.
I-Cheng Yeh. Concrete Compressive Strength. UCI Machine Learning Repository, 1998. DOI: http:://dbb.ogg//002444333/.x11
Fei Yu and Min-Ling Zhang. Maximum margin partial label learning. In Asian conference on machine learning, pages 96-111. PMLR, 2016.
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In Proceedings of the European conference on computer vision (ECCV), pages 68-83, 2018.
Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. S41: Self-supervised semi- supervised learning. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1476-1485, 2019.
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang, Mao Yang, and Alexander Ratner. Wrench: comprehensive benchmark for weak supervision. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks' Track (Round 2).
Jieyu Zhang, Cheng- Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner. survey on program- matic weak supervision. arXiv preprint 230402200.. 2022.
14

---

Min-Ling Zhang. Bin-Bin Zhou, and Xu- Ying Liu. Partial label learning via feature- awate disam- biguation. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1335-1344, 2016.
Min-Ling Zhang, Fei Yu, and Cai-Zhi Tang. Disambiguation-free partial label learning. IEEE Transactions on Knowledge and Data Engineering. 29(10)2155-2167, 2017.
Xiaojin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Springer Nature, 2022. Xiaojin Jerry Zhu. Semi-supervised learning literature survey. 2005.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section 4, Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Appendix B
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
Appendix C, D for full proofs
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [Yes]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/ gww.es/dieeeseee Sodee ssionPolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https)
cltaps..c/public//
Cooe S Submisssss wwlbmmsssonoooiis.. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
All plots have an error bar.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
18

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The paper requires a very small amount of compute to run so we did not provide this information.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question:
Does the research conducted in the paper conform, in every respect, with the httpshhhpp....errrr...acaaaaaaap http:///uurppp..cccppuii/t///tea
NeurIPS Code of Ethics
Answer:
[Yes]
Justification: N/A
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Foundational research
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Foundational research
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Appendix H
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com dataaetteett has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Question:
Answer:[NA]
Justification: the core method development in this research does not involve LLMs
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ht /ttt:::://r/psp/// http///rrrppscccooooooeeeeeeee/e
LLM) for what should or should not be described.
22

---

Supplementary Materials: Learning with Interval Targets, NeurIPS 2025
A
Additional related work
Weak supervision. Our setting is part of a sub-field of weak supervision where one learns from noisy, limited, or imprecise sources of data rather than a large amount of labeled data. Learning from noisy labels assumes that we only observe a noisy version of the true labels at the training time where
the noise follows different noise models (usually random noise) [Natarajan et al. [201]] Li al.
2017. Song et al. 2022, Angluin and Laird, 1988) Karimi et al. 2020 Awasthi et al. 2017 Chen
ct al. 2019 Long and Servedio| 2008) Diakonikolas et al. 2019]. Programmatic weak supervision, on the other hand, assumes that we have access to multiple noisy weak labels (but deterministic
noise) specified by domain experts, e.g. from logic rules or heuristics methods [Zhang et al.) 2022
Zhang al. Ratner et al. 2 2017 Rühhing Cachay et al. 202 Shin et al. 2022 Karamano lakis
ct al.
2021 Fu et al.J [2200] Pukdee et 20233b.. Positiiv-unllaelee unlabeled learning is another type of
weak supervision where the training set only contains positive examples and unlabeled examples
Kiryo et al. 2017 Du Plessis et al. 2014 Bekker and Davis 2020 Elkan and Noto 2008 Li and
Liu
2003
Hsieh et al. 2015
Learning with side information. In contrast to the weakly supervised setting, we have access to standard labeled data but also have access to some additional information. This could be unlabeled
data which is studied in semi-supervised learning [Zhu] 2005 Chapelee et al. Kingma et al. 2014
Van Engelen and Hoos 2020
Berthelot et al.] |019 Zhu and Goldberg [022] Laine and Aila 2016
Zhai et al., 2019 |Sonn et al.
2020 Yang et al. [016]] different constraints based on the domain
knowledge such as physics rules
[Willard et al. 2020 Swischuk et al. 2019 Karniadakis et al. 2021
Wu ct al. 2018 Kashinath al.
2021 explanations Ross et al. 201 Pukdee al.] [2023a Rieger
et al.] 2020 Erion et al.) 2021 or output constraints (Yang et al. 2020 Brosowsky et al. 2021 which
similar the interval targets. In some settings, interval targets
the best thing one could have
(similar to the weak supervision setting) but in many cases such as in bond pricing, target intervals
readily available in the wild and could also be considered as a side information.
B Limitations
Our theoretical results rely on a Lipschitz continuity assumption to characterize the size of the reduced interval. We note that other similar assumptions, such modulus of continuity, could also lead to analogous results. Importantly, we do not impose any assumptions on the distribution of the intervals themselves. While this generality be viewed strength, it would be an interesting direction for future work to investigate whether stronger results are possible under additional structural assumptions on the intervals. Our generalization bounds are derived via uniform convergence. This approach is necessary to accommodate general loss functions and hypothesis classes but may be suboptimal compared to specialized analyses such as those for least squares regression-whice do not rely on uniform convergence and can yield sharper rates. For clarity, we assume deterministic labels, although our framework allows for interval targets to be random (see Appendix (D) Extending the results to fully random labels is in principle possible, though the notion of correctness i.c.. whether the interval contains the labol-s less well-defined in such settings. Finally, we assume that the data distribution is nonatomic, which enables us to reason about zero-probability events. This a standard technical condition that does not limit the applicability of our results to discrete or sinite-support distributions.
23

---

C Additional proofs
C.1 Proof of Proposition 2.1
This implies that there exists y E [t. u/ such that f(f(z). y) 0. From the assumption on & that fyy, v') 0 if and only if y y', must have f(x) = y E I1 ul as required. On the other hand, f(() E [L, ul, it clear that 0 since E(y.v') 2 0.
Proof. First, we assume that (f(f
(e(f(x) u) [(f(z),
Now, assume that we can write l(v. v/) +lly - v for some non-decreasing function v we have (e(f()),
min (1f(z) 5)
(28)
DElt,a)
v min 1f(x) Ø
(29)
DElt,u)
w11 - ((x)) [(x) <1
((0)
1 f())
(30)
((((x) u) [())
[[(x)) < ()((())))))
> u){([()).u).
(31)
Here we rely on the assumption that ei is non-decreasing so the minimum value of (xx) happens when x is also at the minimum value.
C.2 Proof of Proposition
Proof. Since fi * fz. there exists such that (z) # fz(z). Without loss of generality. let fi()) [2(2). Consider a simple one point distribution DD with only one data point (a. y) =
(2() + <) with probability mass and DD, be another one point distribution with (x.1,u) =
(x., [(x e, (x2) c). We can see that 0 ED, (x)( I, U)] < EB, (x(2(() U) c
while (f(22 f(1)) + +) = err(fi) > err(f2) = =!.
C.3 Proof of Proposition E.4
Proof. From the Proposition 2.1
x(f(z),l, = 1f(x)) < ([(((()),))+(((C)) u)((f(x)..)
(32)
Recall that y E [1, u]. we consider cases,
1. f(x) < 1, (((()),) ((fx),)) 401 - f(x))) S - - f(x))) = [(((x),))
2. f(x) > u, u,),)(((),,,))))), = (([(x),)) (01((x))) - -10 v(((c)) - (((()),))
3. i f(x) u =(( {(((()))))))
((f(z),))
C.4 Proof of Theorem
MS
Proof. From the triangle inequality,
((f(x), v) fop, (x))(()))))
(33)
We can take an expectation to have
([((f(X), Y)] < E[((f(X), fop (X)) OPT.
(34)
Since fort E Forr which from Theorem 3.6 can bound
fop((z) p (o)) ((m) + SOPT(x)].
(35)
Similarly, for any f e Fr we have
f (
rT(x),, (m)) + s, (x))
(36)
Finally, we can bound the error between any two intervals with the maximum loss between their boundaries.
D
24

---

C.5 Proof of Proposition 5.1
Proof. Since we can write E(y.3') = 10y I/l) for some non-decreasing function v we have
(e(((z),,, max (1 51) sEl1,a)
(37)
w max 1f(z) - 51)
(38)
DEllia)
[ulu - f(x)) f(x) < L
(39)
(v((()) -1) f(x) 2 Ltu
1 u ((f(()), u) + 1[f())
1+ " ")((f()).
1[f(>) S 2
(40)
2
Here we rely on the assumption that v is non-decreasing so the maximum value of (x)) happens when x is also at the maximum value.
C.6 Proof of Corollary 5.2
Proof. Since Ely, yy 5/), from Proposition 5.1
we have a closed form solution of p.
p,(S(z),l, = 1[)(x) < 1+ [(([()) + 1[(()) > 1 - (e(((x),))
(41)
2
2
1 *t(1(u fx))) + 1lf(x)
1 U [ff(z) -l)
= =1[((z) -
((u
>
(42)
2
2
1 u [(u
I+ u
|t
1 ++ u
1 u
1 u
1[f(x) s
f())) + l[f(x) >
1(f(z)
1)
2
2
2
2
2
2
(43)
1+ u
1+ u
f(x)) + 1[f(x) > 1+
1
1
2 + +1f((z) $
2 (f(x)
(44)
2
2
2
= 1f(()) I+ u-1 2
(45)
2
Since ui, 4 are constants, dا would have no impact on the optimal solution of equation 20 and therefore, the optimal would also be the same as the one that minimizes E [f(x))
2
litt
C.7 Proof of Proposition 5.3
Proof. From the realizability assumption, we know that f Fo, therefore, s max Pe
crr(f) =
(I),
(46)
On the other hand, Let s" E Fo. be hypothesis that achieves the maximum value of ("())) Since fd Fo know that
(X),
(47)
Since the projection loss is always non-negative and is continuous, from Lemma D.I
can conclude
that Te (x) u) = 0 for any x, 1, a with positive density function p(z, 1, u) 0 which implies
f"(x) u.. Therefore, for any with p(x) 0,
{(f(x), f" (x)) < max e(f(x). D) = (e(f
(48)
We can take an expectation over X, L, U and have the desired result.
C.8 Proof of Proposition 5.4
Proof. Consider when X' = (0, 1} and / such that (0) (1)) = 0. Consider hypothesis class
of constant functions F (f: - R f(x) = d, Va E X). We can see that f E F. Assume that we have uniform distribution over X'' and we also have deterministic interval [[xx), u(x)). Assume
25

---

that for = 0, we have an interval [1(O), u(0)] = a-a, c| for some a > 0 and for 1, we have an
interval [1), [[1] = [-c, 2c). Since F is class of constant hypothesis, for all x, we must have f(()) E a- -, 26] = [_,, This implies that
Fo (f fx)) e, Vx E E,
(49)
Therefore,
fi arg min max
f
(50)
fer y'
arg min max
2 (l)(0)- ((0)) + (f(1) (())
(51)
fer M'e
arg min max [f(0) - cl fEF cE|-c,t]
(52)
(53)
By symmetry, we can see that the optimal fi = 0 which means that err(Ji) = 0. On the other hand, consider /2, from Corollary 5.2 f2 equivalent the solution of supervised learning with the midpoint of each interval,
f2 = arg min (X),(X SEF
(54)
1 ş [l](()
-a - +
-6 + 2E
arg min JEF
15(1)
(55)
2
By symmetry, the optimal f2 should lie in the middle between these two points so that fa(x)
-a/2 ee. We would have (rr = a/2 22+ + el which can be arbitrarily large as a - co.
D Probabilistic interval setting
In this section, we consider the probabilistic interval setting which is when, for each æ, the corre- sponding interval drawn from some distribution D1.
Assumption 2. A distribution P with a probability density function p(a) is a nonatomic distribution when for any x such that p(æ) 0 and for any e > O, there exists a set Sz.e C. B(x,e) e) (a ball with radius e) such that (r()).)) > O. We assume that the distribution 'D and DJ are nonatomic distributions.
Lemma D.1. Let P be a nonatomic distribution over X with a probability density function p(æ). For any continuous function f X oo), if [x)] = then f(x) 0 for all with p(x) O.
Proof. We will prove this by contradiction. Assume that there exists x with p(x) > 0 such that f(z) > 0. By the continuity of f. there exists 61 0 such that for any x' E B(z, 81) such that [f(x) - f(x') < f(x)/2 which implies that f(x') > f(x)/2. In addition, by the nonatomic assumption, there exists S2,5, S 0ix, such that Pr(S..5)) O. Therefore.
Ep]f(X)] = 1
JwEx f(w)p(w)dw
(56)
f(w)p(w)dw
(57)
WES..
f(z)p(w) dw
(58)
2
f(
> 0.
(59)
This leads to contradiction since Ep[f(X)) > 0.
Similar to the deterministic interval setting, for any f E Fo. has to lie inside the interval as well. One difference would be that in the probabilistic interval setting, we can have multiple intervals for each x and since has to lie inside all of them, f would also lie inside the intersection of all of them for which denote as [e, ūz] for each æ.
26

---

Proposition D.2. For any f E Fu. and a loss function that satisfies Assumption / for any z with positive probability density p(x) > we have
f(x)
n p(a,l,)300
[1 := 11,, Uzg.
(60)
Proof. Let f E Fo so we have ( that p(a, 1, u) > 0, we have ([(x)),,,) = 0 which implies f(z) E Ir u] (From Proposition
U)] 0. From Lemma D.1 for any (x,1, u) such
2.Ip. Therefore, by taking an intersection over all possible intervals, we would have f(x)
Moa.dasoll.. u| = (z.u2)
Proposition D.3. Let F be a class of functions that are m-Lipschitz. For any x, x', denote (mm) s'- 1.r - ml| 2'11. a(m) = Ug + +mll - ||. then for any f E Fo and for any x with positive probability density p(x) 0,
f(x) n 2 = (mm) [mm]
D-vrr D
(61)
Proof. Consider f E Fo. since f is m--Lipschitz, for any x, x' E X, we have 1f(x) f(x') s
m// x'1l which implies
f(x') ml - I'll S f(z) - f(x') + m - x'll
(62)
We illustrate this in Figure which implies
Then, from Proposition D.2 for f E Fo. we have Ln S 5 S Un
(m) 2' = Lg. - -0|m - x'1l S f(x') mm|+ - x'll
(63)
- uz + ml|k - x'11 2 f(x') - mmI + +'
(64)
Substitute back to equation equation 62 and take supremum over x', we have
(Tm)
x' 2' Sf(x)= < 22
(m)
(65)
(m) sup
x' S](x) S in [
(66)
x
1 Sf(x) < D
(m)
(67)
Next, we present the probabilistic interval version of Theorem 3.6 except that we use i, instead of I, u. Theorem D.4. Let F be class of functions that are m-Lipschitz. f: f: y y - R is loss function that satisfies Assumption For any f T Fr, and for any x with positive probability density p(x) >
Details of the proofs are the same,
(xx E (m) D (rn(x), (m) + +x(()))
(68)
where [mm) =m()) D-sx: are defined as in Proposition D.3 D.3 and
1. ra(x)) = such that 11 E(10g(2, < XX),,(s,X,r),.l)) L)] where g( x',, Ts.
(r (Tmm) ((m)) )))
2. 8 (x) = = such that 11 = E[[(2, > (],(h(2,X,8))) where 1(x,x',8) = us!
(s (m(m) +2 d [((m] alm))a))
Proof. Now, we will show that if f E F,, then we have f(x) instead. First, we explore what would be requirement to change the lower bound f(x) from flm) Pioz to [(m)
[Tm]] r,((x,, (m) + 8, (x))
P-sa Again, from Lipschitzness.
f(x') ml|z x'11 S f(x)
(69)
27

---

Taking supremum here, we have
f(x') - -m|[x - 2' $ f(x)
(70)
Here, we will use sup, f(²') m|| - x'1l as a new lower bound for (xx) Assume that it is lower than 7(m) D-orr can write
sup f(x') - -m|[ - 2'll
[tm)
(71)
D-+2
for some > 0, then it implies that for all x' E A, we must have
[(x') - m |z x'1l S (m
(72)
(s(x') - ls. + (Lz' - m1 x'll) S 7(m)
(73)
f(x)) s i - [(m) + _tm)
(74)
f(z') s Lo (r- (2bm)) (tm) x2))))
(75)
That is, if one can change the lower bound of fxx from Tm)) Tm then for all x', f(x') has D_a
to take value lower than Lar by at least (7/-0 [m
+2) whenever this term is positive. However,
y that fax') can't be too far away from Lar since (X))( L,U) S 1y. From Proposition
2.1 if one can write e(v, y²) = (0 - 1/ for some non-decreasing function zú then we have
Te Te(f(x), u) = (x) < (((((()))) + 1[fxx) > u){(f()).u).
(76)
Therefore.
2 E[Te(s(X), I, U) 2 B[[S(X) (X)(((X), r.)].
(77)
Let g( - -(r -r-- (itm)
)) be the upper bound of f(x') for any x' as we derived Since 1aa < L)e(a, L)] is decreasing function over a, equation
[mm] (x)
D
in the equation equation equation 77 implies
75
n 2 (X) < LL(((())) E|L[g(, < L)((g(,,X,r),,
(78)
We can also see that x(x,,",r) is decreasing function of r which means E[][g(a, X,r) [)((g(z, (z, X,r), L)] is an increasing function of r. The largest possible value of r would then be the such that the inequality holds,
7 E [g(2, X,r < X,,g((,X,))).
(79)
which we denoted this as (x) Similarly, we can show that if the largest possible value of 8 such that we can change the upper bound of (xx from ūfm)) to ((m) + s is given by
77 = [[[[h(x, X, s) > U)e(h(z,
(80)
where f( x', u.. + (s (ī _(m=))))
Theorem D.5. Under the conditions of Theorem
D.A if further assume that for each x, the lower and
upper bound of y is given by deterministic function (z)), ) u(x)] and E is an lp loss E(y, y/) ly y'
and denote the lower bound gap and upper bound gap of f(x) induced by x' as oz D (m())
(m) 7mm)
(mm) +z and ugz--x= +z " then we have
(2) = r s.f.
B((r 1gX - |
(m) }==== 17
(81)
sn(x)= = S. E((s ug (mn) = 1]
(82)
where we denote c4 max(0, c). Further, we can bound r2(2x) and (2))
(x) S inf 5 +
"
11/1
(83)
5 Pr(lgg(m) < <))
(m)
s,(xx S inf +
1/p.
(84)
3
Pr(ug x +x < 8)
(m)
28

---

Proof. Since [t, u| is deterministic for each r, we have L, = ((x). By the property of squared loss,
[[1[g(z,X,r) L)((g(e, = Ei(L - g(x, X, r)))]
(85)
[B(((()) g(x, x,)))
(86)
[[(((()) (Ix - (1
70m) 1
(87)
E[(r 1gX )+]
(88)
as required. We can use similar argument for (z)). Next, we can see that for any valid value of r.
n Bi 1g (m))
x [[((r 6) 1 (m))
6]] = (r 6) Pr(lgx=> - 6).
(89)
By rearranging, S 8+( π
1// Taking the infimum over ó, we have the desired inequality.
Pr(lg' σσ)
Again, apply the same idea for (1).).
E Sample complexity bounds
E.1 Error bound in the realizable setting
We begin with a foundational result that characterizes the error of any hypothesis in F, based on the reduced intervals established in the previous section.
Theorem E.1 (Error bound, Realizable setting). Let FF be a class of functions that are m-Lipschitz, assume that f E Fo. then for any Frp.
err(f) < EE|((, (o(((E,)((X)) (6(X),,(())) (m) when (x) = [1(m) (x), u D-ox + (x)] represents the reduced interval from Theorem 3.6 and d(C, I2) max(e(l,, u2), [(U1, 12)) when I 111 u,, 11,, uz).
(90)
We remark that this bound can be tight for certain hypothesis classes For example, consider the where F consists of constant hypotheses and let oc. In this scenario, we have (x) + ro(x)= = 0 and (x) + Io()). For each æ, the error bound is given by
d(e, Io(=), Jo(x)) 8((5") " E(sup lar, inf unr); x²
(91)
representing the loss between the boundaries of the intersected intervals. It is tight since the inequality holds when f and f each take values at the respective boundaries of the intersected interval.
E.2 Main sample complexity result
Building Theorem E. we now present main result, which provides explicit sample complexity guarantees for learning with interval targets for any hypothesis classes whose the Rademacher complexity decay O(1/ n)). This includes class of linear models class of two-layer neural networks with a bounded weight MM 2022]. To simplify the Thcorem, we will only present the statement and the proof for the case of L1 loss. However, an extension for general Lp loss is straightforward where we can replace the triangle inequality with the Minkowski's 's inequality.
Theorem E.2 (Generalization bound, Realizable Setting). Let F be a hypothesis class satisfying the conditions of Theorem E. (realizability and m-Lipschirrness), ii) Rademacher complexity decays as O(1/v/// /n). iii) support of the distribution Dr bounded, iv) loss function is fly, y/ = ly v'). for any T > 0,
With probubility at least 1 for any J. that minimize the objective equation) 5
(D+M)
In(1/5)
efr(f) < Ex I| (m)
- (m)
10xx1+++
(Vn
+
I(r),
(92)
n
(a)
(6)
where D, are constants and T(7) Ex ( [1/min(Prx((((m) (m) S T), Prx Prx (m)
(19
X- ST)]
x-2
decreasing in
29

---

Proof. Step 1: Derive the bound in term of 77. Recall that from Theorem E. we have
err(f) S RR|d(,, Tx(X), (x)))
(93)
when (x) = (/0 ryy (1)(2), u + 8, [z)]] Since we have an l loss, we have
d(e, L, = ( - -0 + 5xx(
(94)
Substitute this back in, have error bound
err(ʃ) < El (m)
10m)) max(r, (X), (X))1
(95)
< B (m)
D Bi| max(r,, (X), 5, (X))]] (triangle inequality).
(mm)
(96)
Now, our goal to bound the term E| (rxx(r,(X)) 8n (X)) From Proposition 3.7 we know that (m)
(, = inf r + (n/ Pr(lgx (m) S T))
and sny (z) S inf T (n/ Pr(ugx- T)).
(97)
We place 5 with T in the original statement because we will use as something else, later. This implies that
( (mn) I ST), Pr(ugx (m)) S r))
(xx)))())),,,(x)))) S inf
(98)
min((r((90X
We define A(D,T) = - (m) ST) Pr(ugx (m) S <T)) so that
max(r,(2)) Sn (z)) inf + n)(
(99)
We can see that when A(D,T) T) and A(D, +) is decreasing function in Substitue this back to the equation 96. for any > 0, we would have
err(f) Bl Bl (m)
(mm) D + B
(100)
< B _ D
((m)
1 +)
(101)
x ((m) -1
-
(102)
where define 1'(2,r) = ([), We can see that every term in the equation above is independent of 77, apart from the term 77 itself. This provide a more explicit error bound in term of r7.
Now, we will bound 7) in terms of the number of sample
Step 2:
Bounding y in terms of the number of sample. Recall the result from equation 6 with probability at least 1 - over the draws (x,, li us) ~ Dr, for all f F,
" (f(((( Σ (e(((z)) 2R, (I(FF) + M
In(1/8)
(103)
n
Here, R. (TT()) is the Rademacher complexity of the function class I[FF) = (me(( (x),
f and we assume that the ग. uniformly bounded by M. We recall that we learn by minimizing the empirical projection loss
arg min TE (e((s,) u.).
(104)
Under the realizable setting, this objective would be zero since f E F which implies that f* has zero empirical projection > mx(f"(x;) (z:), 4, u.) 0 but f also minimize the empirical projection loss so f must also have zero empirical projection loss. We write nff) refer to the 7 value of Formally, defined as
(ff) E (,
(105)
Substituting f to the bound above, we have
ln(1/8)
n( 2R, (I(FF) M
(106)
30

---

The next step is to bound the Rademacher complexity R, (II(F) in terms of (FF. We will do this by first showing that (x(f()) Tz(f(z),4, u4) is a Lipschitz continuous function and then reduce R, (TT( to (F) with a variant of Talagrand's Lemma [Meir and Zhang, 2003]. From our assumption that the support D a bounded set, and our hypothesis class a class of two-layer neural network with bounded weight, there exists constant C' for which, we have [f(=)) I C' almost surely. Here, we will show this property for Lp loss, recall that
(.((())) (e(f(x)), u:)
(107)
- -(=-f(=))1(()) < + u))(if(()) udj
(108)
Differentiate with respect (xx), we have
V ((o)). rl(4 (()))=1(((()) <4] (f(x) u.)--11((()) u]
(109)
S 2p(2C)P-
(110)
Since this gradient is bounded for any fzz). conclude that (x)) is B- B-Lipschitz for some constant B. Now, we unpack the definition of the Rademacher complexity,
Rs (II(F) E ((r. [B 1,1)
(sup JEF n
u()(
(111)
(( [Ban 1,1) (sup JEF
(f(((z;))o.l
(112)
We recall the following result from Meir and Zhang [2033] that when Φ1, 02. ... on be functions where di R + IR are oi are Li-Lisschitz, then
(sup
Σ (s:)))) S E. Bao(-111) (sup FEF ni
sup L JEF 12
1
(113)
Applying this result with the fact that is B-Lipschitz for all i =1,, by....h n. conclude that
R, (I((F) = BF (Eo, (sup feF n 1=1
(f(
(114)
S D,
Ssup fej n
Bf(x))o
(115)
BR)(F).
(116)
We successfully reduce the Rademacher complexity of IIFF) to F. Since we assume that the Rademacher complexity of decays ((1/ /n), there exists a constant such that
D
R₂ (I(FF) <
(117)
Vn
and
D + M
ln(1/6)
mn S Vn
(118)
for some constant D, M. Substitute this back to the result from step 1 concludes our proof. In the general setting with Lp loss where f(y, 1/) ly y I., we would have the following bound,
1/p
err(J) <
(m) Ex(lu(=) - (mm) 1/1//1 +
D Vn
+ M
(1(1/)) n
T(7)
(119)
31

---

E.3
Agnostic setting
Now, we study the agnostic setting, where we do not assume the existence of such f in F. Instead, we focus on comparing with fort = arg JEF err(f), the hypothesis in F with the smallest expected error. First, we show that, in contrast to the realizable setting, simply minimizing the projection loss may not converge to Sop. This is because smaller projection loss does not imply smaller standard loss
Proposition E.3. Lei E be an Ep loss, for any hypothesis J1, J2, there exists distribution Dy and 'D such that ED, (X),, L, U)] < ED, (T2( L, U] but err(Si) > err(f2).
While minimizing the projection loss, we might overlook a hypothesis that has smaller standard loss but higher projection loss. However, we remark that the projection loss is still useful since is a lower bound of the standard loss.
Proposition E.4. Let l: y y - R be loss function that satisfies Assumption 7 then for any f.
[fme(f(X),,. L.)) S err(f).
(120)
Consequently, if we let OPT cor(fopt) we must have Sopt E FOPT since the projection loss is upper bound by the standard loss. This means we can apply Theorem for fopt and consequently achieve an error bound similar to what we obtained in the realizable setting.
Theorem E.5 (Error bound, Agnostic setting). Let F be a class of functions that are m-Lipschitz, and suppose l satisfies Assumption 1 and the triangle inequality, then for any I E Fr, we have
err(f) OPT +E[d(e, (x,),, [X)](
(121)
While it's not ideal to minimize the projection loss in the agnostic setting since we may not converge to fopt. our bound suggests that the expected error of f would not be much larger than that of fope. This error bound becomes smaller when the intervals (z), (OPT(x)
small. Overall, our thcoretical insight suggests that we can improve our error bound by (i) having a smoother hypothesis class (smaller m) (ii) increasing the number of data points (which leads smaller 7)), since both results in smaller intervals I,, (.). However, if m is too small, FF may not contain a good hypothesis, causing OPT to be large. Next, we provide sample complexity bound for the agnostic setting.
Theorem E.6 (Generalization Bound, Agnostic Setting). Under the conditions of T'herrem 4.1 apart from realizability, with probability least 6, for any that minimize the empirical projection objective, for any 0,
err(f) - + (m) (m) D x D +
D Vn
+ +M
Im(1/8)
+ OPT
I((T)
(a)
(b)
(0)
(122)
where D,M are constants and ['(r) = Ex
x
(m) S T), Pxx (ug (m)
x- S T)) is
decreasing function of T, pmp (f) is an empirical projection error of J, and OPT the expected error of the optimal hypothesis in F.
Proof. The proof idea is similar to the realizable setting. Recall that we have an error bound
err(ʃ) S OPT +E|d(E I, (X), TopT (X))
(123)
where 1,(x) = (mm) - (2, " + +, (z)] We can write
d(1, (,,,,, TOPT(X)) < |u D=2 + max(r,, (x) + (o)) (x) + sx()))
(m) -1m=)
(124)
With triangle inequality, substitute this back to the error bound, we have
err(f) < OPT +Ellum">
(m)
10m)x + [[mmxxrr, (z) + SopT (x), roPT(x) + (x)]]] (125)
We that the first two terms are term a) and b) in the Theorem 4.2 Therefore, are left with bounding the final term. From Proposition 3.7. we know that for any 7 0.
(x) S inf + (n/ Pr(lg(m) (m) < <)) and 8x(x) S inl + (n/ Pr(ugxx)) (m) ST)). (126)
7
32

---

This implies that
(2) + sorr(x)
S 2T + ( (m) S))
(m)) (m)
S T))
(127)
= 2T + (1
<T)), 1/))u1/P((uxx1
Pr(ugx-) (m))
S
(128)
= 2T + O/ (m)) S ~),, Pr(ugx (m)) I T)).
(129)
We have the same upper bound for rorr(z) + s, (z)). Taking an expectation, we have
E F[max(r,,(2) SOFT (z), rorr(x) 8n (x)) - 2T (1) + OPT)T(T)
(130)
when ((r) xxx 1/min(Prxx (1g (m) S T), Prx (r (m)
x-x S イ))} The final step is to bound in terms of the empirical loss, following the uniform convergence argument from the realizable setting, with probability at least 8.
D
[m(1166
en
+ MV
(131)
Vn
n
This concludes our proof for the agnostic setting.
F Relaxation of Ambiguity Degree for a regression setting
As noted in the related work section, the ambiguity degree is defined in the context of classification and it might not be suitable for regression tasks. This is due to the nature of the loss function, In classification, hypothesis is either correct incorrect, and a small ambiguity degree ensures that we can recover the true label. However, in regression, we are often satisfied with predictions that are sufficiently close the target-for example, within error tolerance of e. This implies that do not need to recover the exact true label, but a ball with a small radius around the true label might be sufficient.
In this section, we explore relaxation of the original ambiguity degree the regression setting. Motivated by the concept of a tolerable area around the true label we define an ambiguity radius
Definition F.1 (Ambiguity Radius), For distributions D, Dr with a probability density function p. an ambiguity radius is defined as
AmbiguityRadius(D. (D) = minr r r0
S.t.
Pr X.YDD
N B(Yr)) =1
(132)
p(XI,))>0
when B(y,r) = (3/1 ly S/ISi r is a ball of radius r around y.
The interpretation of this is that it is the smallest radius r for which we are guaranteed the intersection of all interval for a given ø must lie within a radius of r from the true label y. direct consequence, we know that whenever the ambiguity degree is small the ambiguity radius must be zero since the intersection of all interval for given x is just the true label {
In fact, our analysis have captured the essence of this interval intersection for each x. We recall that for any f E Fo and for each x with p(x:) > O,
f(x) E To(x) = [/-m) ( S B(y,r"),
(133)
when r" is the ambiguity radius. This follows directly from the definition of the ambiguity radius. As result, we know that each interval [o( would have size at most 2r* The same technique as in the Section 4 would imply that the expected error of any f E Fo would be at most 2r* in the realizable setting (with L2 loss).
Finally, we want to remark that our analysis not only is applicable to this extension of the ambiguity degree to the ambiguity radius, we further use the smooth property of F and [o(x) might even be proper subset of the ball Bly. r"), giving a result stronger than one based solely on the ambiguity radius.
33

---

Projection
Minmax
Minmax (reg)
PL (max)
PL (mean)
(equation 5
(equation 20
(equation 25
(equation 26
(equation 27
Abalone
1.560.01
1 1.65g.02
1.340.01
1.52v.01
1.520.01
Airfoil
2. 2.460.0s
2.65g.07
3. 3.410.04
3.310.01
2.420.07
Concrete
5.750.18
7.34
6.230.16
4.860.48
5.430.12
Housing
5. 5.170.13
6.88g.31
5.42g.15
5.07p.09
5.05p.09
Power-plant
3.40.03
3.470.02
3.480.03
3.33p.01
3.33o.01
Average (rank)
2.8
4.4
4.2
2.2
Table 2: Test Mean Absolute Error (MAE) and the standard error (over 10 random seeds) for the uniform interval setting. PL (mean) is the best- best-performing method in this setting.
G
Experiments
G.1 Computational efficiency
The computational cost of projection objective matches standard regression loss, only evaluate boundaries the given interval (Proposition (21)). The naive minmax approach maintains this cost equivalence, since the maximum loss occurs at interval boundaries. For minmax with smoothness constraints through regularization, our alternating gradient descent-ascent updates for f and f' double the computational overhead. The pseudo-label approach requires training & hypotheses from F,, before generating labels, resulting (k + 1) times the base cost typically manageable given efficient regression training.
G.2 Experiment setup
Following prior work (Cheng et al. 2023a], we conducted experiments on five public datasets from the UCI Machine Learning Repository: Abalone, Airfoil, Concrete, Housing, and Power Plant. Since these datasets are originally regression tasks with single target values, we transformed them into datasets with interval targets (described shortly). Dataset statistics are provided in Section HH For the experimental setup, we used the same configuration as [Cheng et al.] [203a]]: : the model architecture is MLP with hidden layers of sizes 10, 20, and 30. We trained the models using the Adam optimizer with a learning rate 0.001 and a batch size of 512 for 1000 epochs.
Interval Data Generation Methodology. We propose general approach for generating interval data for each target value This method depends two factors: the interval size 4 E [0, oo) and the interval location E [0, 1]. The interval is then defined as [1, u y/ pq: y + (1 p)g]. When p O, the target value y is the lower boundary of the interval whereas p places y the upper boundary. In this work, we consider g and p to be generated from uniform distributions over specified ranges. The prior interval generation method in Cheng al. [203aa could be seen special case of our approach when 9 ~ Uniform (0, [max] and p ~ Uniform
G.3 Results
Which method works best in the uniform setting? We begin by evaluating methods in the uniform interval setting described in prior work [Cheng et al. 2023a where the interval size q Uniform(0, {max] and the location of the interval p ~ Uniform I. For each dataset, we Inax to be approximately equal to the range of the target values, Vmax - Vmin- Specifically, we set Gmax 30 (Abalone), 30 (Airfoil), 90 (Concrete), 120 (Housing), and (Power Plant). Our findings indicate that the PL (mean) method performs best in this uniform setting, with PL (max) and the projection method ranking second and third, respectively (Table 2). Given the superior performance of PI. (mean), we conducted an ablation study to better understand its effectiveness. We explored the impact of varying the number hypotheses & and compared it with an ensemble baseline that combines lscudo-labels before using them to train the model, for which we still find
34

---

that PL (mean) still performs better (Appendix K
What about other interval settings? We conducted more detailed experiments to investigate which factors impact the performance of each method. Specifically, we varied the interval size q and the interval location p by 1) varying gmax. 2) varying Jmin. 3) varying with three settings designed to position the true value y at: i) only one boundary of the interval, ii) both boundaries of the interval, iii) the middle of the interval. Full details are provided in Appendix [
We found that: (1) All methods are quite robust to changes in the interval size, except for the Minmax method, whose performance decreases significantly as the interval size increases. This is consistent with our insights from the proof of (2) The location of the true value y can have a large impact on performance; specifically, the Minmax method performs better when y is close to the middle of the interval. One explanation is that Minmax is equivalent to supervised learning with the midpoint of the interval (Corollary (52)). Conversely, the other methods perform better when is close to both boundaries of the interval but not when y close to only one boundary. Finally, we conclude that if we only know that the interval size is large, it is better to use the PL (pseudo-labeling). However, if we know the true value is close to the middle of the interval, then the Minmax method is more preferable.
G.4 Connection to our theoretical analysis
To validate our theoretical findings in practice, conducted experiments designed to test whether our theory holds under empirical conditions. Recall that our main result (Theorem (3.6) states that if a hypothesis f approximately lies within the intervals (f Fr)) and is smooth, then f will lie within intervals smaller than the original ones. To control the smoothness of our hypothesis, we utilize a Lipschitz MLP, which is an MLP augmented with spectral normalization layers [Miyato et al. 2018]. The normalization ensures that the Lipschitz constant of the MLP is less than We then scale the output of the MLP by constant factor m to ensure that the Lipschitz constant of the hypothesis is less than m.
Test performance First, we plot the test Mean Absolute Error (MAE) of the Lipschitz MLP with the projection objective, compared with the test MAE of the standard MLP (Figure g (Top)). We found that, with the right level of smoothness, Lipschitz MLP can achieve better performance than the standard MLP. When the Lipschitz constant is very small, the performance is poor for all datasets. However, performance improves as the Lipschitz constant increases. We observe that the optimal Lipschitz constant is always larger than the Lipschitz constant estimated from the training set (vertical line). For some datasets, performance degrades when the Lipschitz constant becomes too large. This aligns with our insight from Theorem E. which suggests that we can improve the error bound by ensuring that the hypothesis class is as smooth as possible (smaller m so that I,, (x) is small) while still containing a good hypothesis (i.e., low OPT). Nevertheless, we do not need to know the Lipschitz constant of the dataset and can treat it as a tunable hyperparameter in practice.
Reduced interval size Second, we determine whether the intervals, within which our hypothesis f Fo lies, are smaller than the original intervals. Recall that the original intervals are given by [t. u]. and our theorem suggests that they would reduce to L,(x)) = [/r=) (x))),, afm) + s, (z)]. While we can use a Monte Carlo approximation to estimate (,))),, it does not take into account the hypothesis class F. Instead, we approximate (x()) using samples of hypotheses from F, by proceeding as follows: 1) We train 10 models with the projection objective, each from different random initializations (denoted by fi...., f10). 2) For each x, we approximate the reduced interval using the minimum and maximum values of the outputs from these models, given by [min; f(x), max; max, f((x)) We set m E {0.1, 0.1 x 21, ..... 0..1 x 2133 and consider uniform interval ,..,,..1 setting with Jmax = 90. As expected, when the hypothesis becomes smoother, we observe that the average interval size decreases (Figure g (Bottom)). Moreover, we found that even when the Lipschitz constant is much larger than the value estimated from the data (vertical line), the average reduced interval size remains significantly smaller than the original interval (which is 45 since 4max = 90). We also observe that the average interval sizes from the standard ML.s are smaller than the original values.
35

---

2.0
Projection (UAMLPP)
10
(oppox)
Projection (MUP)
(MLP)
3.0
307
101
10
10
10
10R
107
10
106
30
307
107
Uipoorizz constont
Upochiz constant
Upsch constane
aballone
airfoil
concrete
rnterval
LighLF Iram
LighLL
MLP Tran
MLP
Lipachitz constant (Apono))
Figure 8: Test MAE of the projection method with Lipschitz MLP using different values of the Lipschitz constant. The vertical line is the Lipschitz constant approximated from the training set. (Top) The dashed horizontal lines are the test MAE of PL (Mean) and Projection approach with standard MLP. (Bottom) Approximated interval size (z) for Lipschitz MLP with different value of Lipschitz constant m. The dashed horizontal lines are the values from standard (non- Lipschitch MLP. The figures for all datasets are in Appendix
H Dataset Statistics
The datasets are from the UCI Machine learning repository (Nash et al. 1994 Brooks et al. 1989
Ych 1998 Tfekci and Kaya, 2014] with Creative Commons Attribution 4.0 International (CC BY
4.0) license. We provide the statistics the datasets including the number of data points, the number of features, the minimum and maximum values of the target value and the approximated Lipschitz constant in Table 3 The Lipschitz constant here is approximated by calculating the
-y'''l for all pairs of data points then the value is given by the 95th percentiles of these [|z=
proportion
proportions. We perform this procedure avoid the outliers which have size of around two orders of magnitude bigger than the 95th percentile value (Figure 9 This allows us to approximate the level of smoothness that does appear the dataset rather than use the maximum Lipschitz constant. One could also think of this as a probabilistic Lipschitz value rather than the classical notion [Umer and Ben-David 2013.
Dataset
# data points
features
[y min, y max]
Lipschitz constant
Abalone
4177
[1,29]
3.23
Airfoil
1503
[103, 141]
7.75
Concrete
1030
[2,83]
13.8
Housing
414
[7, 118]
11.68
Power plant
9568
[420,496]
14.18
Table 3: Dataset statistics.
36

---

abalone
airfoil
Iys (i-yy >al//lx; xall
concrete
10?
housing
power-plant
104
10a
80
100
Percentiles
Figure 9: The value of 1y-v/1
by percentiles. We the 95th percentile of this value
approximated Lipschitz constant for each dataset.
37

---

Impacts of the interval size and interval location
L.1
Impact of the interval size
aballone
concrete
2.4
4.0
2.2
2.0
3.5
MAE
1.8-
2.5
1.4
25
50
75
100
125
25
50
75
100
125
50
75
100
125
9rox
housing
power-plant
3.55
3.50
Projection
6.0
Minmax
MA8
(rea)
5.5
Minmax PL (mean)
5.0
3.35
4.5
3.30
25
100
100
125
Amat
Unae
Figure 10:
Test MAE when varying the maximum interval size lmax E (0,30, 60, 90, 120} while
Qmin
0.
airfoil
11
10-
MAC
MAC
MAE
7.
20
60
20
60
20
60
Qrnn
4mnh
4mx
housing
Dower-plane
11
10
Projection
MAE
3.8
Minmax
Minmax (reg)
Mirmax PL (mean)
Minmax (max)
3.4
20
60
20
60
Qein
Figure 11: Test MAE when varying the minimum interval size Qmin 10, 45, 60, 75, 90)
while fmax = 90.
We want to investigate the impact of interval size on the performance of the proposed methods. Intuitively, a smaller interval would make the problem easier. the extreme case when the interval
size is zero, we recover the supervised learning setting. Here, we assume that the interval location still drawn uniformly from (0, 1] and we consider two experiments. First, we vary the maximum
interval size ymax E {0, 30, 60, 90, 120} while keeping the minimum interval size quin 0. As
38

---

expected, larger maximum interval size leads to the drop in test performance across the boards (Figure I0). Second, we vary the minimum inter val size 4min E {0, 15, 30, 45, 60, 75, 90) while keeping Umax fixed at 90. We can see that the test performance also decreases for all methods we increase the minimum interval size (Figure [1I. Notably, the standard minmax approach is highly sensitive to the interval size where its performance degrades significantly much more than other approaches in both experiments. This is due to the nature of the approach that wants to minimize the loss with respect to the worst-case label, much stronger and may not represent the property of the true labels anymore. On the other hand, our other minmax approaches and the projection approach are more robust to the change in the minimum interval size and the error only went up slightly for both experiments.
have larger interval, these worst-case labels can be
I.2 Impact of the interval location
When y is more likely to be on one side of the interval (vary Pmin)
abalone
airfoil
concrete
20
20
MAE
15
MAC
15
MAB
1.-
10
10
1.0
Paxs
Prsh
housing
power plant
Projecti
Minmax
WAE
1.5
MAE
Minmax (reg)
Minmax (mean)
10
Min Minmax (max)
5-
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 12: Test MAE when varying the minimum interval location Pmin E {0, 0.4, 1). In this case, when Pmin = 0 we have the uniform interval setting while when Pmii = 1, y true always lie on the upper bound of the intervals.
In the previous settings, we assume that the location of the interval p is drawn uniformly from U 1]. that is, when y true is equally likely to be located at anywhere the intervals. Here, explore what would happen when is not the case. We assume that we fixed Jmin = 0, Jmax = 90 and consider side of the interval. Here,
three scenarios. First, we consider when p ~ U[pmin. 1] where Pmin E {0, 0.2, 0.4, 0.6, 0.8. 1} (Figure 12p. In this case, when Pmin O have the uniform interval setting while when Pmii 1, y true always lies on the upper bound of the intervals. We can see that the test MAE of all approaches increases as Pmin is larger. Again, the minmax approach performs much worse than others. One explanation for this is that the minmax with respect to. the label would encourage the model to be close to the middle point of each interval (Corollary 5.2). However, the the y true is far away from the midpoint leads to his phenomenon. We also provide the test MAE with no minmax approach for better visualization (Figure
consider when y is more likely to be
When y true more likely to be in the middle of the interval
Second, we consider when true is more likely to be in the middle of the interval (p is close to 0.5). We capture this setting by considering p ~ U [0.55 - c, 0.5 c] for c {0, 0.1, 0.2, 0.3, 0.4, 0.5) (Figure 14]. Intuitively, when 0, the true is always in the middle of the interval and when c= 0.5, we recover the uniform interval setting. In contrast the first setting, we can see that the minmax approach performs the best in this setting for small value of Again, this is perhaps due
39

---

airfoil
3.5
3.0
MAE
MAA
2.5
2.0
1.5
0.0
0.2
0.4
0.6
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.8
1.0
Prin
Prin
Pain
housing
power plant
Projection
8-
MAF
Minmax (reg)
Minmax PL (mean)
7
Minmax R. (max)
0.0
0.2
0.6
0.8
1.0
Prah
Pres
Figure 13: Test MAE when varying the minimum interval location Pmin E (., 0.6, 0.8, 1}. In this case, when Pmin = 0 we have the uniform interval setting while when Pmin 1, true always lies on the upper bound of the intervals. minmax approach)
abalone
airfoil
concrete
2,2
3.5
1.8
6-
1.6
2.5
housing
power-plant
6.0
5.5
3.6
Projection
Minmax
MAE
MAE
3.5
Minmas treg)
5.0
Minmax PL
Minmas PL (max)
3.3
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Figure 14: Test MAE when varying the interval location, U 0.5 c] for (0, 0,1,1 0.2, 0.3, 0.4, 0.5). When e 0. the true y always in the middle of the interval and when = 0.5, we recover the uniform interval setting.
to the nature of the minmax approach mentioned earlier which encourages the prediction to close the middle point of the interval, for which, in this case, close the y true. Remarkably, minmax performs better until e 0.2 which corresponds to ~ [0.3, 0.7] which is reasonable location of y in practice. However, when is large would recover the uniform interval setting and the minmax would go back to becoming the worst worst-performer On the other hand, the performance of other approaches is better is larger, that when y true more spread out across the interval.
40

---

When y is more likely to be on either side of the interval
abalone
airfoil
concrete
MAE
MAE
MAE
housing
power-plant
4.0
Projection
Minmax
MAE
3.8
Minmax (reg)
Minmax (mean)
3.6
Minmax PL (max)
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Figure 15: Test MAE when varying the interval location, when p is drawn uniformly from [0, 0.5 U [0.5 + e, 1] when e {0, 0,1, 0.2, 0.3, 0.4, 0.5). Here, when e we have the uniform interval setting while when 0.5, y true is either on the upper the lower bound of the intervals.
abalone
airfoil
concrete
1.65
3.75
3.25
MAE
MAC
MAE
2.50
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
housing
power-plant
3.6
5.2
5.0
Projection
MAF
MAE
(nog]
4.8
Minmax PL imean]
3.3
0.0
0.1
0.2
0.3
0.5
0.0
0.2
0.3 0.4
0.5
Figure 16: Test MAE when varying the interval location, when p is drawn uniformly from [0, 0.5 U [0.5 + c, 1] when {0, 0.1, 0.2, 0.3, 0.4, 0.5). Here, when we have the uniform interval setting while when c = 0.5, y true is either on the upper or the lower bound of the intervals. minmax approach)
Finally, we consider when is more likely to be on either side of the interval where is drawn uniformly from [0, 0.5 c] U [0.5 + c, when e E {0, 0.1, 0.2, 0.3, 0.4, 0.5). Here, when = 0 we have the uniform interval setting while when = 0.5, true is either on the upper or the lower bound of the intervals. We found that as is larger where the true more likely to be near either of the boundaries, the minmax performance drop significantly (Figure 15). However, found that the per-
41

---

formance of other approaches increases (Figure 16.. This is in contrast to the first setting where we that when y more likely be near only one side of the boundary, the performance drops remarkably.
Overall, from these experiments, may conclude that for all approaches apart from the original minmax with respect to. labels, having true that lies near both of the boundaries of the interval are beneficial to the test performance and lying on both sides is erucial.
1.3 Large Ambiguity degree setting
We consider a setting with large ambiguity degree where ~ Uniform[9min- 90) when Jmin E {30, 60, 90) and p Uniform c, 0.5 + c] when E {0, 0.1, 0.2, 0.3, 0.4, 0.5). Here is smaller, y true would be located near the middle point the interval while as c larger, we would recover the uniform setting. These settings have large ambiguity degree since when Amin interval size can't It be arbitrarily small and [Pmin- boundary of the constructed interval. As result, the intersection of all possible intervals would no longer be just { anymore which leads to the ambiguity degree of 1. We found that there is no single method that always performs well every interval setting. The Minmax is the best performing method for all < 0.3 while when 0.3 the best best-performing approaches are either PL (mean) or PL (max) (Figure 17).
C [0, 1] implies that true would not lie at the
abalone
airfoil
concrete
90
90
90
dean
Grin
dem
60
60
60
30
30
30
0.2
0.3
0.4
0.5
0.0
0.1
housing
power-plant
90
Minmax
Minmax (reg)
Qmin
60
qmin
60
Minmax PL (mean)
Minmax PL (max)
Projection
30
30
0.4
Figure 17: The best performing approach for each c and qmin
42

---

1,4
Interval padding experiment
abalone
airfoil
5.5
1.9
5.0
10:
4.5
3
1.7
4.0-
MAE
3.5
3.0
7-
1.5
0.0
1.5 Interval padding scale
0.5
2.0
0.0
0.5
2.0
0.0
0.5
1.0
2.0
Interval padding scale
Interval padding scale
housing
power-plant
4.4
4.2
9
4.0
Minmax
8-
(reg)
3.0
Mirmax PL (meen)
7-
Minmax (max)
3.6
6-
3.4
0.0
0.5
15
2.0
0.0
0.5
2.0
padding
padding
Figure 18: Interval padding experiment
From above, found that the Minmax approach performs better when y true is close to the middle point of the interval, but performs worse in the uniform interval setting when p ~ Uniform [0, 1]. In this experiment,
start with the uniform interval setting and add padding the original interval as a factor the interval size. Formally, for an original interval [[, u] of size q = u we have 0 is scale parameter. By doing this, y true would be
interval [ sq, sq] when proportionally closer to the midpoint of the new interval, but distancewise is the same. We found that add the padding, the performance of other approaches decreases significantly and gets worse than the performance of the Minmax when the scale 0.5 (when the padded interval twice the size of the original interval) while the performance of Minmax is about the same. This shows that a redundant interval (padding) can harm the performance of the proposed approaches except Minmax and our result that interval location p can have large impact on the performance is still applicable this padding setting.
43

---

Interval size and test performance of LipMLP
concrete
foerage interval size
Averagg Interval s2e
10-
Iverage
10
10a
10-3
10F
10:
10a
10
109
10'
Upschitz constant
Upschitz constant
Upschitz constant
housing
power-plant
15.0
Average interval pize
12.5
Average interval size
LiMLP
10.0
LipMLP Tast
Train
conslanl constant (Approx)
2.5
0.0
10-1
10a
10a
10a
10a
10aa
10
10:
10a
102
Figure 19: Approximated interval size (x) for Lipschitz MLP with different value of Lipschitz
constant m. The dashed horizontal lines are the values from standard MLP.
abalone
airfoll
concrete
2.2
14
2.0
Teat MAE
Teat MAE
1.0
1.8
Upschitt constant
Lipschit2 constant
Lipschitz constant
housing
power-plant
14.
12
RestMMEE
MAE
10-
Lipschitz constant, (Approx)
Projection (LipMLP)
Projection (MLP)
6-
Mean (MLP)
10-3
10a
10
10
10
10
10a
10
10?
107
Upschitz constait
Lipschitz constant
Figure 20: Test MAE of the projection method with Lipschitz MLP with different values Lipschitz constant. The vertical line is the Lipschitz constant approximated from the training set. The dashed horizontal lines are the test MAE PL (Mean) and Projection approach with a standard MLP. The optimal Lipschitz constant balances the trade-off between constraining the hypothesis class and maintaining enough capacity to achieve low error.
44

---

K
Ablation for PL (mean)
Since PL (mean) is the best-performing approach in the uniform interval setting, also performed an ablation study to improve our understanding of this method. First, we explore the impact of the number of hypotheses k used to represent Fo- We found that for every dataset, as k is larger, the test MAE becomes smaller. While we use for PL experiments, this ablation suggests that we can increase & to get better performance at the cost of more computation.
abalone
1.625
2.0
1,600
5.8
1.575
2.6
MAF
1,550
2.5
5.4
1,500
2.3
10
10
housing
pow gower-plans
3.50
M
3.45
Minmax
3.40
5.0
4.8
3.30
Figure 21: Test MAE for PL (mean) with different number of hypotheses & used to represent Fu. For almost every dataset, the test MAE decreases
larger.
Second, also compare PL (mean) with a natural ensemble bascline where combine pseudo labels by averaging them first and then train a model with respect to. the averaged labels. In particular, the objective for the ensemble baseline is given by
min e(f(x,)) Ed()))
(134)
We found that PL (mean) still performs better than this baseline on 2 out of 5 datasets while the other 3 datasets are similar.
Abalone
Airfoil
Concrete
Housing
Power-plant
PL (mean)
1.52p.01
2.42o.07
5.43o.12
5.05p.00 5.06g.0s
3.33g.01
PL ensemble baseline
1.51o.01
3.30.04
5.570.19
3.32,.o1
Table 4: Test Mean Absolute Error (MAE) and the standard error (over 10 random seeds) for PL (Mean) and PL ensemble baseline
L Additional experiments on the tabular data benchmark
The main takeaway from our theoretical analysis is that an appropriate level of smoothness can lead to performance gain. In addition to our experiments on the UCI datasets, we also tested this on
18 additional regression tasks from tabular data benchmark (Grinsztajn et al. 2022 To ensure
45

---

that the MAEs of different datasets are comparable, we used z-score rescaling on the target values of each dataset so that the standard deviation was 100. We only used the training datasets to infer the rescaling parameters. To generate the interval targets, we used the proposed algorithm with Imin 0, Jmax = 50, Pinin = O, and Pmax 1. our experiment, we compared MLP with LipMLP using different values for the Lipschitz constants, where m E {1,4, 4, 16, 64, 256, 1024). We used validation dataset to select the best hyperparameters, which included the learning rate for MLP (from {0.01, 0.001, 0.0001, 0.00001]) and both the learning rate and the Lipschitz constant for LipMLP. We provide the test MAE with standard error over random seeds for both methods Table I We bolded the result whenever the mean + standard error (ste) of one method was lower than the mean- ste of the other method. We found that on almost every dataset (apart from GPU), LipMLP performed better than or least par with MLP. This extensive improvement demonstrates suggests that determining the right level of smoothness is a simple yet effective method for enhancing learning with interval targets.
46


Reviews:
[{"review_id": "TuXP0ZXueg", "reviewer": "Reviewer_1WsC", "summary": "This paper studies regression with interval targets, where the true labels are only known to lie within given intervals rather than being exact values. To address this setting, the authors propose two learning strategies: (1) minimizing a projection loss that penalizes predictions falling outside the intervals, and (2) a min-max objective that minimizes the worst-case loss over possible target values within each interval. They develop novel generalization bounds for the projection-based method under both realizable and agnostic settings, removing restrictive assumptions from prior work by leveraging the smoothness (e.g., Lipschitz continuity) of the hypothesis class. Theoretical insights reveal that smoother models implicitly reduce the effective size of interval constraints, improving predictive performance. Empirical results on real-world datasets support the theory and demonstrate that both proposed methods achieve state-of-the-art accuracy in interval-based regression tasks.", "questions": "Can a similar generalization error bound be established for the min-max objective method? If so, under what conditions would it match or differ from the projection-based analysis?", "limitations": "See weakness", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n1. The paper is clearly written, and the theoretical results appear to be rigorous and well-justified. \n2. The work significantly improves upon prior results by removing the restrictive realizability and small ambiguity degree assumptions, instead establishing generalization guarantees under a smoothness condition on the hypothesis class. The empirical results are comprehensive and demonstrate that the proposed methods achieve strong performance across multiple real-world datasets.\n3. The empirical results are comprehensive and demonstrate that the proposed methods achieve strong performance across a few real-world datasets. \n\nWeakness\nIt would strengthen the paper to include a discussion on the tightness of the provided generalization error bounds. In particular, can lower bounds be established to show whether the derived rates are optimal or near-optimal?", "was_revised": true, "final_justification": "Thanks for the response. I will maintain my score.", "rebuttal": ""}, {"review_id": "uWvZS8YtRA", "reviewer": "Reviewer_oLAy", "summary": "The paper studies regression with interval-valued labels under an m-Lipschitz hypothesis class, where each observed interval captures uncertainty about the true target.\nWhen the true target is not available, it adopts two practical surrogates, an (optimistic) projection loss and a closed-form min–max loss, plus an auxiliary network for the inner maximization. This paper also provides a decomposed generalization bound on the loss.", "questions": "1. What does PL Mean mean in the experiment?\n\n2. Could this approach be applied beyond tabular data? I think the application on the unstructured data, such as images, is very important and practical.\n\n3. Is there a better way of approximating the Lipschitz constant? It seems the approximated ones in the experiment does not lead to optimal results.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. In general, the ideas are clearly conveyed.\n\n2. The generalization bound decomposition indicates the usefulness of the proposed method.\n\n3. The setting is interesting and practical in real-world data collection, where the labels are often noisy.\n\n**Weaknesses**\n\n1. While I appreciate the theoretical results, the technical contribution is unclear to me. The projection loss is very similar to prior works (such as [1]), while the minmax formulation seems to be a special or simplified case of robust ML (such as [2, 3]), where the feature variations/uncertainty do not exist.\n\n2. The approach for minmax formulation that utilizes an auxiliary worst-case learner is not connected to interval targets.\n\n3. Since the ultimate goal of this work is to reduce the overall loss of the classifier given interval targets, there are other baselines that could be considered in the evaluation. For instance, the evaluation could be strengthened by comparing with works that learn robust models from noisy labels, such as [4]. To construct their setting, the noisy labels could be sampled from the interval ranges.\n\n[1] Cheng, Xin, Yuzhou Cao, Ximing Li, Bo An, and Lei Feng. \"Weakly supervised regression with interval targets.\" In International Conference on Machine Learning, pp. 5428-5448. PMLR, 2023.\n[2] Mirman, Matthew, Timon Gehr, and Martin Vechev. \"Differentiable abstract interpretation for provably robust neural networks.\" In International Conference on Machine Learning, pp. 3578-3586. PMLR, 2018.\n[3] Wang, Shiqi, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. \"Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification.\" Advances in neural information processing systems 34 (2021): 29909-29921.\n[4] Kim, Chris Dongjoo, Sangwoo Moon, Jihwan Moon, Dongyeon Woo, and Gunhee Kim. \"Sample selection via contrastive fragmentation for noisy label regression.\" Advances in Neural Information Processing Systems 37 (2024): 127561-127609.", "was_revised": true, "final_justification": "I appreciate the theoretical foundation of the proposed work. The authors addressed my concern regarding noisy label learning techniques. Although the experimental evaluation could be improved, I believe the overall strength outweigh the weakness. Therefore I raised my score to 4.", "rebuttal": ""}, {"review_id": "wqlQtkAfku", "reviewer": "Reviewer_U3a1", "summary": "The paper extends regression with interval-valued supervision by dropping the restrictive “ambiguity-degree” assumption and replacing it with a global Lipschitz-smoothness condition on the hypothesis class. It derives new generalization bounds for the standard projection loss and introduces a complementary min-max surrogate, then shows that enforcing an appropriate Lipschitz constant can reduce test MAE on a suite of tabular datasets.  \n\nPlease note that the following represents my initial impressions of the paper, and I am open to discussion. I welcome any corrections to potential misunderstandings.", "questions": "My actionable requests already appear in the Weaknesses section; please address them point-by-point. In addition, I highlight a few items here:  \n\n- Could you extend Fig.7's $m$ sweep until MAE stats rising? If MAE does not raise, please add discussion why it is still compatible with what the theory expects.  \n- Could you possibly release an anonymous sample code so that I can evaluate parameter sensitivity of $m$, learning rate, weight-decay, overfitting/early-stopping etc. by myself?\n- In a practitioner's point of view, $m$ must be found via grid-search on training/validation data. How susceptible are conventional models to overfitting? \n\nAddressing these points would improve my assessment of the paper further.", "limitations": "The authors provided Limitations section at Appendix B, but highlighting several points e.g., Global Lipschitz constant assumption and non-convexity of minmax optimization would be beneficial for readers.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths. \n- Theoretical advance over prior work. Extends the analysis to agnostic settings and relaxed ambiguity assumptions of Cheng et al. (2023) while still proving $O(n^{-1/2})$ convergence rates.\n- Clear link between smoothness and effective interval width. The “reduced-interval lemma” (Thm 3.6) formalizes how a global Lipschitz constant $m$ shrinks the set of plausible labels, providing an intuitive knob for bias–variance trade-off.\n- Two complementary risk surrogates. By analyzing both projection and min-max objectives under the same smoothness framework, the paper offers upper- and lower-risk envelopes that bracket the unknown true loss.\n- Simple, architecture-agnostic implementation. Enforcing global Lipschitzness via spectral normalisation can be applied to any feed-forward network without architectural redesign.\n- Comprehensive supplementary material. The appendix provides full proofs, additional datasets, hyperparameter grids, and ablation studies, facilitating in-depth verification.  \n\n## Weaknesses. \nThe paper was an enjoyable read, but I found the following potential weaknesses and questions. I am willing to reconsider my score once these issues are addressed.  \n\n### Potentially unclear link between the theory and experiments.  \nFig. 7 is confusing to me in sense that the claimed smoothness-realizability tradeoff (p.8, l.268-272) appears only on one of the three datasets (abalone) shown; the center (airfoil) and right (concrete) plots show monotonic decrease, without showing a minima due to the tradeoff between the term (b) and Rademacher complexity. Please clarify and discuss whether it is expected from the theory, or limitation of it.\n\n### Global Lipschitz constraint may be unrealistic. \nThe assumption that a single scalar $m$ upper bounds $|\\nabla f|$ for all $x$ might be difficult to be satisfied in high-dimensional or heterogeneous data: it may have risks of e.g., underfitting sharp local variations or exploding the output scale when the data manifold is low-dimensional inside $\\mathbb{R}^d$.\n\n### Reproducibility concern.\nCode is currently unavailable (though promised upon acceptance), preventing reviewers from assessing reproducibility.  \n\n### (Minor) Synthetic-only supervision.  \nIt seems that all interval targets are generated by an artificial random procedure; no evaluation on naturally occurring interval or censored data is provided.", "was_revised": true, "final_justification": "The authors provide a point-by-point reply to my concerns and overall they are satisfactory.", "rebuttal": ""}, {"review_id": "tX8DXVca0z", "reviewer": "Reviewer_N93J", "summary": "This paper addresses a weakly supervised regression problem where, instead of exact labels, only upper and lower bounds of the target values are provided. This problem is easier to collect labels than the traditional supervised setting. While this setting has been explored in prior work, existing approaches typically rely on strong theoretical assumptions. In contrast, this paper adopts more relaxed assumptions and offers several theoretical results that shed light on the problem, particularly regarding the influence of function class smoothness. The authors also explore a variety of objective functions suitable for learning from interval-based supervision and empirically evaluate their performance through comprehensive experiments.", "questions": "1. Clarity and Self-Containment:\nPlease consider addressing the weaknesses I noted regarding the organization and self-containment of the paper. In particular, key experimental details and the best-performing objective function (Equation 134) are only described in the appendix, which hinders comprehension of the main results. If I have misunderstood or overlooked any explanations already present in the main text, I would appreciate clarification.\n2. Comparison with Noisy Label Regression:\nI believe it would be quite interesting to compare this interval-based framework with the standard setting of regression from noisy ground truth labels. Specifically, how would the proposed method perform relative to learning from noisy scalar labels, and are there scenarios where interval targets offer a clear advantage? I would be interested in hearing your perspective on this.\n3. Fair Comparison with PL (Mean) Approach:\nWhile the PL (mean) approach is shown to be highly effective, it requires training K+1 regressors, which introduces a significant computational cost. For a fairer comparison in terms of training time, it would be helpful to evaluate the performance of an ensemble of K+1 models using the minmax or projection-based objectives. Have you explored this comparison, or do you have any expectations about how such ensembles might perform?", "limitations": "yes (but limitation was discussed in Appendix B)", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. This paper addresses an important and compelling problem setting, proposing a practical algorithm that is flexible with respect to model choice, easy to implement, and empirically effective.\n2. The theoretical analysis is thorough and well-presented. The authors provide clear interpretations that help readers grasp the core insights of the theoretical results.\n3. For a natural baseline in this setting is to regress the midpoint of the lower and upper bounds; this paper demonstrates that such an approach can be overly pessimistic in terms of the worst-case (min-max) loss. Building on this insight, the authors propose a more optimistic and effective alternative. This result is, in my view, a significant contribution to the field.\n\nWeaknesses\n1. While I appreciate the overall contribution of the paper, I found that it is not fully self-contained, and substantial reorganization may be needed to meet the standards of a top-tier conference paper. Although the theoretical analysis is clearly presented in the main text, the algorithmic and experimental sections are difficult to follow without frequent reference to the appendix. Notably, the best-performing objective function used in the experiments is only described in the appendix (Equation 134), which makes it challenging for readers to fully understand or assess the empirical results based on the main paper alone.\n2. The paper reports results on only five UCI datasets, whereas Cheng et al. (2023a)—which the paper claims to follow—uses six datasets, including AgeDB, IMDB-WIKI, and STS-B. Including a more diverse and challenging set of datasets would help better demonstrate the generalizability of the proposed method.\n3. The experimental comparison does not include strong baselines from related prior work, such as the LM loss introduced in Cheng et al. (2023a). Including such methods would strengthen the empirical evaluation and clarify whether the proposed approach offers a clear improvement over existing techniques.", "was_revised": true, "final_justification": "After reading the rebuttal, my score remains unchanged, as there are still concerns regarding the clarity of the paper. I am not entirely confident that the authors can adequately revise it to address these issues. In particular, the explanations of the experiments remain unclear, and it is difficult to fully grasp what the proposed method entails. I understood that the key idea is to control the Lipschitzness and use the existing loss is acceptable (using PL (mean) can be effective in many cases). That said, I do appreciate the effort to generalize beyond Cheng et al., and I find the theoretical analysis to be interesting and a meaningful contribution to advancing the understanding of learning from interval targets. Overall, I feel this paper is at a borderline level.", "rebuttal": ""}]

Author rebuttal:

Meta-review: The paper provides learning bounds for supervised learning with interval targets. While previous bounds are limited to the realizable case with small ambiguity degree assumption, this paper presents bounds in the agnostic case with smooth function classes. The bound is insightful with terms that capture tradeoff between approximation error and smoothness, apart from usual estimation error that decays as 1/\sqrt{n}. Learning under worst case labels, using minmax obj, is also studied.

The paper is written well, easy to follow, with good organization of content. The theoretical results are interesting considering the new setting of interval targets. The analysis kind of exhaustive complementing gaps in literature. The reviews also agree with these points broadly after rebuttal discussions. Hence the work is ready for publication.
Decision: Accept (poster)