惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

阮一峰的网络日志
阮一峰的网络日志
博客园 - 司徒正美
D
DataBreaches.Net
宝玉的分享
宝玉的分享
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
博客园 - 【当耐特】
人人都是产品经理
人人都是产品经理
博客园 - Franky
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
IT之家
IT之家
博客园 - 三生石上(FineUI控件)
J
Java Code Geeks
腾讯CDC
博客园_首页
The Cloudflare Blog
S
SegmentFault 最新的问题
C
Check Point Blog
美团技术团队
爱范儿
爱范儿
大猫的无限游戏
大猫的无限游戏
Hugging Face - Blog
Hugging Face - Blog
T
The Blog of Author Tim Ferriss
A
About on SuperTechFans
Blog — PlanetScale
Blog — PlanetScale

math.ST updates on arXiv.org

What is Learnable in Valiant's Theory of the Learnable? Learning Perturbations to Extrapolate Your LLM Byzantine-Robust Distributed Sparse Learning Revisited The Sample Complexity of Multiple Change Point Identification under Bandit Feedback A proximal gradient algorithm for composite log-concave sampling Model-based Bootstrap of Controlled Markov Chains Approximation of Maximally Monotone Operators : A Graph Convergence Perspective Posterior Contraction Rates for Sparse Kolmogorov-Arnold Networks in Anisotropic Besov Spaces MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound A Spectral Framework for Closed-Form Relative Density Estimation Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability Higher-Order Equilibrium Tracking for EM-Compressible Online Estimation Scaling Limits of Long-Context Transformers A Note on Non-Negative $L_1$-Approximating Polynomials Susceptibilities and Patterning: A Primer on Linear Response in Bayesian Learning Linear Response Estimators for Singular Statistical Models Statistical inference with belief functions: A survey Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity Adaptive auditing of AI systems with anytime-valid guarantees Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions Risk-Controlled Post-Processing of Decision Policies Covariate Balancing and Riesz Regression Should Be Guided by the Neyman Orthogonal Score in Debiased Machine Learning A Unified Pair-GRPO Family: From Implicit to Explicit Preference Constraints for Stable and General RL Alignment Time-Inhomogeneous Preconditioned Langevin Dynamics A Fine-Grained Understanding of Uniform Convergence for Halfspaces CITE: Anytime-Valid Statistical Inference in LLM Self-Consistency Ratio-based Loss Functions Optimal Confidence Band for Kernel Gradient Flow Estimator A renormalization-group inspired lattice-based framework for piecewise generalized linear models
List-Decodable Robust Mean Estimation and Learning Mixtur...
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart · 2017-11-20 · via math.ST updates on arXiv.org

We study the problem of list-decodable Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. We develop a set of techniques that yield new efficient algorithms with significantly improved guarantees for these problems. {\bf List-Decodable Mean Estimation.} Fix any $d \in \mathbb{Z}_+$ and $0< α<1/2$. We design an algorithm with runtime $O (\mathrm{poly}(n/α)^{d})$ that outputs a list of $O(1/α)$ many candidate vectors such that with high probability one of the candidates is within $\ell_2$-distance $O(α^{-1/(2d)})$ from the true mean. The only previous algorithm for this problem achieved error $\tilde O(α^{-1/2})$ under second moment conditions. For $d = O(1/ε)$, our algorithm runs in polynomial time and achieves error $O(α^ε)$. We also give a Statistical Query lower bound suggesting that the complexity of our algorithm is qualitatively close to best possible. {\bf Learning Mixtures of Spherical Gaussians.} We give a learning algorithm for mixtures of spherical Gaussians that succeeds under significantly weaker separation assumptions compared to prior work. For the prototypical case of a uniform mixture of $k$ identity covariance Gaussians we obtain: For any $ε>0$, if the pairwise separation between the means is at least $Ω(k^ε+\sqrt{\log(1/δ)})$, our algorithm learns the unknown parameters within accuracy $δ$ with sample complexity and running time $\mathrm{poly} (n, 1/δ, (k/ε)^{1/ε})$. The previously best known polynomial time algorithm required separation at least $k^{1/4} \mathrm{polylog}(k/δ)$. Our main technical contribution is a new technique, using degree-$d$ multivariate polynomials, to remove outliers from high-dimensional datasets where the majority of the points are corrupted.