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 transforms the traditionally "messy" non-convex training of neural networks into a scalable convex problem. By leveraging GPU acceleration and clever preconditioning, it is the first convex-reformulation algorithm to successfully train on massive datasets like ImageNet and complex architectures like GPT-2. Crucially, it offers global convergence guarantees and requires near-zero hyperparameter tuning.

The Problem: The Art vs. Science of Training

Training deep neural networks is notoriously difficult because their "loss landscapes" are non-convex—full of hills, valleys, and plateaus that can easily trap standard optimizers like SGD or Adam. Consequently, training often feels like an art form: engineers must meticulously tune learning rates, momentum, and weight decay to find a good solution. This process is computationally expensive and offers no mathematical guarantee that the final model is actually the best possible one (the global minimum).

While researchers have previously shown that shallow ReLU networks can be mathematically reformulated as convex problems (which do have guaranteed global minima), these methods were historically "memory hogs." They couldn't scale beyond tiny datasets like MNIST because the resulting convex programs involved massive, constrained linear models that were far too slow to solve on modern hardware.

Methods: Bridging Theory and Scale

The authors introduce CRONOS (Convex ReLU Optimized Neural networks via Operator Splitting) to bridge the gap between theoretical elegance and practical scale.

  1. ADMM for Robustness: They use the Alternating Direction Method of Multipliers (ADMM), an "operator splitting" technique. ADMM breaks the complex training objective into smaller, manageable sub-problems that can be solved in parallel.
  2. Nyström Preconditioning: The most expensive part of the ADMM step is solving a massive linear system. CRONOS uses a randomized Nyström approximation to create a "preconditioner"—essentially a mathematical shortcut that exploits the fact that most data matrices in machine learning are approximately low-rank. This allows them to solve the system in a fraction of the time.
  3. JAX & GPU Acceleration: The algorithm is implemented in JAX, utilizing Just-In-Time (JIT) compilation and XLA to run efficiently on high-end GPUs (like the RTX-4090).
  4. CRONOS-AM for Deep Networks: To move beyond shallow (two-layer) networks, they developed CRONOS-AM. This uses Alternating Minimization to treat the last two layers with the convex CRONOS solver while optimizing the earlier layers using standard methods, allowing it to handle arbitrary architectures like CNNs and Transformers.

Key Insights and Ideas

  • Scalability is Finally Here: The "aha moment" is the realization that convex reformulations aren't just for toy problems. By combining randomized linear algebra (Nyström) with modern GPU frameworks (JAX), the computational bottleneck of convex neural networks has been broken.
  • Hyperparameter-Free Training: Unlike Adam or SGD, which can fail if the learning rate is slightly off, CRONOS is remarkably robust. It converges to the global minimum under mild assumptions without the need for extensive grid searches for the "perfect" optimizer settings.
  • Convexity as a Primitive: By treating the convex solver as a "primitive" building block, CRONOS-AM shows that we can inject global optimality into specific parts of a deep network, stabilizing the training of complex architectures.

Key Results

The authors validated CRONOS across a diverse range of vision (CIFAR-10, ImageNet) and language (IMDb) tasks, testing architectures from MLPs to GPT-2 transformer blocks.

Validation accuracy over time for CIFAR-10 and ImageNet.
  • ImageNet Success: CRONOS-AM achieved a validation accuracy of 88.47% on ImageNet binary classification, performing comparably to or better than heavily tuned versions of Adam, SGD, and Shampoo.
  • Superior Language Modeling: On the IMDb sentiment task using a GPT-2 architecture, CRONOS reached 93.91% validation accuracy, outperforming tuned AdamW.
  • Speed and Efficiency: Despite performing more complex mathematical operations per iteration, CRONOS-AM’s total runtime was comparable to standard optimizers. For example, on CIFAR-10, CRONOS-AM took ~3.0 seconds, while AdamW took ~3.14 seconds.
Table comparing peak validation accuracy and best learning rates across optimizers.
  • Theoretical Rigor: The authors provide a proof that CRONOS converges to the global minimum at an $O(1/K)$ rate, providing a level of mathematical certainty that stochastic gradient methods lack. Furthermore, as shown in the table above, CRONOS-AM achieves top-tier accuracy without requiring a tuned learning rate (noted as NA).

Limitations and Future Work

While a major leap forward, the authors note a few areas for growth:

  • Architecture Specificity: The current convex reformulation is specifically tied to ReLU activations. Extending this to other activation functions (like GeLU or Swish) remains a challenge.
  • Multi-GPU Scaling: While it runs fast on a single RTX-4090, future work should explore scaling CRONOS across multi-GPU or TPU clusters for even larger models.
  • Theoretical Gap for Deep Networks: While CRONOS has global convergence guarantees for shallow networks, the alternating minimization used in CRONOS-AM for deep networks currently lacks the same level of ironclad theoretical proof, though it performs excellently in practice.

Summary updated

Abstract

We introduce the CRONOS algorithm for convex optimization of two-layer neural networks. CRONOS is the first algorithm capable of scaling to high-dimensional datasets such as ImageNet, which are ubiquitous in modern deep learning. This significantly improves upon prior work, which has been restricted to downsampled versions of MNIST and CIFAR-10. Taking CRONOS as a primitive, we then develop a new algorithm called CRONOS-AM, which combines CRONOS with alternating minimization, to obtain an algorithm capable of training multi-layer networks with arbitrary architectures. Our theoretical analysis proves that CRONOS converges to the global minimum of the convex reformulation under mild assumptions. In addition, we validate the efficacy of CRONOS and CRONOS-AM through extensive large-scale numerical experiments with GPU acceleration in JAX. Our results show that CRONOS-AM can obtain comparable or better validation accuracy than predominant tuned deep learning optimizers on vision and language tasks with benchmark datasets such as ImageNet and IMDb. To the best of our knowledge, CRONOS is the first algorithm which utilizes the convex reformulation to enhance performance on large-scale learning tasks.
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