Learning from interval targets

Thank you for your feedback and suggestions. We hope the following responses address all your questions.

1. I think the authors can do a better job about making explicit the fact that although the learner observes interval targets, the goal is to still do well with respect to the original regression loss.

We have made this setting more explicit in the revised version.

2. Lack of specification on how error rates decay with sample size. It is not clear how the excess risk in lines (13) and (16) decays with the sample size n.

We have added an explicit generalization bound for both realizable (13) and agnostic setting (16) in terms of the number of data points $n$ in Appendix A. This result is applicable to any hypothesis class $\mathcal{F}$ where the Rademacher complexity grows as $O(1/\sqrt{n})$. For instance, the class of two-layer neural network with bounded weight satisfies this property.

3. Does Proposition 3.1 hold uniformly for all $x \in X$? If so, I am confused since $f \in \mathcal{F}_0$ only guarantees that $f(x) \in [l_x, u_x]$ almost surely. So there could still be $x$ (albeit in a measure 0 set), for which this is not true.

Our result in Proposition 3.1 holds for any $x \in \mathcal{X}$ with a positive probability density function $p(x) > 0$. We have made this more clear in the revised version. We note that this is stronger than $f(x) \in [l_x, u_x]$ almost surely, and we deal with a set with measure 0 with an assumption that the distribution $D_I$ is a non-atomic distribution (Assumption 2 in Appendix E).

4. What norm is being used on line 236?

We used $L_1$ norm and this is made clearer in the revision.

5. Is the guarantee on line 267 pointwise or in expectation? If it is pointwise for every $x$, how are you accounting for the fact that the functions $f \in F_\eta$ may have projection loss bigger than $\eta$ for low probability x? Is this accounted for by definition of $r_{\eta}(x)$ and $s_{\eta}(x)$? If so, it would be good to explain how the buffer $r_{\eta}(x)$ and $s_{\eta}(x)$ account for that.

The guarantee in line 267, is pointwise and holds for any $x \in \mathcal{X}$ with a positive probability density $p(x) > 0$. We are able to deal with any $x$ with a large projection loss (although with low probability) by relating $x$ with its neighbor $x'$. The main idea is that, with smoothness, if $f(x)$ is too small (too large) then for any neighbor $x'$, $f(x')$ has to be close to $f(x)$ and thus, would be too small (too large) as well. But this can't happen too much since the expected projection loss is smaller than $\eta$ and we bound how much $f(x)$ can be far away from the given interval with $r_{\eta}(x)$ and $s_{\eta}(x)$. The full proof in Appendix C. We will make this connection clearer in the revised version.

6. Is $F_0$ known to the learner in Equation (23)? It seems like the learner needs to know the distribution D over X to compute $F_0$ based on line 170. So because the learner doesn't know $\mathcal{D}$, it shouldn't be able to perform the optimization in Equation (23). What am I missing here?

Yes, we would not have access to $F_0$ in practice. Therefore, we propose to approximate the objective in equation (23) with the regularization approach and with pseudo labels. In general, we could learn $f_j \in F_\eta$ for some small $\eta$ and we could treat a set of such functions as an approximation of $F_0$ (pseudo labels idea). We have made this connection more explicit in the revised version.

7. Based on the bullet points above, how does the learner know that the $f_1,...,f_j$ in line 409-410 belong to $F_0$ if $F_0$ is not known?

In practice, $f_1,...,f_j$ would belong to $F_{\eta}$ for some small $\eta$. We can achieve this by training with a different random seed. $F_\eta$ is a superset of $F_0$ where we use it to approximate $F_0$. We have made this approximation aspect is more clear in the revised version.

8. In Equation (24), are the minimizations and maximizations over $f$ and $f'$ being done both over $\mathcal{F}$? Or is the maximization of $f'$ being done over $\mathcal{F}_0$? If it is the latter, the same question I had above holds - how can the learner do this if $\mathcal{F}_0$ is unknown?

The minimizations and maximizations over $f$ and $f'$ are being done both over $\mathcal{F}$. However, we have a regularization on $f'$ to encourage $f'$ to be in $\mathcal{F}_0$.

Thank you for your feedback and questions. We hope the following responses address all your questions.

1. Just notation problems, but it is difficult to follow the effect of the Lipschitz constant m. It may be better to add m to all operations affected by m (e.g., replacing $l_{x' \to x}$ with $l_{x' \to x}^{(m)}$).

We have incorporated this in the revised version.

2. Section 2, line 133: What is the "$\ell_1$ loss as the surrogate" for the 0-1 loss? The l1-loss surrogate for (1) is not so obvious, although we can understand it after reading its mathematical expression in (Cheng et al., 2023a).

Yes, by $\ell_1$ surrogate loss for 0-1 loss, we refer to equation 12) in Cheng et al. 2023a. We made this more explicit in the revised version.

