Publication Type
Journal Article
Version
acceptedVersion
Publication Date
6-2021
Abstract
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.
Keywords
Convex Optimization, Precondition, Online Convex Optimization, Stochastic Variance-Reduced Algorithm
Discipline
Artificial Intelligence and Robotics | Theory and Algorithms
Research Areas
Intelligent Systems and Optimization
Areas of Excellence
Digital transformation
Publication
IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume
44
Issue
10
First Page
5933
Last Page
5946
ISSN
0162-8828
Identifier
10.1109/TPAMI.2021.3087328
Publisher
Institute of Electrical and Electronics Engineers
Citation
ZHOU, Pan; YUAN, Xiao-Tong; LIN Zhouchen; and HOI, Steven C. H..
A hybrid stochastic-deterministic minibatch proximal gradient method for efficient optimization and generalization. (2021). IEEE Transactions on Pattern Analysis and Machine Intelligence. 44, (10), 5933-5946.
Available at: https://ink.library.smu.edu.sg/sis_research/8979
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/TPAMI.2021.3087328