Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization

Stochastic variance-reduced gradient (SVRG) algorithms have been shown to\nwork favorably in solving large-scale learning problems. Despite the remarkable\nsuccess, the stochastic gradient complexity of SVRG-type algorithms usually\nscales linearly with data size and thus could still be expensive for huge data.\nTo address this deficiency, we propose a hybrid stochastic-deterministic\nminibatch proximal gradient (HSDMPG) algorithm for strongly-convex problems\nthat enjoys provably improved data-size-independent complexity guarantees. More\nprecisely, for quadratic loss $F(\\theta)$ of $n$ components, we prove that\nHSDMPG can attain an $\\epsilon$-optimization-error\n$\\mathbb{E}[F(\\theta)-F(\\theta^*)]\\leq\\epsilon$ within\n$\\mathcal{O}\\Big(\\frac{\\kappa^{1.5}\\epsilon^{0.75}\\log^{1.5}(\\frac{1}{\\epsilon})+1}{\\epsilon}\\wedge\\Big(\\kappa\n\\sqrt{n}\\log^{1.5}\\big(\\frac{1}{\\epsilon}\\big)+n\\log\\big(\\frac{1}{\\epsilon}\\big)\\Big)\\Big)$\nstochastic gradient evaluations, where $\\kappa$ is condition number. For\ngeneric strongly convex loss functions, we prove a nearly identical complexity\nbound though at the cost of slightly increased logarithmic factors. For\nlarge-scale learning problems, our complexity bounds are superior to those of\nthe prior state-of-the-art SVRG algorithms with or without dependence on data\nsize. Particularly, in the case of $\\epsilon=\\mathcal{O}\\big(1/\\sqrt{n}\\big)$\nwhich is at the order of intrinsic excess error bound of a learning model and\nthus sufficient for generalization, the stochastic gradient complexity bounds\nof HSDMPG for quadratic and generic loss functions are respectively\n$\\mathcal{O} (n^{0.875}\\log^{1.5}(n))$ and $\\mathcal{O}\n(n^{0.875}\\log^{2.25}(n))$, which to our best knowledge, for the first time\nachieve optimal generalization in less than a single pass over data. Extensive\nnumerical results demonstrate the computational advantages of our algorithm\nover the prior ones.\n