Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods

Logistic regression is one of the most popular methods in binary\nclassification, wherein estimation of model parameters is carried out by\nsolving the maximum likelihood (ML) optimization problem, and the ML estimator\nis defined to be the optimal solution of this problem. It is well known that\nthe ML estimator exists when the data is non-separable, but fails to exist when\nthe data is separable. First-order methods are the algorithms of choice for\nsolving large-scale instances of the logistic regression problem. In this\npaper, we introduce a pair of condition numbers that measure the degree of\nnon-separability or separability of a given dataset in the setting of binary\nclassification, and we study how these condition numbers relate to and inform\nthe properties and the convergence guarantees of first-order methods. When the\ntraining data is non-separable, we show that the degree of non-separability\nnaturally enters the analysis and informs the properties and convergence\nguarantees of two standard first-order methods: steepest descent (for any given\nnorm) and stochastic gradient descent. Expanding on the work of Bach, we also\nshow how the degree of non-separability enters into the analysis of linear\nconvergence of steepest descent (without needing strong convexity), as well as\nthe adaptive convergence of stochastic gradient descent. When the training data\nis separable, first-order methods rather curiously have good empirical success,\nwhich is not well understood in theory. In the case of separable data, we\ndemonstrate how the degree of separability enters into the analysis of $\\ell_2$\nsteepest descent and stochastic gradient descent for delivering\napproximate-maximum-margin solutions with associated computational guarantees\nas well. This suggests that first-order methods can lead to statistically\nmeaningful solutions in the separable case, even though the ML solution does\nnot exist.\n