PaperlayerView exact revision on arXiv

Source-linked AI summary

Classification vs regression in overparameterized regimes: Does the loss function matter?

Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, Anant Sahai

arXiv:2005.08054v2cs.LGcs.ITstat.ML

TL;DR

The paper asks whether training and testing loss functions play the same role in overparameterized classification and regression. It analyzes minimum-norm interpolation and hard-margin SVM solutions in Gaussian linear models, showing that training procedures can coincide while test-loss behavior differs sharply. In particular, some regimes classify well under 0-1 loss but fail under square loss.

  • Problem

    The paper examines whether the apparently different training losses used for classification and regression produce different predictors and whether their test-loss behavior differs in overparameterized settings.

  • Method

    The paper analyzes minimum-ℓ2-norm interpolation and hard-margin SVM solutions in overparameterized linear models with Gaussian features, including isotropic and bi-level covariance ensembles.

  • Results

    The paper shows that sufficient overparameterization makes all training points support vectors and can make hinge-, logistic-, and square-loss optimization produce the same predictor, while some regimes generalize well under 0-1 loss but poorly under square loss.

  • Takeaways & Limitations

    Training-loss equivalence does not imply test-loss equivalence: classification can generalize well under conditions where regression does not.

  • Takeaways & Limitations

    The main generalization result is developed under Gaussian features and a bi-level covariance structure, though the paper discusses extensions to arbitrary covariance matrices and sub-Gaussian features.

Abstract

from arXiv · show

We compare classification and regression tasks in an overparameterized linear model with Gaussian features. On the one hand, we show that with sufficient overparameterization all training points are support vectors: solutions obtained by least-squares minimum-norm interpolation, typically used for regression, are identical to those produced by the hard-margin support vector machine (SVM) that minimizes the hinge loss, typically used for training classifiers. On the other hand, we show that there exist regimes where these interpolating solutions generalize well when evaluated by the 0-1 test loss function, but do not generalize if evaluated by the square loss function, i.e. they approach the null risk. Our results demonstrate the very different roles and properties of loss functions used at the training phase (optimization) and the testing phase (generalization).

1. Introduction

The paper compares training and testing losses for classification and regression in overparameterized linear models. It shows that different training losses can yield the same predictor, while test losses reveal distinct generalization behavior.

  • The study directly compares classification and regression loss functions across optimization and generalization in overparameterized linear models.
  • With sufficient overparameterization, every training point becomes a support vector with high probability, making hinge-, logistic-, and square-loss optimization yield the same outcome.
  • The paper identifies regimes where predictors generalize well under 0-1 loss but poorly under square loss, showing that classification and regression can differ asymptotically.
  • The same minimum-ℓ2-norm solution can succeed at both tasks, succeed at classification while failing at regression, or fail in other regimes depending on effective overparameterization.
  • Its classification analysis provides non-asymptotically matching upper and lower bounds and links techniques from regression interpolation to classification.

2. Related work

Related work establishes the importance of implicit regularization and feature structure in overparameterized interpolation. This paper extends those ideas to clarify when classification is easier to generalize than regression and why margin-based explanations can mislead.

  • Overparameterized models can interpolate training data while generalizing well, challenging the conventional expectation that zero training error implies poor generalization.
  • Gradient descent on logistic loss converges to the hard-margin SVM, while zero-initialized square-loss gradient descent converges to minimum-ℓ2-norm interpolation.
  • Theorem 11 shows that sufficient overparameterization makes the SVM interpolate binary labels, establishing equivalence across several training losses.
  • The paper links the hard-margin SVM and minimum-ℓ2-norm interpolation by showing that every training example can be a support vector in an overparameterized separable setting.
  • Margin-based generalization explanations can be misleading for interpolated classifiers in this setting.
  • Classification requires milder signal-preservation conditions than regression, and a signal-processing view tracks survival of true features and contamination by false features.

3. Setup

The setup uses iid feature-label data generated from a linear signal with possible label noise, and studies minimum-norm interpolation and hard-margin SVM solutions when features outnumber samples. Test performance is measured separately for regression and classification under Gaussian feature ensembles.

  • The model uses a known feature map, an unknown linear signal, binary or real-valued outputs, and independent label noise for classification.
  • The overparameterized regime is defined by d ≥ n, where the number of features is at least the number of samples.
  • Minimum-ℓ2-norm interpolators arise from square-loss minimization, while the hard-margin SVM imposes Yiφ(Xi)⊤α ≥ 1 for every training point.
  • When d ≥ n, any binary-label interpolator satisfies the SVM feasibility constraints almost surely, so the training data are linearly separable.
  • Regression and classification are evaluated using mean-square error and classification error, respectively, with expectations taken over random test inputs.
  • The study analyzes isotropic and bi-level Gaussian covariance ensembles, varying feature dimension and parameters controlling preferred directions and effective overparameterization.
  • The bi-level construction permits classification to generalize well even when a condition sufficient for regression does not hold.

