  We introduce two algorithms for nonconvex regularized finite sum
minimization, where typical Lipschitz differentiability assumptions are relaxed
to the notion of relative smoothness. The first one is a Bregman extension of
Finito/MISO, studied for fully nonconvex problems when the sampling is
randomized, or under convexity of the nonsmooth term when it is essentially
cyclic. The second algorithm is a low-memory variant, in the spirit of SVRG and
SARAH, that also allows for fully nonconvex formulations. Our analysis is made
remarkably simple by employing a Bregman Moreau envelope as Lyapunov function.
In the randomized case, linear convergence is established when the cost
function is strongly convex, yet with no convexity requirements on the
individual functions in the sum. For the essentially cyclic and low-memory
variants, global and linear convergence results are established when the cost
function satisfies the Kurdyka-\L ojasiewicz property.
