Asymptotic behaviour of learning rates in Armijo's condition
share
Fix a constant 0<α <1. For a C^1 function f:ℝ^k→ℝ, a point x and a positive number δ >0, we say that Armijo's condition is satisfied if f(x-δ∇ f(x))-f(x)≤ -αδ ||∇ f(x)||^2. It is a basis for the well known Backtracking Gradient Descent (Backtracking GD) algorithm. Consider a sequence {x_n} defined by x_n+1=x_n-δ _n∇ f(x_n), for positive numbers δ _n for which Armijo's condition is satisfied. We show that if {x_n} converges to a non-degenerate critical point, then {δ _n} must be bounded. Moreover this boundedness can be quantified in terms of the norms of the Hessian ∇ ^2f and its inverse at the limit point. This complements the first author's results on Unbounded Backtracking GD, and shows that in case of convergence to a non-degenerate critical point the behaviour of Unbounded Backtracking GD is not too different from that of usual Backtracking GD. On the other hand, in case of convergence to a degenerate critical point the behaviours can be very much different. We run some experiments to illustrate that both scenrios can really happen. In another part of the paper, we argue that Backtracking GD has the correct unit (according to a definition by Zeiler in his Adadelta's paper). The main point is that since learning rate in Backtracking GD is bound by Armijo's condition, it is not unitless.
READ FULL TEXT