PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-concordant analysis for logistic regression

Francis Bach

arXiv:0910.4627v1cs.LGmath.ST

TL;DR

Non-asymptotic analysis is simpler for square-loss regression because estimators have closed-form expressions, whereas logistic-loss analysis requires local approximations. This paper extends self-concordant analysis to logistic regression and applies it to ℓ2- and ℓ1-regularization, enabling simple extensions of least-squares results without added complex assumptions.

  • Problem

    Non-asymptotic theoretical results are harder for logistic loss than square loss because logistic estimators generally lack closed-form solutions.

  • Method

    The paper introduces an extension of self-concordant functions, proves global Taylor bounds and Newton-method results, and applies them to regularized logistic regression.

  • Results

    The techniques extend least-squares theoretical results to logistic regression with ℓ2- and ℓ1-regularization, including model consistency and prediction efficiency results.

  • Takeaways & Limitations

    New theoretical results for binary classification through logistic regression can be derived from corresponding least-squares results without added complex assumptions.

  • Takeaways & Limitations

    The analysis could be extended to other logistic-regression settings, sparsity-inducing norms, and resampling-based procedures.

Abstract

from arXiv · show

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.

1 Introduction

Non-asymptotic analysis is simplest for square-loss regression because its quadratic objective yields closed-form estimators. The paper develops self-concordance-based tools to extend similarly simple analyses to logistic regression with ℓ2- and ℓ1-regularization.

  • Motivation: Quadratic objectives make square-loss regression estimators available in closed form, greatly simplifying theoretical analysis.For nonquadratic M-estimation objectives, local approximations and additional derivative-related assumptions complicate sharp non-asymptotic results.
  • Motivation: Self-concordant functions simplify Newton analyses by controlling third derivatives through second derivatives.The paper uses this optimization perspective for statistical analysis rather than solving the optimization problems themselves.
  • Contribution: The paper introduces a modified self-concordance framework with globally upper- and lower-bounding Taylor expansions and Newton-method guarantees.These tools support non-asymptotic local quadratic analysis without complex additional assumptions.
  • Applications: The techniques are applied to ℓ2-regularized logistic regression under both unrestricted conditional distributions and well-specified models.The well-specified setting includes asymptotic generalization-performance expansions with explicit remainder bounds.
  • Applications: For ℓ1-regularization, the paper extends results on model consistency and prediction efficiency from square-loss regression to logistic regression.Additional Bernstein-like concentration inequalities for quadratic forms of bounded random variables support close correspondence with least-squares results.

2 Taylor expansions and Newton’s method

The paper generalizes self-concordant analysis to convex functions whose third derivatives obey a different curvature-dependent bound. This yields global Taylor controls and Newton-method guarantees while retaining a need for a non-uniform Hessian lower bound.

  • Classical self-concordance: Self-concordance controls third derivatives by the 3/2 power of the second derivative and supports Taylor and Newton-method bounds.These classical results include convergence and error guarantees when the Newton decrement is sufficiently small.
  • Modified framework: The logistic loss is not self-concordant because its third derivative is bounded by a constant times its second derivative instead.The paper therefore develops an alternative third-derivative control tailored to logistic loss.
  • Modified framework: Under |g′′′(t)| ≤ R∥v∥2 × g′′(t), the new framework provides upper and lower second-order Taylor expansions valid globally in the displacement.The remainder accounts for local curvature rather than growing as a generic third-order polynomial.
  • Newton’s method: The same derivative control yields Newton-method results analogous to self-concordant guarantees, provided the Hessian has a positive smallest eigenvalue and the decrement is sufficiently small.The framework extends the error and one-step Newton bounds used in classical analysis.
  • Scope: Unlike regular self-concordance, the modified notion is not affine-invariant and still requires a non-uniform lower Hessian bound.These limitations define the conditions under which the technical extension applies.

3 Application to logistic regression

