BREGMAN PROXIMAL ALGORITHMS FOR COMPOSITE AND FINITE-SUM NONCONVEX MINIMIZATION PROBLEMS

The employment of Bregman divergences in splitting algorithms has been growing in popularity in the last few years. Firstly, the extra degree of freedom in the metric selection can lead to new algorithms or may provide new insights on known ones. Secondly, while many classical such schemes are bound to Lipschitz differentiability requirements (especially in the nonconvex setting), the recently introduced notion of ``relative smoothness'' has considerably widened the range of problems that can be addressed. / This talk deals with Bregman proximal algorithms in the fully nonconvex setting. The employment of the Bregman Moreau envelope as Lyapunov function leads to extremely simple and intuitive converge analyses that naturally extend to block-coordinate variants. Furthermore, continuity of the envelope allows one to design linesearch-type extensions that preserve oracle complexity and convergence properties of first-order (Bregman) splitting schemes, and yet can attain up to superlinear asymptotic rates when directions of quasi-Newton type are selected.