A Hybrid Stochastic-Deterministic Minibatch Proximal Gradient Method for Efficient Optimization and Generalization

Pan Zhou, Xiao-Tong Yuan, Zhouchen Lin, Steven C. H. Hoi

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 ( <small>HSDMPG</small> ) algorithm for strongly convex problems with linear prediction structure, e.g., least squares and logistic/softmax regression. <small>HSDMPG</small> 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 <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> components, <small>HSDMPG</small> attains an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> -optimization-error within <inline-formula><tex-math notation="LaTeX">$\mathcal {O} \left(\kappa \log ^{\zeta +1}\left(\frac{1}{\epsilon }\right)\frac{1}{\epsilon }\bigwedge n\log ^{\zeta }\left(\frac{1}{\epsilon }\right)\right)$</tex-math></inline-formula> stochastic gradient evaluations, where <inline-formula><tex-math notation="LaTeX">$\kappa$</tex-math></inline-formula> is condition number, <inline-formula><tex-math notation="LaTeX">$\zeta =1$</tex-math></inline-formula> for quadratic loss and <inline-formula><tex-math notation="LaTeX">$\zeta =2$</tex-math></inline-formula> for generic loss. For large-scale problems, our complexity outperforms those of SVRG-type algorithms with/without dependence on data size. Particularly, when <inline-formula><tex-math notation="LaTeX">$\epsilon =\mathcal {O}(1/\sqrt{n})$</tex-math></inline-formula> which matches the intrinsic excess error of a learning model and is sufficient for generalization, our complexity for quadratic and generic losses is respectively <inline-formula><tex-math notation="LaTeX">$\mathcal {O} (n^{0.5}\log ^{2}(n))$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\mathcal {O} (n^{0.5}\log ^{3}(n))$</tex-math></inline-formula> , which for the first time achieves optimal generalization in less than a single pass over data. Besides, we extend <small>HSDMPG</small> to online strongly convex problems and prove its higher efficiency over the prior algorithms. Numerical results demonstrate the computational advantages of <small>HSDMPG</small> .
BibTeX
@article{zhou2022hybrid,
  author = {Pan Zhou and Xiao-Tong Yuan and Zhouchen Lin and Steven C. H. Hoi},
  title = {{A Hybrid Stochastic-Deterministic Minibatch Proximal Gradient Method for Efficient Optimization and Generalization}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2022},
  doi = {10.1109/tpami.2021.3087328},
}

Loading related content...

Figure