Optimal stochastic and online learning with individual iterates

Lei，Yunwen1,2; Yang，Peng1; Tang，Ke1; Zhou，Ding Xuan3

2019

1049-5258

Advances in Neural Information Processing Systems

32

Stochastic composite mirror descent (SCMD) is a simple and efficient method able to capture both geometric and composite structures of optimization problems in machine learning. Existing strategies require to take either an average or a random selection of iterates to achieve optimal convergence rates, which, however, can either destroy the sparsity of solutions or slow down the practical training speed. In this paper, we propose a theoretically sound strategy to select an individual iterate of the vanilla SCMD, which is able to achieve optimal rates for both convex and strongly convex problems in a non-smooth learning setting. This strategy of outputting an individual iterate can preserve the sparsity of solutions which is crucial for a proper interpretation in sparse learning problems. We report experimental comparisons with several baseline methods to show the effectiveness of our method in achieving a fast training speed as well as in outputting sparse solutions.

第一 ; 通讯

英语

EI

20203609142105

Structural optimization ; Stochastic systems ; E-learning ; Learning systems

Control Systems:731.1 ; Optimization Techniques:921.5 ; Numerical Methods:921.6 ; Systems Science:961

2-s2.0-85090174438

Scopus

1.University Key Laboratory of Evolving Intelligent Systems of Guangdong Province,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China
2.Department of Computer Science,Technical University of Kaiserslautern,Kaiserslautern,67653,Germany
3.School of Data Science,Department of Mathematics,City University of Hong Kong,Kowloon,Hong Kong

Lei，Yunwen,Yang，Peng,Tang，Ke,et al. Optimal stochastic and online learning with individual iterates[C],2019.