Stochastic Variance Reduced Primal Dual Algorithms for Empirical
  Composition Optimization
  We consider a generic empirical composition optimization problem, where there
are empirical averages present both outside and inside nonlinear loss
functions. Such a problem is of interest in various machine learning
applications, and cannot be directly solved by standard methods such as
stochastic gradient descent. We take a novel approach to solving this problem
by reformulating the original minimization objective into an equivalent min-max
objective, which brings out all the empirical averages that are originally
inside the nonlinear loss functions. We exploit the rich structures of the
reformulated problem and develop a stochastic primal-dual algorithm, SVRPDA-I,
to solve the problem efficiently. We carry out extensive theoretical analysis
of the proposed algorithm, obtaining the convergence rate, the computation
complexity and the storage complexity. In particular, the algorithm is shown to
converge at a linear rate when the problem is strongly convex. Moreover, we
also develop an approximate version of the algorithm, named SVRPDA-II, which
further reduces the memory requirement. Finally, we evaluate our proposed
algorithms on several real-world benchmarks, and experimental results show that
the proposed algorithms significantly outperform existing techniques.
