Timezone: »
Poster
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
Ilias Diakonikolas · Vasilis Kontonis · Christos Tzamos · Nikos Zarifis
We study the problem of agnostically learning homogeneous halfspaces in the distribution-specific PAC model.
For a broad family of structured distributions, including log-concave distributions, we show that non-convex SGD
efficiently converges to a solution with misclassification error $O(\opt)+\eps$, where $\opt$ is the misclassification
error of the best-fitting halfspace. In sharp contrast, we show that optimizing any convex surrogate inherently
leads to misclassification error of $\omega(\opt)$, even under Gaussian marginals.
Author Information
Ilias Diakonikolas (UW Madison)
Vasilis Kontonis (University of Wisconsin-Madison)
Christos Tzamos (UW Madison)
Nikos Zarifis (University of Wisconsin-Madison)
More from the Same Authors
-
2021 Spotlight: List-Decodable Mean Estimation in Nearly-PCA Time »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard · Jerry Li · Kevin Tian -
2021 Spotlight: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2021 Spotlight: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2023 Poster: Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Method »
Constantine Caramanis · Dimitris Fotakis · Alkis Kalavasis · Vasilis Kontonis · Christos Tzamos -
2023 Poster: Efficient Testable Learning of Halfspaces with Adversarial Label Noise »
Ilias Diakonikolas · Daniel Kane · Vasilis Kontonis · Sihan Liu · Nikos Zarifis -
2023 Poster: Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise »
Ilias Diakonikolas · Jelena Diakonikolas · Daniel Kane · Puqian Wang · Nikos Zarifis -
2023 Poster: The Gain from Ordering in Online Learning »
Vasilis Kontonis · Mingchen Ma · Christos Tzamos -
2023 Poster: SLaM: Student-Label Mixing for Distillation with Unlabeled Examples »
Vasilis Kontonis · Fotis Iliopoulos · Khoa Trinh · Cenk Baykal · Gaurav Menghani · Erik Vee -
2023 Oral: Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Method »
Constantine Caramanis · Dimitris Fotakis · Alkis Kalavasis · Vasilis Kontonis · Christos Tzamos -
2022 Poster: Linear Label Ranking with Bounded Noise »
Dimitris Fotakis · Alkis Kalavasis · Vasilis Kontonis · Christos Tzamos -
2022 Poster: Weighted Distillation with Unlabeled Examples »
Fotis Iliopoulos · Vasilis Kontonis · Cenk Baykal · Gaurav Menghani · Khoa Trinh · Erik Vee -
2021 Poster: ReLU Regression with Massart Noise »
Ilias Diakonikolas · Jong Ho Park · Christos Tzamos -
2021 Poster: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2021 Poster: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2021 Poster: List-Decodable Mean Estimation in Nearly-PCA Time »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard · Jerry Li · Kevin Tian -
2020 Poster: List-Decodable Mean Estimation via Iterative Multi-Filtering »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard -
2020 Poster: Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals »
Ilias Diakonikolas · Daniel Kane · Nikos Zarifis -
2020 Poster: The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise »
Ilias Diakonikolas · Daniel M. Kane · Pasin Manurangsi -
2020 Poster: Outlier Robust Mean Estimation with Subgaussian Rates via Stability »
Ilias Diakonikolas · Daniel M. Kane · Ankit Pensia -
2019 Poster: Private Testing of Distributions via Sample Permutations »
Maryam Aliakbarpour · Ilias Diakonikolas · Daniel Kane · Ronitt Rubinfeld -
2019 Poster: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Poster: Distribution-Independent PAC Learning of Halfspaces with Massart Noise »
Ilias Diakonikolas · Themis Gouleakis · Christos Tzamos -
2019 Poster: Equipping Experts/Bandits with Long-term Memory »
Kai Zheng · Haipeng Luo · Ilias Diakonikolas · Liwei Wang -
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Oral: Distribution-Independent PAC Learning of Halfspaces with Massart Noise »
Ilias Diakonikolas · Themis Gouleakis · Christos Tzamos -
2019 Poster: Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Eric Price · Alistair Stewart -
2019 Poster: A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families »
Brian Axelrod · Ilias Diakonikolas · Alistair Stewart · Anastasios Sidiropoulos · Gregory Valiant