Jun Liu

Ye Yuan, Ling Shi, Jun Liu et al.

Fueled by applications in sensor networks, these years have witnessed a surge of interest in distributed estimation and filtering. A new approach is hereby proposed for the Distributed Kalman Filter (DKF) by integrating a local covariance computation scheme. Compared to existing well-established DKF methods, the virtue of the present approach lies in accelerating the convergence of the state estimates to those of the Centralized Kalman Filter (CKF). Meanwhile, an algorithm is proposed that allows each node to compute the averaged measurement noise covariance matrix within a minimal discrete-time running steps in a distributed way. Both theoretical analysis and extensive numerical simulations are conducted to show the feasibility and superiority of the proposed method.

Jun Liu, Ye Yuan

We prove that various stochastic gradient descent methods, including the stochastic gradient descent (SGD), stochastic heavy-ball (SHB), and stochastic Nesterov's accelerated gradient (SNAG) methods, almost surely avoid any strict saddle manifold. To the best of our knowledge, this is the first time such results are obtained for SHB and SNAG methods. Moreover, our analysis expands upon previous studies on SGD by removing the need for bounded gradients of the objective function and uniformly bounded noise. Instead, we introduce a more practical local boundedness assumption for the noisy gradient, which is naturally satisfied in empirical risk minimization problems typically seen in training of neural networks.

Jun Liu, Ye Yuan

The vast majority of convergence rates analysis for stochastic gradient methods in the literature focus on convergence in expectation, whereas trajectory-wise almost sure convergence is clearly important to ensure that any instantiation of the stochastic algorithms would converge with probability one. Here we provide a unified almost sure convergence rates analysis for stochastic gradient descent (SGD), stochastic heavy-ball (SHB), and stochastic Nesterov's accelerated gradient (SNAG) methods. We show, for the first time, that the almost sure convergence rates obtained for these stochastic gradient methods on strongly convex functions, are arbitrarily close to their optimal convergence rates possible. For non-convex objective functions, we not only show that a weighted average of the squared gradient norms converges to zero almost surely, but also the last iterates of the algorithms. We further provide last-iterate almost sure convergence rates analysis for stochastic gradient methods on weakly convex smooth functions, in contrast with most existing results in the literature that only provide convergence in expectation for a weighted average of the iterates.

Ye Yuan, Mu Li, Jun Liu et al.

We propose a new method to accelerate the convergence of optimization algorithms. This method simply adds a power coefficient $γ\in[0,1)$ to the gradient during optimization. We call this the Powerball method and analyze the convergence rate for the Powerball method for strongly convex functions. While theoretically the Powerball method is guaranteed to have a linear convergence rate in the same order of the gradient method, we show that empirically it significantly outperforms the gradient descent and Newton's method, especially during the initial iterations. We demonstrate that the Powerball method provides a $10$-fold speedup of the convergence of both gradient descent and L-BFGS on multiple real datasets.