Sparse Mean Estimation in Adversarial Settings via Incremental Learning

• URL: http://arxiv.org/abs/2305.15276v3
• Date: Mon, 25 Aug 2025 02:33:59 GMT
• Title: Sparse Mean Estimation in Adversarial Settings via Incremental Learning
• Authors: Jianhao Ma, Rui Ray Chen, Yinghui He, Salar Fattahi, Wei Hu,
• Abstract summary: We propose a scalable method to learn sparse mean estimation in the presence of heavy-tailed distributions and adversarial corruptions.<n>Our method achieves the optimal statistical rate, matching the information-theoretic lower bound.<n>More broadly, our work is the first to reveal the incremental learning phenomenon of the subient method in the presence of heavy-tailed distributions and adversarial corruption.
• Score: 20.522038784234947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of sparse mean estimation under adversarial corruptions, where the goal is to estimate the $k$-sparse mean of a heavy-tailed distribution from samples contaminated by adversarial noise. Existing methods face two key limitations: they require prior knowledge of the sparsity level $k$ and scale poorly to high-dimensional settings. We propose a simple and scalable estimator that addresses both challenges. Specifically, it learns the $k$-sparse mean without knowing $k$ in advance and operates in near-linear time and memory with respect to the ambient dimension. Under a moderate signal-to-noise ratio, our method achieves the optimal statistical rate, matching the information-theoretic lower bound. Extensive simulations corroborate our theoretical guarantees. At the heart of our approach is an incremental learning phenomenon: we show that a basic subgradient method applied to a nonconvex two-layer formulation with an $\ell_1$-loss can incrementally learn the $k$ nonzero components of the true mean while suppressing the rest. More broadly, our work is the first to reveal the incremental learning phenomenon of the subgradient method in the presence of heavy-tailed distributions and adversarial corruption.

Related papers

• Causality-aligned Prompt Learning via Diffusion-based Counterfactual Generation [45.395353088233556]
  We introduce a theoretically grounded $textbfDi$ffusion-based $textbfC$ounterf$textbfa$ctual $textbfp$rompt learning framework.<n>Our method performs excellently across tasks such as image classification, image-text retrieval, and visual question answering, with particularly strong advantages in unseen categories.
  arXiv  Detail & Related papers  (2025-07-26T09:27:52Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Adversarial learning for nonparametric regression: Minimax rate and adaptive estimation [3.244945627960733]
  We establish the minimax rate of convergence under adversarial $L_risks with $1 leq leq infty$ and propose a piecewise local estimator that achieves the minimax optimality.<n>We construct a data-driven adaptive estimator that is shown to achieve, within a logarithmic factor, the optimal rate across a broad scale of non and adversarial classes.
  arXiv  Detail & Related papers  (2025-06-02T02:38:47Z)
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination [13.980910832909906]
  We show that any function class that can be approximated by low-degrees can be efficiently learned under bounded contamination.<n>We obtain the first efficient algorithms for tolerant testable learning of functions of halfspaces with respect to any fixed log-concave distribution.
  arXiv  Detail & Related papers  (2025-05-26T16:17:48Z)
• Robust Representation Consistency Model via Contrastive Denoising [83.47584074390842]
  randomized smoothing provides theoretical guarantees for certifying robustness against adversarial perturbations.<n> diffusion models have been successfully employed for randomized smoothing to purify noise-perturbed samples.<n>We reformulate the generative modeling task along the diffusion trajectories in pixel space as a discriminative task in the latent space.
  arXiv  Detail & Related papers  (2025-01-22T18:52:06Z)
• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  We study the task of high-dimensional entangled mean estimation in the subset-of-signals model. We show that the optimal error (up to polylogarithmic factors) is $f(alpha,N) + sqrtD/(alpha N)$, where the term $f(alpha,N)$ is the error of the one-dimensional problem and the second term is the sub-Gaussian error rate.
  arXiv  Detail & Related papers  (2025-01-09T18:31:35Z)
• Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares [4.335413713700667]
  We give a new analysis of the canonical sum-of-squares program introduced in citekothari2018robust. We show that this program efficiently achieves optimal error rate for all $varepsilon in[0,frac12)$.
  arXiv  Detail & Related papers  (2024-11-21T16:57:05Z)
• Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data [3.1138411427556445]
  In the measurement-constrained problems, despite the availability of large datasets, we may be only affordable to observe the labels on a small portion of the large dataset. This poses a critical question that which data points are most beneficial to label given a budget constraint. In this paper, we focus on the estimation of the optimal individualized threshold in a measurement-constrained M-estimation framework.
  arXiv  Detail & Related papers  (2024-11-21T00:21:17Z)
• Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
  We integrate the $varepsilon$-greedy bandit algorithm for decision-making with a hard thresholding algorithm for estimating sparse bandit parameters.<n>Under a margin condition, our method achieves either $O(T1/2)$ regret or classical $O(T1/2)$-consistent inference.
  arXiv  Detail & Related papers  (2024-11-10T01:47:11Z)
• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
  We show that an efficient learning algorithm for sparse linear regression can be used to solve sparse PCA problems with a negative spike. We complement our reduction with low-degree and statistical query lower bounds for the sparse problems from which we reduce.
  arXiv  Detail & Related papers  (2024-02-21T19:55:01Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Robust Nonparametric Regression under Poisoning Attack [13.470899588917716]
  An adversarial attacker can modify the values of up to $q$ samples from a training dataset of size $N$. Our initial solution is an M-estimator based on Huber loss minimization. The final estimate is nearly minimax optimal for arbitrary $q$, up to a $ln N$ factor.
  arXiv  Detail & Related papers  (2023-05-26T09:33:17Z)
• Do PAC-Learners Learn the Marginal Distribution? [19.54058590042626]
  The Fundamental Theorem of PAC Learning asserts that learnability of a concept class $H$ is equivalent to the $textituniform convergence$ of empirical error in $H$.<n>This work revisits the connection between PAC learning, uniform convergence, and density estimation beyond the distribution-free setting.
  arXiv  Detail & Related papers  (2023-02-13T11:42:58Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• List-Decodable Sparse Mean Estimation [7.594050968868919]
  A surge of recent research interest has been focusing on the list-decodable setting where $alpha in (0, frac12]$, and the goal is to output a finite number of estimates among which at least one approximates the target mean. In this paper, we consider that the underlying target is the mean distribution $k$ and the first contribution is the first sample $Obig(mathrmpoly(k, log dbig)$, i.e. poly-logarithmic in the dimension dimension.
  arXiv  Detail & Related papers  (2022-05-28T05:13:45Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  Modern machine learning models often employ a huge number of parameters and are typically optimized to have zero training loss. We examine how these benign overfitting phenomena occur in a two-layer neural network setting. We show that it is possible for the two-layer ReLU network interpolator to achieve a near minimax-optimal learning rate.
  arXiv  Detail & Related papers  (2021-06-06T19:08:53Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Learning Minimax Estimators via Online Learning [55.92459567732491]
  We consider the problem of designing minimax estimators for estimating parameters of a probability distribution. We construct an algorithm for finding a mixed-case Nash equilibrium.
  arXiv  Detail & Related papers  (2020-06-19T22:49:42Z)
• List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
  We are given a set $T$ of points in $mathbbRd$ with the promise that an unknown $alpha$-fraction of points in $T$ are drawn from an unknown mean and bounded covariance distribution $D$. We output a small list of hypothesis vectors such that at least one of them is close to the mean of $D$. In more detail, our algorithm is sample and computationally efficient, and achieves information-theoretically near-optimal error.
  arXiv  Detail & Related papers  (2020-06-18T17:47:37Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.