8 citations · 11 across the 6 of their papers we have counts for
6 papers
High dimensional online calibration in polynomial time
Binghui Peng
In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space over a sequence of days, with the goal of being calibrated…
Theoretical limitations of multi-layer Transformer
Lijie Chen, Binghui Peng, Hongxun Wu
Transformers, especially the decoder-only variants, are the backbone of most modern large language models; yet we do not have much understanding of their expressive power except fo…
The complexity of approximate (coarse) correlated equilibrium for incomplete information games
Binghui Peng, Aviad Rubinstein
We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in $\mathit{ex…
On Limitations of the Transformer Architecture
Binghui Peng, Srini Narayanan, Christos Papadimitriou
What are the root causes of hallucinations in large language models (LLMs)? We use Communication Complexity to prove that the Transformer layer is incapable of composing functions…
The sample complexity of multi-distribution learning
Binghui Peng
Multi-distribution learning generalizes the classic PAC learning to handle data coming from multiple distributions. Given a set of data distributions and a hypothesis class of…
Fast swap regret minimization and applications to approximate correlated equilibria
Binghui Peng, Aviad Rubinstein
We give a simple and computationally efficient algorithm that, for any constant , obtains -swap regret within only rounds; t…