Timezone: »
Empirical evidence shows that in favorable situations semi-supervised learning (SSL) algorithms can capitalize on the abundancy of unlabeled training data to improve the performance of a learning task, in the sense that fewer labeled training data are needed to achieve a target error bound. However, in other situations unlabeled data do not seem to help. Recent attempts at theoretically characterizing the situations in which unlabeled data can help have met with little success, and sometimes appear to conflict with each other and intuition. In this paper, we attempt to bridge the gap between practice and theory of semi-supervised learning. We develop a rigorous framework for analyzing the situations in which unlabeled data can help and quantify the improvement possible using finite sample error bounds. We show that there are large classes of problems for which SSL can significantly outperform supervised learning, in finite sample regimes and sometimes also in terms of error convergence rates.
Author Information
Aarti Singh (CMU)
Rob Nowak (Wisconsin)
Jerry Zhu (University of Wisconsin-Madison)
Related Events (a corresponding poster, oral, or spotlight)
-
2008 Oral: Unlabeled data: Now it helps, now it doesn't »
Wed. Dec 10th 01:00 -- 01:20 AM Room
More from the Same Authors
-
2021 : Game Redesign in No-regret Game Playing »
Yuzhe Ma · Young Wu · Jerry Zhu -
2021 : Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments »
Amin Rakhsha · Xuezhou Zhang · Jerry Zhu · Adish Singla -
2021 : Game Redesign in No-regret Game Playing »
Yuzhe Ma · Young Wu · Jerry Zhu -
2021 : Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments »
Amin Rakhsha · Xuezhou Zhang · Jerry Zhu · Adish Singla -
2023 Poster: Mechanism Design for Collaborative Normal Mean Estimation »
Yiding Chen · Jerry Zhu · Kirthevasan Kandasamy -
2023 Poster: Dream the Impossible: Outlier Imagination with Diffusion Models »
Xuefeng Du · Yiyou Sun · Jerry Zhu · Yixuan Li -
2022 Poster: Provable Defense against Backdoor Policies in Reinforcement Learning »
Shubham Bharti · Xuezhou Zhang · Adish Singla · Jerry Zhu -
2021 Poster: Local Signal Adaptivity: Provable Feature Learning in Neural Networks Beyond Kernels »
Stefani Karp · Ezra Winston · Yuanzhi Li · Aarti Singh -
2020 Poster: Preference-based Reinforcement Learning with Finite-Time Guarantees »
Yichong Xu · Ruosong Wang · Lin Yang · Aarti Singh · Artur Dubrawski -
2020 Spotlight: Preference-based Reinforcement Learning with Finite-Time Guarantees »
Yichong Xu · Ruosong Wang · Lin Yang · Aarti Singh · Artur Dubrawski -
2019 Poster: On Testing for Biases in Peer Review »
Ivan Stelmakh · Nihar Shah · Aarti Singh -
2019 Spotlight: On Testing for Biases in Peer Review »
Ivan Stelmakh · Nihar Shah · Aarti Singh -
2019 Poster: Policy Poisoning in Batch Reinforcement Learning and Control »
Yuzhe Ma · Xuezhou Zhang · Wen Sun · Jerry Zhu -
2019 Poster: Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models »
Farnam Mansouri · Yuxin Chen · Ara Vartanian · Jerry Zhu · Adish Singla -
2019 Poster: A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning »
Xuanqing Liu · Si Si · Jerry Zhu · Yang Li · Cho-Jui Hsieh -
2018 Poster: How Many Samples are Needed to Estimate a Convolutional Neural Network? »
Simon Du · Yining Wang · Xiyu Zhai · Sivaraman Balakrishnan · Russ Salakhutdinov · Aarti Singh -
2018 Poster: Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates »
Yining Wang · Sivaraman Balakrishnan · Aarti Singh -
2018 Poster: Adversarial Attacks on Stochastic Bandits »
Kwang-Sung Jun · Lihong Li · Yuzhe Ma · Jerry Zhu -
2017 Workshop: Teaching Machines, Robots, and Humans »
Maya Cakmak · Anna Rafferty · Adish Singla · Jerry Zhu · Sandra Zilles -
2017 Poster: Hypothesis Transfer Learning via Transformation Functions »
Simon Du · Jayanth Koushik · Aarti Singh · Barnabas Poczos -
2017 Poster: Gradient Descent Can Take Exponential Time to Escape Saddle Points »
Simon Du · Chi Jin · Jason D Lee · Michael Jordan · Aarti Singh · Barnabas Poczos -
2017 Spotlight: Gradient Descent Can Take Exponential Time to Escape Saddle Points »
Simon Du · Chi Jin · Jason D Lee · Michael Jordan · Aarti Singh · Barnabas Poczos -
2017 Poster: On the Power of Truncated SVD for General High-rank Matrix Estimation Problems »
Simon Du · Yining Wang · Aarti Singh -
2017 Poster: Noise-Tolerant Interactive Learning Using Pairwise Comparisons »
Yichong Xu · Hongyang Zhang · Aarti Singh · Artur Dubrawski · Kyle Miller -
2016 : Optimal Teaching for Online Perceptrons »
Xuezhou Zhang · Jerry Zhu -
2016 Workshop: The Future of Interactive Machine Learning »
Kory Mathewson @korymath · Kaushik Subramanian · Mark Ho · Robert Loftin · Joseph L Austerweil · Anna Harutyunyan · Doina Precup · Layla El Asri · Matthew Gombolay · Jerry Zhu · Sonia Chernova · Charles Isbell · Patrick M Pilarski · Weng-Keen Wong · Manuela Veloso · Julie A Shah · Matthew Taylor · Brenna Argall · Michael Littman -
2016 Poster: Data Poisoning Attacks on Factorization-Based Collaborative Filtering »
Bo Li · Yining Wang · Aarti Singh · Yevgeniy Vorobeychik -
2016 Poster: Finite Sample Prediction and Recovery Bounds for Ordinal Embedding »
Lalit Jain · Kevin Jamieson · Rob Nowak -
2016 Poster: Active Learning with Oracle Epiphany »
Tzu-Kuo Huang · Lihong Li · Ara Vartanian · Saleema Amershi · Jerry Zhu -
2015 Workshop: Multiresolution methods for large-scale learning »
Inderjit Dhillon · Risi Kondor · Rob Nowak · Michael O'Neil · Nedelina Teneva -
2015 : Tsybakov Noise Adaptive Margin-Based Active Learning »
Aarti Singh -
2015 Poster: Differentially private subspace clustering »
Yining Wang · Yu-Xiang Wang · Aarti Singh -
2015 Poster: Human Memory Search as Initial-Visit Emitting Random Walk »
Kwang-Sung Jun · Jerry Zhu · Timothy T Rogers · Zhuoran Yang · Ming Yuan -
2015 Poster: NEXT: A System for Real-World Development, Evaluation, and Application of Active Learning »
Kevin G Jamieson · Lalit Jain · Chris Fernandez · Nicholas J. Glattard · Rob Nowak -
2015 Spotlight: NEXT: A System for Real-World Development, Evaluation, and Application of Active Learning »
Kevin G Jamieson · Lalit Jain · Chris Fernandez · Nicholas J. Glattard · Rob Nowak -
2014 Poster: Optimal Teaching for Limited-Capacity Human Learners »
Kaustubh R Patil · Jerry Zhu · Łukasz Kopeć · Bradley C Love -
2014 Spotlight: Optimal Teaching for Limited-Capacity Human Learners »
Kaustubh R Patil · Jerry Zhu · Łukasz Kopeć · Bradley C Love -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2013 Poster: Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic »
James L Sharpnack · Akshay Krishnamurthy · Aarti Singh -
2013 Poster: Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis »
Nikhil Rao · Christopher R Cox · Rob Nowak · Timothy T Rogers -
2013 Spotlight: Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis »
Nikhil Rao · Christopher R Cox · Rob Nowak · Timothy T Rogers -
2013 Poster: Machine Teaching for Bayesian Learners in the Exponential Family »
Jerry Zhu -
2013 Poster: Low-Rank Matrix and Tensor Completion via Adaptive Sampling »
Akshay Krishnamurthy · Aarti Singh -
2013 Poster: Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation »
Martin Azizyan · Aarti Singh · Larry Wasserman -
2013 Poster: Cluster Trees on Manifolds »
Sivaraman Balakrishnan · Srivatsan Narayanan · Alessandro Rinaldo · Aarti Singh · Larry Wasserman -
2012 Workshop: Algebraic Topology and Machine Learning »
Sivaraman Balakrishnan · Alessandro Rinaldo · Donald Sheehy · Aarti Singh · Larry Wasserman -
2012 Poster: Query Complexity of Derivative-Free Optimization »
Kevin G Jamieson · Rob Nowak · Benjamin Recht -
2011 Poster: How Do Humans Teach: On Curriculum Learning and Teaching Dimension »
Faisal Khan · Jerry Zhu · Bilge Mutlu -
2011 Poster: Minimax Localization of Structural Information in Large Noisy Matrices »
Mladen Kolar · Sivaraman Balakrishnan · Alessandro Rinaldo · Aarti Singh -
2011 Poster: Noise Thresholds for Spectral Clustering »
Sivaraman Balakrishnan · Min Xu · Akshay Krishnamurthy · Aarti Singh -
2011 Spotlight: Noise Thresholds for Spectral Clustering »
Sivaraman Balakrishnan · Min Xu · Akshay Krishnamurthy · Aarti Singh -
2011 Spotlight: Minimax Localization of Structural Information in Large Noisy Matrices »
Mladen Kolar · Sivaraman Balakrishnan · Alessandro Rinaldo · Aarti Singh -
2011 Poster: Learning Higher-Order Graph Structure with Features by Structure Penalty »
Shilin Ding · Grace Wahba · Jerry Zhu -
2011 Poster: Active Ranking using Pairwise Comparisons »
Kevin G Jamieson · Rob Nowak -
2010 Oral: Humans Learn Using Manifolds, Reluctantly »
Bryan R Gibson · Jerry Zhu · Timothy T Rogers · Chuck Kalish · Joseph Harrison -
2010 Oral: Identifying graph-structured activation patterns in networks »
James L Sharpnack · Aarti Singh -
2010 Poster: Identifying graph-structured activation patterns in networks »
James L Sharpnack · Aarti Singh -
2010 Poster: Humans Learn Using Manifolds, Reluctantly »
Bryan R Gibson · Jerry Zhu · Timothy T Rogers · Chuck Kalish · Joseph Harrison -
2010 Poster: Transduction with Matrix Completion: Three Birds with One Stone »
Andrew B Goldberg · Jerry Zhu · Benjamin Recht · Junming Sui · Rob Nowak -
2010 Session: Spotlights Session 1 »
Jerry Zhu -
2009 Poster: Human Rademacher Complexity »
Jerry Zhu · Timothy T Rogers · Bryan R Gibson -
2009 Poster: Noisy Generalized Binary Search »
Rob Nowak -
2009 Session: Oral Session 1: Information Theory and Estimation »
Rob Nowak -
2008 Workshop: Machine learning meets human learning »
Nathaniel D Daw · Tom Griffiths · Josh Tenenbaum · Jerry Zhu -
2008 Poster: Human Active Learning »
Jerry Zhu · Rui M Castro · Timothy T Rogers · Rob Nowak · Ruichen Qian · Chuck Kalish -
2006 Poster: Inferring Network Structure from Co-Occurrences »
Michael Rabbat · Mario T Figueiredo · Rob Nowak