PaperlayerView exact revision on arXiv

Source-linked AI summary

The Impact of Regularization on High-dimensional Logistic Regression

Fariborz Salehi, Ehsan Abbasi, Babak Hassibi

arXiv:1906.03761v4stat.MLcs.ITcs.LGmath.ITmath.PR

TL;DR

Structured parameter vectors motivate regularized logistic regression, but precise performance characterization in high dimensions is the focus of this work. The paper analyzes RLR through a nonlinear-equation system, deriving asymptotic performance predictions for locally-Lipschitz metrics.

  • Problem

    High-dimensional logistic regression with structured parameter vectors motivates methods that incorporate this structure through regularization.

    Source: §1 · p. 2, §3 · p. 4

  • Method

    The paper uses the Convex Gaussian Min-max Theorem to reduce the RLR analysis to a scalar optimization and a system of six nonlinear equations.

    Source: §3 · p. 4, §3.2 · p. 5

  • Results

    Theorem 1 precisely predicts the asymptotic behavior of locally-Lipschitz performance measures, including mean-squared error.

    Source: §3 · p. 4

  • Takeaways & Limitations

    The characterization applies to general convex penalties and is worked out for quadratic and ℓ1 regularization, including explicit performance measures for sparse logistic regression.

    Source: §6 · p. 11

    The theorem assumes a separable regularizer and i.i.d. parameter entries, although the authors note these assumptions could be relaxed.

    Source: §3.2 · p. 5

Abstract

from arXiv · show

Logistic regression is commonly used for modeling dichotomous outcomes. In the classical setting, where the number of observations is much larger than the number of parameters, properties of the maximum likelihood estimator in logistic regression are well understood. Recently, Sur and Candes have studied logistic regression in the high-dimensional regime, where the number of observations and parameters are comparable, and show, among other things, that the maximum likelihood estimator is biased. In the high-dimensional regime the underlying parameter vector is often structured (sparse, block-sparse, finite-alphabet, etc.) and so in this paper we study regularized logistic regression (RLR), where a convex regularizer that encourages the desired structure is added to the negative of the log-likelihood function. An advantage of RLR is that it allows parameter recovery even for instances where the (unconstrained) maximum likelihood estimate does not exist. We provide a precise analysis of the performance of RLR via the solution of a system of six nonlinear equations, through which any performance metric of interest (mean, mean-squared error, probability of support recovery, etc.) can be explicitly computed. Our results generalize those of Sur and Candes and we provide a detailed study for the cases of $\ell_2^2$-RLR and sparse ($\ell_1$-regularized) logistic regression. In both cases, we obtain explicit expressions for various performance metrics and can find the values of the regularizer parameter that optimizes the desired performance. The theory is validated by extensive numerical simulations across a range of parameter values and problem instances.

1 Introduction

High-dimensional logistic regression must account for structured parameter vectors, while prior work often offered only orderwise performance bounds for regularized estimators. This paper characterizes regularized logistic regression through nonlinear equations and studies general convex penalties alongside quadratic and sparse cases.

1 Introduction

  • Structured parameter vectors motivate regularization, which corresponds to a MAP estimate with a non-uniform prior favoring structured solutions.The paper notes sparse, group-sparse, low-rank, and finite-alphabet structures as examples.Source: §1 · p. 2

1.1 Prior work

  • Earlier regularized-logistic-regression studies often required strong structure assumptions and gave orderwise bounds rather than precise estimates; regularization can also permit recovery when the MLE does not exist.The MLE's performance in the proportional high-dimensional regime had been precisely analyzed, with bias among the reported findings [5] [27] [28].Source: §1.1 · p. 2

1.2 Summary of contributions

  • Six nonlinear equations characterize asymptotic RLR performance and yield locally-Lipschitz metrics, including mean, mean-squared error, and support-recovery probability.The equations reduce to three when the regularizer is absent or quadratic; in the absent-regularizer case they recover the results of Sur and Candes [27].Source: §1.2 · p. 2
  • The analysis uses the Convex Gaussian Min-max Theorem, and numerical simulations validate its theoretical findings across problem settings.The work applies its characterization to quadratic and ℓ1 regularization, with the latter allowing explicit computation of quantities such as correct support-recovery probability.Source: §1.2 · p. 2

