Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning

Hoang Tran, Qinzi Zhang, Ashok CutkoskySubmission to ICLR 2025 · Withdrawn

TL;DR

Standard convergence proofs for deep learning optimizers rely on theoretical assumptions—such as convexity, global smoothness, and the classical descent lemma—that frequently fail in practice. By measuring these analytical quantities directly along real training trajectories, the authors reveal that deep neural networks routinely optimize successfully even when textbook theory insists they shouldn't.

What Problem Does This Paper Address?

Optimization theory traditionally justifies algorithms like SGD, AdaGrad, and Adam by bounding a convergence criterion through an intermediate algebraic expression (e.g., regret or gradient inner-products) using assumptions such as convexity or $L$-smoothness. However, deep neural networks are manifestly non-convex and often non-smooth (due to ReLUs and MaxPool layers).

Rather than merely asking whether high-level assumptions like global smoothness hold, the authors investigate whether the low-level algebraic identities and inequalities that optimization proofs actually rely on hold along real optimization trajectories. If these core theoretical mechanics fail empirically, existing proofs cannot explain why modern optimizers work in practice.

Methods

The authors introduce lightweight, on-the-fly empirical metrics to track theoretical optimization quantities during training:

  1. Instantaneous Convexity Gap & Convexity Ratio: Measures deviation from convexity both locally ($y_t = x_{t-1}$) and globally ($y_t = x^*$, an approximate final stationary point): $$\text{convexity\_ratio}_T = \frac{\sum_{t=1}^T \langle \nabla F(x_t), x_t - x^* \rangle}{\sum_{t=1}^T (F(x_t) - F(x^*))}$$ Values $\ge 1$ denote convexity, values between $0$ and $1$ permit weak quasi-convexity convergence arguments (with a $1/K$ bound degradation), and values $<0$ violate convex analysis entirely.

  2. Instantaneous and Maximum Smoothness: Computes $\frac{\|\nabla f(x_t, z_t) - \nabla f(x_{t-1}, z_t)\|}{\|x_t - x_{t-1}\|}$. The authors demonstrate that this metric serves as a computationally cheap proxy for Hessian spectral norm (sharpness) without requiring expensive Hessian-vector products.

  3. Update Correlation (Testing the Descent Lemma): Smooth non-convex convergence proofs fundamentally depend on a negative inner-product between the gradient and the step, $\langle \nabla F(x_{t+1}), x_{t+1} - x_t \rangle < 0$, to ensure loss decrease. The authors measure an unbiased estimator: $$\text{update\_corr}_t = \langle \nabla f(x_{t+1}, z_{t+1}), x_{t+1} - x_t \rangle$$

  4. Random Scaling (RS) Framework Validation: They evaluate an alternative non-smooth framework where update steps are scaled by an exponential random variable ($s_t \sim \text{Exp}(1)$), testing whether stochastic online-to-non-convex conversion identities hold in practice.

Datasets

The authors evaluate these metrics across classical and modern deep learning benchmarks:

  • Synthetic Data & OpenML Datasets: Synthetic squared loss and logistic regression on Aloi, Connect-4, Covertype, and Poker.
  • Computer Vision: CIFAR-10 and ImageNet trained on ResNet-18.
  • Natural Language Processing: Pre-training BERT on the C4 dataset and GPT-2 on The Pile and C4 datasets.

Key Insights and Ideas

  • Local Convexity Occurs Along Optimization Paths: Even though neural network loss surfaces are globally non-convex, optimizers like SGD and AdamW frequently trace paths where the local convexity gap is negative (locally convex), notably on CIFAR-10 and GPT-2.
  • Convexity-Based Bounds Can Partially Survive in Vision/BERT: On CIFAR-10 and BERT, the convexity ratio remains positive ($>0.5$ for CIFAR-10; $>0.1$ for BERT). This suggests weak quasi-convexity arguments could theoretically hold with only a modest (e.g., $10\times$) constant-factor degradation in convergence bounds.
  • The Descent Lemma Fails in Deep Learning: In almost all deep learning runs (ImageNet, BERT, CIFAR-10), the average update correlation is positive. According to standard smooth non-convex optimization theory, a positive update correlation implies the loss should diverge or increase. Yet, models train effectively, meaning standard smooth descent lemmas fail to describe reality.
  • Loss Landscapes Resemble Ill-Conditioned Ravines: A positive update correlation indicates that updates bounce rapidly back and forth across valley walls (at the "edge of stability") while still drifting toward better minima.
  • Random Scaling Bridges the Gap: Applying randomized step-sizes ($s_t \sim \text{Exp}(1)$) yields an update correlation that is consistently negative and tightly tracks empirical loss reduction, supporting emerging non-smooth optimization frameworks.

Key Results

  • Smoothness Values Are Huge: Measured empirical smoothness constants range between $10^3$ and $10^6$ under standard learning rate schedules. When learning rates drop, smoothness spikes, aligning closely with "edge of stability" dynamics.
  • Fast Sharpness Proxy: The authors' finite-difference smoothness metric tracks the true maximum eigenvalue of the Hessian on CIFAR-10 with high fidelity, enabling sharpness tracking on large-scale models where Hessian calculations are intractable.
  • Positive Update Correlations Across Tasks: On ResNet-18 (ImageNet/CIFAR-10) and BERT, standard AdamW and SGDM exhibit positive average update correlations, directly falsifying the mechanism assumed in classical non-convex convergence proofs.

Limitations and Future Work

  • Anomalous Dataset Sensitivities: GPT-2 displayed negative update correlations on The Pile, but flipped to positive when trained on C4 or when The Pile was shuffled; the underlying reason remains unexplained.
  • Alternative Theoretical Foundations: While random scaling (RS) accurately predicts loss progress, it is not yet widely used in standard architectures without modifications.
  • Need for New Proof Paradigms: The authors call on optimization theorists to stop relying on traditional descent lemmas and global smoothness bounds, and instead develop analyses reflecting ill-conditioned, non-smooth landscapes and oscillatory dynamics.

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 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. In general, we find that real optimizers often make progress even when typical optimization analysis suggests that they should not. This highlights a need for developing new theoretical frameworks that are better aligned with practice.
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