High-Accuracy List-Decodable Mean Estimation

Дата публикации: 27-08-2026 00:00:00

In list-decodable learning, we are given a set of data points such that an α-fraction of these points come from a “nice” distribution D, for some small α ≪ 1, and the goal is to output a short list of candidate solutions, such that at least one element of this list recovers some non-trivial information about D. By now, there is a large body of work on this topic; however, while many algorithms can achieve optimal list size in terms of α, all known algorithms must incur error which decays, in some cases quite poorly, with 1 / α. In this paper, we ask if this is inherent: is it possible to trade off list size with accuracy in list-decodable learning? More formally, given ε > 0, can we output a slightly larger list in terms of α and ε, but so that one element of this list has error at most ε with the ground truth? We call this problem high-accuracy list-decodable learning. Our main result is that non-trivial high-accuracy guarantees, both information-theoretically and algorithmically,...

Схожие новости

#	Наименование новости	Тональность	Информативность	Дата публикации
1	Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models	0	11.59	27-08-2026
2	Error Analysis for Deep ReLU Feedforward Density-Ratio Estimation with Bregman Divergence	0	8.78	17-08-2026
3	Nonparametric Estimation of a Factorizable Density using Diffusion Models	0	8.59	17-08-2026
4	The Distribution of Ridgeless Least Squares Interpolators	0	5.78	17-08-2026
5	Dimensional Reduction for Sampled Priors and Application to Photometric Redshift Distributions	0	5.3	04-08-2026
6	Robust Representation Learning for Privacy-Preserving Machine Learning: A Multi-Objective Autoencoder Approach	0	7	27-08-2025
7	CPU- and GPU-Based Distributed Sampling in Dirichlet Process Mixtures for Large-Scale Analysis	0	8.44	31-05-2026
8	Predicting galaxy bias using machine learning	0	8.79	18-08-2026
9	Machine Learning Models for Predicting Long-Term Visual Acuity in Highly Myopic Eyes	0	9.79	01-12-2023

Классификация: Наука. Схожих патентов: 0. Схожих новостей: 9. Тональность: 0. Информативность: 9.77. Источник: escholarship.org.