1.2NAFeb 17, 2017
Accurate Quotient-Difference algorithm: error analysis, improvements and applicationsPeibing Du, Roberto Barrio, Hao Jiang et al.
The compensated quotient-difference (Compqd) algorithm is proposed along with some applications. The main motivation is based on the fact that the standard quotient-difference (qd) algorithm can be numerically unstable. The Compqd algorithm is obtained by applying error-free transformations to improve the traditional qd algorithm. We study in detail the error analysis of the qd and Compqd algorithms and we introduce new condition numbers so that the relative forward rounding error bounds can be derived directly. Our numerical experiments illustrate that the Compqd algorithm is much more accurate than the qd algorithm, relegating the influence of the condition numbers up to second order in the rounding unit of the computer. Three applications of the new algorithm in the obtention of continued fractions and in pole and zero detection are shown.
1.2NAMar 19, 2016
A note on the convergence of nonconvex line searchTao Sun, Lizhi Chenga, Hao Jiang
In this note, we consider the line search for a class of abstract nonconvex algorithm which have been deeply studied in the Kurdyka-Lojasiewicz theory. We provide a weak convergence result of the line search in general. When the objective function satisfies the Kurdyka-Lojasiewicz property and some certain assumption, a global convergence result can be derived. An application is presented for the L0-regularized least square minimization in the end of the paper.
19.8OCNov 5, 2018
Non-ergodic Convergence Analysis of Heavy-Ball AlgorithmsTao Sun, Penghang Yin, Dongsheng Li et al.
In this paper, we revisit the convergence of the Heavy-ball method, and present improved convergence complexity results in the convex setting. We provide the first non-ergodic O(1/k) rate result of the Heavy-ball algorithm with constant step size for coercive objective functions. For objective functions satisfying a relaxed strongly convex condition, the linear convergence is established under weaker assumptions on the step size and inertial parameter than made in the existing literature. We extend our results to multi-block version of the algorithm with both the cyclic and stochastic update rules. In addition, our results can also be extended to decentralized optimization, where the ergodic analysis is not applicable.