  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 random,
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.