3. Section 2, equation (2): What are the capital letters L and U ? Perhaps the lower and upper bounds as random variables? (If so, what are their distributions?)

Yes, L and U are the lower and upper bounds as random variables. We assume that the tuple $(x_i, l_i, u_i)$ is sampled i.i.d. from a distribution $\mathcal{D}_I$ (line 106).

4. Section 3, equation (6) and the succeeding sentences: Are $\pi_\ell$ and $\pi_l$ the same? (Perhaps just non-unified notations?)

Yes, we have fixed this in the revised version.

5. Section 3.2, Proposition 3.2: What situation the induced lower bound and upper bounds of $f(x)$ is effective? As far as my understanding, if the size of the bounds is small at $X'$ ,the size at another point $x$ must be accordingly small under the constraint of Lipschitz continuity.

First, we note that under a small ambiguity degree assumption, our bound would be very effective where we would recover the true label, $[l_{\mathcal{D} \to x}, u_{\mathcal{D} \to x}] = \{y\}$. Our bound is also applicable when the ambiguity degree is large and yes, you have the right intuition. Our bound is more effective when the hypothesis class is smoother, and when the neighbor intervals are "far away'' from the given interval, so that it would force the hypothesis to be near the edge of the given interval (see Figure 1b for an illustration).

6. Section 3.3.1, equation (13): What are the definitions of $I_0$ and $I_\eta$ ? (Although I could guess them,) their specific definitions seems not to be given.

We had defined $I_\eta$ in Theorem 3.3 in the previous version. In the revision, we define this explicitly in Section 3.3 so that it is easier for the reader.

7. Section 3.3.1, equation (14): Is the equation correct? The rightmost expression of the equation looks like independent from $x$.

Yes, this is correct. Here we consider and example when our error bound is tight when the hypothesis class only contains a constant function. Therefore, the right-hand side is independent from $x$.

8. Section 4: Are the notations $f$ in equations (20) and (21) are related? If not, it is better to introduce different variables.

Yes, they are the same hypothesis $f$ that we learn from the hypothesis class $\mathcal{F}$. However, they are not related and we can incoporate this in the revised version.

9. Section 5 (Appendix D): What is the obstacle (e.g., computational cost) to run the proposed method for a larger dataset? The datasets used in the experiments have up to 10000 samples.

There is no bottleneck for running this method on a larger dataset. In particular, the complexity of the projection method is the same as the complexity of traditional regression (with the same function class). For the pseudo-label methods, the complexity is $k$ times of the complexity of the traditional regression method when $k$ is the number of pseudo labels for each instance. We expect our proposed methods to scale well with the size of the datasets.

10. Section 5: The proposed method assumes that the class of hypotheses is m-Lipschitz, but in the experiment how can we limit the prediction model (MLP in this case) as m-Lipschitz? (The paper refers the existing work (Cheng et al., 2023a), but in the existing work it looks that m-Lipschitz is not employed.)

We use an MLP with a spectral normalization layer (Miyato et al. 2018)(see Section 5.2). The normalization ensures that the Lipschitz constant of the MLP is less than 1. We then scale the output of the MLP by a constant factor m to ensure that the Lipschitz constant of the hypothesis is less than $m$.

11. Section 5: What loss function does the experiment employed? (More specifically, $\psi$ in Assumption 1)

We use mean absolute error or $l_1$ loss in our experiment. This is equivalent to $\psi(x) = x$ in Assumption 1.

Dear reviewer, please let us know if you have any other questions. If we have resolved all your concerns, would you be willing to reconsider your score?

I was convinced with author's responses, however, I will retain my score after reading others' reviews.

