Cover Image

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Hongjie, Sridharan, Deepak Narayanan, Steurer, David
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On efficient robust regression with subquadratic samples
by: Adil, Deeksha, et al.
Published: (2026)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
by: Chen, Hongjie, et al.
Published: (2025)

Robust Sparse Mean Estimation via Sum of Squares
by: Diakonikolas, Ilias, et al.
Published: (2022)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Robust Mixture Learning when Outliers Overwhelm Small Groups
by: Dmitriev, Daniil, et al.
Published: (2024)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

High-Accuracy List-Decodable Mean Estimation
by: Chen, Ziyun, et al.
Published: (2025)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

New Bounds for Kernel Sums via Fast Spherical Embeddings
by: Wagner, Tal
Published: (2026)

Simple KNN-Based Outlier Detection Achieves Robust Clustering
by: Jiang, Tianle, et al.
Published: (2026)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
by: Maity, Binita, et al.
Published: (2024)

Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
by: Gahlawat, Harmender, et al.
Published: (2025)

Improved algorithms for learning quantum Hamiltonians, via flat polynomials
by: Narayanan, Shyam
Published: (2024)

Fast, robust approximate message passing
by: Ivkov, Misha, et al.
Published: (2024)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)

List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
by: Diakonikolas, Ilias, et al.
Published: (2022)

On the Structure of Replicable Hypothesis Testers
by: Aamand, Anders, et al.
Published: (2025)

Learning Mixtures of Spherical Gaussians via Fourier Analysis
by: Chakraborty, Somnath, et al.
Published: (2020)

Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination
by: Diakonikolas, Ilias, et al.
Published: (2026)

Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
by: Diakonikolas, Ilias, et al.
Published: (2025)

Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio
by: Yoshinaga, Toru, et al.
Published: (2026)

Entangled Mean Estimation in High-Dimensions
by: Diakonikolas, Ilias, et al.
Published: (2025)

Learning-Augmented Moment Estimation on Time-Decay Models
by: Nagawanshi, Soham, et al.
Published: (2026)

PLAN: Variance-Aware Private Mean Estimation
by: Aumüller, Martin, et al.
Published: (2023)

MNL-Bandit with Knapsacks: a near-optimal algorithm
by: Aznag, Abdellah, et al.
Published: (2021)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

Distributed Least Squares in Small Space via Sketching and Bias Reduction
by: Garg, Sachin, et al.
Published: (2024)

Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
by: Kalavasis, Alkis, et al.
Published: (2026)

High-Dimensional Gaussian Mean Estimation under Realizable Contamination
by: Diakonikolas, Ilias, et al.
Published: (2026)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
by: Fang, Ziyi, et al.
Published: (2025)

A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
by: Pensia, Ankit
Published: (2024)

Log-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation
by: Hyun, Jake
Published: (2024)

John Ellipsoids via Lazy Updates
by: Woodruff, David P., et al.
Published: (2025)

On Purely Private Covariance Estimation
by: d'Orsi, Tommaso, et al.
Published: (2025)

The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks
by: Abbe, Emmanuel, et al.
Published: (2022)

Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
by: Song, Shihong, et al.
Published: (2024)

Learning-Augmented Frequency Estimation in Sliding Windows
by: Shahout, Rana, et al.
Published: (2024)