  


Condition Number Analysis of Logistic Regression, and its Implications for Standard FirstOrder Solution Methods
Robert M. Freund(rfreundmit.edu) Abstract: Logistic regression is one of the most popular methods in binary classification, wherein estimation of model parameters is carried out by solving the maximum likelihood (ML) optimization problem, and the ML estimator is defined to be the optimal solution of this problem. It is well known that the ML estimator exists when the data is nonseparable, but fails to exist when the data is linearly separable. Firstorder methods are the algorithms of choice for solving largescale instances of the logistic regression problem. In this paper, we introduce a pair of condition numbers that measure the degree of nonseparability or separability of a given dataset in the setting of binary classification, and we study how these condition numbers relate to and inform the properties and the convergence guarantees of firstorder methods. When the training data is nonseparable, we show that the degree of nonseparability naturally enters the analysis and informs the properties and convergence guarantees of two standard firstorder methods: steepest descent (for any given norm) and stochastic gradient descent. Expanding on the work of Bach, we also show how the degree of nonseparability enters into the analysis of linear convergence of steepest descent (without needing strong convexity), as well as the adaptive convergence of stochastic gradient descent. When the training data is separable, firstorder methods rather curiously have good empirical success  a behavior that is not well understood in theory. In the case of separable data, we demonstrate how the degree of separability enters into the analysis of $\ell_2$ steepest descent and stochastic gradient descent for delivering approximatemaximummargin solutions with associated computational guarantees as well. This suggests that firstorder methods can lead to statistically meaningful solutions in the separable case, even though the ML solution does not exist. Keywords: steepest descent, stochastic gradient descent, condition numbers, logistic regression Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Applications  Science and Engineering (Statistics ) Category 3: Applications  Science and Engineering (DataMining ) Citation: Download: [PDF] Entry Submitted: 10/19/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  