2020/01/07 by Tuyen Trung Truong, Truong, Tuyen Trung · 3 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2001.02005
Convergence for Two-way Backtracking GD can be proven under more general assumptions, in particular valid for C^2 functions. In statement of Theorem 0.3, need to add the assumption that {f(x_n}) is non-increasing. Some typos corrected. 5 pages
openalex publication_date 2020/01/07 · arxiv created 2020/01/08 · arxiv updated 2020/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In unconstrained optimisation on an Euclidean space, to prove convergence in Gradient Descent processes (GD) xn+1=xn-δn ∇ f(xn) it usually is required that the learning rates δn's are bounded: δn≤ δ for some positive δ. Under this assumption, if the sequence xn converges to a critical point z, then with large values of n the update will be small because ||xn+1-xn||\lesssim ||∇ f(xn)||. This may also force the sequence to converge to a bad minimum. If we can allow, at least theoretically, that the learning rates δn's are not bounded, then we may have better convergence to better minima. A previous joint paper by the author showed convergence for the usual version of Backtracking GD under very general assumptions on the cost function f. In this paper, we allow the learning rates δn to be unbounded, in the sense that there is a function h:(0,∞)→ (0,∞ ) such that lim t→ 0th(t)=0 and δn\lesssim max \h(xn),δ\ satisfies Armijo's condition for all n, and prove convergence under the same assumptions as in the mentioned paper. It will be shown that this growth rate of h is best possible if one wants convergence of the sequence \xn\. A specific way for choosing δn in a discrete way connects to Two-way Backtracking GD defined in the mentioned paper. We provide some results which either improve or are implicitly contained in those in the mentioned paper and another recent paper on avoidance of saddle points.