More Like this

1. Model theory and agnostic online learning via excellent sets

   https://doi.org/10.1090/tran/9235  

   Malliaris, M; Moran, S (November 2024, Transactions of the American Mathematical Society)

   We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $\mathrm{ϵ<\#comment/>}$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemerédi’s celebrated Regularity Lemma). We prove that $\mathrm{ϵ<\#comment/>}$-excellent sets exist for any $\mathrm{ϵ<\#comment/>}>\frac{1}{2}$in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $\mathrm{ϵ<\#comment/>}>1/2^{2^k}$or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide. 

   more » « less
2. Smoothed Analysis of Online and Differentially Private Learning

   Haghtalab, Nika; Roughgarden, Tim; Shetty, Abhishek (October 2020, Advances in neural information processing systems)

   Practical and pervasive needs for robustness and privacy in algorithms have inspired the design of online adversarial and differentially private learning algorithms. The primary quantity that characterizes learnability in these settings is the Littlestone dimension of the class of hypotheses [Alon et al., 2019, Ben-David et al., 2009]. This characterization is often interpreted as an impossibility result because classes such as linear thresholds and neural networks have infinite Littlestone dimension. In this paper, we apply the framework of smoothed analysis [Spielman and Teng, 2004], in which adversarially chosen inputs are perturbed slightly by nature. We show that fundamentally stronger regret and error guarantees are possible with smoothed adversaries than with worst-case adversaries. In particular, we obtain regret and privacy error bounds that depend only on the VC dimension and the bracketing number of a hypothesis class, and on the magnitudes of the perturbations. 

   more » « less
3. An Equivalence Between Private Classification and Online Prediction

   Bun, Mark; Livni, Roi; Moran, Shay (January 2020, 61st Annual IEEE Symposium on Foundations of Computer Science)

   null (Ed.)

   We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. This answers an open question of Alon et al. (STOC 2019) who proved the converse statement (this question was also asked by Neel et al. (FOCS 2019)). Together these two results yield an equivalence between online learnability and private PAC learnability. We introduce a new notion of algorithmic stability called “global stability” which is essential to our proof and may be of independent interest. We also discuss an application of our results to boosting the privacy and accuracy parameters of differentially-private learners. 

   more » « less
4. Private and Online Learnability Are Equivalent

   https://doi.org/10.1145/3526074  

   Alon, Noga; Bun, Mark; Livni, Roi; Malliaris, Maryanthe; Moran, Shay (August 2022, Journal of the ACM)

   Let H be a binary-labeled concept class. We prove that H can be PAC learned by an (approximate) differentially private algorithm if and only if it has a finite Littlestone dimension. This implies a qualitative equivalence between online learnability and private PAC learnability. 

   more » « less
5. A multi-class extension of the mean field Bolker–Pacala population model

   https://doi.org/10.1515/rose-2018-0013  

   Bessonov, Mariya; Molchanov, Stanislav; Whitmeyer, Joseph (September 2018, Random Operators and Stochastic Equations)

   Abstract We extend our earlier mean field approximation of the Bolker–Pacala model of population dynamics by dividing the population into N classes, using a mean field approximation for each class but also allowing migration between classes as well as possibly suppressive influence of the population of one class over another class. For {N\geq 2} , we obtain one symmetric nontrivial equilibrium for the system and give global limit theorems. For {N=2} , we calculate all equilibrium solutions, which, under additional conditions, include multiple nontrivial equilibria. Lastly, we prove geometric ergodicity regardless of the number of classes when there is no population suppression across the classes. 

   more » « less