Related papers: Agnostic Online Learning and Excellent Sets

Agnostic Online Learning and Excellent Sets

URL: http://arxiv.org/abs/2108.05569v1
Date: Thu, 12 Aug 2021 07:33:33 GMT
Title: Agnostic Online Learning and Excellent Sets
Authors: Maryanthe Malliaris and Shay Moran
Abstract summary: We prove existence of large indivisible'' sets in $k$-edge stable graphs. A theme in these proofs is the interaction of two abstract notions of majority, arising from measure, and from rank or dimension.
Score: 21.87574015264402
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We revisit a key idea from the interaction of model theory and combinatorics, the existence of large ``indivisible'' sets, called ``$\epsilon$-excellent,'' in $k$-edge stable graphs (equivalently, Littlestone classes). Translating to the language of probability, we find a quite different existence proof for $\epsilon$-excellent sets in Littlestone classes, using regret bounds in online learning. This proof applies to any $\epsilon < {1}/{2}$, compared to $< {1}/{2^{2^k}}$ or so in the original proof. We include a second proof using closure properties and the VC theorem, with other advantages but weaker bounds. As a simple corollary, the Littlestone dimension remains finite under some natural modifications to the definition. A theme in these proofs is the interaction of two abstract notions of majority, arising from measure, and from rank or dimension; we prove that these densely often coincide and that this is characteristic of Littlestone (stable) classes. The last section lists several open problems.

Related papers

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)
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)
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)
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)
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)

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