Timezone: »
We consider a novel data driven approach for designing semi-supervised learning algorithms that can effectively learn with only a small number of labeled examples. 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 two decades, several elegant graph-based semi-supervised learning algorithms for inferring 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 heuristics and domain-specific art, 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 for commonly used parametric families of graphs that provably perform well on new instances 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, our results hold for large classes of problems. We expect some of the tools and techniques we develop along the way to be of independent interest, for data driven algorithms more generally.
Author Information
Maria-Florina Balcan (Carnegie Mellon University)
Dravyansh Sharma (Sharma)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Data driven semi-supervised learning »
Thu. Dec 9th 04:30 -- 06:00 PM Room
More from the Same Authors
-
2021 Spotlight: Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm · Ellen Vitercik -
2022 Poster: Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm · Ellen Vitercik -
2022 Poster: Provably tuning the ElasticNet across instances »
Maria-Florina Balcan · Misha Khodak · Dravyansh Sharma · Ameet Talwalkar -
2022 Poster: Maximizing Revenue under Market Shrinkage and Market Uncertainty »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm -
2022 Poster: Learning Predictions for Algorithms with Predictions »
Misha Khodak · Maria-Florina Balcan · Ameet Talwalkar · Sergei Vassilvitskii -
2021 Poster: Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing »
Mikhail Khodak · Renbo Tu · Tian Li · Liam Li · Maria-Florina Balcan · Virginia Smith · Ameet Talwalkar -
2021 Poster: Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond »
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm · Ellen Vitercik -
2021 Poster: Learning-to-learn non-convex piecewise-Lipschitz functions »
Maria-Florina Balcan · Mikhail Khodak · Dravyansh Sharma · Ameet Talwalkar -
2019 Poster: Envy-Free Classification »
Maria-Florina Balcan · Travis Dick · Ritesh Noothigattu · Ariel Procaccia -
2019 Poster: Adaptive Gradient-Based Meta-Learning Methods »
Misha Khodak · Maria-Florina Balcan · Ameet Talwalkar -
2018 Poster: Data-Driven Clustering via Parameterized Lloyd's Families »
Maria-Florina Balcan · Travis Dick · Colin White -
2018 Spotlight: Data-Driven Clustering via Parameterized Lloyd's Families »
Maria-Florina Balcan · Travis Dick · Colin White -
2017 : Invited Talk: Sample and Computationally Efficient Active Learning Algorithms »
Maria-Florina Balcan -
2017 Poster: Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions »
Maria-Florina Balcan · Hongyang Zhang -
2016 Poster: Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling »
Maria-Florina Balcan · Hongyang Zhang -
2016 Poster: Sample Complexity of Automated Mechanism Design »
Maria-Florina Balcan · Tuomas Sandholm · Ellen Vitercik