Weaknesses: - Distinction between F and constituent f_i being convex or strongly convex: why does this matter in practice? In the general learning case, f_i(x) is usually of the form f(x, \xi_i) where \xi_i is the i-th scenario or data. So, many common properties like smoothness, convexity etc. are naturally assumed to "flow" from f to the sample/population average F. What practical scenario do you envision where f_i could be distinct functional forms that are not convex but F is? where would an example like this make sense: f_1 (x) -x 2 (concave), f_2 (x) 2x 2 leading to F(x) x 2 (convex)? Is there any guarantee that doing something like projecting all iterates on to your \cal{S}_{x_0} set (defined on pg 3 of the supplement) to enforce this assumption will not lead to sub optimal results? How does your analysis of the progress made in the shuffled SGD steps compare to progress that would have been made w.r.t epoch count K using deterministic full gradient descent with a proper step-length determination like Armijo rule?

We study without-replacement SGD for solving finite-sum optimization problems. Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) algorithms. First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors. Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.

We study without-replacement SGD for solving finite-sum optimization problems. Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) algorithms. First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors. Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.