# Data driven semi-supervised learning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 52 references that are in the map.
- First posted on arXiv 18 Mar 2021.

## Builds on (most cited first, 12 of 12)

- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Learning to Link](https://mlsanity.com/paper/1907.00533/) (2019)
- [Refined bounds for algorithm configuration: The knife-edge of dual class approximability](https://mlsanity.com/paper/2006.11827/) (2020)
- [Estimating Approximate Incentive Compatibility](https://mlsanity.com/paper/1902.09413/) (2019)
- [Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees](https://mlsanity.com/paper/1905.10819/) (2019)

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

- [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Accelerating ERM for data-driven algorithm design using output-sensitive techniques](https://mlsanity.com/paper/2204.03569/) (2022)
- [Offline-to-online hyperparameter transfer for stochastic bandits](https://mlsanity.com/paper/2501.02926/) (2025)
- [Efficiently Learning the Graph for Semi-supervised Learning](https://mlsanity.com/paper/2306.07098/) (2023)
- [Semantic Contrastive Bootstrapping for Single-positive Multi-label Recognition](https://mlsanity.com/paper/2307.07680/) (2023)
- [Meta Co-Training: Two Views are Better than One](https://mlsanity.com/paper/2311.18083/) (2023)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (2023)
- [TRiCo: Triadic Game-Theoretic Co-Training for Robust Semi-Supervised Learning](https://mlsanity.com/paper/2509.21526/) (2025)
- [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Subsidy design for better social outcomes](https://mlsanity.com/paper/2409.03129/) (2024)
- [Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees](https://mlsanity.com/paper/2502.12937/) (2025)
- [Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws](https://mlsanity.com/paper/2608.01670/) (2026)

## Abstract (arXiv)

We consider a novel data driven approach for designing learning algorithms that can effectively learn with only a small number of labeled examples. This is crucial for modern machine learning applications where labels are scarce or expensive to obtain. We focus on graph-based techniques, where the unlabeled examples are connected in a graph under the implicit assumption that similar nodes likely have similar labels. Over the past decades, several elegant graph-based semi-supervised learning algorithms for how to infer the labels of the unlabeled examples given the graph and a few labeled examples have been proposed. However, the problem of how to create the graph (which impacts the practical usefulness of these methods significantly) has been relegated to domain-specific art and heuristics and no general principles have been proposed. In this work we present a novel data driven approach for learning the graph and provide strong formal guarantees in both the distributional and online learning formalizations. We show how to leverage problem instances coming from an underlying problem domain to learn the graph hyperparameters from commonly used parametric families of graphs that perform well on new instances coming from the same domain. We obtain low regret and efficient algorithms in the online setting, and generalization guarantees in the distributional setting. We also show how to combine several very different similarity metrics and learn multiple hyperparameters, providing general techniques to apply to large classes of problems. We expect some of the tools and techniques we develop along the way to be of interest beyond semi-supervised learning, for data driven algorithms for combinatorial problems more generally.