5 papers · 1 filter
Dynamic estimation of slowly varying sequences
Prashant Gokhale, Mikhail Khodak, Sandeep Silwal
We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude of the difference between the elem…
DynMuon: A Dynamic Spectral Shaping View of Muon
Fangzhou Wu, Rikhav Shah, Sandeep Silwal +1
In recent years, Muon has emerged as the dominant method for training large language models, and transformers more broadly. The essential difference, when compared to standard grad…
Improved Approximations for Hard Graph Problems using Predictions
Anders Aamand, Justin Y. Chen, Siddharth Gollapudi +2
We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the…
Learning-Augmented Frequent Directions
Anders Aamand, Justin Y. Chen, Siddharth Gollapudi +2
An influential paper of Hsu et al. (ICLR'19) introduced the study of learning-augmented streaming algorithms in the context of frequency estimation. A fundamental problem in the st…
Optimal Algorithms for Augmented Testing of Discrete Distributions
Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld +1
We consider the problem of hypothesis testing for discrete distributions. In the standard model, where we have sample access to an underlying distribution , extensive research h…