  Despite the rise to fame of incremental variance-reduced methods in recent
years, their use in nonsmooth optimization is still limited to few simple
cases. This is due to the fact that existing methods require to evaluate the
proximity operator for the nonsmooth terms, which can be a costly operation for
complex penalties. In this work we introduce two variance-reduced incremental
methods based on SAGA and SVRG that can efficiently take into account complex
penalties which can be expressed as a sum of proximal terms. This includes
penalties such as total variation, group lasso with overlap and trend
filtering, to name a few. Furthermore, we also develop sparse variants of the
proposed algorithms which can take advantage of sparsity in the input data.
Like other incremental methods, it only requires to evaluate the gradient of a
single sample per iteration, and so is ideally suited for large scale
applications. We provide a convergence rate analysis for the proposed methods
and show that they converge with a fixed step-size, achieving in some cases the
same asymptotic rate as their full gradient variants. Empirical benchmarks on 3
different datasets illustrate the practical advantages of the proposed methods.
