- Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization Filip Hanzely(filip.hanzelykaust.edu.sa) Peter Richtarik(peter.richtarikkaust.edu.sa) Lin Xiao(lin.xiaomicrosoft.com) Abstract: We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. The relatively smooth condition is much weaker than the standard assumption of uniform Lipschitz continuity of the gradients, thus significantly increases the scope of potential applications. We present accelerated Bregman proximal gradient (ABPG) methods that employ the Bregman distance of the reference function as the proximity measure. These methods attain an $O(k^{-\gamma})$ convergence rate in the relatively smooth setting, where $\gamma\in [1,2]$ is determined by a triangle scaling property of the Bregman distance. We develop adaptive variants of the ABPG method that automatically ensure the best possible rate of convergence and argue that the $O(k^{-2})$ rate is attainable in most cases. We present numerical experiments with three applications: D-optimal experiment design, Poisson linear inverse problem, and relative-entropy nonnegative regression. In all experiments, we obtain numerical certificates showing that these methods do converge with the $O(k^{-2})$ rate. Keywords: accelerated gradient method, convex optimization, relatively smooth, Bregman distance, proximal gradient method Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Nonlinear Optimization Citation: Microsoft Research Technical Report: MSR-TR-2018-22 Download: [PDF]Entry Submitted: 08/09/2018Entry Accepted: 08/09/2018Entry Last Modified: 08/09/2018Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.