Timezone: »

 
Poster
Doubly Accelerated Stochastic Variance Reduced Dual Averaging Method for Regularized Empirical Risk Minimization
Tomoya Murata · Taiji Suzuki

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #172
in Posters Tue »
We develop a new accelerated stochastic gradient method for efficiently solving the convex regularized empirical risk minimization problem in mini-batch settings. The use of mini-batches has become a golden standard in the machine learning community, because the mini-batch techniques stabilize the gradient estimate and can easily make good use of parallel computing. The core of our proposed method is the incorporation of our new ``double acceleration'' technique and variance reduction technique. We theoretically analyze our proposed method and show that our method much improves the mini-batch efficiencies of previous accelerated stochastic methods, and essentially only needs size $\sqrt{n}$ mini-batches for achieving the optimal iteration complexities for both non-strongly and strongly convex objectives, where $n$ is the training set size. Further, we show that even in non-mini-batch settings, our method achieves the best known convergence rate for non-strongly convex and strongly convex objectives.
Keywords: Convex Optimization
[ Paper] 

Author Information

Tomoya Murata (NTT DATA Mathematical Systems Inc.)
Taiji Suzuki (taiji@mist.i.u-tokyo.ac.jp)

More from the Same Authors