Name
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)$ , 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})$ with $\\delta$ 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)$ . |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/TPAMI.2016.2578323 | IEEE Trans. Pattern Anal. Mach. Intell. |
Keywords | Field | DocType |
Optimization,Convergence,Algorithm design and analysis,Standards,Linear programming,Stochastic processes,Training | Stochastic optimization,Computer science,Regularization (mathematics),Rate of convergence,Artificial intelligence,Linear programming,Discrete mathematics,Mathematical optimization,Pattern recognition,Sparse approximation,Stochastic process,Convex function,Stochastic programming | Journal |
Volume | Issue | ISSN |
39 | 6 | 0162-8828 |
Citations | PageRank | References |
4 | 0.42 | 20 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Weizhong Zhang | 1 | 9 | 0.89 |
| Lijun Zhang | 2 | 980 | 63.68 |
| Zhongming Jin | 3 | 71 | 2.87 |
| Rong Jin | 4 | 6206 | 334.26 |
| Deng Cai | 5 | 7938 | 320.26 |
| Xuelong Li | 6 | 15049 | 617.31 |
| Ronghua Liang | 7 | 376 | 42.60 |
| Xiaofei He | 8 | 9139 | 386.38 |