2 citations · 3 across the 10 of their papers we have counts for
11 papers
The Conditional Regret-Capacity Theorem for Batch Universal Prediction
Marco Bondaschi, Michael Gastpar
We derive a conditional version of the classical regret-capacity theorem. This result can be used in universal prediction to find lower bounds on the minimal batch regret, which is…
What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains
Chanakya Ekbote, Marco Bondaschi, Nived Rajaraman +4
In-context learning (ICL) is a hallmark capability of transformers, through which trained models learn to adapt to new tasks by leveraging information from the input context. Prior…
From Markov to Laplace: How Mamba In-Context Learns Markov Chains
Marco Bondaschi, Nived Rajaraman, Xiuying Wei +5
While transformer-based language models have driven the AI revolution thus far, their computational complexity has spurred growing interest in viable alternatives, such as structur…
Batch Normalization Decomposed
Ido Nachum, Marco Bondaschi, Michael Gastpar +1
\emph{Batch normalization} is a successful building block of neural network architectures. Yet, it is not well understood. A neural network layer with batch normalization comprises…
Transformers on Markov Data: Constant Depth Suffices
Nived Rajaraman, Marco Bondaschi, Kannan Ramchandran +2
Attention-based transformers have been remarkably successful at modeling generative processes across various domains and modalities. In this paper, we study the behavior of transfo…
Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models
Alliot Nagle, Adway Girish, Marco Bondaschi +3
We formalize the problem of prompt compression for large language models (LLMs) and present a framework to unify token-level prompt compression methods which create hard prompts fo…
Local to Global: Learning Dynamics and Effect of Initialization for Transformers
Ashok Vardhan Makkuva, Marco Bondaschi, Chanakya Ekbote +4
In recent years, transformer-based models have revolutionized deep learning, particularly in sequence modeling. To better understand this phenomenon, there is a growing interest in…
Batch Universal Prediction
Marco Bondaschi, Michael Gastpar
Large language models (LLMs) have recently gained much popularity due to their surprising ability at generating human-like English sentences. LLMs are essentially predictors, estim…
Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains
Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish +4
Attention-based transformers have achieved tremendous success across a variety of disciplines including natural languages. To deepen our understanding of their sequential modeling…
LASER: Linear Compression in Wireless Distributed Optimization
Ashok Vardhan Makkuva, Marco Bondaschi, Thijs Vogels +3
Data-parallel SGD is the de facto algorithm for distributed optimization, especially for large scale machine learning. Despite its merits, communication bottleneck is one of its pe…
Alpha-NML Universal Predictors
Marco Bondaschi, Michael Gastpar
Inspired by the connection between classical regret measures employed in universal prediction and Rényi divergence, we introduce a new class of universal predictors that depend on…