2 Preliminaries

The preliminaries establish notation and a binary logistic-model setup, then define regularized maximum likelihood using a convex penalty to represent parameter complexity. Under the stated assumptions, estimator performance is characterized through six nonlinear equations.

2.2 Mathematical Setup

  • The model uses n training pairs (x_i, y_i), where each feature vector is in R^p and each binary label is Bernoulli.The parameter is β* in R^p, and the goal is to estimate it from the training data.Source: §2.2 · p. 3
  • The logistic link is ρ(t) = log(1 + e^t), whose derivative is the standard logistic function; maximum likelihood minimizes the negative log-likelihood.The negative log-likelihood optimization is convex in β.Source: §2.2 · p. 3
  • RLR adds λ times a convex complexity function f to the negative log-likelihood to exploit structure in the parameter.The regularization parameter λ must be tuned properly.Source: §2.2 · p. 3
  • The performance characterization uses six nonlinear equations with six unknowns to compute descriptive statistics such as the estimate's mean and variance.The analysis assumes a separable regularizer and Gaussian data; the parameter entries are drawn from a distribution Π.Source: §2.2 · pp. 3–4

3 Main Results

The section characterizes asymptotic regularized logistic regression (RLR) performance through six nonlinear equations, whose solution supports performance measures such as mean-squared error. It also derives descriptive statistics of the estimate, including its correlation with the true signal and the error of a centered estimate.

3.1 A nonlinear system of equations

  • Six nonlinear equations in six unknowns characterize performance given signal strength and the sample-to-feature ratio.The equations involve proximal operators; the authors report using fixed-point iteration to solve them numerically.Source: §3.1 · p. 4

3.2 Asymptotic performance of regularized logistic regression

  • Theorem 1 characterizes the asymptotic behavior of RLR estimates through a proximal operator applied to a Gaussian-perturbed true signal.The characterization applies to locally Lipschitz performance measures and depends on the regularizer and the distribution of the true signal.Source: §3 · p. 4, §3.2 · p. 5
  • The analysis derives the nonlinear system as the first-order optimality condition of a scalar optimization obtained through the CGMT.The proof first recasts the optimization as a bilinear form, derives an equivalent optimization, then reduces it to six scalar variables.Source: §3.2 · p. 5
  • The theorem’s assumptions are conservative: the authors say separability of the regularizer and i.i.d. signal entries can be weakened.They consider the stated assumptions adequate for the paper’s applications.Source: §3.2 · p. 5

3.3 Correlation and variance of the RLR estimate

  • The correlation statistic is indexed by ᾱ, and centering the estimate around ᾱβ* yields a decorrelated estimate whose mean-squared error is then evaluated.The paper presents these as applications of Theorem 1.Source: §3.3 · pp. 5–6

4 RLR with ℓ2 2-regularization

The section analyzes ℓ2^2-regularized logistic regression and its performance as the regularization parameter varies. In the unregularized case, the analysis recovers the result reported by Sur and Candes [27].

4 RLR with ℓ2 2-regularization

  • Figure 1 presents regularized logistic regression with ℓ2 penalty: dashed lines show Theorem 2’s theoretical result, while dots show empirical results averaged over 100 independent trials with p = 250 and κ = 1.The measures are correlation factor ᾱ, variance σ̄², and mean-squared error.Source: Figure 1 · p. 7, §4 · p. 7
  • Theorem 2 characterizes the asymptotic behavior of locally-Lipschitz performance measures using ᾱ and σ̄ from a nonlinear system.For ℓ2^2 regularization, the proximal operator is a simple rescaling, allowing the first three system equations to be rewritten.Source: §4 · pp. 6–7
  • Increasing λ reduces the correlation factor ᾱ and variance σ̄^2, while an optimal λ minimizes mean-squared error for each δ.The reported curves show a λopt achieving minimum mean-squared error for different δ values.Source: §4 · p. 8

