PaperlayerView exact revision on arXiv

Source-linked AI summary

A Model of Double Descent for High-dimensional Binary Linear Classification

Zeyu Deng, Abla Kammoun, Christos Thrampoulidis

arXiv:1911.05822v2stat.MLcs.LGeess.SP

TL;DR

The paper asks how binary linear-classification error changes with the overparameterization ratio when logistic-loss GD trains on selected features. It combines GD implicit-bias results with CGMT analyses of ML and SVM solutions, finding phase-dependent behavior and double-descent risk curves.

  • Problem

    The paper examines how classification error depends on overparameterization in binary linear classification, extending double-descent analysis beyond linear regression.

  • Method

    The analysis combines deterministic GD implicit-bias results with CGMT characterizations of logistic ML and hard-margin SVM performance under Gaussian-feature models.

  • Results

    The risk curves exhibit double descent, with GD behavior switching at the separability threshold between the ML and max-margin regimes.

  • Takeaways & Limitations

    The analysis provides explicit classification-error curves across overparameterization ratios and identifies an overparameterized regime that can contain the global minimum for the studied models.

  • Takeaways & Limitations

    The analysis assumes specific Gaussian data and feature-selection models, while the effect of feature correlation on double descent remains an open extension.

Abstract

from arXiv · show

We consider a model for logistic regression where only a subset of features of size $p$ is used for training a linear classifier over $n$ training samples. The classifier is obtained by running gradient descent (GD) on logistic loss. For this model, we investigate the dependence of the classification error on the overparameterization ratio $κ=p/n$. First, building on known deterministic results on the implicit bias of GD, we uncover a phase-transition phenomenon for the case of Gaussian features: the classification error of GD is the same as that of the maximum-likelihood (ML) solution when $κ<κ_\star$, and that of the max-margin (SVM) solution when $κ>κ_\star$. Next, using the convex Gaussian min-max theorem (CGMT), we sharply characterize the performance of both the ML and the SVM solutions. Combining these results, we obtain curves that explicitly characterize the classification error for varying values of $κ$. The numerical results validate the theoretical predictions and unveil double-descent phenomena that complement similar recent findings in linear regression settings as well as empirical observations in more complex learning scenarios.

1 Introduction

This paper studies double descent in binary linear classification as the overparameterization ratio changes, extending sharp high-dimensional analyses beyond linear regression. It combines implicit-bias results for logistic-loss GD with CGMT-based analyses of ML and SVM solutions.

  • Theoretical excess-risk predictions match GD and hard-margin SVM simulations and predict a separability transition at κ⋆.The transition occurs with high probability when κ exceeds κ⋆.
  • The paper investigates classification error versus κ=p/n for binary linear classification with Gaussian features, paralleling prior linear-regression studies.
  • GD follows the ML solution in the nonseparable regime and the max-margin SVM solution after data become separable.The transition is governed by a phase threshold κ⋆.
  • CGMT extensions support feasibility analysis for hard-margin SVM, relaxed boundedness requirements, and almost-sure convergence results.
  • Across all κ, the analysis yields risk curves displaying double descent, complementing findings in regression and empirical observations in more complex learning settings.

2 Learning model

The learning model trains on a selected subset of features from Gaussian binary-classification data and evaluates the resulting linear classifier by expected test risk. Logistic-loss GD converges to different estimators depending on whether the training data are separable.

  • 2.1 Data generation models: The paper studies binary classification under a Gaussian-mixture model and a logistic model.
  • 2.2 Feature selection model for training data: Each training example exposes only a selected sub-vector w_i of p features from the full d-dimensional feature vector.The selected set is S={1,…,p}, and p is the model size.
  • 2.2 Feature selection model for training data: After choosing p, the learner estimates the first p entries of the unknown weight vector and forms a linear classifier for new samples.
  • 2.3 Classification rule: The estimator minimizes empirical risk using gradient descent, with logistic loss ℓ(t)=log(1+e^-t).
  • 2.3 Classification rule: Test performance is measured by expected classification risk, excess risk relative to the best full-feature linear classifier, and cosine similarity with the true weight vector.
  • 2.4 GD behavior: When data are linearly separable, normalized logistic-loss GD iterates converge to the max-margin solution; otherwise GD converges to the empirical-loss minimizer, which is the ML estimator under the logistic model.

