Convexity , Surrogate Functions and Iterative Optimization in Multi-class Logistic Regression Models
Abstract. In this paper, we propose a family of surrogate maximization (SM) algorithms for multi-class logistic regression models (also called conditional exponential models). An SM algorithm aims at turning an otherwise intractable maximization problem into a tractable one by iterating two steps. The S-step computes a tractable surrogate function to substitute the original objective function, and the M-step seeks to maximize this surrogate function. We apply SM algorithms to logistic regression models, leading to the standard SM, generalized SM, gradient SM, and quadratic SM algorithms. Compared with Newton’s method, these SM algorithms dramatically save computational costs when either the dimensionality or number of data samples is huge. Finally, we demonstrate the efficacy of these SM algorithms and compare their empirical performance on text categorization.