1 citations · 1 across the 3 of their papers we have counts for
3 papers
cs.LG2022
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…
cs.LG2021★ 1 cited
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…
cs.DS2021
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
David Steurer, Stefan Tiegel
We develop a general framework to significantly reduce the degree of sum-of-squares proofs by introducing new variables. To illustrate the power of this framework, we use it to spe…