6 citations · 17 across the 24 of their papers we have counts for
18 papers · 1 filter
Transformers Learn Two Competing Sorting Algorithms, and Only One Length-Generalizes
Khashayar Gatmiry, Nathan W. Henry, Chloe H. Su +5
We show that two-layer transformers trained to near-zero loss on a sorting task converge to one of two mechanistically distinct solution classes depending on their initialization.…
RLTLDR: Self-improvement by Internalizing Self-generated Feedback
Michael Kirchhof, Eleonora Gualdoni, Andrew Szot +6
The common paradigm of reinforcement learning with verifiable rewards (RLVR) is to let agents make multiple attempts at a task, and optimize towards the successful ones. This becom…
Learn Your Own Thoughts: Abstract Token Curriculum
Khashayar Gatmiry, Avrajit Ghosh, Parsa Mirtaheri +4
Large Language Models (LLMs) have achieved remarkable reasoning capabilities by utilizing chain-of-thought (CoT) as a scratchpad for intermediate stages of thinking. However, CoT t…
High-accuracy and dimension-free sampling with diffusions
Khashayar Gatmiry, Sitan Chen, Adil Salim
Diffusion models have shown remarkable empirical success in sampling from rich multi-modal distributions. Their inference relies on numerically solving a certain differential equat…
On the Role of Depth and Looping for In-Context Learning with Task Diversity
Khashayar Gatmiry, Nikunj Saunshi, Sashank J. Reddi +2
The intriguing in-context learning (ICL) abilities of deep Transformer models have lately garnered significant attention. By studying in-context linear regression on unimodal Gauss…
Computing Optimal Regularizers for Online Linear Optimization
Khashayar Gatmiry, Jon Schneider, Stefanie Jegelka
Follow-the-Regularized-Leader (FTRL) algorithms are a popular class of learning algorithms for online linear optimization (OLO) that guarantee sub-linear regret, but the choice of…
Simplicity Bias via Global Convergence of Sharpness Minimization
Khashayar Gatmiry, Zhiyuan Li, Sashank J. Reddi +1
The remarkable generalization ability of neural networks is usually attributed to the implicit bias of SGD, which often yields models with lower complexity using simpler (e.g. line…
Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?
Khashayar Gatmiry, Nikunj Saunshi, Sashank J. Reddi +2
The remarkable capability of Transformers to do reasoning and few-shot learning, without any fine-tuning, is widely conjectured to stem from their ability to implicitly simulate a…
What does guidance do? A fine-grained analysis in a simple setting
Muthu Chidambaram, Khashayar Gatmiry, Sitan Chen +2
The use of guidance in diffusion models was originally motivated by the premise that the guidance-modified score is that of the data distribution tilted by a conditional likelihood…
Adversarial Online Learning with Temporal Feedback Graphs
Khashayar Gatmiry, Jon Schneider
We study a variant of prediction with expert advice where the learner's action at round is only allowed to depend on losses on a specific subset of the rounds (where the struct…
Learning Mixtures of Gaussians Using Diffusion Models
Khashayar Gatmiry, Jonathan Kelner, Holden Lee
We give a new algorithm for learning mixtures of Gaussians (with identity covariance in ) to TV error , with quasi-polynomial ($O(n^{\text{poly\,log}…
EM for Mixture of Linear Regression with Clustered Data
Amirhossein Reisizadeh, Khashayar Gatmiry, Asuman Ozdaglar
Modern data-driven and distributed learning frameworks deal with diverse massive data generated by clients spread across heterogeneous environments. Indeed, data heterogeneity is a…
The Inductive Bias of Flatness Regularization for Deep Matrix Factorization
Khashayar Gatmiry, Zhiyuan Li, Ching-Yao Chuang +3
Recent works on over-parameterized neural networks have shown that the stochasticity in optimizers has the implicit regularization effect of minimizing the sharpness of the loss fu…
A Unified Approach to Controlling Implicit Regularization via Mirror Descent
Haoyuan Sun, Khashayar Gatmiry, Kwangjun Ahn +1
Inspired by the remarkable success of large neural networks, there has been significant interest in understanding the generalization performance of over-parameterized models. Subst…
Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond
Tasuku Soma, Khashayar Gatmiry, Sharut Gupta +1
Distributionally robust optimization (DRO) can improve the robustness and fairness of learning methods. In this paper, we devise stochastic algorithms for a class of DRO problems i…
On the generalization of learning algorithms that do not converge
Nisha Chandramoorthy, Andreas Loukas, Khashayar Gatmiry +1
Generalization analyses of deep learning typically assume that the training converges to a fixed point. But, recent results indicate that in practice, the weights of deep neural ne…
Convergence of the Riemannian Langevin Algorithm
Khashayar Gatmiry, Santosh S. Vempala
We study the Riemannian Langevin Algorithm for the problem of sampling from a distribution with density with respect to the natural measure on a manifold with metric . We as…
Testing Determinantal Point Processes
Khashayar Gatmiry, Maryam Aliakbarpour, Stefanie Jegelka
Determinantal point processes (DPPs) are popular probabilistic models of diversity. In this paper, we investigate DPPs from a new perspective: property testing of distributions. Gi…