Polynomial-time algorithm for list-decodable linear regression with batches.
problem Efficiently decoding linear regression with a fraction of adversarial data.
method Polynomial time algorithm using batches of i.i.d. samples.
result Returns a list of size O(1/α^2) with one item close to true parameter.
New method for estimating sparse means in noisy data.
problem Estimating the mean of a sparse distribution in the presence of outliers.
method Difference-of-Pairs Filtering technique for list-decodable sparse mean estimation.
result First sample and computationally efficient algorithm for list-decodable sparse mean estimation.
Paper tackles high-accuracy list-decodable learning for mean estimation.
problem Estimate the mean of a distribution with a small fraction coming from a nice distribution.
method Developed a novel proof of identifiability and a new algorithmic approach.
result Achieved high-accuracy guarantees for list-decodable mean estimation.
New algorithm for robust mean estimation in high dimensions with nearly-PCA time complexity.
problem Robust mean estimation in high-dimensional data with a minority of contaminated data.
method List-decodable mean estimation algorithm using a novel soft downweighting method, SIFT, and a Ky Fan matrix multiplicative weights procedure.
result Optimal sample complexity and error rate for list-decodable mean estimation with runtime nearly matching PCA.
Statistical Query lower bound shows difficulty in list-decodable linear regression.
problem List-decodable linear regression with adversarial corruption.
method Statistical Query (SQ) lower bound analysis.
result Lower bound of d p o l y ( 1 / α ) d^{\mathrm{poly}(1/α)} d poly ( 1/ α ) for list-decodable linear regression. Polynomial-time algorithm for estimating covariance in corrupted Gaussian data.
problem Estimating covariance in data with up to 1-α fraction of adversarial corruptions.
method Uses low-degree sum-of-squares certificates for anti-concentration and hypercontractivity.
result Outputs a list of candidate parameters with high probability containing a nearly correct covariance.
New algorithm recovers mixture means even with many outliers.
problem Estimating mixture means when outliers overwhelm small groups.
method Proposes an algorithm for robust mixture learning with minimal list-size overhead.
result Order-optimal error guarantees for each mixture mean.
Algorithm estimates covariance from noisy data efficiently.
problem Estimating covariance from a noisy set of points.
method Spectral techniques for list-decodable covariance estimation.
result Efficient algorithm with poly(1/α) sample and time complexity.
Boosting improves accuracy with fewer calls to weak learners for certain concept classes.
problem Improving accuracy of learning algorithms with limited weak learner calls.
method Combines boosting and list-decodable codes to achieve better performance for specific concept classes.
result A new boosting algorithm that achieves strong learning with fewer calls to weak learners and additional samples.
We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than 1 / 2 1/2 1/2 fraction of examples. For any α < 1 α< 1 α < 1 , our algorithm takes as input a sample { ( x i , y i ) } i ≤ n \{(x_i,y_i)\}_{i \leq n} {( x i , y i ) } i ≤ n of n n n linear equations where α n αn α n of the equations satisfy $y_i = \l…
A simple model explains phase transition in large language models.
problem Understanding the emergence of abilities in large language models.
method Modeling LLM as a sequence-to-sequence random function and using a list decoder.
result A critical threshold exists where the expected number of erroneous sequences grows exponentially.
New method estimates mean from noisy data with few outliers.
problem Estimate mean from noisy data with few outliers.
method Iterative multi-filtering approach.
result Achieves near-optimal error with practical efficiency.
New method certifies anti-concentration for various non-Gaussian distributions.
problem Efficiently certifying anti-concentration for non-Gaussian distributions.
method Sum-of-Squares relaxation of integer program for anti-concentration.
result Quasi-polynomial time certificates for non-Gaussian distributions.
New algorithm clusters data with almost-linear time, robust to corruption.
problem Clustering mixtures of distributions with adversarial corruption.
method List-decodable mean estimation, robust mean estimation, iterative multi-filtering.
result First almost-linear time algorithms for clustering mixtures of k well-behaved distributions.
New algorithm for batch list-decodable linear regression with stronger guarantees.
problem Efficiently list-decoding linear regression with a fraction of corrupted batches.
method Uses higher-order moments and Sum-of-Squares (SoS) certification to achieve better guarantees.
result Achieves substantially smaller minimum batch size and final error, with optimal list size.
Paper tackles MLR prediction error without assuming realizable models.
problem Prediction error in mixture of linear regressions without realizable assumptions.
method Developed algorithms for list-decoding MLR predictions and minimized empirical risk.
result Alternating minimization algorithm finds best fit lines in non-realizable settings.
In list-decodable subspace recovery, the input is a collection of n n n points α n αn α n (for some α ≪ 1 / 2 α\ll 1/2 α ≪ 1/2 ) of which are drawn i.i.d. from a distribution D \mathcal{D} D with a isotropic rank r r r covariance Π ∗ Π_* Π ∗ (the \emph{inliers}) and the rest are arbitrary, potential adversarial outliers. The goal is to recover a $O(1/α)…
Study on list learning with noisy data, showing limits and some learnable cases.
problem Learning from noisy data in a list learning context.
method Inspired by coding theory, extends list learning model to study sparse conjunctions and parities/majors.
result Sparse conjunctions can be efficiently list learned under certain conditions, but parities and majors cannot be efficiently learned.
Proves subgaussian distributions are SoS-certifiably subgaussian, enabling efficient algorithms for various statistical tasks.
problem Efficiently learning from subgaussian distributions in high dimensions.
method Universal constant C C C and polynomial sum of squares (SoS) approach. result Proves subgaussian distributions are SoS-certifiably subgaussian.
Study shows private learning of mixtures of Gaussians is possible with polynomial samples.
problem Estimating mixtures of Gaussians under differential privacy constraints.
method Developed a new framework for privately learning mixtures of Gaussians without structural assumptions.
result Polynomial number of samples (poly(k,d,1/α,1/ε,log(1/δ))) sufficient for estimation up to total variation distance α with (ε, δ)-DP.
New algorithm reduces contamination in supervised learning.
problem Learning with contamination in supervised learning.
method Iterative polynomial filtering.
result Efficient learning of functions with contamination.
This paper bridges outlier-robust estimation in robotics and computer vision with robust statistics.
problem Outlier-robust estimation for geometric perception in robotics and computer vision.
method Adapting and extending robust linear regression and list-decodable regression to non-convex domains and vector-valued measurements.
result Performance guarantees for modern estimation algorithms in the presence of outliers.
Smoothed analysis shows that many classes become learnable from positive-only samples.
problem Learning from positive-only samples is challenging due to negative results in worst-case settings.
method Smoothed analysis of positive-only learning, assuming samples from a reference distribution smooth with respect to the true distribution.
result All VC classes become learnable in the smoothed model with O ( V C / ε 2 ) O(VC/ε^2) O ( V C / ε 2 ) positive samples for ε ε ε classification error. Efficiently estimates common mean in high-dimensional data with noisy subset.
problem Estimating common mean in high-dimensional data with noisy subset.
method Iterative refinement strategy with rejection sampling and dimension-reduction.
result Achieves near-optimal error of f ( α , N ) + D / ( α N ) f(α,N) + \sqrt{D/(αN)} f ( α , N ) + D / ( α N ) .