On stability of Weak Greedy Algorithm in the presence of noise

2025/12/23 by V. N. Temlyakov, Temlyakov, V. N.
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computability, Logic, AI Algorithms #FOS: Mathematics #Functional Analysis (math.FA) #Numerical Analysis (math.NA) #Stochastic Gradient Optimization Techniques

paper · doi:10.48550/arxiv.2512.20750

openalex publication_date 2025/12/23 · openalex created_date 2025/12/26 · openalex updated_date 2026/07/28

Abstract

This paper is devoted to the theoretical study of the efficiency, namely, stability of some greedy algorithms. In the greedy approximation theory researchers are mostly interested in the following two important properties of an algorithm -- convergence and rate of convergence. In this paper we present some results on one more important property of an algorithm -- stability. Stability means that small perturbations do not result in a large change in the outcome of the algorithm. In this paper we discuss one kind of perturbations -- noisy data.

Citations

• Brief introduction in greedy approximation

Related

• Noisy Optimization: Convergence with a Fixed Number of Resamplings
• Greedy algorithms: a review and open problems
• Sparse approximation and recovery by greedy algorithms
• On Greedy Algorithms with bounded cumulative coherence
• On the rate of convergence of greedy algorithms