AF: Small: Memory Bounded Optimization and Learning

AF：小：内存限制优化和学习

• 批准号: 2341890
• 负责人: Gregory Valiant
• 金额: $ 60万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-01-01 至 2026-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2341890&HistoricalAwards=false
• 关键词: AF; Small; Memory; Bounded; Optimization

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.

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