Agnostic Online Learning and Excellent Sets

• URL: http://arxiv.org/abs/2108.05569v3
• Date: Sun, 06 Jul 2025 09:18:39 GMT
• Title: Agnostic Online Learning and Excellent Sets
• Authors: Maryanthe Malliaris, Shay Moran,
• Abstract summary: We show that $epsilon$-excellent sets exist for any $epsilon frac12$ in $k$-edge stable graphs in the sense of model theory.<n>We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types.
• Score: 18.557423328068122
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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 $\epsilon$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemer\'edi's celebrated Regularity Lemma). We prove that $\epsilon$-excellent sets exist for any $\epsilon < \frac{1}{2}$ in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $\epsilon < 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.

Related papers

• Primality Testing via Circulant Matrix Eigenvalue Structure: A Novel Approach Using Cyclotomic Field Theory [2.0547410497538445]
  This paper presents a novel primality test based on the eigenvalue structure of circulant matrices constructed from roots of unity.<n>We prove that integer $n > 2$ is prime if and only if a minimal validation of the matrix of $C_n = W_n + W_n2$ has exactly two irreducible factors.
  arXiv  Detail & Related papers  (2025-04-28T17:46:57Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  We show that when a pure strategy Nash equilibrium exists, $c$ becomes zero, leading to an optimal instance-dependent regret bound. Our algorithm also enjoys last-iterate convergence and can identify the pure strategy Nash equilibrium with near-optimal sample.
  arXiv  Detail & Related papers  (2025-02-24T20:20:06Z)
• The Aldous--Lyons Conjecture II: Undecidability [3.8370118222043694]
  We show that given a tailored non-local game $G$, it is undecidable to distinguish between the case where $G$ has a special kind of perfect strategy, and the case where every strategy for $G$ is far from being perfect. Using a reduction introduced in the companion paper [BCLV24], this undecidability result implies a negative answer to the Aldous--Lyons conjecture.
  arXiv  Detail & Related papers  (2024-12-30T22:59:56Z)
• Topological entanglement and number theory [0.0]
  Recent developments in the study of topological multi-boundary entanglement in the context of 3d Chern-Simons theory suggest a strong interplay between entanglement measures and number theory. We show that in the semiclassical limit of $k to infty$, these entropies converge to a finite value.
  arXiv  Detail & Related papers  (2024-10-02T12:43:57Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, mildly, and quantum learning theory.
  arXiv  Detail & Related papers  (2024-09-17T23:09:25Z)
• Lean-STaR: Learning to Interleave Thinking and Proving [53.923617816215774]
  We present Lean-STaR, a framework for training language models to produce informal thoughts prior to each step of a proof.<n>Lean-STaR achieves state-of-the-art results on the miniF2F-test benchmark within the Lean theorem proving environment.
  arXiv  Detail & Related papers  (2024-07-14T01:43:07Z)
• A Trichotomy for Transductive Online Learning [32.03948071550447]
  We present new upper and lower bounds on the number of learner mistakes in the transductive' online learning setting of Ben-David, Kushilevitz and Mansour (1997). This setting is similar to standard online learning, except that the adversary fixes a sequence of instances to be labeled at the start of the game, and this sequence is known to the learner.
  arXiv  Detail & Related papers  (2023-11-10T23:27:23Z)
• Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
  We show that both list-replicable and globally stable learning are impossible in the PAC setting. Specifically, we establish optimal bounds for list replicability and global stability numbers in finite classes.
  arXiv  Detail & Related papers  (2023-11-02T21:10:16Z)
• Simple online learning with consistent oracle [55.43220407902113]
  We consider online learning in the model where a learning algorithm can access the class only via the emphconsistent oracle -- an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far.
  arXiv  Detail & Related papers  (2023-08-15T21:50:40Z)
• Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions [33.49807210207286]
  A new auxiliary function $xi$ helps eliminate the complexity of handling the correlation between the numerator and denominator of AdaGrads iterations. We show that AdaGrad succeeds in converging under $(L_0)$smooth condition as long as the learning rate is lower than a threshold.
  arXiv  Detail & Related papers  (2023-05-29T09:33:04Z)
• The unstable formula theorem revisited via algorithms [18.557423328068122]
  In response to gaps in existing learning models, we introduce a new statistical learning model, called Probably Eventually Correct'' or PEC.<n>We characterize Littlestone (stable) classes in terms of this model.<n>In order to obtain a characterization of Littlestone classes in terms of frequent definitions, we build an equivalence theorem highlighting what is common to many existing approximation algorithms.
  arXiv  Detail & Related papers  (2022-12-09T18:53:34Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Don't Explain Noise: Robust Counterfactuals for Randomized Ensembles [50.81061839052459]
  We formalize the generation of robust counterfactual explanations as a probabilistic problem. We show the link between the robustness of ensemble models and the robustness of base learners. Our method achieves high robustness with only a small increase in the distance from counterfactual explanations to their initial observations.
  arXiv  Detail & Related papers  (2022-05-27T17:28:54Z)
• NaturalProver: Grounded Mathematical Proof Generation with Language Models [84.2064569475095]
  Theorem proving in natural mathematical language plays a central role in mathematical advances and education. We develop NaturalProver, a language model that generates proofs by conditioning on background references. NaturalProver is capable of proving some theorems that require short (2-6 step) proofs, and providing next-step suggestions that are rated as correct and useful over 40% of the time.
  arXiv  Detail & Related papers  (2022-05-25T17:01:18Z)
• multiPRover: Generating Multiple Proofs for Improved Interpretability in Rule Reasoning [73.09791959325204]
  We focus on a type of linguistic formal reasoning where the goal is to reason over explicit knowledge in the form of natural language facts and rules. A recent work, named PRover, performs such reasoning by answering a question and also generating a proof graph that explains the answer. In our work, we address a new and challenging problem of generating multiple proof graphs for reasoning over natural language rule-bases.
  arXiv  Detail & Related papers  (2021-06-02T17:58:35Z)
• Pareto Optimal Model Selection in Linear Bandits [15.85873315624132]
  We study a model selection problem in the linear bandit setting, where the learner must adapt to the dimension of the optimal hypothesis class on the fly. In this paper, we first establish a lower bound showing that, even with a fixed action set, adaptation to the unknown intrinsic dimension $d_star$ comes at a cost.
  arXiv  Detail & Related papers  (2021-02-12T16:02:06Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  We present a simple proof for the benefit of depth in multi-layer feedforward network with rectified activation ("depth separation") We present a concrete neural network with linear depth (in $m$) and small constant width ($leq 4$) that classifies the problem with zero error.
  arXiv  Detail & Related papers  (2021-01-18T15:40:27Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  We prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $tilde O(d6)$, ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2O(d)$ on the sample complexity.
  arXiv  Detail & Related papers  (2020-12-07T18:17:46Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.