AF: Small: Memory Bounded Optimization and Learning

算法所需的内存量是当代大规模机器学习和优化系统中的关键因素，对系统规模、质量和能效产生深远影响。然而，尽管它具有实际意义，但仍然存在许多根本问题。 哪些学习和优化问题需要大量的内存来解决？ 在算法使用的内存量和其他计算资源（如数据量或运行时间）之间是否存在固有的权衡？ 对于实际重要的学习和优化设置，存在哪些新的低内存算法？ 该项目解决了这些问题，其双重目标是开发适用于广泛的学习和优化问题的有用的低内存算法，并了解何时不可避免地使用大量内存。 该项目还包含一个重要的教育，推广和指导组件，以培养下一代的研究人员和从业者，并促进学术界和工业界对这些主题的更广泛的讨论。该项目的总体目标之一是启动一个以内存为中心的优化和学习的角度，首先绘制内存限制下的凸优化的布局。 这涉及到既要考虑具体的问题类别，如线性回归和线性规划，也要考虑更抽象的优化和学习框架。 在所有这些设置中，决定内存使用和收敛速度之间权衡的关键问题参数是什么？ 什么类型的问题结构可以被惊人的内存效率算法所利用？这个项目的第二个技术重点是探索内存的考虑作为一个透镜，通过它来检查问题的明显计算难度，如学习奇偶噪声，寻找密集的子图，稀疏的主成分分析。 除了这些直接的技术目标之外，该项目的工作将建立算法，信息理论和概念工具，以促进未来在内存高效计算的实践和理论方面的工作。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.