4.1 Unstructured case

  • Setting λ = 0 recovers the maximum-likelihood estimate, and the analysis gives the result of Sur and Candes [27].Studying the likelihood-ratio-test interpretation of γ̄ is outside the paper’s scope.Source: §4.1 · p. 8

5 Sparse Logistic Regression

The section applies the general RLR analysis to sparse logistic regression with an ℓ1 penalty. It derives performance and support-recovery results, with theoretical predictions compared against simulations.

5 Sparse Logistic Regression

  • Sparse LR uses an ℓ1 penalty for feature selection, and the analysis describes its nonlinear-system expectations using two q-functions.The nonzero entries of β* are modeled with a Gaussian distribution; the ℓ1 proximal operator is soft-thresholding.Source: §5 · p. 8, §5.1 · p. 8

5.1 Convergence behavior of sparse LR

  • Theoretical predictions match empirical simulations, and the λopt minimizing mean-squared error decreases as δ increases.Figure 2 reports ᾱ, σ̄^2, and mean-squared error across λ.Source: §5.1 · p. 9, Figure 2 · p. 9

5.2 Support recovery

  • With a hard threshold ε, support recovery is assessed by false-alarm and misdetection probabilities.E1 is the probability of including an off-support entry; E2 is the probability of missing an on-support entry.Source: §5.2 · p. 10
  • As p → ∞, the limits of E1 and E2 as ε ↓ 0 are given by Q(t̄1) and 1 − Q(t̄2), respectively.The result assumes λ yields a unique solution to the nonlinear system.Source: §5.2 · p. 10
  • Figure 3 compares theoretical error probabilities with simulation averages over 100 trials at p = 250, κ = 1, and ε = 0.001.The panels show false detection and missed-support probabilities.Source: Figure 3 · p. 10

6 Conclusion and Future Directions

The conclusion summarizes the general RLR characterization and its ℓ2^2 and ℓ1 special cases. It also identifies extensions to non-Gaussian data and conditions for solution existence as future work.

6 Conclusion and Future Directions

  • The paper characterizes regularized maximum-likelihood performance through a nonlinear system, with applications to ℓ2^2-RLR and ℓ1-RLR.For quadratic regularization the system simplifies to three equations; at λ = 0 the analysis recovers Sur and Candes [27].Source: §6 · pp. 10–11
  • For sparse logistic regression, two q-functions represent the probabilities of on- and off-support recovery.The analysis assumes Gaussian datapoints; extending it to non-Gaussian distributions is proposed as future work.Source: §6 · p. 11
  • Future work includes conditions on λ, as a function of δ and κ, that guarantee existence of the RLR solution.The conclusion notes that this has been studied in the unstructured setting by Candes and Sur [5].Source: §6 · p. 11

A Convex Gaussian Min-max Theorem (CGMT)

The appendix states the convex Gaussian min-max theorem and its asymptotic corollary. The framework relates a primary optimization to an auxiliary one under specified convexity, compactness, and Gaussian assumptions.

A Convex Gaussian Min-max Theorem (CGMT)

  • The CGMT associates a primary optimization problem with an auxiliary optimization problem to investigate properties such as phase transitions.The theorem’s stated conditions include convex compact feasible sets and a convex-concave objective.Source: A Convex Gaussian Min-max Theorem (CGMT) · p. 14
  • The CGMT setup assumes standard-normal i.i.d. entries for G, g, and h, along with convex compact sets and a convex-concave ψ.The probabilities in the theorem are with respect to the randomness in G, g, and h.Source: A Convex Gaussian Min-max Theorem (CGMT) · p. 14
  • The asymptotic corollary applies when the auxiliary optimal costs converge to constants with the primary cost’s limit strictly smaller.It uses the same notation and assumptions as Theorem 3.Source: A Convex Gaussian Min-max Theorem (CGMT) · p. 14

B Useful Mathematical Tools

This section gathers mathematical tools used in the proofs, including properties of the Moreau envelope and proximal operators. It also states lemmas for logistic loss and separable functions.