3 Sharp Asymptotics

The paper derives sharp asymptotic predictions for logistic-loss GD in high-dimensional binary classification, including a phase transition between ML and SVM behavior. CGMT-based analysis characterizes classification performance across model sizes and both data regimes.

  • Asymptotic performance: Sharp asymptotic formulae predict test error and cosine similarity as functions of the number of training parameters p.The results apply to logistic-loss GD under the paper’s logistic and Gaussian-mixtures learning models.
  • Non-separable data: In the under-parameterized regime, GD converges to behavior characterized through the logistic maximum-likelihood estimator.The paper analyzes the corresponding ML estimator using a system of nonlinear equations for its asymptotic parameters.
  • Phase transition: The training data is separable almost surely for large n when κ > κ⋆ and nonseparable when κ < κ⋆.Separability permits zero training error and defines the interpolating regime; below the threshold, training error remains non-vanishing.
  • CGMT analysis: CGMT extensions establish feasibility, relax boundedness requirements, and support almost-sure convergence for optimization-based statistical analyses.The paper applies these extensions to the separability threshold and the asymptotics of ML and SVM estimators.
  • Separable data: In the separable regime, GD behavior is characterized through the hard-margin SVM, whose classification performance is analyzed asymptotically under both data models.The hard-margin SVM cost converges almost surely to q⋆, so its margin converges in probability to 1/q⋆.

4 Numerical results and discussion

The numerical results characterize how feature-selection models, data distributions, signal strength, and training-set size shape double-descent curves in logistic classification. Across settings, test error shows a second descent after the interpolation threshold, while the curve’s detailed shape and optimum depend on the model and data.

  • Feature-selection models: The linear feature-selection model increases signal strength with the number of trained features, whereas the polynomial model imposes diminishing returns controlled by γ.In the polynomial model, signal strength increases with κ but less substantially at larger κ.
  • Logistic data: Under logistic data, theoretical curves for cosine similarity and excess risk are evaluated across κ for linear and polynomial feature-selection models.The linear curves use ζ = 3 and r = 2, 5, 10; the polynomial curves use r = 10 and γ = 1, 2, 5.
  • Data models: The logistic and Gaussian-mixture models differ at high signal-to-noise ratio because logistic learning becomes a one-bit measurement problem rather than linear regression.This explains the substantially larger cosine similarity observed for the Gaussian-mixture model at comparable signal strength.
  • Double descent: Double descent appears across the reported plots: risk decreases, rises near interpolation, and descends again beyond κ⋆, while cosine similarity exhibits double ascent.Beyond κ⋆, GD converges to the max-margin classifier because the training data become linearly separable.
  • Double descent: The overparameterized risk curve can be monotonically decreasing or U-shaped, with the latter more pronounced for larger γ in the polynomial model.The normalized max-margin quantity remains monotonic even when the risk has a U-shape, so classical margin behavior does not predict the full risk curve.
  • Optimal model size: For linear feature selection, the global minimum occurs beyond κ⋆ for both logistic and Gaussian-mixture data, whereas polynomial models can attain their optimum below κ⋆.The optimal κ can therefore correspond to zero training error while still minimizing classification error.
  • Training-set size: Larger training sets shift the interpolation threshold rightward, but their effect on test error depends on the feature-selection model.In the polynomial model, curves can cross, so more training examples may improve or worsen performance at a fixed model size.

5 Future work

The paper identifies extensions of its double-descent analysis, including correlated features and multiclass settings, while presenting CGMT extensions that may support related optimization analyses. Its training-set-size experiments further show that curve behavior can depend on the feature-selection model.

  • Training-set size: Training-set-size experiments show that larger n shifts the interpolation threshold rightward, but can produce crossed risk curves in polynomial feature selection.Thus, more training examples do not necessarily yield lower test error at every model size in that setting.
  • Future directions: Future work should clarify how feature correlation affects double-descent curves in forms that yield interpretable guidance for practitioners.Existing correlated-feature asymptotics involve unwieldy expressions when the covariance structure enters the formulas.
  • Future directions: Multiclass classification and double descent across training epochs are additional settings proposed for analytical study.The paper notes that prior empirical work finds double descent can depend on training epochs as well as model size.
  • Analytical tools: The analysis uses CGMT extensions for feasibility, boundedness, and almost-sure convergence questions in optimization-based inference.These extensions are presented as potentially useful beyond the hard-margin SVM analysis motivating the paper.

