10 papers
Learning Source Structure: Bayesian Prediction with Transformers
Meir Feder, Ruediger Urbanke
A transformer trained on sequences whose source parameters are drawn afresh each time can learn only what the sequences share: the source family and its prior. The Bayesian predict…
Fisher Simplicity in Kolmogorov-Arnold Networks and Multilayer Perceptrons
Ami Tavory, Meir Feder
Kolmogorov-Arnold Networks (KANs) are motivated in part by interpretability: their learned edge functions can be inspected, pruned, and reduced to symbolic structure. In a fixed-ba…
A Layered Simplex Architecture for Large Alphabets
Meir Feder, Yaniv Fogel, Ruediger Urbanke
Probability estimation over large alphabets under log loss is a well-studied problem, with celebrated methods such as the Good-Turing estimator. We introduce and study a new Bayesi…
Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs
Mark Glass, Meir Feder
We demonstrate that the problem of finding the maximum cut of a planar graph with arbitrary weights can be easily mapped to a minimum T-join problem in the absolute dual graph - th…
Misspecified Universal Learning
Shlomi Vituri, Meir Feder
This paper addresses the problem of universal learning under model misspecification with log-loss. In this setting, the learner operates with a hypothesis class of models denoted b…
Implicit Binarization via Complex Phase Dynamics in Combinatorial Optimization
Khen Cohen, Mark Glass, Meir Feder +1
We introduce a physics-inspired continuous relaxation framework that yields substantially improved solutions for NP-hard combinatorial optimization problems, including Quadratic Un…
Leave-One-Out Learning with Log-Loss
Yaniv Fogel, Meir Feder
We study batch learning with log-loss in the individual setting, where the outcome sequence is deterministic. Because empirical statistics are not directly applicable in this regim…
Information-Theoretic Framework for Understanding Modern Machine-Learning
Meir Feder, Ruediger Urbanke, Yaniv Fogel
We introduce an information-theoretic framework that views learning as universal prediction under log loss, characterized through regret bounds. Central to the framework is an effe…
Universal Batch Learning Under The Misspecification Setting
Shlomi Vituri, Meir Feder
In this paper we consider the problem of universal {\em batch} learning in a misspecification setting with log-loss. In this setting the hypothesis class is a set of models . Ho…
Error Exponent in Agnostic PAC Learning
Adi Hendel, Meir Feder
Statistical learning theory and the Probably Approximately Correct (PAC) criterion are the common approach to mathematical learning theory. PAC is widely used to analyze learning p…