Bregman method

The Bregman method is an iterative algorithm to solve certain convex optimization problems involving regularization. The original version is due to Lev M. Bregman, who published it in 1967¹. The algorithm is a row-action method accessing constraint functions one by one and the method is particularly suited for large optimization problems where constraints can be efficiently enumerated . The algorithm works particularly well for regularizers such as the \ell_1 norm, where it converges very quickly because of an error-cancellation effect.

The Bregman method is an iterative algorithm to solve certain convex optimization problems involving regularization. The original version is due to Lev M. Bregman, who published it in 1967. The algorithm is a row-action method accessing constraint functions one by one and the method is particularly suited for large optimization problems where constraints can be efficiently enumerated . The algorithm works particularly well for regularizers such as the \ell_1 norm, where it converges very quickly because of an error-cancellation effect. The Bregman distance is defined as D^p(u, v) := J(u) - (J(v) + \langle p, u - v\rangle) where p belongs to the subdifferential of J at u (which we denoted \partial J(u) ). One performs the iteration u_{k + 1}:= \min_u(\alpha D(u, u_k) + f(u)) , with \alpha a constant to be chosen by the user (and the minimization performed by an ordinary convex optimization algorithm), or u_{k + 1}:= \min_u(D^{p_k}(u, u_k) + f(u)) , with p_k chosen each time to be a member of \partial J(u_k) . The algorithm starts with a pair of primal and dual variables. Then, for each constraint a generalized projection onto its feasible set is performed, updating both the constraint's dual variable and all primal variables for which there are non-zero coefficients in the constraint functions gradient. In case the objective is strictly convex and all constraint functions are convex, the limit of this iterative projection converges to the optimal primal dual pair. In the case of a basis pursuit-type problem \min_{x: Ax = b}(|x|_1 + \frac{1}{2\alpha}|x|_2^2) , the Bregman method is equivalent to ordinary gradient descent on the dual problem \min_y (-b^t y + \frac{\alpha}{2}|A^t y - \text{Proj}_{[-1, 1]^n}(A^t y)|^2) . An exact regularization-type effect also occurs in this case; if \alpha exceeds a certain threshold, the optimum value of x is precisely the optimum solution of \min_{x: Ax = b}|x|_1 . In the Linearized Bregman method, one linearizes the intermediate objective functions D^p(u, u_k) + f(u) by replacing the second term with f(u_k) + \langle f'(u_k), u - u_k\rangle (which approximates the second term near u_k ) and adding the penalty term \frac{1}{2\delta}|u - u_k|_2^2 for a constant \delta . The result is much more computationally tractable, especially in basis pursuit-type problems. In the case of a generic basis pursuit problem \min \mu|u|_1 + \frac{1}{2}|Au - f|_2^2 , one can express the iteration as v_{k + 1} := v_k + A^t(f - Au_k), u_{k + 1, i} := \delta~\text{shrink}(v_{k, i}, \mu) for each component i , where we define \text{shrink}(y, a) := \begin{cases} y - a, & y\in(a,\infty) \\ 0, &y\in[-a, a]\\ y + a, & y\in(-\infty, -a) \end{cases} . Sometimes, when running the Linearized Bregman method, there are periods of "stagnation" where the residual is almost constant. To alleviate this issue, one can use the Linearized Bregman method with kicking, where one essentially detects the beginning of a stagnation period, then predicts and skips to the end of it. Since Linearized Bregman is mathematically equivalent to gradient descent, it can be accelerated with methods to accelerate gradient descent, such as line search, L-BGFS, Barzilai-Borwein steps, or the Nesterov method; the last has been proposed as the accelerated linearized Bregman method. The Split Bregman method solves problems of the form \min_u |\Phi(u)|_1 + H(u) , where \Phi and H are both convex, particularly problems of the form \min_u |\Phi u|_1 + |Ku - f|^2 . We start by rewriting it as the constrained optimization problem \min_{u: d = \Phi(u)} |d|_1 + H(u) , then relax it into \min_{u, d} |d|_1 + H(u) + \frac{\lambda}{2}|d - \Phi(u)|_2^2 where \lambda is a constant. By defining J(u, d) := |d| + H(u) , one reduces the problem to one that can be solved with the ordinary Bregman algorithm. The Split Bregman method has been generalized to optimization over complex numbers using Wirtinger derivatives.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1346044071 under CC BY-SA 4.0; modifications have been made.