1 citations · 5 across the 13 of their papers we have counts for
7 papers · 1 filter
Robust Mixture Learning when Outliers Overwhelm Small Groups
Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel +5
We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fractio…
Testably Learning Polynomial Threshold Functions
Lucas Slot, Stefan Tiegel, Manuel Wiedmer
Rubinfeld & Vasilyan recently introduced the framework of testable learning as an extension of the classical agnostic model. It relaxes distributional assumptions which are difficu…
Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
Rares-Darius Buhai, Jingqiu Ding, Stefan Tiegel
We study computational-statistical gaps for improper learning in sparse linear regression. More specifically, given samples from a -sparse linear model in dimension , we…
Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems
Stefan Tiegel
We show hardness of improperly learning halfspaces in the agnostic model, both in the distribution-independent as well as the distribution-specific setting, based on the assumption…
Fast algorithm for overcomplete order-3 tensor decomposition
Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu +2
We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to . Our algorithm only involves…
Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise
Rajai Nasser, Stefan Tiegel
We give tight statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. In particular, suppose that all labels are corrupted with probability…
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser +3
We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an obl…