CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks

Miria Feng, Zachary Frangella, Mert Pilanci

TL;DR

CRONOS is a new optimization framework that brings the theoretical guarantees of convex optimization to the scale of modern deep learning. By leveraging operator splitting (ADMM) and Nyström preconditioning, the authors have created the first convex-reformulated neural network training algorithm capable of handling high-dimensional datasets like ImageNet and large language models like GPT-2.

What Problem Does This Paper Address?

Training deep neural networks (DNNs) is traditionally a "non-convex" problem. This means the "landscape" of the loss function is full of valleys and peaks, making it NP-hard to find the absolute best solution. As a result, practitioners rely on stochastic first-order optimizers like SGD and Adam, which require meticulous hyperparameter tuning (learning rates, schedules, etc.) and offer no guarantee of reaching a global minimum.

While researchers previously proved that shallow ReLU networks could be reformulated as convex problems (which do have global convergence guarantees), these reformulations were computationally nightmarish. They involved solving massive, constrained linear models that couldn't scale beyond tiny datasets like downsampled MNIST. CRONOS aims to bridge this gap between theoretical elegance and practical scalability.

Methods

The authors introduce two primary algorithms: CRONOS and CRONOS-AM.

  1. CRONOS (The Primitive): Designed for two-layer ReLU networks. It treats the training as a constrained Generalized Linear Model (GLM) with group lasso regularization. To solve this at scale, they use:
  2. ADMM (Alternating Direction Method of Multipliers): A classic optimization technique that breaks a complex problem into smaller, manageable subproblems.
  3. Nyström Preconditioned Conjugate Gradient (NysPCG): This is the "secret sauce." Since the matrices involved are too large to store but are approximately low-rank, they use randomized linear algebra to approximate the matrix and speed up the linear system solver.
  4. JAX & GPU Acceleration: The entire stack is implemented in JAX, allowing for high-performance Just-In-Time (JIT) compilation and efficient GPU utilization.
  5. CRONOS-AM (The Extension): To handle deep, multi-layer networks, they use Alternating Minimization. They treat the last two layers as a convex problem (solved by CRONOS) and the earlier layers as a non-convex feature extractor (updated via standard optimizers like Adam), alternating between the two.

Datasets

The paper validates the approach across a diverse range of benchmarks:

  • Vision: CIFAR-10, Fashion-MNIST, Food-5k, and ImageNet (specifically 512x512 resolution, a major milestone for convex NN methods).
  • Language: The IMDb sentiment classification dataset, integrated with a pretrained GPT-2 architecture.

Key Insights and Ideas

  • Hyperparameter Robustness: Unlike Adam or SGD, which can fail completely if the learning rate is slightly off, CRONOS is nearly hyperparameter-free. It is guaranteed to converge for any fixed penalty parameter ($\rho > 0$), making it much more stable.
  • Exploiting Low-Rank Structure: The authors realized that real-world data matrices (like those in ImageNet) are approximately low-rank. By using Nyström preconditioning, they can solve massive linear systems in $O(\log(1/\delta))$ iterations, effectively removing the computational bottleneck that killed previous convex methods.
  • Convexity Meets Transformers: This is the first time a convex reformulation has been successfully applied to enhance a Transformer-based model (GPT-2), showing that these theoretical tools aren't just for simple MLPs.

Key Results

  • ImageNet Scalability: CRONOS-AM achieved 88.47% validation accuracy on ImageNet binary classification, performing comparably to or better than heavily tuned Adam and SGD.
  • Language Performance: On the IMDb dataset using GPT-2, CRONOS reached 93.91% accuracy, outperforming tuned AdamW (which hit 93.69%) while being significantly less sensitive to initialization.
  • Competitive Speed: Despite doing more "work" per iteration to maintain convex guarantees, CRONOS-AM’s total runtime is comparable to standard optimizers. For example, on CIFAR-10, CRONOS-AM took ~3.00s compared to Adam’s ~3.02s.

Limitations and Future Work

  • ReLU Focus: The current convex reformulation is specifically derived for ReLU activation functions. Extending this to other activations (like GeLU or Swish) remains a challenge.
  • Hybrid Nature of CRONOS-AM: While the 2-layer primitive is fully convex, the multi-layer extension (CRONOS-AM) still involves an alternating minimization step that is technically non-convex, though it performs well in practice.
  • Architecture Breadth: While they tested MLPs, CNNs, and GPT-2, the authors note that more work is needed to see how these methods scale to even more complex architectures like Vision Transformers (ViTs) on multi-GPU/TPU setups.

Summary updated

BibTeX
@inproceedings{feng2024cronos,
  author = {Miria Feng and Zachary Frangella and Mert Pilanci},
  title = {{CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=YfLzYczAo3},
}
Figure