Image de couverture de livre

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chen, Hongjie, Ding, Jingqiu, Hua, Yiding, Tiegel, Stefan
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Machine Learning
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
par: Chen, Hongjie, et autres
Publié: (2024)

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
par: Chen, Hongjie, et autres
Publié: (2024)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
par: Diakonikolas, Ilias, et autres
Publié: (2024)

Private graphon estimation via sum-of-squares
par: Chen, Hongjie, et autres
Publié: (2024)

Rate-optimal community detection near the KS threshold via node-robust algorithms
par: Ding, Jingqiu, et autres
Publié: (2025)

Testably Learning Polynomial Threshold Functions
par: Slot, Lucas, et autres
Publié: (2024)

Sample-Optimal Private Regression in Polynomial Time
par: Anderson, Prashanti, et autres
Publié: (2025)

A Framework for Searching in Graphs in the Presence of Errors
par: Dereniowski, Dariusz, et autres
Publié: (2018)

Robust Mixture Learning when Outliers Overwhelm Small Groups
par: Dmitriev, Daniil, et autres
Publié: (2024)

SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
par: Diakonikolas, Ilias, et autres
Publié: (2024)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
par: Chen, Sitan, et autres
Publié: (2026)

Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination
par: Diakonikolas, Ilias, et autres
Publié: (2024)

Towards Optimal Robustness in Learning-Augmented Paging
par: Chen, Peng, et autres
Publié: (2026)

Robust Sparse Regression with Non-Isotropic Designs
par: Liu, Chih-Hung, et autres
Publié: (2024)

Robust Learning with Optimal Error
par: Blanc, Guy
Publié: (2026)

Robust Dynamic Staffing with Predictions
par: Feng, Yiding, et autres
Publié: (2025)

Robust Sparse Mean Estimation via Sum of Squares
par: Diakonikolas, Ilias, et autres
Publié: (2022)

Improved Approximations for Hard Graph Problems using Predictions
par: Aamand, Anders, et autres
Publié: (2025)

On efficient robust regression with subquadratic samples
par: Adil, Deeksha, et autres
Publié: (2026)

A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
par: Pensia, Ankit
Publié: (2024)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
par: Li, Yi, et autres
Publié: (2024)

Dynamic Similarity Graph Construction with Kernel Density Estimation
par: Laenen, Steinar, et autres
Publié: (2025)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
par: Yang, Yichun, et autres
Publié: (2024)

Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians
par: Novikov, Gleb
Publié: (2025)

Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond
par: Takakura, Shokichi, et autres
Publié: (2025)

Value-Compressed Sparse Column (VCSC): Sparse Matrix Storage for Redundant Data
par: Ruiter, Skyler, et autres
Publié: (2023)

Optimal Approximate Matrix Multiplication over Sliding Windows
par: Yao, Ziqi, et autres
Publié: (2025)

Optimal Embedding Dimension for Sparse Subspace Embeddings
par: Chenakkod, Shabarish, et autres
Publié: (2023)

Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
par: Pittas, Thanasis, et autres
Publié: (2024)

Non-Stationary Online Resource Allocation: Learning from a Single Sample
par: Feng, Yiding, et autres
Publié: (2026)

Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
par: Chen, Yixin, et autres
Publié: (2021)

Rényi-infinity constrained sampling with $d^3$ membership queries
par: Kook, Yunbum, et autres
Publié: (2024)

Almost-Optimal Local-Search Methods for Sparse Tensor PCA
par: Lovig, Max, et autres
Publié: (2025)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
par: Silwal, Sandeep, et autres
Publié: (2025)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
par: Joshi, Nirmit, et autres
Publié: (2024)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
par: Karpov, Nikolai, et autres
Publié: (2025)

High-Accuracy List-Decodable Mean Estimation
par: Chen, Ziyun, et autres
Publié: (2025)

A Simple Sparse Matrix Vector Multiplication Approach to Padded Convolution
par: Chaudhry, Zan
Publié: (2024)

Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes
par: Portella, Victor S., et autres
Publié: (2024)

Near-Optimal Algorithms for Omniprediction
par: Okoroafor, Princewill, et autres
Publié: (2025)