Search

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 [A. Defazio and J. Domke, Proc. Mach. Learn. Res. (PMLR), 32 (2014), pp. 1125-1133; J. Mairal, SIAM J. Optim., 25 (2015), pp. 829-855], 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 [R. Johnson and T. Zhang, Advances in Neural Information Processing Systems 26, Curran Associates, Red Hook, NY, 2013, pp. 315-323] and SARAH [L. M. Nguyen et al., Proc. Mach. Learn. Res. (PMLR), 70 (2017), pp. 2613-2621], that also allows for fully nonconvex formulations. Our analysis is made remarkably simple by employing a Bregman-Moreau envelope as the 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-Łojasiewicz property. [ABSTRACT FROM AUTHOR]

We introduce BELLA, a locally superlinearly convergent Bregman forward-backward splitting method for minimizing the sum of two nonconvex functions, one of which satisfies a relative smoothness condition and the other one is possibly nonsmooth. A key tool of our methodology is the Bregman forward-backward envelope (BFBE), an exact and continuous penalty function with favorable first- and second-order properties, which enjoys a nonlinear error bound when the objective function satisfies a Lojasiewicz-type property. The proposed algorithm is of linesearch type over the BFBE along user-defined update directions and converges subsequentially to stationary points and globally under the Kurdyka--Lojasiewicz condition. Moreover, when the update directions are superlinear in the sense of Facchinei and Pang [Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I, Springer, New York, 2003], owing to the given nonlinear error bound unit stepsize is eventually always accepted and the algorithm attains superlinear convergence rates even when the limit point is a nonisolated minimum. [ABSTRACT FROM AUTHOR]

Although originally designed and analyzed for convex problems, the alternating direction method of multipliers (ADMM) and its close relatives, Douglas–Rachford splitting (DRS) and Peaceman–Rachford splitting (PRS), have been observed to perform remarkably well when applied to certain classes of structured nonconvex optimization problems. However, partial global convergence results in the nonconvex setting have only recently emerged. In this paper we show how the Douglas–Rachford envelope, introduced in 2014, can be employed to unify and considerably simplify the theory for devising global convergence guarantees for ADMM, DRS, and PRS applied to nonconvex problems under less restrictive conditions, larger prox-stepsizes, and overrelaxation parameters than previously known. In fact, our bounds are tight whenever the overrelaxation parameter ranges in (0, 2]. The analysis of ADMM uses a universal primal equivalence with DRS that generalizes the known duality of the algorithms. [ABSTRACT FROM AUTHOR]