Timezone: »
Poster
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi
Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #233
We study the problem of {\em properly} learning large margin halfspaces in the agnostic PAC model.
In more detail, we study the complexity of properly learning $d$-dimensional halfspaces
on the unit ball within misclassification error $\alpha \cdot \opt_{\gamma} + \eps$, where $\opt_{\gamma}$
is the optimal $\gamma$-margin error rate and $\alpha \geq 1$ is the approximation ratio.
We give learning algorithms and computational hardness results
for this problem, for all values of the approximation ratio $\alpha \geq 1$,
that are nearly-matching for a range of parameters.
Specifically, for the natural setting that $\alpha$ is any constant bigger
than one, we provide an essentially tight complexity characterization.
On the positive side, we give an $\alpha = 1.01$-approximate proper learner
that uses $O(1/(\eps^2\gamma^2))$ samples (which is optimal) and runs in time
$\poly(d/\eps) \cdot 2^{\tilde{O}(1/\gamma^2)}$. On the negative side,
we show that {\em any} constant factor approximate proper learner has runtime
$\poly(d/\eps) \cdot 2^{(1/\gamma)^{2-o(1)}}$,
assuming the Exponential Time Hypothesis.
Author Information
Ilias Diakonikolas (UW Madison)
Daniel Kane (UCSD)
Pasin Manurangsi (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Thu. Dec 12th 12:45 -- 12:50 AM Room West Ballroom C
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 -
2022 Poster: SQ Lower Bounds for Learning Single Neurons with Massart Noise »
Ilias Diakonikolas · Daniel Kane · Lisheng Ren · Yuxin Sun -
2022 Poster: Nearly-Tight Bounds for Testing Histogram Distributions »
ClĂ©ment L Canonne · Ilias Diakonikolas · Daniel Kane · Sihan Liu -
2022 Poster: Private Isotonic Regression »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Poster: List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Ankit Pensia · Thanasis Pittas -
2022 Poster: Anonymized Histograms in Intermediate Privacy Models »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Poster: Cryptographic Hardness of Learning Halfspaces with Massart Noise »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi · Lisheng Ren -
2022 Poster: Outlier-Robust Sparse Estimation via Non-Convex Optimization »
Yu Cheng · Ilias Diakonikolas · Rong Ge · Shivam Gupta · Daniel Kane · Mahdi Soltanolkotabi -
2022 Poster: Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions »
Ilias Diakonikolas · Daniel Kane · Jasper Lee · Ankit Pensia -
2021 Poster: ReLU Regression with Massart Noise »
Ilias Diakonikolas · Jong Ho Park · Christos Tzamos -
2021 Poster: User-Level Differentially Private Learning via Correlated Sampling »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2021 Poster: Deep Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang -
2021 Poster: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2021 Poster: Contextual Recommendations and Low-Regret Cutting-Plane Algorithms »
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider -
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: Non-Convex SGD Learns Halfspaces with Adversarial Label Noise »
Ilias Diakonikolas · Vasilis Kontonis · Christos Tzamos · Nikos Zarifis -
2020 Poster: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
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 -
2020 Oral: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2020 Poster: The Power of Comparisons for Actively Learning Linear Classifiers »
Max Hopkins · Daniel Kane · Shachar Lovett -
2019 Poster: Private Testing of Distributions via Sample Permutations »
Maryam Aliakbarpour · Ilias Diakonikolas · Daniel Kane · Ronitt Rubinfeld -
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 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 -
2018 Poster: Robust Learning of Fixed-Structure Bayesian Networks »
Yu Cheng · Ilias Diakonikolas · Daniel Kane · Alistair Stewart