Back to Search
Start Over
Sparse Learning with Stochastic Composite Optimization.
- Source :
- IEEE Transactions on Pattern Analysis & Machine Intelligence; Jun2017, Vol. 39 Issue 6, p1223-1236, 14p
- Publication Year :
- 2017
-
Abstract
- In this paper, we study Stochastic Composite Optimization (SCO) for sparse learning that aims to learn a sparse solution from a composite function. Most of the recent SCO algorithms have already reached the optimal expected convergence rate \mathcal O(1/\lambda T)<alternatives> <inline-graphic xlink:href="zhang-ieq1-2578323.gif"/></alternatives>, but they often fail to deliver sparse solutions at the end either due to the limited sparsity regularization during stochastic optimization (SO) or due to the limitation in online-to-batch conversion. Even when the objective function is strongly convex, their high probability bounds can only attain \mathcal O(\sqrt\log (1/\delta)/T) <alternatives><inline-graphic xlink:href="zhang-ieq2-2578323.gif"/></alternatives> with $\delta$<alternatives> <inline-graphic xlink:href="zhang-ieq3-2578323.gif"/></alternatives> is the failure probability, which is much worse than the expected convergence rate. To address these limitations, we propose a simple yet effective two-phase Stochastic Composite Optimization scheme by adding a novel powerful sparse online-to-batch conversion to the general Stochastic Optimization algorithms. We further develop three concrete algorithms, OptimalSL, LastSL and AverageSL, directly under our scheme to prove the effectiveness of the proposed scheme. Both the theoretical analysis and the experiment results show that our methods can really outperform the existing methods at the ability of sparse learning and at the meantime we can improve the high probability bound to approximately \mathcal {O}(\log (\log (T)/\delta)/\lambda T)<alternatives> <inline-graphic xlink:href="zhang-ieq4-2578323.gif"/></alternatives>. [ABSTRACT FROM AUTHOR]
- Subjects :
- EDUCATION
MATHEMATICAL programming
ALGORITHMS
MATHEMATICAL optimization
FIBERS
Subjects
Details
- Language :
- English
- ISSN :
- 01628828
- Volume :
- 39
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Pattern Analysis & Machine Intelligence
- Publication Type :
- Academic Journal
- Accession number :
- 122985188
- Full Text :
- https://doi.org/10.1109/TPAMI.2016.2578323