We introduce a pair of condition numbers associated with the sample data for logistic regression that measures the degree of separability or non-separability of the data sample. When the sample data is not separable (as is routinely the case in logistic regression), the degree of non-separability naturally enters the analysis and the computational properties of standard first-order methods such as steepest descent, greedy coordinate descent, stochastic gradient descent, etc. When the sample data is separable -- in which case the logistic regression problem has no solution -- the degree of separability can be used to show rather surprisingly that standard first order methods also deliver approximate-maximum-margin solutions with associated computational guarantees as well. The guarantees we develop hold for any dataset. This is joint work with Paul Grigas and Rahul Mazumder.
Robert Freund is the Theresa Seley Professor in Management Science at the Sloan School of Management at MIT. His main research interests are in convex optimization, computational complexity and related computational science, convex geometry, large-scale nonlinear optimization, and related mathematical systems. He received his B.A. in Mathematics from Princeton University and M.S. and Ph.D. degrees in Operations Research at Stanford University. He has served as Co-Editor of the journal Mathematical Programming and Associate Editor of several optimization and operations research journals. He is the former Co-Director of MIT Operations Research Center, the MIT Program in Computation for Design and Optimization, and the former Chair of the INFORMS Optimization Section, and former Deputy Dean of the Sloan School at MIT (2008-11). He received the Longuet-Higgins Prize in computer vision (2007) as well as numerous teaching and education awards at MIT in conjunction with the course and textbook (co-authored with Dimitris Bertsimas) Data, Models, and Decisions: the Fundamentals of Management Science.