Step-Size Decay and Structural Stagnation in Greedy Sparse Learning

• URL: http://arxiv.org/abs/2603.07703v1
• Date: Sun, 08 Mar 2026 16:09:51 GMT
• Title: Step-Size Decay and Structural Stagnation in Greedy Sparse Learning
• Abstract summary: Greedy algorithms are central to sparse approximation and stage-wise learning methods such as matching pursuit and boosting.<n>It is known that the Power-Relaxed Greedy Algorithm with step sizes $m-$ may fail to converge when $>1$ in general Hilbert spaces.<n>We study realizable regression problems with controlled feature coherence and derive explicit lower bounds on the residual norm.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Greedy algorithms are central to sparse approximation and stage-wise learning methods such as matching pursuit and boosting. It is known that the Power-Relaxed Greedy Algorithm with step sizes $m^{-α}$ may fail to converge when $α>1$ in general Hilbert spaces. In this work, we revisit this phenomenon from a sparse learning perspective. We study realizable regression problems with controlled feature coherence and derive explicit lower bounds on the residual norm, showing that over-decaying step-size schedules induce structural stagnation even in low-dimensional sparse settings. Numerical experiments confirm the theoretical predictions and illustrate the role of feature coherence. Our results provide insight into step-size design in greedy sparse learning.

Related papers

• On the Learning Curves of Revenue Maximization [62.087200798198786]
  A learning curve plots the decay of an algorithm's error for a fixed underlying distribution as a function of the number of training samples.<n>Prior work on revenue-maximizing learning algorithms adopts a distribution-free perspective, which parallels the PAC learning framework in learning theory.<n>We show that there exists a Bayes-consistent algorithm, meaning that its learning curve converges to zero for any arbitrary valuation distribution.
  arXiv  Detail & Related papers  (2026-04-29T17:38:25Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  Learning intersections of halfspaces is a central problem in Computational Learning Theory.<n>Even for just two halfspaces, it remains a major open question whether learning is possible in time.<n>We introduce a novel algorithm that provably circumvents the CSQ hardness barrier.
  arXiv  Detail & Related papers  (2025-11-13T00:28:24Z)
• Asymptotically optimal reinforcement learning in Block Markov Decision Processes [0.22835610890984168]
  Reinforcement Learning (RL) is impractical in many real-world settings with exponentially large state and action spaces.<n>We provide a regret analysis that explicitly leverages clustering, demonstrating that accurate latent state estimation can indeed effectively speed up learning.<n>This algorithm achieves a regret that is $O(sqrtT+n2)$ on a large class of BMDPs susceptible to clustering.
  arXiv  Detail & Related papers  (2025-10-15T16:54:06Z)
• The informativeness of the gradient revisited [4.178980693837599]
  We give a general bound on the variance in terms of a parameter related to the pairwise independence of the target function class.<n>In addition to the theoretical analysis, we present experiments to understand better the nature of recent deep learning-based attacks on Learning with Errors.
  arXiv  Detail & Related papers  (2025-05-28T09:23:37Z)
• Beyond Progress Measures: Theoretical Insights into the Mechanism of Grokking [50.465604300990904]
  Grokking refers to the abrupt improvement in test accuracy after extended overfitting.<n>In this work, we investigate the grokking mechanism underlying the Transformer in the task of prime number operations.
  arXiv  Detail & Related papers  (2025-04-04T04:42:38Z)
• Inexact subgradient methods for semialgebraic functions [18.293072574300798]
  Motivated by the extensive application of approximate gradients in machine learning, we investigate subexact additive methods subject to persistent errors.<n>Our analysis addresses both vanishing and constant step-size regimes.
  arXiv  Detail & Related papers  (2024-04-30T12:47:42Z)
• Adaptive Federated Learning Over the Air [108.62635460744109]
  We propose a federated version of adaptive gradient methods, particularly AdaGrad and Adam, within the framework of over-the-air model training. Our analysis shows that the AdaGrad-based training algorithm converges to a stationary point at the rate of $mathcalO( ln(T) / T 1 - frac1alpha ).
  arXiv  Detail & Related papers  (2024-03-11T09:10:37Z)
• Understanding Gradient Regularization in Deep Learning: Efficient Finite-Difference Computation and Implicit Bias [15.739122088062793]
  Gradient regularization (GR) is a method that penalizes the norm of the training loss during training. We show that a specific finite-difference computation, composed of both gradient ascent and descent steps, reduces the computational cost for GR. We demonstrate that finite-difference GR is closely related to some other algorithms based on iterative ascent and descent steps for exploring flat minima.
  arXiv  Detail & Related papers  (2022-10-06T07:12:54Z)
• Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit [36.17720004582283]
  This work conducts such an exploration through the lens of learning $k$-sparse parities of $n$ bits. We find that neural networks exhibit surprising phase transitions when scaling up dataset size and running time.
  arXiv  Detail & Related papers  (2022-07-18T17:55:05Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  We study the problem of regret minimization for episodic Reinforcement Learning (RL) We focus on learning with general function classes and general model classes. We show that a logarithmic regret bound is realizable by algorithms with $O(log T)$ switching cost.
  arXiv  Detail & Related papers  (2022-03-03T02:55:55Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  We show that it is possible to obtain regret scaling as $mathcalO(sqrtV_1star K)$ in reinforcement learning with large state spaces. We demonstrate that existing techniques based on at least squares estimation are insufficient to obtain this result.
  arXiv  Detail & Related papers  (2021-12-07T00:29:57Z)
• Adiabatic ground state preparation in an expanding lattice [0.0]
  We implement and characterize a numerical algorithm inspired by the $s$-source framework [Phys. Rev.B 93, 045127] for building a quantum many-body ground state wavefunction on a lattice of size $2L$. We find that the construction works particularly well when the gap is large and, interestingly, at scale in critical points.
  arXiv  Detail & Related papers  (2020-02-22T01:18:48Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

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.