Stochastic Variance Reduced Primal Dual Algorithms for Empirical Composition Optimization
From MaRDI portal
Publication:6322473
arXiv1907.09150MaRDI QIDQ6322473
Author name not available (Why is that?)
Publication date: 22 July 2019
Abstract: 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.
Has companion code repository: https://github.com/adidevraj/SVRPDA
This page was built for publication: Stochastic Variance Reduced Primal Dual Algorithms for Empirical Composition Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6322473)
