6 citations · 17 across the 24 of their papers we have counts for
27 papers
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…
Rethinking Invariance in In-context Learning
Lizhe Fang, Yifei Wang, Khashayar Gatmiry +2
In-Context Learning (ICL) has emerged as a pivotal capability of auto-regressive large language models, yet it is hindered by a notable sensitivity to the ordering of context examp…
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…
Projection-Free Online Convex Optimization via Efficient Newton Iterations
Khashayar Gatmiry, Zakaria Mhammedi
This paper presents new projection-free algorithms for Online Convex Optimization (OCO) over a convex domain . Classical OCO algorithms (such as O…
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…
Sampling with Barriers: Faster Mixing via Lewis Weights
Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala
We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope defined by inequalities in endowed with the metric defined by the Hessian of a convex barrie…
When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?
Yuansi Chen, Khashayar Gatmiry, Minhui Jiang
We analyze the mixing time of Metropolized Hamiltonian Monte Carlo (HMC) with the leapfrog integrator to sample from a distribution on whose log-density is smooth, h…
A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetry
Yuansi Chen, Khashayar Gatmiry
We study the mixing time of Metropolis-Adjusted Langevin algorithm (MALA) for sampling a target density on . We assume that the target density satisfies -isoperi…
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…
Bandit Algorithms for Prophet Inequality and Pandora's Box
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla +1
The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stop…
Quasi-Newton Steps for Efficient Online Exp-Concave Optimization
Zakaria Mhammedi, Khashayar Gatmiry
The aim of this paper is to design computationally-efficient and optimal algorithms for the online and stochastic exp-concave optimization settings. Typical algorithms for these se…
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…