In supervised learning, we leverage a labeled dataset to design methodsfor function estimation.In many practical situations, we are able to obtainalternative feedback, possibly at a low cost. A broad goal is to understand the usefulnessof, and to design algorithms to exploit, this alternative feedback.We focus on a semi-supervised setting where we obtain additional ordinal (or comparison) information for potentially unlabeled samples. We considerordinal 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 non-parametric regression, showing that in many cases it is possible to accurately estimate an underlying function with a very small labeled set, effectively escaping the curse of dimensionality.We develop an algorithm called Ranking-Regression (RR) and analyze its accuracy as a function of size of the labeled and unlabeled datasetsand various noise parameters.We also present lower bounds, that establish fundamental limits for the task and show that RR is optimal in a variety of settings. Finally, we present experiments that show the efficacy of RR and investigate its robustness to various sources of noise and model-misspecification.