A.2 Novel extensions of the CGMT

The paper extends the CGMT to analyze convex optimization problems with potentially unbounded constraint sets, including feasibility and optimal-cost behavior through sequences of bounded auxiliary problems.

  • Motivation: The extensions address unbounded optimization variables, a limitation of directly applying the standard CGMT in this setting.The dual constraint set is specifically identified as potentially unbounded, and hard-margin SVM may additionally be infeasible.
  • Feasibility: Theorem A.1 links feasibility of an unbounded primary optimization problem to feasibility of a sequence of bounded auxiliary problems.The theorem permits convex, nonnecessarily bounded constraint sets and is motivated by hard-margin SVM feasibility.
  • Optimal cost and solution: Theorem A.2 shows that, when the auxiliary problems are feasible, their limiting optimal costs determine the primary problem’s optimal cost.The result also establishes almost-sure convergence and does not require compact constraint sets.
  • Application: The framework can use scalarized auxiliary problems with convexity properties to replace difficult unbounded auxiliary optimizations.Pointwise convergence of convex functions yields uniform convergence on compact sets, supporting this replacement.
  • Application: A practical recipe bounds the problem, analyzes the bounded auxiliary optimization, and then transfers the result back to the original unbounded problem.The transfer uses convergence of minimizer norms and is applied to logistic-loss minimization when κ < κ⋆.

B.2.1 Proof of the statement (i)

The proof constructs bounded primary and auxiliary optimization problems, applies the CGMT, and uses uniform convergence and probabilistic arguments to establish asymptotic behavior.

  • Probability argument: The proof controls sequences of events using Gordon’s inequality, monotonicity, independence, and the converse of the Borel–Cantelli lemma.These arguments establish that relevant boundedness and finiteness events occur eventually with probability one.
  • SVM application: The hard-margin SVM analysis uses this framework because SVM feasibility is equivalent to linear separability of the data.The resulting feasibility analysis supports the phase-transition argument for the SVM problem.
  • Scalarization: The auxiliary problem is reduced deterministically to a scalar optimization over a few variables, without asymptotic approximation.The reduction optimizes over directions and replaces a vector variable by its norm α.
  • Asymptotics: Almost-sure convergence follows from pointwise convergence of convex functions and uniform convergence on compact sets.The finite-dimensional objective converges to its limiting form under the Gaussian model.

C.2 Proof of Proposition 3.1

The proof of Proposition 3.1 characterizes the separability threshold by analyzing bounded auxiliary problems and showing that the comparison function has a unique crossing.

  • Infeasible regime: κ < g(κ) implies that the separability event fails for all sufficiently large n with probability one.The argument establishes infeasibility of the hard-margin SVM in this regime.
  • Feasible regime: κ > g(κ) implies that the separability event holds for all sufficiently large n with probability one.The proof establishes feasibility of the primary SVM problem through the auxiliary optimization.
  • Threshold: Because g(κ) is decreasing, κ = g(κ) has a unique solution κ⋆ separating the two regimes.Thus κ > κ⋆ implies κ > g(κ), while κ < κ⋆ implies κ < g(κ).
  • Feasible regime: The feasibility direction constructs a nonempty limiting feasible set and controls the auxiliary objective uniformly over a compact region.Uniform convergence then yields feasibility of the primary problem with probability one for sufficiently large n.
  • Scalarization: The proof reduces the auxiliary optimization to scalar variables and uses convexity to justify the required min-max interchange.The scalarized objective is convex-concave, so equality follows from Sion’s min-max theorem.

C.3.3 Proof of (83a)

The proof of (83a) uses uniform convergence of the finite-sample scalarized auxiliary objective to its limiting counterpart and identifies the relevant asymptotic bound.

  • Feasibility: The limiting optimization is feasible because the separability condition makes the set where L(α, µ) ≤ −δ nonempty.This nonemptiness implies feasibility of the corresponding finite-sample problem for large n.
  • Uniform convergence: Uniform convergence of L_n(α, µ) to L(α, µ) over a compact set transfers limiting inequalities to the finite-sample auxiliary problem.The argument applies this convergence for sufficiently large n.
  • Conclusion: Consequently, statement (83a) holds for sufficiently large n independently of k ≥ k0.This is the final step used to establish the required auxiliary-problem bound.

