Stochastic gradient methods are dominant in nonconvex optimization especially for deep models but have low asymptotical convergence due to the fixed smoothness. To address this problem, we propose a simple yet effective method for improving stochastic gradient methods named predictive local smoothness (PLS). First, we create a convergence condition to build a learning rate which varies adaptively with local smoothness. Second, the local smoothness can be predicted by the latest gradients. Third, we use the adaptive learning rate to update the stochastic gradients for exploring linear convergence rates. By applying the PLS method, we implement new variants of three popular algorithms: PLS-stochastic gradient descent (PLS-SGD), PLS-accelerated SGD (PLS-AccSGD), and PLS-AMSGrad. Moreover, we provide much simpler proofs to ensure their linear convergence. Empirical results show that the variants have better performance gains than the popular algorithms, such as, faster convergence and alleviating explosion and vanish of gradients.
# Unrealistic assumptions and trivial theory
This papers proposes a method to adjust the learning rate of stochastic gradient methods. The problem is of great importance but the theoretical results and presentation contain many issues that make the paper unfit for publication.
The main issue that I see is that the assumption made are unrealistic and make the theory trivial. First, for gradient descent, the authors assume that the gradient is of the form L(x_t) (x_t - x*). Under this assumption, gradient descent converges on a single step with step size 1 / L(x_t). In the stochastic setting, they assume that *each* stochastic gradient is of the form L_i(x_t) (x_t - x*), Eq. (11). Again, SGD in this scenario converges in a single iteration with step size 1 / L_i(x_t).
No wonder in this scenario the authors are able to obtain linear convergence of SGD to arbitrary precision (which is known to be impossible even for quadratics).
# Other Issues
* Motivation of Eq. (9) is not discussed in sufficient detail. It is unclear to me how to obtain (9) from (7) as the authors mention. Regarding notation, L(x_t) is a scalar, hence (9) could be written more simply as \nabla f(x_t) = L(x_t) (x_t - x*). Why the need for the Kronecker product?
* The authors should clearly state what are the assumptions in the theorem statement. For theorem 1 these are not clearly stated, and phrases like "Theorem 1 provides a simple condition for the linear convergence of SGD" give the wrong impression that the Theorem is widely applicable.
# Minor
  * Belo Eq. (10): "where \epsilon_1 is a parameter to prevent ||x_t - x_{t-1}|| going to zero: . I guess what the authors meant is to prevent *the denominator* going to zero, you do want ||x_t - x_{t-1}|| to go to zero as you approach a stationary point