CAREER: Foundations of Memory-Constrained Machine Learning

Memory required to perform a computational task is one of the most fundamental measures used by theoretical computer scientists to assess how difficult a task is. Nevertheless, in practice, memory optimization received limited attention until the emergence of big data applications. More recently, the rapid growth of large-scale machine learning (ML) systems, including large language models (LLMs), has pushed model parameter counts far beyond improvements in memory hardware, raising concerns that memory may soon become the primary bottleneck in serving them. This growing need for memory-efficient alternatives is further amplified by interest in on-device learning, driven by concerns over data security, transmission costs, and the demand for personalized applications. The field of learning theory has already deeply explored the data and time required for various ML tasks; however, our understanding of their memory requirements remains limited. The goal of this project is to systematically address this gap and develop a foundational theory of the capabilities and limits of memory-constrained learning. The new approaches explored in the project aims to unconditionally answer whether the data and time requirements to learn drastically increase when using low-memory algorithms – which include the commonly used methods in practice such as stochastic gradient descent. This project draws tools from various mathematical areas such as complexity theory, learning theory and information theory. The educational plan of this project involves training of undergraduate and graduate students through (1) foundational courses in theoretical computer science (TCS), as well as advanced courses at the intersection of these mathematical areas, and (2) supervised undergraduate and graduate research aligned with the themes of this project. The first two thrusts of this project will systematically characterize the memory requirements of fundamental supervised and unsupervised machine learning (ML) tasks in the streaming model – a setting that closely reflects the realities of large-scale data processing. Despite extensive work on streaming algorithms, quantifying the memory requirements of ML tasks in this model presents new challenges that this project aims to address. First, the streaming literature typically focuses on worst-case data streams, whereas learning theory commonly assumes that data are sampled independently and identically from an underlying distribution. Second, establishing memory requirements even when the learner has access to a super-polynomial amount of data requires going beyond the sample regimes considered in independently and identically streams. The third thrust of this project will establish memory requirements in learning paradigms beyond the sample-based model, such as machine unlearning and learning in the query model, with broader implications to LLM safety and computational complexity theory, respectively. 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. NSF Award ID: 2542741 | Program: 01003031DB NSF RESEARCH & RELATED ACTIVIT,01002930DB NSF RESEARCH & RELATED ACTIVIT,01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Sumegha Garg | Institution: Rutgers University New Brunswick, NEW BRUNSWICK, NJ | Award Amount: $344,821 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2542741 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2542741.html