4. Approximating the SVM by exact interpolation

In sufficiently effectively overparameterized Gaussian-feature models, all training points can become SVM support vectors, linking hard-margin SVM solutions to minimum-ℓ2-norm interpolation. This phenomenon enables tractable SVM analysis, although the stated sufficient conditions are stronger than necessary.

  • The analysis explicitly connects the SVM solution to minimum-ℓ2-norm interpolation, which is used to approximate the otherwise difficult margin-maximizing solution.The minimum-norm link is the central device for making the SVM tractable in the overparameterized regime.
  • Sufficient effective overparameterization makes all training points support vectors with high probability, linking positive-margin SVM constraints to exact label interpolation.The result provides a roadmap for analyzing SVM generalization through the corresponding interpolating solution.
  • Theorem 11 establishes binary-label interpolation constraints for every labeling or for a fixed labeling under separate high-probability conditions.The theorem is stated for Gaussian featurization with covariance matrix Σ and the hard-margin SVM solution.
  • The sufficient conditions arise from complementary slackness and concentration arguments, using an epsilon-net bound or sharper Gaussian-isotropy properties.The two conditions differ in the concentration tools applied to the SVM dual.
  • Equation (13) is a strong sufficient condition that still permits non-trivial regimes with good or poor classification generalization, while empirical support-vector proliferation occurs beyond its predictions.For p = 3/2 and r = 1/2, the support-vector fraction reaches 1 around q ≥ 0.7 despite violating both conditions in Equation (13).

5. Generalization analysis for interpolating solution with Gaussian features

The paper analyzes when minimum-ℓ2-norm interpolation generalizes differently for classification and regression in a bi-level Gaussian-feature model. Classification can generalize well under conditions where regression remains poor because classification requires weaker coefficient-recovery conditions.

  • Setup and result: The analysis characterizes regression and classification risks as functions of overparameterization and covariance parameters in the bi-level ensemble.The parameters p, q, and r control feature count, relative eigenvalue weights, and preferred-feature count.
  • Setup and result: Under 1-sparse signal assumptions, there exists a regime where regression test loss remains prohibitively high while classification test loss converges to 0 as n →∞.This regime is identified through the asymptotic behavior of minimum-ℓ2-norm interpolation for real and binary labels.
  • Setup and result: The principal intermediate regime is (1 −r) < q < (1 −r) + (p−1) 2, where classification generalizes but regression does not.The paper identifies this interval as the main separation between the two tasks.
  • Setup and result: Regression generalizes well iff q < (1 −r), a condition tied to preserving signal in the preferred features.Higher q reduces the ratio between large and small eigenvalues, making signal preservation harder.
  • Path to analysis: Classification vs regression test error: The intermediate regime depends on overparameterization supplying many unimportant directions that can absorb effective noise harmlessly.The paper links this mechanism to the parameter p and the enlarged feature dimension d = np.
  • Path to analysis: Classification vs regression test error: Classification is easier to generalize because it requires contamination-to-survival ratio CN/SU →0, whereas regression requires CN →0 and SU →1.Thus, the regression conditions directly imply the weaker classification requirement, but not conversely.

6. Examining margin-based explanations for generalization

The paper tests whether margin-based bounds explain generalization in overparameterized models and finds that they can be tautological and fail to track true test behavior. Increasing normalized margin accompanies opposite error trends under isotropic and weak-feature settings.

  • Motivation: Margin-based bounds are examined as a possible explanation for generalization in overparameterized classification models.The analysis focuses on hard-margin SVMs and normalized training margins.
  • Why bounds fail: The bounds are uninformative in sufficiently overparameterized settings because intrinsic data dimension enters critically through ∥Φtrain∥F.For separable data, the average training-loss term is zero, leaving the complexity-dependent term central to the bound.
  • Why bounds fail: The bounds remain greater than 1 in both isotropic and weak-feature settings, making them tautological.The ∥Φtrain∥F term cancels the apparent benefit of increasing normalized margin.
  • Empirical comparison: Normalized margin increases with overparameterization, but test error decreases for weak features and increases for isotropic features.Thus, the same margin trend accompanies contrasting generalization behavior across featurizations.
  • Conclusion: Margin-based bounds are not predictive of overparameterized-model behavior in this setting, despite possible generalization benefits from suitable large-margin notions.For linear models, maximizing margin is equivalent to minimizing the parameter norm, but the relevant explanation requires first-principles analysis rather than existing bounds.

A.1 Empirical evidence that all training points become support vectors

