  Although deep learning has made great progress in recent years, the exploding
economic and environmental costs of training neural networks are becoming
unsustainable. To address this problem, there has been a great deal of research
on *algorithmically-efficient deep learning*, which seeks to reduce training
costs not at the hardware or implementation level, but through changes in the
semantics of the training program. In this paper, we present a structured and
comprehensive overview of the research in this field. First, we formalize the
*algorithmic speedup* problem, then we use fundamental building blocks of
algorithmically efficient training to develop a taxonomy. Our taxonomy
highlights commonalities of seemingly disparate methods and reveals current
research gaps. Next, we present evaluation best practices to enable
comprehensive, fair, and reliable comparisons of speedup techniques. To further
aid research and applications, we discuss common bottlenecks in the training
pipeline (illustrated via experiments) and offer taxonomic mitigation
strategies for them. Finally, we highlight some unsolved research challenges
and present promising future directions.
