11 citations · 14 across the 11 of their papers we have counts for
11 papers
Optimal Online Discrepancy Minimization in Linear Time
Ishaq Aden-Ali
We provide an online algorithm with the following guarantee: for any fixed sequence of vectors with , the algorithm assigns each ar…
Subliminal Effects in Your Data: A General Mechanism via Log-Linearity
Ishaq Aden-Ali, Noah Golowich, Allen Liu +3
Training modern large language models (LLMs) has become a veritable smorgasbord of algorithms and datasets designed to elicit particular behaviors, making it critical to develop te…
Quantization for Vector Search under Streaming Updates
Ishaq Aden-Ali, Hakan Ferhatosmanoglu, Alexander Greaves-Tunnell +2
Large-scale vector databases for approximate nearest neighbor (ANN) search typically store a quantized dataset in main memory for fast access, and full precision data on remote dis…
On the Injective Norm of Sums of Random Tensors and the Moments of Gaussian Chaoses
Ishaq Aden-Ali
We prove an upper bound on the expected injective norm of sums of subgaussian random tensors. Our proof is simple and does not rely on any explicit geometric or chaining a…
Majority-of-Three: The Simplest Optimal Learner?
Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen +1
Developing an optimal PAC learning algorithm in the realizable setting, where empirical risk minimization (ERM) is suboptimal, was a major open problem in learning theory for decad…
Optimal PAC Bounds Without Uniform Convergence
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty +1
In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hann…
The One-Inclusion Graph Algorithm is not Always Optimal
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty +1
The one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth achieves an optimal in-expectation risk bound in the standard PAC classification setup. In one of the first…
On the amortized complexity of approximate counting
Ishaq Aden-Ali, Yanjun Han, Jelani Nelson +1
Naively storing a counter up to value would require bits of memory. Nelson and Yu [NY22], following work of [Morris78], showed that if the query answers need only b…
Privately Learning Mixtures of Axis-Aligned Gaussians
Ishaq Aden-Ali, Hassan Ashtiani, Christopher Liaw
We consider the problem of learning mixtures of Gaussians under the constraint of approximate differential privacy. We prove that $\widetilde{O}(k^2 d \log^{3/2}(1/δ) / α^2 \vareps…
On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
Ishaq Aden-Ali, Hassan Ashtiani, Gautam Kamath
We provide sample complexity upper bounds for agnostically learning multivariate Gaussians under the constraint of approximate differential privacy. These are the first finite samp…
On the Sample Complexity of Learning Sum-Product Networks
Ishaq Aden-Ali, Hassan Ashtiani
Sum-Product Networks (SPNs) can be regarded as a form of deep graphical models that compactly represent deeply factored and mixed distributions. An SPN is a rooted directed acyclic…