C.3.5 Proof of (88)

The proof establishes (88) by separating deviations in q and ρ, then using monotonicity and uniqueness properties of η to obtain the required bound.

  • The proof has two parts: first controlling deviations in q, then deviations in ρ.
  • Uniform convergence and convexity transfer the separation argument to the finite-sample optimization, completing the proof of (88).
  • Case 1: ρ ∈[−1, 1]: For q outside S_q, the decreasing function min_ρ η(q, ρ) and its unique zero q⋆ yield the required positive separation.
  • Case 2: |ρ −ρ⋆|> ξ: For ρ outside S_ρ, assuming the bound fails contradicts strict decrease in q and the unique minimizer ρ⋆ of η(q⋆, ρ).

C.4 Proof sketch for GM model

The GM-model proof converts the hard-margin SVM into a Gaussian min-max problem and then scalarizes it, revealing the phase-transition threshold through feasibility.

  • The GM feature model writes each feature vector as signal plus Gaussian noise, with labels independent of the noise after a sign transformation.
  • Decomposing β into signal-aligned and orthogonal components reduces the vector optimization to scalar variables and Gaussian projections.
  • The auxiliary hard-margin SVM is infeasible when its limiting scalar objective remains positive for every q ≥ 0 and ρ ∈[−1, 1].
  • The infeasibility condition is equivalent to the threshold relation involving g(κ), linking the GM optimization to the phase transition.

D On the solutions to the equation g(κ) = κ in Proposition 3.1

This section proves that the threshold function g(κ) decreases with κ and that g(κ)=κ has a unique solution κ⋆∈(0, 1/2).

  • Because signal strength s(κ) increases with κ, the threshold function g is strictly decreasing.
  • Continuity, monotonicity, and the value g(0)=1/2 establish a unique crossing κ⋆ of g(κ) and κ in (0, 1/2).
  • The monotonicity proof compares the auxiliary Gaussian expectation at two noise or signal levels and uses an increasing-function lemma.
  • For the auxiliary function η, strict decrease in q, existence of a zero, and uniqueness of its minimizer support the corresponding threshold characterization.

F.1 Proof of Proposition 3.2

The proof analyzes logistic-loss minimization through the CGMT, reducing the primary optimization to a scalar auxiliary problem and establishing convergence and uniqueness below the phase-transition threshold.

  • The logistic-loss problem is recast as a bounded primary optimization and paired with a bounded auxiliary optimization under the CGMT.
  • Scalarization aligns the auxiliary variables with Gaussian directions, introduces scalar norms, and uses convex-concave minimax exchanges.
  • Uniform convergence, level-boundedness, and convexity connect the finite-dimensional auxiliary problems to their limiting optimization.
  • The limiting optimizer determines the classifier’s cosine similarity and risk through the resulting formulas.
  • For κ<κ⋆, the supremum is not attained as λ→0, because κ<κ⋆ implies κ<g(κ).
  • Strict convexity yields a unique minimizer, allowing the CGMT conclusion that the finite-sample norm and intercept converge to their limiting values.

H Additional numerical results

The additional numerical results examine cosine similarity, risk, and simulation–theory agreement across logistic and Gaussian-mixture settings. They compare empirical averages or simulations with theoretical predictions for selected model configurations.

  • Cosine similarity is plotted against the overparameterization ratio κ for binary logistic regression under polynomial feature selection.The setting matches Figure 1.
  • For the Gaussian-mixture exponential model with γ = 2, the results report cosine similarity and risk curves.Cosine similarity appears on the left and risk on the right.
  • For signal strength r = 10, simulations are compared with theoretical predictions for the logistic model.The figure uses crosses for simulations and lines for theoretical predictions.
  • For the Gaussian-mixture model with signal strength r2 = 10, simulations are compared with theoretical predictions.The plotted quantities include absolute risk, cosine similarity, and auxiliary solutions or parameter averages.
  • Detailed simulation results are also shown for the Gaussian-mixture exponential model with r = 1.
Loading 1911.05822v2…