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 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 … Read more

Convexity Conditions and the Legendre-Fenchel Transform for the Product of Finitely Many Positive Definite Quadratic Forms

While the product of finitely many convex functions has been investigated in the field of global optimization, some fundamental issues such as the convexity condition and the Legendre-Fenchel transform for the product function remain unresolved. Focusing on quadratic forms, this paper is aimed at addressing the question: \emph{When is the product of finitely many positive … Read more

Algebraic Tail Decay of Condition Numbers for Random Conic Systems under a General Family of Input Distributions

We consider the conic feasibility problem associated with linear homogeneous systems of inequalities. The complexity of iterative algorithms for solving this problem depends on a condition number. When studying the typical behaviour of algorithms under stochastic input one is therefore naturally led to investigate the fatness of the distribution tails of the random condition number … Read more

Unifying Condition Numbers for Linear Programming

In recent years, several condition numbers were defined for a variety of linear programming problems based upon relative distances to ill-posedness. In this paper we provide a unifying view of these condition numbers. To do so, we introduce yet another linear programming problem and show that its distance to ill-posedness naturally captures the most commonly … Read more

A characterization of the distance to infeasibility under block-structured perturbations

We discuss several generalizations of the classical Eckart and Young identity. We show that a natural extension of this identity holds for rectangular matrices defining conic systems of constraints, and for perturbations restricted to a particular block structure, such as those determined by a sparsity pattern. Our results extend and unify the classical Eckart and … Read more