Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning

Hoang Tran, Qinzi Zhang, Ashok Cutkosky

TL;DR

Optimization theory often relies on "clean" assumptions like convexity and smoothness that don't strictly exist in the messy world of deep learning. This paper looks "under the hood" of theoretical proofs to measure the low-level mathematical identities that actually drive convergence; they find that while smoothness-based theories largely fail in practice, convexity-based math surprisingly holds up well enough to explain why our optimizers work.

What Problem Does This Paper Address?

There is a massive "theory-practice gap" in deep learning. Researchers develop optimizers like Adam or SGD based on mathematical proofs that assume the loss landscape is either convex (shaped like a bowl) or smooth (no sudden changes in slope). However, we know neural network landscapes are notoriously non-convex and jagged.

The authors argue that simply asking "Is this function convex?" is the wrong question. Instead, they ask: "Do the specific mathematical identities used in these proofs actually hold during a real training run?" By measuring these low-level quantities, they aim to find out which theoretical frameworks are actually useful for predicting real-world performance and which are just "analytical conveniences."

Methods

The authors introduce several "on-the-fly" empirical metrics to monitor training:

  • Convexity Ratio: A metric that measures the relationship between the gradient and the distance to the optimum. A ratio $>1$ implies convexity, while a ratio between $0$ and $1$ suggests "weak quasi-convexity."
  • Update Correlation: This measures how well the gradient at the next step aligns with the current update. Standard "smooth" optimization theory predicts this should be negative (meaning we are moving "downhill"), but the authors measure what actually happens.
  • Instantaneous Smoothness: A computationally cheap proxy for "sharpness" (the Hessian's spectral norm). Instead of calculating expensive second-order derivatives, they measure how much the gradient changes between two consecutive steps.
  • Random Scaling (RS): They test a newer theoretical technique where step sizes are randomly scaled (sampled from an exponential distribution) to see if it makes the training progress more predictable in non-smooth environments.

Datasets

The study covers a broad spectrum to ensure the findings aren't specific to one architecture:

  • Convex Baselines: Synthetic squared loss and Logistic Regression on OpenML datasets (Aloi, Poker, Connect-4, etc.).
  • Image Classification: CIFAR-10 and ImageNet using ResNet18.
  • Natural Language Processing: Pre-training BERT (on the C4 dataset) and GPT-2 (on the Pile dataset).

Key Insights and Ideas

  • The "Convexity" Surprise: Even though neural networks are globally non-convex, the Convexity Ratio remains positive throughout training. This suggests that the math used to analyze convex optimizers (like AdaGrad) is actually a decent approximation for what's happening in deep learning.
  • Smoothness is a Myth: In almost all deep learning experiments, the Update Correlation was positive. In plain English: the optimizer is constantly "bouncing" against the walls of narrow ravines rather than sliding smoothly down a hill. This directly contradicts the "descent lemma" used in most smoothness-based proofs.
  • A Cheap Sharpness Tool: Their "instantaneous smoothness" metric tracked the actual Hessian-based sharpness almost perfectly. This is a big win for engineers who want to monitor model sharpness in real-time without the massive computational overhead of second-order math.
  • The "Multiple Minima" Reality: Convexity looks great when measured against the endpoint of the current training run. However, if you measure it against the endpoint of a different run (with a different random seed), the convexity disappears. This confirms that while the path to "your" minimum looks convex, the global landscape is still a wild, multi-peaked mountain range.

Key Results

  • Convexity Ratios: For CIFAR-10 and ImageNet, AdamW maintained a convexity ratio $>1$, effectively behaving as if the function were convex. SGDM was lower (around $0.5$) but still positive, fitting the definition of "weak quasi-convexity."
  • Smoothness Failure: Smoothness constants were found to be massive ($10^3$ to $10^6$), making it mathematically difficult to justify calling these landscapes "smooth" in any practical sense.
  • Random Scaling Validation: When using Random Scaling (RS), the sum of update correlations perfectly matched the actual loss decrease. This validates newer "non-smooth" optimization theories as being more representative of reality than classical smooth theories.

Limitations and Future Work

  • Optimizer Scope: The study focused exclusively on SGDM and AdamW. While these are the industry standards, the authors acknowledge that other optimizers (like Lion or Shampoo) might exhibit different behaviors.
  • The "Why" of Positive Correlation: The paper identifies that update correlations are positive (the "bouncing" behavior), but it doesn't fully explain why the models still converge so effectively despite this.
  • Theoretical Rescue: The authors hope these metrics will inspire theorists to develop new assumptions that "rescue" optimization analysis by better reflecting the positive update correlations and local convexity observed in practice.

Summary updated

Abstract

There is a significant gap between our theoretical understanding of optimization algorithms used in deep learning and their practical performance. Theoretical development usually focuses on proving convergence guarantees under a variety of different assumptions, which are themselves often chosen based on a rough combination of intuitive match to practice and analytical convenience. In this paper, we carefully measure the degree to which the standard optimization analyses are capable of explaining modern algorithms. To do this, we develop new empirical metrics that compare real optimization behavior with analytically predicted behavior. Our investigation is notable for its tight integration with modern optimization analysis: rather than simply checking high-level assumptions made in the analysis (e.g. smoothness), we also verify key low-level identities used by the analysis to explain optimization behavior that might hold even if the high-level motivating assumptions do not. Notably, we find that smoothness-based analyses fail in practice under most scenarios, but the key identities commonly used in convex-optimization analyses often hold in practice despite the objective's global non-convexity.
BibTeX
@misc{tran2024reevaluating,
  author = {Hoang Tran and Qinzi Zhang and Ashok Cutkosky},
  title = {{Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning}},
  year = {2024},
  eprint = {2407.01825},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.01825},
}
Figure