Search

Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distinguish between two fundamentally different algorithms—Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Polyak's heavy-ball method—we study an alternative limiting process that yields high-resolution ODEs. We show that these ODEs permit a general Lyapunov function framework for the analysis of convergence in both continuous and discrete time. We also show that these ODEs are more accurate surrogates for the underlying algorithms; in particular, they not only distinguish between NAG-SC and Polyak's heavy-ball method, but they allow the identification of a term that we refer to as "gradient correction" that is present in NAG-SC but not in the heavy-ball method and is responsible for the qualitative difference in convergence of the two methods. We also use the high-resolution ODE framework to study Nesterov's accelerated gradient method for (non-strongly) convex functions, uncovering a hitherto unknown result—that NAG-C minimizes the squared gradient norm at an inverse cubic rate. Finally, by modifying the high-resolution ODE of NAG-C, we obtain a family of new optimization methods that are shown to maintain the accelerated convergence rates of NAG-C for smooth convex functions. [ABSTRACT FROM AUTHOR]

Stochastic gradient Langevin dynamics (SGLD) is a fundamental algorithm in stochastic optimization. Recent work by Zhang et al. (2017) presents an analysis for the hitting time of SGLD for the first and second order stationary points. The proof in Zhang et al. (2017) is a two-stage procedure through bounding the Cheeger's constant, which is rather complicated and leads to loose bounds. In this paper, using intuitions from stochastic differential equations, we provide a direct analysis for the hitting times of SGLD to the first and second order stationary points. Our analysis is straightforward. It only relies on basic linear algebra and probability theory tools. Our direct analysis also leads to tighter bounds comparing to Zhang et al. (2017) and shows the explicit dependence of the hitting time on different factors, including dimensionality, smoothness, noise strength, and step size effects. Under suitable conditions, we show that the hitting time of SGLD to first-order stationary points can be dimension-independent. Moreover, we apply our analysis to study several important online estimation problems in machine learning, including linear regression, matrix factorization, and online PCA. [ABSTRACT FROM AUTHOR]

Summary of Contribution: Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees (Fenwick 1994) and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. Local polynomial regression is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this paper, we significantly accelerate the computation of local polynomial estimates by novel applications of multidimensional binary indexed trees. Both time and space complexity of our proposed algorithm is nearly linear in the number of input data points. Simulation results confirm the efficiency and effectiveness of our proposed approach. Summary of Contribution. Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. [ABSTRACT FROM AUTHOR]