Search for: All records

We introduce two complementary techniques for efficient optimization that reduce memory requirements while accelerating training of large-scale neural networks. The first technique, Subset-Norm step size, generalizes AdaGrad-Norm and AdaGrad(-Coordinate) through step-size sharing. Subset-Norm (SN) reduces AdaGrad’s memory footprint from O(d) to O(sqrt(d)), where d is the model size. For non-convex smooth objectives under coordinate-wise sub-gaussian noise, we show a noise-adapted high-probability convergence guarantee with improved dimensional dependence of SN over existing methods. Our second technique, Subspace-Momentum, reduces the momentum state’s memory footprint by restricting momentum to a low-dimensional subspace while performing SGD in the orthogonal complement. We prove a high-probability convergence result for Subspace-Momentum under standard assumptions. Empirical evaluation on pre-training and fine-tuning LLMs demonstrates the effectiveness of our methods. For instance, combining Subset-Norm with Subspace-Momentum achieves Adam’s validation perplexity for LLaMA 1B in approximately half the training tokens (6.8B vs 13.1B) while reducing Adam’s optimizer-states memory footprint by more than 80% with minimal additional hyperparameter tuning. 

In the maximum coverage problem we are given d subsets from a universe [n], and the goal is to output k subsets such that their union covers the largest possible number of distinct items. We present the first algorithm for maximum coverage in the turnstile streaming model, where updates which insert or delete an item from a subset come one-by-one. Notably our algorithm only uses polylogn update time. We also present turnstile streaming algorithms for targeted and general fingerprinting for risk management where the goal is to determine which features pose the greatest re-identification risk in a dataset. As part of our work, we give a result of independent interest: an algorithm to estimate the complement of the pth frequency moment of a vector for p ≥ 2. Empirical evaluation confirms the practicality of our fingerprinting algorithms demonstrating a speedup of up to 210x over prior work. 

Constrained k-submodular maximization is a general framework that captures many discrete optimization problems such as ad allocation, influence maximization, personalized recommendation, and many others. In many of these applications, datasets are large or decisions need to be made in an online manner, which motivates the development of efficient streaming and online algorithms. In this work, we develop single-pass streaming and online algorithms for constrained k-submodular maximization with both monotone and general (possibly non-monotone) objectives subject to cardinality and knapsack constraints. Our algorithms achieve provable constant-factor approximation guarantees which improve upon the state of the art in almost all settings. Moreover, they achieve the fastest known running times and have optimal space usage. We experimentally evaluate our algorithms on instances for ad allocation and other applications, where we observe that our algorithms are practical and scalable, and construct solutions that are comparable in value even to offline greedy algorithms. 

Constrained k-submodular maximization is a general framework that captures many discrete optimization problems such as ad allocation, influence maximization, personalized recommendation, and many others. In many of these applications, datasets are large or decisions need to be made in an online manner, which motivates the development of efficient streaming and online algorithms. In this work, we develop single-pass streaming and online algorithms for constrained k-submodular maximization with both monotone and general (possibly non-monotone) objectives subject to cardinality and knapsack constraints. Our algorithms achieve provable constant-factor approximation guarantees which improve upon the state of the art in almost all settings. Moreover, they achieve the fastest known running times and have optimal space usage. We experimentally evaluate our algorithms on instances for ad allocation and other applications, where we observe that our algorithms are practical and scalable, and construct solutions that are comparable in value even to offline greedy algorithms. 

The requirement for C₂H₂concentrations below 2 parts per million (ppm) in gas streams for C₂H₄polymerization necessitates its semihydrogenation to C₂H₄. We demonstrate selective chemical looping combustion of C₂H₂in C₂H₄-rich streams by Bi₂O₃as an alternative catalytic pathway to reduce C₂H₂concentration below 2 ppm. Bi₂O₃combusts C₂H₂with a first-order rate constant that is 3000 times greater than the rate constant for C₂H₄combustion. In successive redox cycles, the lattice O of Bi₂O₃can be fully replenished without discernible changes in local Bi coordination or C₂H₂combustion selectivity. Heterolytic activation of C–H bonds across Bi–O sites and the higher acidity of C₂H₂results in lower barriers for C₂H₂activation than C₂H₄, enabling selective catalytic hydrocarbon combustion leveraging differences in molecular deprotonation energies. 

Despite longstanding excitement and progress toward understanding liquid–liquid phase separation in natural and artificial membranes, fundamental questions have persisted about which molecules are required for this phenomenon. Except in extraordinary circumstances, the smallest number of components that has produced large-scale, liquid–liquid phase separation in bilayers has stubbornly remained at three: a sterol, a phospholipid with ordered chains, and a phospholipid with disordered chains. This requirement of three components is puzzling because only two components are required for liquid–liquid phase separation in lipid monolayers, which resemble half of a bilayer. Inspired by reports that sterols interact closely with lipids with ordered chains, we tested whether phase separation would occur in bilayers in which a sterol and lipid were replaced by a single, joined sterol–lipid. By evaluating a panel of sterol–lipids, some of which are present in bacteria, we found a minimal bilayer of only two components (PChemsPC and diPhyPC) that robustly demixes into micron-scale, liquid phases. It suggests an additional role for sterol–lipids in nature, and it reveals a membrane in which tie-lines (and, therefore, the lipid composition of each phase) are straightforward to determine and will be consistent across multiple laboratories. 

Digital learning games can help address gender disparities in math by promoting better learning experiences and outcomes for girls. However, there is a need for more research to understand why some digital learning games might be especially effective for girls studying mathematics. In this study, we assess two possible pathways: that girls might benefit from math games because they reduce the anxiety and evaluation apprehension that girls are more likely to experience when doing math; and that girls might benefit from math games when they enjoy the narrative and thus experience greater engagement. To evaluate these pathways, our work uses multiple dimensions of gender (e.g., gender identity and gender-typed interests, activities, and traits) and surveys of affective experiences to examine the impact of three learning systems with identical learning content: a digital learning game, Decimal Point, that has consistently led to better learning for girls over boys; a new masculine-typed game, Ocean Adventure, developed based on a survey of over 300 students; and a conventional tutoring system. We predicted that girls and students with stronger feminine-typed characteristics would experience less math anxiety in both Decimal Point and Ocean Adventure compared to the tutor. We also predicted that girls and students with stronger feminine-typed characteristics would experience greater engagement and learning with Decimal Point while boys and students with stronger masculine-typed characteristics would experience greater engagement and learning with Ocean Adventure. Consistent with predictions, students with stronger feminine-typed characteristics experienced less anxiety and evaluation apprehension in both games compared to the tutor. This suggests that math learning games may provide a way to address these negative affective experiences. In terms of our measures of engagement, we found that students with stronger masculine-typed characteristics reported greater experience of mastery in the masculine Ocean Adventure; however, this was the only indicator that the more masculine narrative of Ocean Adventure led to different experiences based on gender. This suggests that narrative alone may not have a strong enough effect on students based on gender, especially when other game features are kept constant. Contrary to our predictions, there were no effects of gender identity or condition on learning outcomes, although both masculine-typed and feminine-typed characteristics were negatively associated with learning. Overall, these results point to the value of a multi-dimensional model of gender in assessing learning with a game, the important role learning games can have in reducing math anxiety and evaluation apprehension for girls and students with feminine-typed characteristics, and the nuanced effects of game narratives on experiences with game-based learning.