The paper applies its modified Taylor and Newton analysis to fixed-design logistic regression, using the logistic loss’s curvature relationship to control one-step Newton iterates. The resulting framework targets both unregularized and regularized statistical analyses under explicit modeling settings.

  • Setup: Logistic regression is formulated for fixed design points x_i and independent binary outputs y_i ∈ {−1, 1}.The paper allows outputs to be independent without requiring identical distributions.
  • Logistic loss: The logistic loss satisfies |ℓ′′′(u)| ≤ ℓ′′(u), enabling the modified third-derivative framework to apply to its empirical cost.The cost is proportional to the negative conditional log-likelihood under the logistic model.
  • Newton approximation: The analysis studies one-step Newton iterates from population-defined vectors and uses them to approximate empirical global minimizers or regularized minimizers.This links the local quadratic approximation to the statistical estimators analyzed in the paper.
  • Modeling: The well-specified model assumes a vector w0 generating each conditional output distribution through the sigmoid function.Under this model, the conditional mean and variance correspond to derivatives of the logistic loss.
  • Evaluation: Generalization performance is measured by J0(w), corresponding under well specification to average Kullback–Leibler divergence to the best model.Classification performance under 0–1 loss is outside the paper’s scope.
  • Modeling: Unlike analyses requiring strong convexity of the logistic loss on a compact domain, this approach does not require a uniform positive lower bound on its second derivative.The paper attributes this to its finer control of the third derivative, even when the conventional lower bound becomes very small.

4 Regularization by the ℓ2-norm

The paper extends logistic-regression analysis to ℓ2-regularized estimators using self-concordant tools, covering misspecified and well-specified models, risk estimation, and links to kernel methods.

  • 4.1 Reproducing kernel Hilbert spaces and splines: ℓ2-regularized logistic regression has a unique global minimizer, whose generalization performance is analyzed under minimal assumptions and under well-specified models.The analysis also connects linear logistic regression to spline and RKHS methods through the representer theorem.
  • 4.2 Minimal assumptions (misspecified model): Under only bounded covariates and independent outputs, the analysis yields an oracle inequality with the slow rate n^-1/2 when the population minimum is attained.These assumptions do not require a well-specified logistic model.
  • 4.3 Well-specified models: The well-specified analysis provides non-asymptotic upper and lower bounds with explicit constants, extending asymptotic generalization expansions.The approach locally approximates the objectives around w0 using a one-step Newton iterate, subject to a small Newton decrement and an upper bound on κ.
  • 4.3 Well-specified models: Logistic regression has lower degrees of freedom than least-squares regression with λ multiplied by 4, reflecting reduced variance for nearly deterministic observations.The reduction is measured through the logistic degrees-of-freedom quantities based on the weighted Gram matrix Q.
  • 4.4 Smoothing parameter selection: A data-dependent criterion estimates generalization performance up to a λ-independent constant and can support data-driven selection of the regularization parameter.The theorem is further used to derive oracle inequalities for minimizing the criterion.
  • 4.4 Smoothing parameter selection: When the logistic model is well-specified, the procedure avoids estimating unknown noise variance, although estimating the matrix Q still requires dependence on w0.Generalized cross-validation is identified as a related criterion for future study.

5 Regularization by the ℓ1-norm

The paper extends square-loss results to logistic regression with ℓ1 regularization, addressing model consistency and predictive efficiency through weighted-Gram assumptions and self-concordant analysis.

  • 5 Regularization by the ℓ1-norm: The ℓ1-regularized logistic estimator extends recent square-loss results on model consistency and prediction efficiency.The section treats an estimator minimizing the empirical logistic risk plus λ∥w∥1 under a well-specified model.
  • 5 Regularization by the ℓ1-norm: The relevant design matrix is the weighted Gram matrix Q, which replaces the unweighted Gram matrix used for square loss.The paper considers assumptions on Q and notes that other assumptions could also be used.
  • 5.1 Model consistency condition: Model consistency is established under a strict condition involving ∥Q_KcK Q_KK^-1 s_K∥∞ < 1.The theorem gives a probability upper bound for the event that the estimated sign vector differs from sign(w0), under assumptions (A1)–(A4).
  • 5.1 Model consistency condition: The logistic-loss consistency result preserves the favorable scaling log p = O(n) for a suitable λ.Additional terms depending on the full-data radius R may be large, although bounds involving only relevant features could be derived.
  • 5.2 Efficiency: Under a restricted eigenvalue condition, ℓ1 regularization yields an estimation-error bound and an oracle inequality for generalization performance.The result directly mimics the corresponding square-loss theorem except for an added bound on λ.
  • 5.2 Efficiency: With λ selected at the stated logarithmic rate, the paper obtains J0(ŵλ) ≤ J0(w0) + 120 log p n^-1 |K|ρ^-2 with probability at least 1 − 2/p.The proof is described as a direct extension of the square-loss result with few additional assumptions.