B Useful Mathematical Tools

  • The Moreau envelope is defined for a convex function, its proximal operator is given by an optimization solution, and its derivative has a stated formula.The section refers readers to for a proof and further properties of the envelope.Source: B Useful Mathematical Tools · p. 15
  • For logistic loss ρ(z) = log(1 + e^z), the section states identities and derivative properties of its proximal operator.The derivation uses ρ′(−z) = 1 − ρ′(z).Source: B Useful Mathematical Tools · p. 15
  • Stein’s lemma equates E[Zf(Z)] with E[f′(Z)] for a function f on the real numbers.The lemma is attributed to.Source: B Useful Mathematical Tools · p. 15
  • For an invariantly separable function, the section states a relation involving its proximal operator and the Moreau envelope of its scalar component.The function is expressed as a sum of scalar functions across coordinates.Source: B Useful Mathematical Tools · p. 15

C Proof of Theorem 1

The proof analyzes regularized logistic regression in the high-dimensional limit by applying the CGMT and reducing the auxiliary optimization to a scalar problem. Its optimality conditions yield the nonlinear system used to characterize performance.

C Proof of Theorem 1

  • The proof targets a precise characterization as p and n tend to infinity at fixed ratio δ = n/p, assuming independently drawn Gaussian data.The analysis uses the CGMT and derives the nonlinear system from first-order conditions of the scalar optimization.Source: C Proof of Theorem 1 · p. 16

C.1 Finding the auxiliary optimization

  • The CGMT setup rewrites the program as a min-max problem and decomposes H so the labels are independent of H2.The proof imposes artificial compact, convex feasible sets, chosen large enough not to affect the optimization; compactness is then set aside in the arguments.Source: §C.1 · pp. 16–17

C.2 Analyzing the auxiliary optimization

  • The proof constructs the auxiliary optimization and reduces its analysis to a scalar optimization over variable magnitudes.The reduction uses scalar variables to replace a norm with its squared form and uses the law of large numbers to replace Moreau envelopes with expectations.Source: §C.1 · p. 17, §C.2 · pp. 17, 18, 20
  • The auxiliary optimization uses expected Moreau envelopes for the regularizer and link function, with an asymptotically justified reversal of the min-max order.The reversal is justified in the asymptotic setting because the original optimization is convex-concave and the two optimizations are tightly related there.Source: §C.2 · pp. 18, 20

C.3 Finding the optimality condition of the scalar optimization

This section derives the scalar optimization’s first-order conditions and shows their equivalence to the paper’s nonlinear system. It then uses the system’s unique solution to describe the auxiliary optimizer and establish convergence to the primary optimizer.

C.3 Finding the optimality condition of the scalar optimization

  • The six first-order optimality conditions of the scalar objective are equivalent to the nonlinear system (6).The derivation takes derivatives with respect to the scalar variables and uses properties of the expected Moreau envelopes.Source: §C.3 · pp. 21–23
  • The unique solution of the nonlinear system determines the auxiliary optimizer through the proximal operator.The proof identifies the optimizer of the Moreau envelope of f with the solution of the auxiliary optimization.Source: §C.3 · p. 23
  • The convergence argument uses bounded optimization sets, the strong law of large numbers, and CGMT to show the primary optimizer lies in the specified set with probability approaching 1.The argument first establishes this property for the auxiliary optimizer as p tends to infinity.Source: §C.3 · p. 23

D Proof of Theorem 2

The proof of Theorem 2 reduces its characterization to a system of three equations in three unknowns. For 2-regularization, the scalar proximal operator is available in closed form.

D Proof of Theorem 2

  • The proof reduces the remaining conditions to a system of three equations with three unknowns after computing θ, r, and τ from the first three equations of system (6).The passage identifies this as the step needed to derive Theorem 2 from Theorem 1.Source: D Proof of Theorem 2 · pp. 23–25
  • For 2-regularization, the scalar function is 1/2 times its argument squared, so its proximal operator has a closed-form expression.The section substitutes that expression into the equations for the specialization.Source: D Proof of Theorem 2 · p. 24
Loading 1906.03761v4…