AF: Small: Memory Bounded Optimization and Learning

The amount of memory an algorithm requires stands as a critical factor in contemporary large-scale machine learning and optimization systems, exerting a profound impact on system size, quality, and energy efficiency. However, despite its practical significance, numerous fundamental questions persist. What learning and optimization problems require significant memory to solve? Are there inherent tradeoffs between the amount of memory an algorithm uses, and other computational resources such as the amount of data, or runtime? And what sorts of new, low-memory algorithms exist for practically important learning and optimization settings? This project tackles these questions, with the dual goals of developing useful low-memory algorithms applicable to a broad range of learning and optimization problems, and understanding when significant memory usage is unavoidable. This project also contains a significant educational, outreach, and mentoring component to train the next generation of researchers and practitioners and foster broader discussions of these topics within the academic and industrial research communities. One of the overarching goals of the project is to initiate a memory-centric perspective on optimization and learning, beginning by charting the lay-of-the-land of convex optimization under memory restrictions. This involves considering both concrete classes of problems such as linear regression and linear programming, as well as more abstract optimization and learning frameworks. In all these settings, what are the key problem parameters that determine the tradeoffs between memory usage and convergence rates? And what types of problem structure can be leveraged by surprisingly memory-efficient algorithms? A second technical thrust of this project is to explore memory considerations as a lens through which to examine the apparent computational hardness of problems like learning parities with noise, finding dense subgraphs, and sparse principal component analysis. Beyond these immediate technical goals, work on this project will establish algorithmic, information theoretic, and conceptual tools to facilitate future work on both the practical and theoretical aspects of memory-efficient computing. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.