Abstract
We consider the problem of minimizing the sum of an average function of alarge number of smooth convex components and a general, possiblynon-differentiable, convex function. Although many methods have been proposedto solve this problem with the assumption that the sum is strongly convex, fewmethods support the non-strongly convex case. Adding a small quadraticregularization is a common trick used to tackle non-strongly convex problems;however, it may cause loss of sparsity of solutions or weaken the performanceof the algorithms. Avoiding this trick, we propose an accelerated randomizedmirror descent method for solving this problem without the strongly convexassumption. Our method extends the deterministic accelerated proximal gradientmethods of Paul Tseng \cite{Tseng} and can be applied even when proximal pointsare computed inexactly. We also propose a scheme for solving the problem whenthe component functions are non-smooth.