The Fourier-feature experiment provides empirical evidence that minimum-norm interpolation and the SVM coincide as overparameterization grows, with every training point becoming a support vector.

  • Equal-weight Fourier features: With d=n and equal feature weights, minimum-ℓ2-norm hard-margin SVM optimization forces every training point to become a support vector.The Fourier features make the first n training-data columns resemble a rotated, scaled identity.
  • Equal-weight Fourier features: Adding balanced aliases preserves the all-support-vector property in the isotropic case whenever d is a multiple of n.The construction extends the equal-weight setting by adding equivalent feature copies.
  • Non-isotropic features: Across the tested decay values, minimum-ℓ2-norm interpolation and the SVM show a remarkable equivalence, supporting the phenomenon established theoretically for Gaussian featurization.This experiment supplied initial empirical evidence that all training points become support vectors in high dimensions.

A.2 Regression vs Classification

In the Fourier-feature model, regression requires the true signal to survive, whereas classification can remain accurate when contamination is small relative to the surviving signal. This creates a regime in which classification succeeds although regression approaches null risk.

  • Model and mechanism: The minimum-norm interpolator recovers coefficients for the true feature and its exact aliases in the regularly spaced Fourier-feature model.The coefficient on the true feature represents signal survival, while alias coefficients contribute contamination at test points.
  • Signal survival: 1 if q < 1 −r; 0 if q > 1 −r, so the signal fully survives only when q < (1 −r).This asymptotic survival threshold is obtained from the coefficient approximation for the true feature.
  • Classification: The Fourier-feature construction illustrates the distinction through contamination from aliases, which can flip a test-point prediction sign even when interpolation is exact.The contamination term aggregates contributions from falsely discovered features.
  • Classification: Classification can succeed beyond the regression threshold because it depends on the sign of the prediction, provided contamination remains sufficiently small relative to the surviving signal.The relevant comparison is the survival factor a versus the contamination standard deviation σCN.
  • Regression: When q < (1 −r), regression mean-square error approaches zero, whereas q > (1 −r) makes regression MSE approach the null risk.The result combines signal survival with the asymptotic decay of the contamination contribution.

A.2.1 Implications for classification: existence of the separating regime

Classification succeeds in a broader overparameterized regime than regression because sign prediction can tolerate vanishing signal when contamination vanishes faster. The Fourier-feature analysis establishes an intermediate regime where classification works but regression does not, while leaving the farthest regime unresolved.

  • Classification criterion: For classification, the relevant target is sgn(cos(X)) under X ∼ Unif [−π, π], rather than the real-valued prediction itself.Classification therefore depends on predicting the correct sign with high probability.
  • Separating regime: When q > (1 −r), the survival factor a tends to zero, but classification can still work if contamination is sufficiently smaller than a.The sufficient comparison is σCN ≪ a.
  • Noise: For noisy training data, additive noise does not contribute to regression error when q < (1 −r) and a ≈1 unless the noise variance grows faster than n^(1−r).The noise contribution vanishes asymptotically under the stated scaling.
  • Scope of the result: The Fourier-feature analysis proves regression failure beyond q > (1 −r), but the third qualitative regime remains inconclusive for classification performance.The classification calculation provides an upper bound, and whether it is matched by a lower bound remains open.

Appendix B. Additional notation for proofs

The appendix introduces leave-one-out covariance and Gram-matrix notation used in the proofs. The covariance is diagonalized without loss of generality, and both full-spectrum and leave-one-out representations are retained.

  • Covariance notation: The analysis assumes zero-mean Gaussian features with diagonal covariance Σ, without loss of generality after transforming to its eigenvector basis.A coordinate transformation can diagonalize a non-diagonal covariance matrix.
  • Leave-one-out construction: For an index t, the leave-one-out covariance Σ−t removes one eigenvalue from the spectrum, and its eigenvalues are denoted eλj.This notation supports the proof's comparison between full and reduced spectra.
  • Gram matrices: The appendix expresses effective Gram matrices using both the full covariance spectrum and the leave-one-out spectrum.The two equivalent forms of the leave-one-out Gram matrix are used throughout the analysis.

C.1 Proof of Theorem 11

