Sharp Characterization of Optimal Minibatch Size for Stochastic Finite Sum Convex Optimization The minibatching technique has been extensively adopted to facilitate stochastic firstorder methods because of their computational efficiency in parallel computing for largescale machine learning and data mining. However, the optimal minibatch size determination for accelerated stochastic gradient methods is not completely understood. Actually, there appears tradeoff between the iteration complexity and the total computational complexity; that is, the number of iterations (minibatch queries) can be decreased by increasing the minibatch size, but too large minibatch size would result in an unnecessarily large total computational cost. In this study, we give a sharp characterization of the minimax optimal minibatch size to achieve the optimal iteration complexity by providing a reachable lower bound for minimizing finite sum of convex functions and, surprisingly, show that the optimal method with the minimax optimal minibatch size can achieve both of the optimal iteration complexity and the optimal total computational complexity simultaneously. Finally, this feature is verified experimentally.

Nonasymptotic Analysis of Stochastic Methods for NonSmooth NonConvex Regularized Problems Stochastic Proximal Gradient (SPG) methods have been widely used for solving optimization problems with a simple (possibly nonsmooth) regularizer in machine learning and statistics. However, to the best of our knowledge no nonasymptotic convergence analysis of SPG exists for nonconvex optimization with a nonsmooth and nonconvex regularizer. All existing nonasymptotic analysis of SPG for solving nonsmooth nonconvex problems require the nonsmooth regularizer to be a convex function, and hence are not applicable to a nonsmooth nonconvex regularized problem. This work initiates the analysis to bridge this gap and opens the door to nonasymptotic convergence analysis of nonsmooth nonconvex regularized problems. We analyze several variants of minibatch SPG methods for minimizing a nonconvex objective that consists of a smooth nonconvex loss and a nonsmooth nonconvex regularizer. Our contributions are twofold: (i) we show that they enjoy the same complexities as their counterparts for solving convex regularized nonconvex problems in terms of finding an approximate stationary point; (ii) we develop more practical variants using dynamic minibatch size instead of a fixed minibatch size without requiring the target accuracy level of solution. The significance of our results is that they improve upon thestateofart results for solving nonsmooth nonconvex regularized problems. We also empirically demonstrate the effectiveness of the considered SPG methods in comparison with other peer stochastic methods.