Ishaq Aden-Ali

Selected publications

1. Preprint

   Optimal Online Discrepancy Minimization in Linear Time

   Ishaq Aden-Ali

   Preprint, 2026

   Abs arXiv

   We provide an online algorithm with the following guarantee: for any fixed sequence of vectors \(v_1,…,v_T ∈\mathbb{R}^d\)with \(\|v_i\|_2 \le 1\), the algorithm assigns each arriving vector \(v_t\) a random sign \(\varepsilon_t\) such that every prefix sum \(\sum_{i=1}^{t} \varepsilon_i v_i\) can be written as the sum of three coupled standard Gaussian vectors. Our algorithm runs in \(O(dT)\) time and achieves the optimal prefix discrepancy bound \(\max_{1 \le t \le T} \left\| \sum_{i=1}^{t} \varepsilon_i v_i \right\|_∞= O\left(\sqrt{\log T}\right)\) with high probability. This recovers the optimal bound of Kulkarni, Reis, and Rothvoss, whose algorithm runs in time exponential in \(T\) and \(d\). The algorithm and main proof were discovered in a GPT-5.5 Pro Extended conversation prompted by the author.

2. ICML

   Subliminal Effects in Your Data: A General Mechanism via Log-Linearity

   Ishaq Aden-Ali, Noah Golowich, Allen Liu, Abhishek Shetty, Ankur Moitra, and Nika Haghtalab

   International Conference on Machine Learning, 2026

   Abs arXiv Code

   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 techniques to understand the effects of datasets on the model’s properties. This is exacerbated by recent experiments that show datasets can transmit signals that are not directly observable from individual datapoints, posing a conceptual challenge for dataset-centric understandings of LLM training and suggesting a missing fundamental account of such phenomena. Towards understanding such effects, inspired by recent work on the linear structure of LLMs, we uncover a general mechanism through which hidden subtexts can arise in generic datasets. We introduce Logit-Linear-Selection (LLS), a method that prescribes how to select subsets of a generic preference dataset to elicit a wide range of hidden effects. We apply LLS to discover subsets of real-world datasets so that models trained on them exhibit behaviors ranging from having specific preferences, to responding to prompts in a different language not present in the dataset, to taking on a different persona. Crucially, the effect persists for the selected subset, across models with varying architectures, supporting its generality and universality.

3. Preprint

   On the Injective Norm of Sums of Random Tensors and the Moments of Gaussian Chaoses

   Ishaq Aden-Ali

   Preprint, 2025

   Abs arXiv

   We prove an upper bound on the expected \( \ell_p \) injective norm of sums of subgaussian random tensors. Our proof is simple and does not rely on any explicit geometric or chaining arguments. Instead, it follows from a simple application of the PAC-Bayesian lemma, a tool that has proven effective at controlling the suprema of certain “smooth” empirical processes in recent years. Our bound strictly improves a very recent result of Bandeira, Gopi, Jiang, Lucca, and Rothvoss. In the Euclidean case (\(p=2\)), our bound sharpens a result of Latała that was central to proving his estimates on the moments of Gaussian chaoses. As a consequence, we obtain an elementary proof of this fundamental result.

4. COLT

   Majority-of-Three: The Simplest Optimal Learner?

   Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy

   Conference on Learning Theory, 2024

   Abs arXiv

   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 decades. The problem was finally resolved by Hanneke a few years ago. Unfortunately, Hanneke’s algorithm is quite complex as it returns the majority vote of many ERM classifiers that are trained on carefully selected subsets of the data. It is thus a natural goal to determine the simplest algorithm that is optimal. In this work we study the arguably simplest algorithm that could be optimal: returning the majority vote of three ERM classifiers. We show that this algorithm achieves the optimal in-expectation bound on its error which is provably unattainable by a single ERM classifier. Furthermore, we prove a near-optimal high-probability bound on this algorithm’s error. We conjecture that a better analysis will prove that this algorithm is in fact optimal in the high-probability regime.

5. FOCS

   Optimal PAC Bounds Without Uniform Convergence

   Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy

   IEEE Symposium on Foundations of Computer Science, 2023

   Abs arXiv

   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 Hanneke established sharp upper bounds in this setting. However, the reliance of their argument on the uniform convergence principle limits its applicability to more general learning settings such as multiclass classification. In this paper, we address this issue by providing optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments. Our framework converts the leave-one-out error of permutation invariant predictors into high probability risk bounds. As an application, by adapting the one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth, we propose an algorithm that achieves an optimal PAC bound for binary classification. Specifically, our result shows that certain aggregations of one-inclusion graph algorithms are optimal, addressing a variant of a classic question posed by Warmuth. We further instantiate our framework in three settings where uniform convergence is provably suboptimal. For multiclass classification, we prove an optimal risk bound that scales with the one-inclusion hypergraph density of the class, addressing the suboptimality of the analysis of Daniely and Shalev-Shwartz. For partial hypothesis classification, we determine the optimal sample complexity bound, resolving a question posed by Alon, Hanneke, Holzman, and Moran. For realizable bounded regression with absolute loss, we derive an optimal risk bound that relies on a modified version of the scale-sensitive dimension, refining the results of Bartlett and Long. Our rates surpass standard uniform convergence-based results due to the smaller complexity measure in our risk bound.