The proof of Theorem 11 establishes that sufficiently overparameterized Gaussian-feature SVM solutions have all training points as support vectors. It does so by controlling random Gram-matrix quantities and verifying positivity of the dual variables.

  • Proof setup: The proof analyzes the random Gram matrix A and its leave-one-out representation through concentration bounds for Gaussian and inverse-Wishart quantities.These bounds control operator norms and quadratic forms needed to establish the support-vector condition.
  • Support-vector conclusion: Complementary slackness implies that all training points are support vectors when every coordinate of the unconstrained dual solution is positive.The unconstrained solution is β* := A^-1Ytrain, and positivity is established uniformly over the n points.
  • Matrix control: The epsilon-net argument controls the operator norm of E := A − ||λ||1 I_n with high probability.Lemma 20 supplies the concentration statement used to derive the required inequalities.
  • Bi-level specialization: The bi-level ensemble satisfies the sufficient conditions for Theorem 11 when the parameter scaling obeys the derived constraints on p, q, and r.The proof substitutes ||λ||1 = d = n^p into the general condition and obtains sufficient asymptotic inequalities.
  • Assumptions: The proof requires sufficiently large n and uses asymptotic scaling relations that omit constants.The appendix explicitly notes that the conditions rely on repeated use of the ≍ relation and the large-n assumption.

D.1 Bounds on survival and contamination

The section characterizes survival and contamination for minimum-ℓ2-norm interpolation of binary and real outputs under effective-rank conditions. It establishes matching survival behavior up to constants and high-probability contamination bounds, using concentration arguments for Gaussian-feature matrices.

  • Survival: Theorem 22 bounds survival for binary and real interpolation when rk(Σ) and rk(Σ−t) scale at least linearly with n.The bounds use universal constants independent of (n, d, k, Σ).
  • Survival: The survival bounds for binary and real interpolation match in their dependence on n up to constants.
  • Contamination: Theorem 23 characterizes contamination for binary and real interpolation under k ≤ n/c5 and rk(Σ−t) ≥ b2.The binary and real cases are stated separately, with bounds holding with high probability over the training data.
  • Contamination: Contamination bounds hold almost surely conditional on survival factors, whose randomness is then combined through a union bound.
  • Proof strategy: The proofs combine eigenvalue concentration, Hanson-Wright inequalities, Gaussian norm bounds, and Sherman-Morrison-Woodbury identities.

Appendix E. Implications for bi-level covariance: Proof of Theorem 13

The appendix specializes survival and contamination bounds to a bi-level covariance ensemble and substitutes them into classification and regression test-loss expressions. It identifies parameter regimes where signal survival and contamination differ between binary and real interpolation.

  • Reduction to test loss: The bi-level analysis substitutes the ensemble spectrum into general survival and contamination bounds, then into classification and regression test-loss expressions.
  • Binary interpolation: For q > (1 − r), binary-interpolation signal survival vanishes asymptotically, while q ≤ (1 − r) retains nontrivial but potentially attenuated survival.
  • Real interpolation: Real-output interpolation can have zero asymptotic signal attenuation, with SUr(1; n) → 1.
  • Noise robustness: For real-valued outputs, independent additive zero-mean Gaussian label noise does not change asymptotic survival scaling in the selected bi-level parameter range.The excess features absorb this label noise.
  • Contamination regimes: The resulting upper and lower contamination bounds match up to constants for real interpolation when (p − 1) ≤ (1 − r), and for binary interpolation when q > (1 − r).

E.1 Proof of Theorem 13

The proof of Theorem 13 combines lower and upper bounds on regression loss with corresponding classification-loss bounds. These bounds yield distinct asymptotic regimes for the two test losses in the bi-level ensemble.

  • Regression: The proof derives a regression-test-loss lower bound from the test-loss representation, survival bounds, and contamination lower bounds.
  • Regression: The proof derives a regression-test-loss upper bound using the real-output survival and contamination upper bounds.
  • Conclusion: The proof completes the characterization by combining the regression and classification bounds through a sandwich argument.
  • Classification and regression regimes: The limiting SNR is infinite when 0 < q < (p − 1)/(2 + (1 − r)) and zero when q > (p − 1)/(2 + (1 − r)).
  • Classification: The classification test loss is bounded using the limiting SNR and the classification-loss representation.

F.3 Proof of Lemma 27

The lemma proof rewrites contamination for binary and real interpolation as equivalent quadratic-form expressions. It obtains these forms from interpolator coefficients, matrix identities, and positive-definite concentration bounds.

  • Binary interpolation: For binary labels, each interpolator coefficient is expressed using the random Gram matrix and then transformed with the Sherman-Morrison-Woodbury identity.
  • Binary interpolation: The binary contamination factor is obtained by substituting the coefficient expressions into its definition and introducing the residual eyt.
  • Binary interpolation: High-probability quadratic-form bounds control the binary contamination terms using positive-definiteness and independence conditions.
  • Real interpolation: The real-output derivation mirrors the binary case, applying the same matrix identity and contamination definition to real-output coefficients.
  • Matrix tools: The auxiliary matrix inequalities rely on operator-norm submultiplicativity and eigenvalue bounds for products of positive-definite matrices.
Loading 2005.08054v2…