Duality and Auxiliary Functions for Bregman Distances

Abstract : In this paper, the authors formulate and prove a convex duality theorem for minimizing a general class of Bregman distances subject to linear constraints. The duality result is then used to derive iterative algorithms for solving the associated optimization problem. Their presentation is motivated by the recent work of Collins, Schapire, and Singer (2001), who showed how certain boosting algorithms and maximum likelihood logistic regression can be unified within the framework of Bregman distances. In particular, specific instances of the results given here are used by Collins et al. (2001) to show the convergence of a family of iterative algorithms for minimizing the exponential or logistic loss. Following an introduction, Section 2 recalls the standard definitions from convex analysis that will be required, and presents the technical assumptions made on the class of Bregman distances that the authors work with. They also introduce some new terminology, using the terms Legendre-Bregman conjugate and Legendre-Bregman projection to extend the classical notion of the Legendre conjugate and transform to Bregman distances. Section 3 contains the statement and proof of the duality theorem that connects the primal problem with its dual, showing that the solution is characterized in geometrical terms by a Pythagorean equality. Section 4 defines the notion of an auxiliary function, which is used to construct iterative algorithms for solving constrained optimization problems. This section shows how convexity can be used to derive an auxiliary function for Bregman distances based on separable functions. The last section summarizes the main results of the paper.