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.