# Efficient Algorithms for Learning from Coarse Labels

arXiv: https://arxiv.org/abs/2108.09805 · HTML: https://mlsanity.com/paper/2108.09805/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 105 references that are in the map.
- First posted on arXiv 22 Aug 2021.

## Builds on (most cited first, 30 of 40)

- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Does label smoothing mitigate label noise?](https://mlsanity.com/paper/2003.02819/) (2020)
- [Weakly- and Semi-Supervised Learning of a DCNN for Semantic Image Segmentation](https://mlsanity.com/paper/1502.02734/) (2015)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Progressive Identification of True Labels for Partial-Label Learning](https://mlsanity.com/paper/2002.08053/) (2020)
- [Provably Consistent Partial-Label Learning](https://mlsanity.com/paper/2007.08929/) (2020)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Learning from Complementary Labels](https://mlsanity.com/paper/1705.07541/) (2017)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Classification with Asymmetric Label Noise: Consistency and Maximal Denoising](https://mlsanity.com/paper/1303.1208/) (2013)
- [Leveraged Weighted Loss for Partial Label Learning](https://mlsanity.com/paper/2106.05731/) (2021)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Grafit: Learning fine-grained image representations with coarse labels](https://mlsanity.com/paper/2011.12982/) (2020)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [Fine-grained Angular Contrastive Learning with Coarse Labels](https://mlsanity.com/paper/2012.03515/) (2020)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019)
- [Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds](https://mlsanity.com/paper/1805.02677/) (2018)

## Built on by (most cited first, 21 of 21)

- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Coarse-To-Fine Incremental Few-Shot Learning](https://mlsanity.com/paper/2111.14806/) (2021)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [Hyperbolic Space with Hierarchical Margin Boosts Fine-Grained Learning from Coarse Labels](https://mlsanity.com/paper/2311.11019/) (2023)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Label Ranking through Nonparametric Regression](https://mlsanity.com/paper/2111.02749/) (2021)
- [Active Labeling: Streaming Stochastic Gradients](https://mlsanity.com/paper/2205.13255/) (2022)
- [Multi-Scale Graph Learning for Anti-Sparse Downscaling](https://mlsanity.com/paper/2505.01948/) (2025)
- [Fine-grained Classes and How to Find Them](https://mlsanity.com/paper/2406.11070/) (2024)
- [BackSplit: The Importance of Sub-dividing the Background in Biomedical Lesion Segmentation](https://mlsanity.com/paper/2511.19394/) (2025)
- [Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample](https://mlsanity.com/paper/2509.20993/) (2025)
- [Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers](https://mlsanity.com/paper/2605.18662/) (2026)
- [Efficient Subclass Segmentation in Medical Images](https://mlsanity.com/paper/2307.00257/) (2023)
- [Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms](https://mlsanity.com/paper/2602.23341/) (2026)
- [Improving Selective Classification with Pairwise Queries for Binary Classification](https://mlsanity.com/paper/2605.30615/) (2026)
- [Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue](https://mlsanity.com/paper/2607.22889/) (2026)
- [When Is Coarse Supervision Worth It? Cost-Aware Learning under Unknown Aggregation](https://mlsanity.com/paper/2609.36704/) (2026)

## Abstract (arXiv)

For many learning problems one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the annotator. In this work, we formalize these settings and study the problem of learning from such coarse data. Instead of observing the actual labels from a set Z, we observe coarse labels corresponding to a partition of Z (or a mixture of partitions). Our main algorithmic result is that essentially any problem learnable from fine grained labels can also be learned efficiently when the coarse data are sufficiently informative. We obtain our result through a generic reduction for answering Statistical Queries (SQ) over fine grained labels given only coarse labels. The number of coarse labels required depends polynomially on the information distortion due to coarsening and the number of fine labels |Z|. We also investigate the case of (infinitely many) real valued labels focusing on a central problem in censored and truncated statistics: Gaussian mean estimation from coarse data. We provide an efficient algorithm when the sets in the partition are convex and establish that the problem is NP-hard even for very simple non-convex sets.