6 Conclusion

The paper concludes that extended self-concordant tools transfer square-loss theory to logistic regression with ℓ2 and ℓ1 regularization, while identifying several directions for broader extensions.

  • 6 Conclusion: The proposed extension of self-concordant functions enables simple transfers of theoretical square-loss results to logistic loss.The authors emphasize that the resulting logistic-regression results require no added complex assumptions.
  • 6 Conclusion: The techniques are applied to both ℓ2- and ℓ1-regularized logistic regression.The conclusion frames these applications as showing that logistic-regression results can be derived from corresponding least-squares results.
  • 6 Conclusion: Future work includes sequential experimental design, other sparsity-inducing regularizers, non-parametric problems, and resampling-based procedures.The paper also points to generalized linear models beyond logistic regression and density estimation for exponential-family models.

A Proofs of optimization results

The proofs establish one-dimensional Taylor bounds from a third-derivative control condition and use them to support the paper’s optimization analysis.

  • A Proofs of optimization results: The proof strategy follows earlier Newton-method techniques while replacing the usual third-derivative control.The third derivative F′′′(w) is treated as a trilinear function, and the assumptions are shown equivalent to the required control condition.
  • A Proofs of optimization results: For convex three-times differentiable g with |g′′′(t)| ≤ Sg′′(t), Lemma 1 provides upper and lower Taylor expansions for t ≥ 0.The lemma is the central one-dimensional ingredient for obtaining bounds beyond ordinary local Taylor approximations.
  • A Proofs of optimization results: The proof derives exponential bounds on g′′ by integrating −S ≤ d log g′′(t)/dt ≤ S.The argument handles both strictly positive second derivatives and the identically zero case.
  • A Proofs of optimization results: Unlike a uniform third-derivative bound, the resulting lower bound does not decrease as rapidly as a third-order polynomial bound.The corresponding expression can also be interpreted as an upper bound on the Taylor remainder.
  • A Proofs of optimization results: The proofs use continuity and boundedness of auxiliary exponential-ratio functions on compact sets.These functions are extended continuously to the real line before compact-set bounds are applied.

A.2 Proof of Proposition 1

The proposition proof applies the one-dimensional derivative bounds along optimization directions to control Taylor remainders, Hessians, Newton steps, and minimizer existence.

  • A.2 Proof of Proposition 1: Applying the scalar lemma to F(w + tv) yields the multivariate Taylor inequalities used in the proposition.Taking t = 1 produces the first two inequalities, while applying the argument to a quadratic form controls Hessian variation.
  • A.2 Proof of Proposition 1: The Hessian quadratic form changes by exponential factors bounded through R∥v∥2 along a direction v.This gives the stated Hessian control for all vectors u.
  • A.2 Proof of Proposition 1: A remainder function h(t) isolates the error after subtracting the value, gradient, and Hessian terms at w.Its second derivative is bounded using the third derivative and the Hessian controls before integration.
  • A.2 Proof of Proposition 1: When λ(w) > 0, Hessian invertibility makes F strictly convex, so any attained minimum is unique.The proof later uses convexity and an ellipsoid argument to establish existence of a minimizer under the relevant conditions.
  • A.2 Proof of Proposition 1: An ellipsoid defined by v⊤F′′(w)v = 16ν(F,w)^2 has function value at least F(w), yielding a minimizer-distance bound by convexity.The argument normalizes directions so that v⊤F′′(w)v = 1 and then rescales them.
  • A.2 Proof of Proposition 1: The Newton step v = −F′′(w)^−1F′(w) is used to transfer the minimizer bound from w to w + v.The Newton decrement is controlled at the updated point through the Hessian variation inequality.

