Research map / Learning theory and algorithms / Sample complexity

Simple and Optimal Sublinear Algorithms for Mean Estimation

NeurIPS 2025 · Learning theory and algorithms › Sample complexity · approach: Distributed estimation under communication limits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives sublinear (1+ε)-approximate Euclidean mean algorithms with optimal O(ε^-1 log δ^-1) sample complexity via coordinate-wise median-of-means, geometric median-of-means with a fast gradient descent, and an order-statistics MinSumSelect, plus experiments on MNIST, Fashion-MNIST and CoverType.

Problem

Estimating the Euclidean mean of a point set (minimizing sum of squared distances) with a multiplicative (1+ε) guarantee and high success probability 1-δ using few uniform samples and fast running time.

Approach

Split O(ε^-1 log δ^-1) uniform samples into O(log δ^-1) sample means of size O(ε^-1) and aggregate them via coordinate-wise median, geometric median (with a simple projected-median gradient descent), or a recursive truncated-sum order statistic; all achieve optimal sample complexity and near-linear running time.

Key results

• Proves that O(ε^-1 log δ^-1) uniform samples suffice for a (1+ε)-approximate mean with probability 1-δ, with a matching Ω(ε^-1 log δ^-1) lower bound.
• Coordinate-wise median-of-means and FastGD (geometric median-of-means) run in O(ε^-1 d log δ^-1) time, breaking the O(log^2 δ^-1) barrier of prior algorithms.
• Experimentally, the empirical mean and CoordWiseMedian are among the most accurate, while MinSumSelect and CoordWiseMedian are the fastest; FastGD shows a slight accuracy edge over CoordWiseMedian in most cases.

Measured effects reported in the paper

Surprising findings

• The empirical mean, despite weak worst-case guarantees, consistently ranks among the most accurate estimators on the real datasets.
• Neither the coordinate-wise median nor the geometric median dominates the other; each can be strictly better on different instances.

Limitations

• Worst-case constructions show the empirical mean needs Ω(ε^-1 δ^-1) samples for high-probability guarantees.
• The constants are not optimized and the MinSumSelect recursion depth trades sample complexity against running time.
• Experiments are limited to CPU runs with memory limits capping the synthetic sample size at 5·10^5.

Experimental setup

Datasets: MNIST Fashion-MNIST CoverType synthetic Gaussian

Benchmarks: MNIST Fashion-MNIST CoverType synthetic Gaussian

Metrics: accuracy (ALG/OPT cost ratio) runtime

Baselines: empirical mean CSS WY CoordWiseMedian

Builds on: median-of-means Chernoff bound sensitivity sampling coresets

Closest papers by meaning

• Private Geometric Median in Nearly-Linear Time (NeurIPS 2025 · similarity 0.87)
• Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+\alpha$ Moments (NeurIPS 2023 · similarity 0.86)
• A Subquadratic Time Algorithm for Robust Sparse Mean Estimation (ICML 2024 · similarity 0.84)
• Statistical-Computational Trade-offs for Density Estimation (NeurIPS 2024 · similarity 0.83)
• Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.83)
• Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means (ICML 2025 · similarity 0.82)