1 citations · 2 across the 9 of their papers we have counts for
11 papers
Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors
Qian Li, Shang-Hua Teng
Why large language models trained via log-loss minimization over massive and diverse datasets exhibit broad capabilities and generalizable skills is not yet fully understood. Grau-…
Energy-Guided Learning for Heat Equation with Noisy Source: Optimal Estimation and Generalization Bounds
Zixiang Zhou, Xiaohui Chen, Shanghua Teng
Data and the governing partial differential equations (PDEs) of continuous-time dynamical systems provide rich structure for statistical learning. A central challenge is how to int…
Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
Julian Asilis, Shaddin Dughmi, Vatsal Sharan +3
Two of the most fundamental questions in statistical learning theory are the following: which prediction problems are learnable, and how should they be learned? For the former, ele…
Prediction Under Imperfect Compression: A Theory of Approximate MDL
Qian Li, Xinyu Mao, Shang-Hua Teng +1
Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: . Fo…
Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
Qian Li, Xinyu Mao, Shang-Hua Teng
Positional encoding (PE) is widely viewed as necessary for transformers to process ordered sequences: without them, the next-token map appears permutation-invariant in its context…
A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse
Atul Ganju, Travis McVoy, Shaddin Dughmi +1
We study language generation in the limit under a global preference ordering on strings, as introduced by Kleinberg and Wei. As is done in previous work, we aim for breadth, but im…
Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective
Siwei Wang, Yifei Shen, Haoran Sun +5
Recent reinforcement learning (RL) methods have substantially enhanced the planning capabilities of Large Language Models (LLMs), yet the theoretical basis for their effectiveness…
Semi-Random Graphs, Robust Asymmetry, and Reconstruction
Julian Asilis, Xi Chen, Dutch Hansen +1
The Graph Reconstruction Conjecture famously posits that any undirected graph on at least three vertices is determined up to isomorphism by its family of (unlabeled) induced subgra…
Proper Learnability and the Role of Unlabeled Data
Julian Asilis, Siddartha Devic, Shaddin Dughmi +2
Proper learning refers to the setting in which learners must emit predictors in the underlying hypothesis class , and often leads to learners with simple algorithmic forms (e.g.…
ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models
Siwei Wang, Yifei Shen, Shi Feng +3
Planning is a crucial element of both human intelligence and contemporary large language models (LLMs). In this paper, we initiate a theoretical investigation into the emergence of…
A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
Kyle Burke, Matthew Ferland, Svenja Huntemann +1
In this paper, we address a natural question at the intersection of combinatorial game theory and computational complexity: "Can a sum of simple tepid games in canonical form be in…