Hard Thresholding Pursuit Algorithms for Least Absolute Deviations Problem

• URL: http://arxiv.org/abs/2601.06558v1
• Date: Sat, 10 Jan 2026 12:55:59 GMT
• Title: Hard Thresholding Pursuit Algorithms for Least Absolute Deviations Problem
• Authors: Jiao Xu, Peng Li, Bing Zheng,
• Abstract summary: Least absolute deviations (LAD) is a statistical optimality criterion widely utilized in scenarios where a minority of measurements are contaminated by outliers of arbitrary magnitudes.<n>In this paper, we delve into the robustness of the variant of adaptive iterative hard thresholding to outliers, known as graded fast hard thresholding pursuit (GFHTP$_$) algorithm.<n> Numerical experiments reveal that the GFHTP$_$ algorithm consistently outperforms competing algorithms in terms of both robustness and computational efficiency.
• Score: 14.123089301194623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Least absolute deviations (LAD) is a statistical optimality criterion widely utilized in scenarios where a minority of measurements are contaminated by outliers of arbitrary magnitudes. In this paper, we delve into the robustness of the variant of adaptive iterative hard thresholding to outliers, known as graded fast hard thresholding pursuit (GFHTP$_1$) algorithm. Unlike the majority of the state-of-the-art algorithms in this field, GFHTP$_1$ does not require prior information about the signal's sparsity. Moreover, its design is parameterless, which not only simplifies the implementation process but also removes the intricacies of parameter optimization. Numerical experiments reveal that the GFHTP$_1$ algorithm consistently outperforms competing algorithms in terms of both robustness and computational efficiency.

Related papers

• Principled Algorithms for Optimizing Generalized Metrics in Binary Classification [53.604375124674796]
  We introduce principled algorithms for optimizing generalized metrics, supported by $H$-consistency and finite-sample generalization bounds.<n>Our approach reformulates metric optimization as a generalized cost-sensitive learning problem.<n>We develop new algorithms, METRO, with strong theoretical performance guarantees.
  arXiv  Detail & Related papers  (2025-12-29T01:33:42Z)
• Optimal Rates for Robust Stochastic Convex Optimization [12.620782629498812]
  We develop novel algorithms that achieve minimax-optimal excess risk (up to logarithmic factors) under the $epsilon$-contamination model.<n>Our algorithms do not require stringent assumptions, including Lipschitz continuity and smoothness of individual sample functions.<n>We complement our algorithmic developments with a tight information-theoretic lower bound for robust SCO.
  arXiv  Detail & Related papers  (2024-12-15T00:52:08Z)
• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment.<n>We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  Two recent works established the $O(epsilon-3)$ sample complexity to obtain an $O(epsilon)$-stationary point. However, both require a large batch size on the order of $mathrmploy(epsilon-1)$, which is not only computationally burdensome but also unsuitable for streaming applications. In this work, we solve the prior two problems simultaneously by revisiting a simple variant of the STORM algorithm.
  arXiv  Detail & Related papers  (2023-02-13T00:22:28Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  We present a single-loop algorithm named SLEDGE (Single-Loop-E Gradient Estimator) for periodic convergence. Unlike existing methods, SLEDGE has the advantage of versatility; (ii) second-order optimal, (ii) in the PL region, and (iii) smaller complexity under less of data.
  arXiv  Detail & Related papers  (2022-09-01T11:05:26Z)
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints [7.028225540638832]
  We propose a novel algorithm for decentralized optimization with orthogonality constraints. VRSGT is the first algorithm for decentralized optimization with orthogonality constraints that reduces both sampling and communication complexities simultaneously. In the numerical experiments, VRGTS has a promising performance in a real-world autonomous sample.
  arXiv  Detail & Related papers  (2022-08-29T14:46:44Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty. We propose a variant of EI with a standard incumbent defined via the GP predictive mean. We show that our algorithm converges, and achieves a cumulative regret bound of $mathcal O(gamma_TsqrtT)$.
  arXiv  Detail & Related papers  (2022-03-15T13:17:53Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

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.