Learning from Interval Targets

Thank you for the thoughtful feedback. Please find our individual responses below.

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.

Our original intention was to prioritize the theoretical development in the main text due to strict page limits, but we recognize that this came at the cost of clarity.

Based on your feedback, we will revise the manuscript to improve its self-containment. Specifically, we will move the definition of our primary objective function (formerly Eq. 134) and other key experimental details from the appendix into the main body of the paper.

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.

We have performed an extensive evaluation on 18 datasets, but unfortunately these results had to be moved the Appendix due to space constraints. As detailed in Appendix L (Table 4, page 45), we evaluated our method on 18 diverse tabular datasets from the benchmark suite of Grinsztajn et al. [1]. Our LipMLP significantly outperforms the standard MLP on 14 of the 18 datasets, with similar or competitive performance on the rest. This provides strong evidence for the generalizability of our approach, and we will revise the main text to better highlight these extensive results.

[1] Grinsztajn, Léo, Edouard Oyallon, and Gaël Varoquaux. "Why do tree-based models still outperform deep learning on typical tabular data?." Advances in neural information processing systems 35 (2022): 507-520.

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.

The LM loss from [Cheng et al.] is a specific instance of our more general projection loss framework when the loss function is set to l1​. Therefore, our "Projection MLP" baseline in the experiments is, in fact, equivalent to the LM loss baseline the reviewer requested. Our results show that our proposed LipMLP consistently outperforms this strong baseline on numerous datasets. We will revise the paper to make this equivalence explicit.

Comparison with Noisy Label Regression: I 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.

Please see the general response.

Fair Comparison with PL (Mean) Approach: While 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?

All methods have a pretty low computation anyway since all of them are at a constant factor of a standard liner regression. Therefore, we think the difference in running time is not significant.

The performance of an ensemble is also interesting. In Appendix K, we compare PL(mean) with a natural ensemble baseline where we combine pseudo labels by averaging them first and then train a model with respect to the averaged labels. We found that PL (mean) still performs better than this baseline on 2 out of 5 datasets while the other 3 datasets are similar.

Thank you for the thoughtful feedback. Please find our individual responses below.

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.

We appreciate the reviewer's request for clarification on our novel contributions. We have summarized them below:

1. Projection Loss: We clarify that our work significantly generalizes the projection loss proposed in Cheng et al. [1]. Our key contributions are:

• Generalizes the Loss Function: While [1] focuses specifically on the l1​ loss, our theoretical analysis is general and applies to a broader class of loss functions.
• Relaxes Strong Assumptions: Our framework removes the restrictive assumptions of realizability and small ambiguity degree required by [1]. This makes our analysis more practical and applicable to a wider range of real-world, agnostic learning scenarios.

2. Robust ML: We appreciate the connection to robust ML. The fundamental difference is that robust methods like [2, 3] aim to enforce model stability against adversarial perturbations of the input features. In contrast, our work addresses a bounded (not arbitrary/adversarial) uncertainty in the output labels, since the true label must lie within the known interval.

The approach for minmax formulation that utilizes an auxiliary worst-case learner is not connected to interval targets.

The interval targets are a core components of our min-max formulation since the worst-case labels are generated from a hypothesis that lies inside the interval targets.

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.

Noisy label regression would discard the interval information, and treat a fraction of the data as having arbitrary outliers, which is not the case in our setting. There may be interesting ways to leverage the noisy label literature, leading to a separate approach to the problem, but it is not obvious de facto what the right reduction is. Hence we do not feel it is a necessary baseline. We have also elaborated on this in the general response.

What does PL Mean mean in the experiment?

We apologize for the confusion. PL Mean refers to Pseudo labels (mean) which is our proposed method for solving the minmax objective with constraints. We provided full definitions in Appendix G.

Could this approach be applied beyond tabular data? I think the application on the unstructured data, such as images, is very important and practical.

Yes, it is also applicable to images or any other domains.

Is there a better way of approximating the Lipschitz constant? It seems the approximated ones in the experiment does not lead to optimal results.

Our approach is a standard heuristic for approximating the Lipschitz constant from the dataset which is not necessarily optimal for the LipMLP. In practice, one can just treat the Lipschitz constant for the LipMLP as a hyperparameter and tune them accordingly. This leads to a significant performance gain when compared with the standard MLP (see Table 4 in Appendix L).

I appreciate the detailed response from the authors. I have some concerns remaining and would like to discuss more:

