The Concave-Convex Procedure (CCCP)

Abstract

The Concave-Convex procedure (CCCP) is a way to construct discrete time it-erative dynamical systems which are guaranteed to monotonically decrease global optimization/energy functions. This procedure can be applied to almost any op-timization problem and many existing algorithms can be interpreted in terms of it. In particular, we prove that all EM algorithms and classes of Legendre min-imization and variational bounding algorithms can be re-expressed in terms of CCCP. We show that many existing neural network and mean field theory al-gorithms are also examples of CCCP. The Generalized Iterative Scaling (GIS) algorithm and Sinkhorn’s algorithm can also be expressed as CCCP by changing variables. CCCP can be used both as a new way to understand, and prove con-vergence of, existing optimization algorithms and as a procedure for generating new algorithms.