4 papers
Algorithmic Task Capture, Computational Complexity, and Inductive Bias of Infinite Transformers
Orit Davidovich, Zohar Ringel
We formally define algorithmic capture of combinatorial tasks as the ability of a transformer to extrapolate to arbitrary task sizes with controllable error and logarithmic sample…
Mitigating the Curse of Detail: Scaling Arguments for Feature Learning and Sample Complexity
Noa Rubin, Orit Davidovich, Zohar Ringel
Two pressing topics in the theory of deep learning are the interpretation of feature learning (FL) mechanisms and the determination of implicit bias of networks in the rich regime.…
Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
Orit Davidovich, Shimrit Shtern, Segev Wasserkrug +1
Since the 1990s, considerable empirical work has been carried out to train statistical models, such as neural networks (NNs), as learned heuristics for combinatorial optimization (…
Finding Probably Approximate Optimal Solutions by Training to Estimate the Optimal Values of Subproblems
Nimrod Megiddo, Segev Wasserkrug, Orit Davidovich +1
The paper is about developing a solver for maximizing a real-valued function of binary variables. The solver relies on an algorithm that estimates the optimal objective-function va…