Variance Reduction via Primal-Dual Accelerated Dual Averaging
            for Nonsmooth Convex Finite-Sums

               Chaobing Song 1 Stephen J. Wright 1 Jelena Diakonikolas 1

            Abstract                vectors with n typically large; gi : R ! R, i = 1, 2, . . . , n,
                                be possibly nonsmooth convex loss functions associated
   Structured nonsmooth convex finite-sum opti-
                                with the linear predictor hbi , xi; and ` : Rd ! R ...