A hybrid stochastic-deterministic minibatch proximal gradient method for efficient optimization and generalization

• Main Authors: ZHOU, Pan, YUAN, Xiao-Tong, LIN Zhouchen, HOI, Steven C. H.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Convex Optimization; Precondition; Online Convex Optimization; Stochastic Variance-Reduced Algorithm; Artificial Intelligence and Robotics; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/8979; https://ink.library.smu.edu.sg/context/sis_research/article/9982/viewcontent/2021_TPAMI_HSDN.pdf
• Institution: Singapore Management University

Despite the success of stochastic variance-reduced gradient (SVRG) algorithms in solving large-scale problems, their stochastic gradient complexity often scales linearly with data size and is expensive for huge data. Accordingly, we propose a hybrid stochastic-deterministic minibatch proximal gradient (HSDMPG) algorithm for strongly convex problems with linear prediction structure, e.g. least squares and logistic/softmax regression. HSDMPG enjoys improved computational complexity that is data-size-independent for large-scale problems. It iteratively samples an evolving minibatch of individual losses to estimate the original problem, and can efficiently minimize the sampled subproblems. For strongly convex loss of n components, HSDMPG attains an -optimization-error within O κ logζ+1 1 1 V n logζ 1 stochastic gradient evaluations, where κ is condition number, ζ = 1 for quadratic loss and ζ = 2 for generic loss. For large-scale problems, our complexity outperforms those of SVRG-type algorithms with/without dependence on data size. Particularly, when = O(1/ √ n) which matches the intrinsic excess error of a learning model and is sufficient for generalization, our complexity for quadratic and generic losses is respectively O(n 0.5 log2 (n)) and O(n 0.5 log3 (n)), which for the first time achieves optimal generalization in less than a single pass over data. Besides, we extend HSDMPG to online strongly convex problems and prove its higher efficiency over the prior algorithms. Numerical results demonstrate the computational advantages of HSDM.