Learning Halfspaces with Massart Noise Under Structured Distributions

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

Type: Preprint

Publication Date: 2020-02-13

Citations: 7

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Learning Halfspaces with Massart Noise Under Structured Distributions	2020	Ilias Diakonikolas Vasilis Kontonis Christos Tzamos Nikos Zarifis
+	Non-Convex SGD Learns Halfspaces with Adversarial Label Noise	2020	Ilias Diakonikolas Vasilis Kontonis Christos Tzamos Nikos Zarifis
+ PDF Chat	A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise	2025	Ilias Diakonikolas Nikos Zarifis
+	Learning Halfspaces with Tsybakov Noise	2020	Ilias Diakonikolas Vasilis Kontonis Christos Tzamos Nikos Zarifis
+	Distribution-Independent PAC Learning of Halfspaces with Massart Noise	2019	Ilias Diakonikolas Themis Gouleakis Christos Tzamos
+	Distribution-Independent PAC Learning of Halfspaces with Massart Noise	2019	Ilias Diakonikolas Themis Gouleakis Christos Tzamos
+	Learning Halfspaces with Tsybakov Noise.	2020	Ilias Diakonikolas Vasilis Kontonis Christos Tzamos Nikos Zarifis
+	S-Concave Distributions: Towards Broader Distributions for Noise-Tolerant and Sample-Efficient Learning Algorithms.	2017	Maria-Florina Balcan Hongyang Zhang
+	Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions	2017	Maria-Florina Balcan Hongyang Zhang
+ PDF Chat	Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random	2025	Gautam Chandrasekaran Vasilis Kontonis Konstantinos Stavropoulos Kevin Tian
+	Forster Decomposition and Learning Halfspaces with Noise	2021	Ilias Diakonikolas Daniel M. Kane Christos Tzamos
+	Forster Decomposition and Learning Halfspaces with Noise	2021	Ilias Diakonikolas Daniel M. Kane Christos Tzamos
+	An Efficient Tester-Learner for Halfspaces	2023	Aravind Gollakota Adam R. Klivans Konstantinos Stavropoulos Arsen Vasilyan
+	Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise	2021	Chicheng Zhang Yinan Li
+	Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise	2021	Chicheng Zhang Yinan Li
+	Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach	2023	Yinan Li Chicheng Zhang
+	Sample-Optimal PAC Learning of Halfspaces with Malicious Noise	2021	Jie Shen
+	Efficient Robust Proper Learning of Log-concave Distributions	2016	Ilias Diakonikolas Daniel M. Kane Alistair Stewart
+ PDF Chat	Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate	2024	Jie Shen Xiaoyu Li
+	Learning discrete distributions with infinite support	2020	Doron Cohen Aryeh Kontorovich Geoffrey Wolfer

Works That Cite This (7)

Action	Title	Year	Authors
+	A Study of Neural Training with Non-Gradient and Noise Assisted Gradient Methods.	2020	Anirbit Mukherjee Ramchandran Muthukumar
+	On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise	2020	Jie Shen
+	Threshold Phenomena in Learning Halfspaces with Massart Noise	2021	Ilias Diakonikolas Daniel M. Kane Vasilis Kontonis Christos Tzamos Nikos Zarifis
+	Hardness of Learning Halfspaces with Massart Noise.	2020	Ilias Diakonikolas Daniel M. Kane
+	Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability	2020	Sitan Chen Frederic Koehler Ankur Moitra Morris Yau
+	Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise	2021	Chicheng Zhang Yinan Li
+ PDF Chat	Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination	2022	Sitan Chen Frederic Koehler Ankur Moitra Morris Yau

Works Cited by This (13)

Action	Title	Year	Authors
+ PDF Chat	Risk bounds for statistical learning	2006	Pascal Massart Élodie Nédélec
+ PDF Chat	Concentration of mass on convex bodies	2006	Grigoris Paouris
+	None	2007	Remco van der Hofstad Gerard Hooghiemstra Piet Van Mieghem
+	Nonconvex sampling with the Metropolis-adjusted Langevin algorithm	2019	Oren Mangoubi Nisheeth K. Vishnoi
+ PDF Chat	Lower bounds for non-convex stochastic optimization	2022	Yossi Arjevani Yair Carmon John C. Duchi Dylan J. Foster Nathan Srebro Blake Woodworth
+	Analysis of Boolean Functions	2014	Ryan O’Donnell
+ PDF Chat	Complexity theoretic limitations on learning halfspaces	2016	Amit Daniely
+ PDF Chat	The Power of Localization for Efficiently Learning Linear Separators with Noise	2017	Pranjal Awasthi Maria Florina Balcan Philip M. Long
+	A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics	2017	Yuchen Zhang Percy Liang Moses Charikar
+	Learning geometric concepts with nasty noise	2018	Ilias Diakonikolas Daniel M. Kane Alistair Stewart