6 papers · 1 filter
Tight Sample Complexity of Transformers
Chenxiao Yang, Nathan Srebro, Zhiyuan Li
We tightly characterize the VC dimension of depth- Transformers with a total of parameters, mapping an input sequence of length to a single output, establishing an upper…
On Incentivized Exploration beyond Bayesianism and Full-Information
Dimitar Chakarov, Lee Cohen, Nathan Srebro
We extend Incentive Compatible Exploration beyond the Bayesian full-information setting of Kremer et al. [2014]. We consider agents that may possess external information unknown to…
Learning through Internalization
Nikolaos Tsilivis, Nirmit Joshi, Marko Medvedev +2
We study internalization processes, by which neural-network-based systems absorb an explicit computational procedure into their own weights, and how they facilitate learning. We in…
Learning to Think from Multiple Thinkers
Nirmit Joshi, Roey Magen, Nathan Srebro +2
We study learning with Chain-of-Thought (CoT) supervision from multiple thinkers, all of whom provide correct but possibly systematically different solutions, e.g., step-by-step so…
Recursive Models for Long-Horizon Reasoning
Chenxiao Yang, Nathan Srebro, Zhiyuan Li
Modern language models reason within bounded context, an inherent constraint that poses a fundamental barrier to long-horizon reasoning. We identify recursion as a core principle f…
Positive Distribution Shift as a Framework for Understanding Tractable Learning
Marko Medvedev, Idan Attias, Elisabetta Cornacchia +3
We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training di…