Regression with Comparisons: Escaping the Curse of Dimensionality with Ordinal Information
This addresses the challenge of high-dimensional data labeling costs in machine learning, offering a novel semi-supervised method that is incremental in leveraging alternative feedback types.
The paper tackles the problem of semi-supervised regression by using ordinal information (e.g., comparisons or orderings) for unlabeled samples to reduce the need for labeled data, showing that this approach can effectively escape the curse of dimensionality in many cases.
In supervised learning, we typically leverage a fully labeled dataset to design methods for function estimation or prediction. In many practical situations, we are able to obtain alternative feedback, possibly at a low cost. A broad goal is to understand the usefulness of, and to design algorithms to exploit, this alternative feedback. In this paper, we consider a semi-supervised regression setting, where we obtain additional ordinal (or comparison) information for the unlabeled samples. We consider ordinal feedback of varying qualities where we have either a perfect ordering of the samples, a noisy ordering of the samples or noisy pairwise comparisons between the samples. We provide a precise quantification of the usefulness of these types of ordinal feedback in both nonparametric and linear regression, showing that in many cases it is possible to accurately estimate an underlying function with a very small labeled set, effectively \emph{escaping the curse of dimensionality}. We also present lower bounds, that establish fundamental limits for the task and show that our algorithms are optimal in a variety of settings. Finally, we present extensive experiments on new datasets that demonstrate the efficacy and practicality of our algorithms and investigate their robustness to various sources of noise and model misspecification.