How Far Can Sharpness and Complexity Jointly Explain Generalization?

Technical Summary: How Far Can Sharpness and Complexity Jointly Explain Generalization?

Problem Statement
Deep neural networks often achieve strong predictive performance in highly overparameterized regimes, creating a gap between empirical success and theoretical understanding. Classical capacity-based bounds fail to explain why these networks generalize well on structured data while easily fitting random labels. While recent literature has identified sharpness (sensitivity to perturbations) and complexity (size or information content of the model) as two central factors in generalization, their joint explanatory power remains largely unexplored. Existing quantitative evaluations have largely treated generalization measures as individual scalar predictors, often combining sharpness and complexity into a single scalar via prescribed functional forms. This approach leaves open the question of how much generalization can be explained by the pair of factors $(S, C)$ without committing to a specific combination, and whether failures in prediction stem from the two-factor framework itself or from inadequate metric definitions.

Methodology
The authors employ an empirical and conceptual analysis to investigate the explanatory scope of the sharpness-complexity view across diverse architectures and datasets.

1. Evaluation Frameworks:

   • Linear Regression: The authors fit a linear model $Gap = \beta_0 + \beta_S S + \beta_C C + \epsilon$ to evaluate the predictive power of metric pairs. They report $R^2$ and the signs of coefficients.
   • Pareto Analysis (Pareto Contradiction Rate - PCR): To avoid assumptions about linearity, the authors introduce a non-parametric evaluation tool. They check if the ordering induced by $(S, C)$ metrics agrees with the ordering of generalization gaps. A "candidate pair" consists of two models where one has both lower sharpness and lower complexity. A "contradictory pair" occurs if the model with lower $(S, C)$ has a worse generalization gap. The PCR is the ratio of contradictory pairs to candidate pairs. A low PCR indicates strong agreement with the monotonic relationship expected by the two-factor view.

2. Metric Definitions:

   • Parameter-Level Baselines: The study evaluates existing scale-invariant metrics, specifically Adaptive SAM (adapS) for sharpness and Path Norm for complexity. These are compared against non-invariant baselines like Hessian trace and $\ell_2$ weight norm.
   • Function-Oriented Metrics: To address parameterization ambiguity (where different parameters yield the same function), the authors propose metrics defined closer to function space:
     • Bayes Sharpness (bayesS): Defined as the normalized posterior-averaged loss increase. It uses an adaptive posterior $Q$ with covariance proportional to parameter magnitudes to ensure scale invariance, measuring the actual loss change induced by sampled predictors rather than relying on Hessian approximations.
     • Functional KL Divergence (func norm): A complexity metric derived from PAC-Bayes theory. It computes the KL divergence between prior and posterior distributions after mapping parameter samples to their induced function outputs on a reference dataset. This measures deviation in predictive behavior rather than raw parameter values.

3. Experimental Scope:
   The evaluation covers normalization-equipped architectures (ResNet, VGG, WideResNet), normalization-disabled variants (no-BN), and Vision Transformers (ViT). Crucially, the study includes "Mixed" settings where models from different architectures and datasets (CIFAR-10 and CIFAR-100) are pooled to test cross-architecture and cross-dataset comparability.

Key Contributions

• Joint Explanatory Power Analysis: The paper provides the first large-scale quantitative evaluation of how well sharpness and complexity jointly explain generalization, moving beyond single-scalar measures.
• Methodological Innovation: The introduction of Pareto Analysis (PCR) as a complementary tool to linear regression allows for the assessment of the two-factor view without assuming a specific functional form (linear or otherwise) between $(S, C)$ and the generalization gap.
• Function-Oriented Metrics: The proposal of Bayes Sharpness and Functional KL Divergence offers realizations of sharpness and complexity that are less dependent on raw parameter representations. This addresses the issue of parameterization ambiguity, particularly in architectures with skip connections or normalization layers.
• Diagnostic Insights: The study distinguishes between failures caused by inadequate metric definitions and potential intrinsic limitations of the two-factor framework.

Results

• Limitations of Parameter-Level Metrics: Existing scale-invariant baselines (e.g., adapS + path norm) perform reasonably well on normalization-equipped networks (e.g., ResNet18, WideResNet) but lose explanatory power significantly when normalization is removed (e.g., no-BN ResNet18) or when models are pooled across different architectures. In these cases, regression $R^2$ drops, coefficients become negative, and PCR rises (indicating frequent contradictions).
• Success of Function-Oriented Metrics: The proposed function-oriented pair $(bayesS, func norm)$ significantly extends the explanatory scope.
  • It recovers high $R^2$ and low PCR in normalization-disabled settings where parameter-level metrics fail (e.g., no-BN ResNet18: $R^2$ improves from 0.07 to 0.83; PCR drops from 77.8% to 1.2%).
  • It maintains predictive power in cross-architecture and cross-dataset mixed settings, suggesting these metrics provide a more stable basis for comparison than parameter-level metrics.
• Remaining Failures: The function-oriented metrics fail to provide a complete explanation for Vision Transformers (ViT), particularly in standard settings where test losses are extremely high. In these regimes, the two-factor view yields high PCR and negative coefficients. The authors suggest this may be due to the metrics not being fully function-level (Bayes sharpness still relies on parameter-space perturbations) or because these models operate outside the meaningful generalization regime where PAC-Bayes bounds are loose.
• Single-Factor Insufficiency: Single-factor analysis confirms that neither sharpness nor complexity alone is sufficient to explain generalization, supporting the necessity of the two-factor view.

Significance and Claims
The paper claims that the sharpness-complexity perspective is an informative lens for understanding generalization across diverse settings, but it does not claim to be a complete theory.

• Refining the View: The results suggest that many apparent failures of the two-factor view are due to limitations in metric definitions (specifically, reliance on parameter-level representations) rather than intrinsic flaws in the framework itself. By moving toward function-oriented definitions, the explanatory scope can be significantly expanded.
• Open Questions: The remaining failures (e.g., in ViT) indicate that the current realizations are not yet complete. The authors posit two possibilities: either better, fully function-level definitions of sharpness and complexity are needed to extend the scope further, or the two-factor framework is intrinsically incomplete and requires additional factors beyond $(S, C)$ to fully explain generalization.
• Practical Utility: Metrics with strong explanatory power can serve as diagnostic tools for model comparison, hyperparameter selection, and designing regularization penalties.

In summary, the work quantitatively characterizes the boundaries of the sharpness-complexity framework, demonstrating that while it is a powerful explanatory tool, its effectiveness is contingent on how these factors are realized and measured.