Thank you for your feedback and suggestions. We hope that the following address your main questions regarding the ambiguity degree assumption.

1. The experimental setup considered by the authors is too simplistic, as it only involves a small number of UCI datasets, and the selected datasets are simple (small and low-dimensional). Previous research seems to have also considered experimental setups in CV and NLP.

Our focus on a small set of UCI datasets aims to complement the theoretical contributions of this work with clear, reproducible results. While it would be very valuable, our focus was not on a large-scale and thorough evaluation on the experimental front.

2. The authors' analysis is based on the rejection of the SMALL AMBIGUITY DEGREE ASSUMPTIONS, but I believe their rejection of this assumption is not convincing enough, as it would be impossible to learn if noise is always present.

In regression, predictions close to the target (within an error tolerance $\epsilon$) are often sufficient, making learning with noise more tolerable. For example, when for each label $y$ the given interval is a ball with radius $\epsilon > 0$ around $y$, $[l,u] = [y - \epsilon, y+\epsilon]$. When $\epsilon$ is small enough, then we would expect to be able to learn a good function, albeit with some irreducible (small) error that depends on $\epsilon$. However, since the ambiguity degree is large in this setting, the previous work would not apply.

3. In the regression setting,) should the AMBIGUITY DEGREE ASSUMPTIONS be redefined instead of being directly rejected? A larger AMBIGUITY DEGREE might result in intervals that are always mixed with noise, making it impossible to discern the true label distribution. Alternatively, could the size of intervals be used to constrain the AMBIGUITY DEGREE to satisfy a new relationship?

We have now added a note in the paper outlining an alternate definition in line with your proposal, and how it relates to our definition, in Appendix B. Here's a preview:

Recall that the small ambiguity degree assumption implies that for each instance $x$, the intersection of all intervals of $x$ is the true label $y$; $\bigcap [l_x, u_x] = y$. One possibility along the lines of your suggestion is to redefine it so that the intersection falls within a radius $\epsilon$ around the true label: $\bigcap [l_x, u_x] \subseteq B(y, \epsilon)$. In this case, our analysis already captures the essence of this interval intersection for each $x$. If we have this assumption then our bound would already imply that $f(x) \in I_0(x) \subseteq B(y, \epsilon)$. Further, $I_0(x)$ might even be a proper subset of the ball $B(y, \epsilon)$ based on the smoothness property.

4. In the PL (max) and PL (mean) methods, the authors utilize pseudo labels, but it seems there is no mention of how these pseudo labels are generated.

The pseudo labels are generated from a hypothesis $f_j$ which is a function from $\widetilde{\mathcal{F}}_\eta$ (see equation (25), (26)) for some small $\eta$. We have updated the paper to make this more clear now.

5. The projection loss proposed by the authors (Equation 5) appears to be consistent with the surrogate loss function in [1]. Does this imply that the method in [1] can still be applicable under the new setting (SMALL AMBIGUITY DEGREE ASSUMPTIONS does not apply) ?

We suppose that [1] here refers to a prior work "Weakly supervised regression with interval targets" by Cheng et al., 2023a. The surrogate loss function in [1] is a special case of our $L_p$ loss when $p=1$. In our paper, we have a theoretical result for $L_p$ loss for all $p \geq 1$ and also for a general loss function that satisfies Assumption 1. Our general result implies that [1] is still applicable in the setting when the small ambiguity degree assumption does not apply. On the other hand, previous work does not use the smoothness assumption and do not tune the Lipschitz constant of the hypothesis class. Our analysis found that this is an important variable and demonstrate that tuning the Lipschitz constant leads to a better downstream performance (Figure 3).

We are happy to provide an additional clarification. The empirical projection is given by Equation (5). That is, if we have training samples $(x_i, l_i, u_i)$ for $i = 1,\dots, n$ , then

$f_j \in \arg\min_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^n \pi_\ell(f(x_i), l_i, u_i).$

In practice, training a model using stochastic gradient descent with different random initializations and random seeds ensures that $f_j$ will be different. This process can be repeated $k$ times to obtain $\{f_1, \dots, f_k\}$. We will revise this to be more explicit in the updated version.

Thank you for your feedback and suggestions. We hope that the following address your questions regarding our theoretical results.