• Technical contribution of minmax formulation. Technically, robust ML looks into $min_{M}\ max_{D\in D^P}\ loss(M, D)$ with $M$ and $D$ being the model and data, and $D$ might come from a set of possible datasets with bounded perturbations $D^P$. The difference between this work's minmax formulation and the formulation of most robust ML techniques is that, this work looks at bounded perturbation of labels, while previous works look at that of features. However, the inner optimization for feature perturbation is way more challenging, and can be easily adapted to find worst-case labels.
• Larger, unstructured data experiment. This work closely connects to partial label learning, and most works in that domain have been tested on larger, unstructured data (such as some early works [1,2]). Therefore, I believe the evaluation of this work could be strengthened by including such data as well.
• Comparing with noisy label learning.
  • I understand that the settings of noisy label learning do not include a bounded interval target assumption. However, I view the interval bounds as a more restricted setting, and noisy label learning methods should be able to be applied here. For instance, we can use the mean of each interval (or a randomly sampled value inside the interval) as the noisy (pseudo) label, and apply the noisy label learning techniques.
  • A more interesting question is, whether the pseudo-labeling based on the min-max formulation proposed in this work could be combined with subsequent noisy label learning and show better performance.

[1] Lv, Jiaqi, 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, pp. 6500-6510. PMLR, 2020.

[2] Feng, Lei, 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 (2020): 10948-10960.

Thank you for the thoughtful feedback. Please find our individual responses below.

Potentially unclear link between the theory and experiments. Fig. 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.

Thank you for this question. Our theoretical upper bound consists of three main terms: (a) approximation error, (b) effective interval width, and (c) Rademacher complexity. While the reviewer correctly points to the trade-off between terms (b) and (c), our hypothesis is that for these specific datasets, the empirically dominant trade-off is actually between the approximation error (a) and the effective interval width (b), with the complexity term (c) playing a smaller role.

1. The U-Shape : The U-shape appears when, for a small Lipschitz constant m, the approximation error (a) is large but the effective interval width (b) is small. Conversely, as m grows, the approximation error (a) shrinks, but the model's reliance on the original supervisory intervals causes the effective width (b) to grow, eventually increasing the total error.
2. The Monotonic Decrease: The key insight is that term (b) is highly dependent on the "informativeness" of the initial supervisory intervals. On datasets like Airfoil and Concrete, we believe that the provided intervals are already very tight and informative. Consequently, even as m increases and the approximation error (a) drops, the effective interval width (b) remains small. The trade-off is muted because term (b) never grows large enough to cause an inflection in the error curve within our tested range.

In summary, the shape of the curve is dataset-dependent and hinges on the quality of the interval supervision itself. We will add a discussion to the paper to clarify this nuance. In addition, we also have plots for 2 additional dataset in Appendix J (housing and power-plant dataset) where we observe the U-shape and Monotonic decrease plot respectively.

Global Lipschitz constraint may be unrealistic. The assumption that a single scalar m upper bounds gradient f for all 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 .

We agree with this limitation and have discussed this in the limited work section, we note that other similar assumptions, such as a modulus of continuity, could also lead to analogous results which would be an interesting direction for future work.

Reproducibility concern. Code is currently unavailable (though promised upon acceptance), preventing reviewers from assessing reproducibility.

Unfortunately, we are strictly bound by the conference policy which prohibits sharing new materials or external links during the rebuttal period. This prevents us from providing the codebase at this stage. Given these constraints, we are more than happy to answer any specific questions about our implementation, model architecture, or hyperparameter settings to the best of our ability. We reaffirm our commitment to make the complete, documented codebase publicly available immediately upon acceptance.

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?

We treat m as a hyperparameter tuned via standard validation. The effectiveness of this approach is shown in Table 4 (Appendix L), where our method consistently and significantly outperforms the MLP baseline, confirming it provides robust regularization rather than simply overfitting.

Thank you for the thoughtful feedback. Please find our individual responses below.

It 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?

Our bound can be tight for a certain hypothesis class, for example, a class of constant hypotheses. We discussed this in Appendix E (e.g. see eq (88)).

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?

Yes, a finite-sample generalization bound for the min-max objective can be derived from our population-risk analysis in Eq. (23) using standard uniform convergence techniques. This bound would differ from the projection-based analysis because the min-max loss is, by definition, a pessimistic upper bound on the true loss, while the projection loss is an optimistic surrogate. Consequently, a generalization bound on the min-max risk will be inherently looser, as it provides a more conservative, worst-case guarantee on performance.