12 papers
How fast can you find a good hypothesis?
Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen +1
In the hypothesis selection problem, we are given sample and query access to finite set of candidate distributions (hypotheses), , and samples f…
Support Basis: Fast Attention Beyond Bounded Entries
Maryam Aliakbarpour, Vladimir Braverman, Junze Yin +1
Large language models (LLMs) have demonstrated remarkable performance across a wide range of tasks. However, the quadratic complexity of softmax attention remains a central bottlen…
Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
Maryam Aliakbarpour, Alireza Azizi, Ria Stevens
Independence testing is a fundamental problem in statistical inference: given samples from a joint distribution over multiple random variables, the goal is to determine whether…
Auditing Information Disclosure During LLM-Scale Gradient Descent Using Gradient Uniqueness
Sleem Abdelghafar, Maryam Aliakbarpour, Chris Jermaine
Disclosing information via the publication of a machine learning model poses significant privacy risks. However, auditing this disclosure across every datapoint during the training…
High-Dimensional Robust Mean Estimation with Untrusted Batches
Maryam Aliakbarpour, Vladimir Braverman, Yuhan Liu +1
We study high-dimensional mean estimation in a collaborative setting where data is contributed by users in batches of size . In this environment, a learner seeks to recover…
Shadow Tomography Against Adversaries
Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia +4
We study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of observables with …