1. This paper highlights a generalization bound in Section 3.3 as its main result. However, this bound seems too straightforward and can be quite vacuous.

We want to highlight that one of the technical difficulties in proving Theorem 3.3 is that we allow for $f$ that only approximately lies inside the interval. That is, for certain $x$, $f(x)$ could be arbitrarily far away from the given interval $[l_x, u_x]$. Nevertheless, our bound provides a pointwise reduced interval for each individual $x$. This is non-trivial as we have to work with $f(x)$ that could be arbitrarily far away from the given interval $[l_x, u_x]$.

2. The multiple parameters appearing in the generalization bound are difficult, if impossible at all, to obtain. \ldots To obtain an estimate of $\eta$ one needs to know the Rademacher complexity of $\Pi(F)$ which can be quite difficult to obtain.

Our bounds emphasize learnability in the agnostic setting, which was not known in previous work. That is, as the sample size increases, we can bring error down to the error rate for the best hypothesis in class. Our bounds also reveal that the Lipschitz constant affects generalization. In practice, we would not estimate $I_\eta$ or $r_\eta$ but instead tune relevant parameters, and our analysis shows that the smoothness parameter is an important one to tune. Our experiments confirm the insights of the analysis hold in practice.

3. It's mentioned that Theorem 3.5 can be tight for certain hypothesis classes, for instance, constant hypotheses $\dots$ Could you provide another instance of hypothesis class, where this theorem can be relatively tight?

The bound would also be relatively tight on both extreme when the hypothesis class is smoother (Lipschitz constant $m$ is close to $0$) and when the hypothesis class is very flexible ($m$ is very large). The first setting follows from the fact that the bound holds for a constant hypothesis class when $m = 0$. For the second example, when the hypothesis class is very flexible so that the label of any $x$, is independent of other $x'$, the only information we have is that the true label lies inside a given interval then the best thing we could hope for is that the error for each instance $x$ is at most the size of the interval of each $x$. Since the hypothesis class is too flexible, we can't derive additional information from it.

4. In lines 179-182, it's mentioned that a value of $\eta$ is obtained from the RHS of Equation (6); how would one calculate the Rademacher complexity of $\Pi(F)$ ? How does the tightness of an estimation of $\eta$ affect the later generalization bounds? $\dots$ In lines 201-202, why $\eta_n=O(1/\sqrt{n})$? How does the Rademacher complexity of $\Pi(F)$ affect the order of $\eta_n$?

The result in the line 179-182 is an upper bound of the true value of $\eta$ of the learned hypothesis $f$ (denoted as $\eta_n$). This bound is for a theoretical purpose where we hope to communicate that as we have more training data points $n$, $\eta$ would converge to zero as $\eta_n$ is of $O(1/\sqrt{n})$. As a result, we would be able to learn a hypothesis that lies inside the given intervals more often with more training data.

To see that $\eta_n = O(1/\sqrt{n})$, we recall the definition that $\eta_n = 2R_n(\Pi(\mathcal{F})) + M\sqrt{\frac{\ln(1/\delta)}{n}}$ when $R_n(\Pi(\mathcal{F}))$ is the Rademacher complexity. We can show that $R_n(\Pi(\mathcal{F}))$ can be reduced to $R_n(\mathcal{F})$ and it is known that for many hypothesis class such as a class of two-layer neural networks with bounded weights or linear models, $R_n(\mathcal{F})$ is $O(1/\sqrt{n})$. Therefore, we can conclude that $\eta_n = O(1/\sqrt{n})$. We have provided a rigorous derivation of this in Appendix A.

On the effect of the $\eta$ on the final generalization bound, we have provided an additional Theorem in Appendix A that explicitly how the final error bound decay with the number of training sample $n$ (which also affect how large $\eta$ is).

Dear reviewer,

In the revision, we have comprehensively addressed your main concern regarding explicit bounds. A new Appendix section was added that shows $\eta_n = O(1/\sqrt{n})$ for classes with the Rademacher complexity $R_n = O(1/\sqrt{n})$. In the rebuttal comment before this one, we elaborate on this bound, as well as your other concerns.

We request you to reconsider your score.

Authors

I thank the authors for the responses and clarifications on explicit bounds. I am increasing my score to 5.