Title | ||
---|---|---|
Adaptive Proximal Average based Variance Reducing Stochastic Methods for Optimization with Composite Regularization |
Abstract | ||
---|---|---|
We focus on empirical risk minimization with a composite regulariser, which has been widely applied in various machine learning tasks to introduce important structural information regarding the problem or data. In general, it is challenging to calculate the proximal operator with the composite regulariser. Recently, proximal average (PA) which involves a feasible proximal operator calculation is proposed to approximate composite regularisers. Augmented with the prevailing variance reducing (VR) stochastic methods (e.g. SVRG, SAGA), PA based algorithms would achieve a better performance. However, existing works require a fixed stepsize, which needs to be rather small to ensure that the PA approximation is sufficiently accurate. In the meantime, the smaller stepsize would incur many more iterations for convergence. In this paper, we propose two fast PA based VR stochastic methods - APA-SVRG and APA-SAGA. By initializing the stepsize with a much larger value and adaptively decreasing it, both of the proposed methods are proved to enjoy the O(n log 1/epsilon + m(0) 1/epsilon) iteration complexity to achieve the epsilon accurate solutions, where m(0) is the initial number of inner iterations and n is the number of samples. Moreover, experimental results demonstrate the superiority of the proposed algorithms. |
Year | Venue | Field |
---|---|---|
2019 | THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE | Convergence (routing),Mathematical optimization,Computer science,Empirical risk minimization,Composite number,Regularization (mathematics),Operator (computer programming),Initialization |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jingchang Liu | 1 | 0 | 0.68 |
Linli Xu | 2 | 790 | 42.51 |
Junliang Guo | 3 | 7 | 2.44 |
Xin Sheng | 4 | 0 | 0.68 |