  We consider the problem of estimating the learning rate in adaptive methods,
such as AdaGrad and Adam. We propose Prodigy, an algorithm that provably
estimates the distance to the solution $D$, which is needed to set the learning
rate optimally. At its core, Prodigy is a modification of the D-Adaptation
method for learning-rate-free learning. It improves upon the convergence rate
of D-Adaptation by a factor of $O(\sqrt{\log(D/d_0)})$, where $d_0$ is the
initial estimate of $D$. We test Prodigy on 12 common logistic-regression
benchmark datasets, VGG11 and ResNet-50 training on CIFAR10, ViT training on
Imagenet, LSTM training on IWSLT14, DLRM training on Criteo dataset, VarNet on
Knee MRI dataset, as well as RoBERTa and GPT transformer training on BookWiki.
Our experimental results show that our approach consistently outperforms
D-Adaptation and reaches test accuracy values close to that of hand-tuned Adam.
