REVIEW 3 cited by
On a Faster $R$-Linear Convergence Rate of the Barzilai-Borwein Method
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
The Barzilai-Borwein (BB) method has demonstrated great empirical success in nonlinear optimization. However, the convergence speed of BB method is not well understood, as the known convergence rate of BB method for quadratic problems is much worse than the steepest descent (SD) method. Therefore, there is a large discrepancy between theory and practice. To shrink this gap, we prove that the BB method converges $R$-linearly at a rate of $1-1/\kappa$, where $\kappa$ is the condition number, for strongly convex quadratic problems. In addition, an example with the theoretical rate of convergence is constructed, indicating the tightness of our bound.
Forward citations
Cited by 3 Pith papers
-
The Sharp Worst-Case Asymptotic Rate of the Barzilai--Borwein Method in $\mathbb R^d$ and Hilbert Spaces
For either Barzilai-Borwein rule, the worst asymptotic gradient root factor on strongly convex quadratics is exactly (κ(H)-1)/(κ(H)+1), and the same constant governs local nonlinear convergence under strict differentiability.
-
Kahan's Automatic Step-Size Control for Unconstrained Optimization
Kahan's KGD step-size is shown to converge at least R-linearly with rate 1-1/cond(H) for quadratics, and an adaptive generalization for general optimization is proved and tested.
-
Finite Horizon Optimization: Framework and Applications
A finite-horizon stepsize rule for the primal-dual method on LP, found via a 4x4 SDP, is claimed to accelerate convergence at the T-th iteration and to give about 3.9x speedup on Netlib instances.
Discussion (0). Continue with ORCID to comment.