Self-concordant analysis for logistic regression

By Francis R. Bach. 2009

235 citations recorded by the source corpus.

Most of the non-asymptotic theoretical work in regression is carried out for the square loss, where estimators can be obtained through closed-form expressions. In this paper, we use and extend tools from the convex optimization literature, namely self-concordant functions, to provide simple extensions of theoretical results for the square loss to the logistic loss. We apply the extension techniques to logistic regression with regularization by the $\ell_2$-norm and regularization by the $\ell_1$-norm, showing that new results for binary classification through logistic regression can be easily derived from corresponding results for least-squares regression.

Subfields: Computational Mechanics, Statistics and Probability, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

In Mathematical Optimization

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “Functions in this (generalized) class include common losses such as the Huber loss (Marteau-Ferey et al., 2019), smoothed hinge loss (Zhang and Lin, 2015), and the logistic loss (Bach et al., 2010).”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, background): “Assumption(B3) is satisfied for the logistic loss and extends to all generali zed linear models (see more details in [22]), and the relationship between the thir d derivative and second derivative of the lossl is often referred to aself-concordance(see [9, 25] and references therein).”
Supplementary Appendix for"Inference on Treatment Effects After Selection Amongst High-Dimensional Controls" (2013, neutral): “In case of the logistic link Λ, Lasso for logistic regression is as defined in van de Geer (2008) and Bach (2010), and the associated post-Lasso estimators are as those defined in Belloni, Chernozhukov, and Wei (2013).”
Computational Optimal Transport (2018, background): “, 2013]), which are generalizations of self-concordance; see [Bach, 2010].”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, neutral): “Using equation (7) and the assumption on ϕ, we have ∣∣uT (ℓ′′′(w)[u])u ∣∣ ≤ 1 N N∑ i=1 ∣∣ϕ′′′(yiwTxi)(yiuTxi)3 ∣∣ (i) ≤ Q N N∑ i=1 ( (uTxi) 2ϕ′′(yiw Txi) )1−α (B‖u‖2)1+2α (ii) ≤ B1+2αQ ( 1 N N∑ i=1 (uTxi) 2ϕ′′(yiw Txi) )1−α (‖u‖2)1+2α (iii) ≤ B1+2αQ ( uT ℓ′′(w)u )1−α (‖u‖2)1+2α.”
Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients (2018, methodology): “(a) Logistic regression: The loss function f(x) = log(1+ e) is shown to be 1-quasi-self concordant in [3], and so is exp(D)-stable.”
Fast Randomized Kernel Ridge Regression with Statistical Guarantees (2015, result): “One natural unanswered question is whether it is possible to further reduce the sampling complexity, or is the effective dimensionality also a lower bound on p? And as pointed out by previous work [22, 3], it is likely that the same results hold for smooth losses beyond the squared loss (e.”
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging (2016, methodology): “A more recent line of work [16, 9, 10, 11, 17, 18, 1] has provided rigorous non-asymptotic analysis (with explicit constants) of SGD for stochastic approximation problems including linear and logistic regression.”
Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression (2013, methodology): “(A2) Generalized self-concordance of f (Bach, 2010): for all θ 1 , θ 2 ∈ H , the function (cid:2) (cid”
1-Bit Matrix Completion (2012, background): “A similar theory is available for the closely related problem of sparse binomial regression, which considers more classical statistical models [2,11,34,46,48,52,54,65] and allows non-Gaussian measurements.”
A General Theory of Hypothesis Tests and Confidence Regions for Sparse High Dimensional Models (2014, methodology): “This is accomplished by utilizing a more refined self-concordance property for logistic regressions [1].”
Improved Optimistic Algorithms for Logistic Bandits (2020, methodology): “The proof is based on the generalized self-concordance property of the logistic loss, which is detailed and exploited in other works on the logistic regression (Bach et al., 2010).”
Hessian-CoCoA : a general parallel and distributed framework for non-strongly convex regularizers (2017, methodology): “α(t+1) = α(t) + γ arg min ∆α∈Rn { f (v(t)) +∇ f (v(t))>A∆α + σ′ C 2τ ∆α> A > [1]A[1] 0 .”
Finite-sample Analysis of M-estimators using Self-concordance (2018, methodology): “Second, we can address some common losses in robust estimation, which turn out to be pseudo self-concordant in the sense of [2].”
Program evaluation with high-dimensional data (2013, background): “Our result builds upon the work of Belloni and Chernozhukov (2011b) who provided rates of convergence for variable selection when one is interested in estimating the quantile regression process with exogenous variables.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “In this paper, we argue that the three reasons above for not using Newton method can be circumvented to obtain competitive algorithms: (1) high absolute precisions are indeed not needed for machine learning, but faced with strongly ill-conditioned problems, even a low-precision solution requires sec”
Program evaluation and causal inference with high-dimensional data (2013, background): “Our work also contributes to the line of research on obtaining √ n-consistent and asymptotically normal estimates for low-dimensional components within traditional semiparametric frameworks as in the important work by Bickel (1982), Robinson (1988), Newey (1990), van der Vaart (1991), Andrews (1994b”