Timezone: »
Poster
Robust Learning of Fixed-Structure Bayesian Networks
Yu Cheng · Ilias Diakonikolas · Daniel Kane · Alistair Stewart
We investigate the problem of learning Bayesian networks in a robust model where an $\epsilon$-fraction of the samples are adversarially corrupted. In this work, we study the fully observable discrete case where the structure of the network is given. Even in this basic setting, previous learning algorithms either run in exponential time or lose dimension-dependent factors in their error guarantees. We provide the first computationally efficient robust learning algorithm for this problem with dimension-independent error guarantees. Our algorithm has near-optimal sample complexity, runs in polynomial time, and achieves error that scales nearly-linearly with the fraction of adversarially corrupted samples. Finally, we show on both synthetic and semi-synthetic data that our algorithm performs well in practice.
Author Information
Yu Cheng (Duke University)
Ilias Diakonikolas (University of Southern California)
Daniel Kane (UCSD)
Alistair Stewart (University of Southern California)
More from the Same Authors
-
2021 Spotlight: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2023 Poster: SQ Lower Bounds for Learning Mixtures of Linear Classifiers »
Ilias Diakonikolas · Daniel Kane · Yuxin Sun -
2023 Poster: Robust Matrix Sensing in the Semi-Random Model »
Xing Gao · Yu Cheng -
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 Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas -
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: SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions »
Ilias Diakonikolas · Daniel Kane · Lisheng Ren · Yuxin Sun -
2023 Poster: A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm »
Ilias Diakonikolas · Daniel Kane · Jasper Lee · Ankit Pensia · Thanasis Pittas -
2023 Poster: First Order Stochastic Optimization with Oblivious Noise »
Ilias Diakonikolas · Sushrut Karmalkar · Jong Ho Park · Christos Tzamos -
2023 Poster: Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing »
Shuyao Li · Yu Cheng · Ilias Diakonikolas · Jelena Diakonikolas · Rong Ge · Stephen Wright -
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: List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Ankit Pensia · Thanasis Pittas -
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: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
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 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: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
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: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2018 Poster: Testing for Families of Distributions via the Fourier Transform »
Alistair Stewart · Ilias Diakonikolas · Clément L Canonne -
2018 Spotlight: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2014 Poster: Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms »
Siu On Chan · Ilias Diakonikolas · Rocco A Servedio · Xiaorui Sun