List-Decodable Regression via Expander Sketching

• URL: http://arxiv.org/abs/2511.22524v1
• Date: Thu, 27 Nov 2025 15:04:37 GMT
• Title: List-Decodable Regression via Expander Sketching
• Authors: Herbod Pourali, Sajjad Hashemian, Ebrahim Ardeshir-Larijani,
• Abstract summary: We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity $tildeO((d+log1)/)$, list size $O (1/)$, and near input-sparsity running time $tildeO(mathrmnnz(X)+d3/)$ under standard sub-Gaussian assumptions.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity $\tilde{O}((d+\log(1/δ))/α)$, list size $O(1/α)$, and near input-sparsity running time $\tilde{O}(\mathrm{nnz}(X)+d^{3}/α)$ under standard sub-Gaussian assumptions. Our method uses lossless expanders to synthesize lightly contaminated batches, enabling robust aggregation and a short spectral filtering stage that matches the best known efficient guarantees while avoiding SoS machinery and explicit batch structure.

Related papers

• Robust learning of halfspaces under log-concave marginals [6.852292115526837]
  We give an algorithm that learns linear threshold functions and returns a classifier with boundary volume $O(r+varepsilon)$ at radius perturbation $r$.<n>The time and sample complexity of $dtildeO (1/varepsilon2)$ matches the complexity of Boolean regression.
  arXiv  Detail & Related papers  (2025-05-19T20:12:16Z)
• Batch List-Decodable Linear Regression via Higher Moments [39.32851434877865]
  We study the task of list-decodable linear regression using batches.<n>A batch is called clean if it consists of i.i.d. samples from an unknown linear regression distribution.
  arXiv  Detail & Related papers  (2025-03-12T20:11:07Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  We show that SignSGD with Majority Voting can robustly work on the whole range of complexity with $kappakappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappa
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
  We show a novel notion of sparsity that we dub $(lambda, beta)$-sparsity.<n>In short, there is a set of at most $beta$ groups whose risks at $theta$ all are at least $lambda$ larger than the risks of the other groups.<n>We show how to get a dimension-free semi-adaptive sample complexity bound with a computationally efficient method.
  arXiv  Detail & Related papers  (2024-10-01T13:45:55Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
  We analyze the oracle complexity of the Halpern iteration with minibatch.<n>We propose new model-free algorithms for average and discounted reward MDPs.
  arXiv  Detail & Related papers  (2024-03-19T01:07:35Z)
• Efficient List-Decodable Regression using Batches [33.300073775123835]
  We begin the study of list-decodable linear regression using batches. In this setting only an $alpha in (0,1]$ fraction of the batches are genuine. Each genuine batch contains $ge n$ i.i.d samples from a common unknown distribution and the remaining batches may contain arbitrary or even adversarial samples.
  arXiv  Detail & Related papers  (2022-11-23T07:08:00Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  offline reinforcement learning (RL) learns using pre-collected data without further exploration. Prior algorithms or analyses either suffer from suboptimal sample complexities or incur high burn-in cost to reach sample optimality. We demonstrate that the model-based (or "plug-in") approach achieves minimax-optimal sample complexity without burn-in cost.
  arXiv  Detail & Related papers  (2022-04-11T17:26:19Z)
• An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
  We present an efficient algorithm (RSG+) for canonical correlation analysis (CCA) using a reparametrization of the projection matrices. While the paper primarily focuses on the formulation and technical analysis of its properties, our experiments show that the empirical behavior on common datasets is quite promising.
  arXiv  Detail & Related papers  (2021-06-08T23:38:29Z)
• Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
  We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex optimization.
  arXiv  Detail & Related papers  (2020-10-07T01:43:07Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. We test our methods on problems with $p$ as large as $500,000$.
  arXiv  Detail & Related papers  (2020-06-15T21:55:34Z)

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.