1 citations · 5 across the 13 of their papers we have counts for
15 papers
Algorithms with Polynomially-Improved Approximation Factors for the Norm, and Applications
Samuel B. Hopkins, Stefan Tiegel
The norm of a matrix is defined as . We give…
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…
Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
Hongjie Chen, Jingqiu Ding, Yiding Hua +1
We study the problem of robustly estimating the edge density of Erdős-Rényi random graphs when an adversary can arbitrarily add or remove edges incident to an …
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…
Improved Hardness Results for Learning Intersections of Halfspaces
Stefan Tiegel
We show strong (and surprisingly simple) lower bounds for weakly learning intersections of halfspaces in the improper setting. Strikingly little is known about this problem. For in…
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…
Robust Mean Estimation Without Moments for Symmetric Distributions
Gleb Novikov, David Steurer, Stefan Tiegel
We study the problem of robustly estimating the mean or location parameter without moment assumptions. We show that for a large class of symmetric distributions, the same error as…
Private estimation algorithms for stochastic block models and mixture models
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi +4
We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best know…
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…
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…
A Framework for Searching in Graphs in the Presence of Errors
Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański +1
We consider the problem of searching for an unknown target vertex in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex and the response either a…