B Proof of Theorem 1

The proof controls the empirical regularized logistic estimator through the Newton decrement, then uses concentration to establish the required small-decrement condition with high probability.

  • B Proof of Theorem 1: The estimator and population minimizer are compared when the Newton decrement satisfies ν(ˆJλ, wλ)^2 < λ/(4R^2).Under this condition, the empirical and population regularized minimizers are close.
  • B Proof of Theorem 1: The argument applies an upper Taylor expansion to Jλ around wλ, using v = ˆwλ − wλ and the bound R∥v∥2 ⩽ 4Rν(ˆJλ,wλ).
  • B Proof of Theorem 1: Concentration inequalities are used to verify the Newton-decrement requirement for the empirical regularized risk.
  • B Proof of Theorem 1: For u ⩽ n/125, the proof obtains probability at least 1 − δ = 1 − 8e^−u.
  • B Proof of Theorem 1: For u > n/125, the bound is automatically satisfied because the chosen regularization parameter obeys λ ⩾ R^2.

C Proof of Theorem 2

The proof replaces the empirical logistic risk locally by its quadratic Taylor approximation and uses self-concordant Newton analysis to control estimator and risk behavior.

  • C Proof of Theorem 2: The quadratic approximation is formed around w0 using Q = J′′0(w0), while the one-step Newton iterate has a closed-form expression involving Q + λI.
  • C Proof of Theorem 2: The proposition permits replacing ˆJ0 by its Taylor expansion ˆJT0 for performance analysis when the Newton decrement is sufficiently small.
  • C Proof of Theorem 2: Proposition 3 assumes ν(ˆJλ,w0)^2 ⩽ λ/(4R^2) to establish the quadratic approximation of risks.
  • C Proof of Theorem 2: The proof bounds the relevant error terms using concentration inequalities and Bernstein’s inequality, then combines them with a union bound.
  • C Proof of Theorem 2: Under v ⩽ 1/4, κ ⩽ 1/16, and v^3(nb^2 + d^2)^1/2 ⩽ 12, the proof obtains a global upper bound on the error terms.

E Proof of Theorem 4

The proof establishes ℓ1-regularized logistic guarantees by analyzing a restricted one-step Newton iterate, verifying correct active-set signs and the gradient condition off the support.

  • E Proof of Theorem 4: The restricted minimizer ˜w is constructed with wKc = 0, and optimality requires correct signs on K plus an ℓ∞ gradient bound on Kc.
  • E Proof of Theorem 4: A one-step Newton iterate is used to replace the restricted minimizer while preserving the conditions needed for unrestricted ℓ1 optimality.
  • E Proof of Theorem 4: The proof applies the self-concordant Newton result to the function restricted to active coordinates K.
  • E Proof of Theorem 4: The resulting estimator has the correct signs for covariates indexed by K when the displacement from w0 is sufficiently controlled.
  • E Proof of Theorem 4: The bounds may use the maximal ℓ2-norm of data points after reduction to variables in K.
  • E Proof of Theorem 4: The off-support gradient condition is controlled using concentration inequalities and Bernstein’s inequality under the stated assumptions.

G Concentration inequalities

This section develops concentration inequalities for quadratic forms of bounded random variables and applies them to logistic-regression quantities under misspecified and well-specified models.

  • G Concentration inequalities: The section extends Gaussian quadratic-form concentration results to bounded random variables using a corollary of a general U-statistics result.
  • G Concentration inequalities: Proposition 4 considers bounded vectors yi, independent zero-mean variables εi, and the matrix S = Diag(σi)⊤YY⊤Diag(σi).
  • G Concentration inequalities: The proof combines the U-statistics result with Bernstein’s inequality to derive the stated concentration bound.
  • G Concentration inequalities: The concentration result is applied with yi defined from the regression design and variance structure.
  • G Concentration inequalities: Without model assumptions, the section bounds λmax(S) and tr(S) using R^2/(λn).
  • G Concentration inequalities: In the well-specified case, P = Q, λmax(S) ⩽ 1/n, tr S = d/n, and tr S^2 = d^2/n^2.
Loading 0910.4627v1…