<p>Existing studies on the PGA have established its sharp convergence rate. Among its variants, the PGA with Shrinkage was shown in previous research to admit an upper bound, which may indeed be sharp. Motivated by this conjecture, we construct a worst-case dictionary and an initial iterate to derive a lower bound for the residual of the PGA with Shrinkage. The generally recognized optimal rate of greedy algorithms for arbitrary dictionaies and <InlineEquation ID="IEq1"> <EquationSource Format="MATHML"><math> <mi mathvariant="bold-italic">f</mi> <mo>∈</mo> <msub> <mi mathvariant="script">A</mi> <mn>1</mn> </msub> <mo stretchy="false">(</mo> <mi mathvariant="script">D</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$\boldsymbol{f}\in \mathcal{A}_{1}(\mathcal{D})$</EquationSource> </InlineEquation> is <InlineEquation ID="IEq2"> <EquationSource Format="MATHML"><math> <msup> <mi>m</mi> <mrow> <mo>−</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> </math></EquationSource> <EquationSource Format="TEX">$m^{-1/2}$</EquationSource> </InlineEquation>. Our main results demonstrate that for every <InlineEquation ID="IEq3"> <EquationSource Format="MATHML"><math> <msub> <mi>s</mi> <mn>0</mn> </msub> <mo>≤</mo> <mi>s</mi> <mo>≤</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$s_{0}\le s\le 1$</EquationSource> </InlineEquation> where <InlineEquation ID="IEq4"> <EquationSource Format="MATHML"><math> <msub> <mi>s</mi> <mn>0</mn> </msub> <mo>=</mo> <mn>0.33</mn> </math></EquationSource> <EquationSource Format="TEX">$s_{0} = 0.33$</EquationSource> </InlineEquation>, the PGA with Shrinkage achieves its sharp convergence rate. We also obtain a lower estimate for <InlineEquation ID="IEq5"> <EquationSource Format="MATHML"><math> <mn>0</mn> <mo><</mo> <mi>s</mi> <mo><</mo> <msub> <mi>s</mi> <mn>0</mn> </msub> </math></EquationSource> <EquationSource Format="TEX">$0< s< s_{0}$</EquationSource> </InlineEquation>, but there is a gap between the existing upper bound. Notably, for every <InlineEquation ID="IEq6"> <EquationSource Format="MATHML"><math> <mn>0</mn> <mo><</mo> <mi>s</mi> <mo>≤</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$0< s\le 1$</EquationSource> </InlineEquation> the rate of the PGA with Shrinkage is bounded below by <InlineEquation ID="IEq7"> <EquationSource Format="MATHML"><math> <msup> <mi>m</mi> <mrow> <mo>−</mo> <mi>α</mi> </mrow> </msup> </math></EquationSource> <EquationSource Format="TEX">$m^{-\alpha }$</EquationSource> </InlineEquation> where <InlineEquation ID="IEq8"> <EquationSource Format="MATHML"><math> <mn>0.18</mn> <mo><</mo> <mi>α</mi> <mo><</mo> <mn>0.37</mn> </math></EquationSource> <EquationSource Format="TEX">$0.18<\alpha <0.37$</EquationSource> </InlineEquation>, which is suboptimal. Finally, we complete the proof of the upper bound theorem of the PGA with Shrinkage to establish a comprehensive convergence rate characterization.</p>

Lower estimations of pure greedy algorithm with shrinkage

期刊论文
出版模式：

开放获取
发表日期：

2026年2月2日

查看全文

Fangjing Zhu,
Yi Shen,
Qifeng Zhang

摘要

Existing studies on the PGA have established its sharp convergence rate. Among its variants, the PGA with Shrinkage was shown in previous research to admit an upper bound, which may indeed be sharp. Motivated by this conjecture, we construct a worst-case dictionary and an initial iterate to derive a lower bound for the residual of the PGA with Shrinkage. The generally recognized optimal rate of greedy algorithms for arbitrary dictionaies and $f \in A_{1} (D)$ $\boldsymbol{f}\in \mathcal{A}_{1}(\mathcal{D})$ is $m^{- 1 / 2}$ $m^{-1/2}$ . Our main results demonstrate that for every $s_{0} \leq s \leq 1$ $s_{0}\le s\le 1$ where $s_{0} = 0.33$ $s_{0} = 0.33$ , the PGA with Shrinkage achieves its sharp convergence rate. We also obtain a lower estimate for $0 < s < s_{0}$ $0< s< s_{0}$ , but there is a gap between the existing upper bound. Notably, for every $0 < s \leq 1$ $0< s\le 1$ the rate of the PGA with Shrinkage is bounded below by $m^{- α}$ $m^{-\alpha }$ where $0.18 < α < 0.37$ $0.18<\alpha <0.37$ , which is suboptimal. Finally, we complete the proof of the upper bound theorem of the PGA with Shrinkage to establish a comprehensive convergence rate characterization.