STOCHASTIC AND RANDOMIZED ALGORITHMS FOR LARGE-SCALE OPTIMIZATION IN MACHINE LEARNING

Abstract

This thesis advances the state-of-the-art for two classes of optimization problems in machine learning. In the first part, we revisit the stochastic limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm for strongly convex smooth optimization. By proposing a new coordinate transformation framework, we show that the convergence rates and computational complexities of the stochastic L-BFGS algorithms can be significantly improved compared to previous works. In addition, we propose several practical acceleration strategies to speed up the empirical performance of such algorithms. In the second part, we develop accelerated primal-dual fist-order algorithms for a class of stochastic three-composite convex optimization problems. The method leads to the optimal convergence rate, which significantly improves the convergence rates in previous works. In addition, we establish the connection between these algorithms to the accelerated stochastic alternating direction method of multipliers (ADMM) algorithms.