maximization

Introduction
============

Non-convex optimization is ubiquitous in machine learning. For example, data clustering [@kmeans; @kmeans:plusplus], training classifiers with latent variables [@yu09; @dpm; @Pirsiavash14; @glvm],and training visual object detectors from weakly labeled data [@Hyun14; @Rastegari15; @Ries15] all lead to non-convex optimization problems.

Majorization-Minimization (MM) [@mm] is an optimization framework for designing well-behaved optimization algorithms for non-convex functions. MM algorithms work by iteratively optimizing a sequence of easy-to-optimize surrogate functions that bound the objective. Two of the most successful instances of MM algorithms are Expectation-Maximization (EM) [@em] and the Concave-Convex Procedure (CCCP) [@cccp]. However, both have a number of drawbacks in practice, such as sensitivity to initialization and lack of uncertainty modeling for latent variables. This has been noted in works such as [@gen_em; @dpm; @naderi12; @kumar12; @ping14].

We propose a new procedure, *Generalized Majorization-Minimization ([G-MM]{})*, for optimizing non-convex objective functions. Our approach is inspired by MM, but we generalize the bound construction process. Specifically, we relax the strict bound construction method in MM to allow for a *set* of valid bounds to be used, while still maintaining algorithmic convergence. This relaxation gives us more freedom in bound selection and can be used to design better optimization algorithms.

In training latent 