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 develop a new algorithm called CronosAM, which combines Cronos with alternating minimization, to obtain an algorithm capable of training multi-layer networks with arbitrary architectures.On the theoretical side, we show Cronos converges to the global minimum of the convex reformulation under mild assumptions.We validate the efficacy of Cronos and CronosAM through extensive numerical experiments.In particular, we show that CronosAM can obtain comparable or better validation accuracy than standard tuned deep learning optimizers on vision and language tasks with benchmark datasets such as ImageNet and IMDB.To the best of our knowledge, CronosAM is the first algorithm to utilize the convex reformulation to enhance performance on large-scale learning tasks.