113 citations · 146 across the 25 of their papers we have counts for
27 papers
The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization
Nived Rajaraman, Yanjun Han
We establish improved lower bounds on the minimax expected regret of stochastic bandit convex optimization for -Lipschitz functions on the -dimensional Euclidean ball. For ti…
Learning to Reason with Curriculum II: Compositional Generalization
Nived Rajaraman, Audrey Huang, Miroslav Dudik +3
Compositional generalization, the ability to solve complex problems by combining solutions to simpler sub-problems, is a fundamental capability of both natural and artificial intel…
Select and Improve: Understanding the Mechanics of Post-Training for Reasoning
Akshay Krishnamurthy, Audrey Huang, Nived Rajaraman
Reinforcement learning has rapidly emerged as a key component in the training of reasoning and coding models, yet it remains poorly understood from a mechanistic perspective. We st…
Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum
Nived Rajaraman, Audrey Huang, Miro Dudik +3
Chain-of-thought reasoning, where language models expend additional computation by producing thinking tokens prior to final responses, has driven significant advances in model capa…
Interactive Learning of Single-Index Models via Stochastic Gradient Descent
Nived Rajaraman, Yanjun Han
Stochastic gradient descent (SGD) is a cornerstone algorithm for high-dimensional optimization, renowned for its empirical successes. Recent theoretical advances have provided a de…
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…
The Space Complexity of Learning-Unlearning Algorithms
Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman +2
We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users. Formally, consider an algorithm for a particular learning…
: Faster Test-Time Scaling through Speculative Drafts
Mert Cemri, Nived Rajaraman, Rishabh Tiwari +6
Scaling test-time compute has driven the recent advances in the reasoning capabilities of large language models (LLMs), typically by allocating additional computation for more thor…
Computational Intractability of Strategizing against Online Learners
Angelos Assos, Yuval Dagan, Nived Rajaraman
Online learning algorithms are widely used in strategic multi-agent settings, including repeated auctions, contract design, and pricing competitions, where agents adapt their strat…
Scaling Test-Time Compute Without Verification or RL is Suboptimal
Amrith Setlur, Nived Rajaraman, Sergey Levine +1
Despite substantial advances in scaling test-time compute, an ongoing debate in the community is how it should be scaled up to enable continued and efficient improvements with scal…
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…
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…
Toward a Theory of Tokenization in LLMs
Nived Rajaraman, Jiantao Jiao, Kannan Ramchandran
While there has been a large body of research attempting to circumvent tokenization for language modeling (Clark et al., 2022; Xue et al., 2022), the current consensus is that it i…
Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensing
Nived Rajaraman, Devvrit, Aryan Mokhtari +1
Pruning schemes have been widely used in practice to reduce the complexity of trained models with a massive number of parameters. In fact, several practical studies have shown that…
Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits
Nived Rajaraman, Yanjun Han, Jiantao Jiao +1
We consider the sequential decision-making problem where the mean outcome is a non-linear function of the chosen action. Compared with the linear model, two curious phenomena arise…
Sample Efficient Deep Reinforcement Learning via Local Planning
Dong Yin, Sridhar Thiagarajan, Nevena Lazic +3
The focus of this work is sample-efficient deep reinforcement learning (RL) with a simulator. One useful property of simulators is that it is typically easy to reset the environmen…
Spectral Regularization Allows Data-frugal Learning over Combinatorial Spaces
Amirali Aghazadeh, Nived Rajaraman, Tony Tu +1
Data-driven machine learning models are being increasingly employed in several important inference problems in biology, chemistry, and physics which require learning over combinato…
Minimax Optimal Online Imitation Learning via Replay Estimation
Gokul Swamy, Nived Rajaraman, Matthew Peng +5
Online imitation learning is the problem of how best to mimic expert demonstrations, given access to the environment or an accurate simulator. Prior work has shown that in the infi…
Missing Mass Estimation from Sticky Channels
Prafulla Chandra, Andrew Thangaraj, Nived Rajaraman
Distribution estimation under error-prone or non-ideal sampling modelled as "sticky" channels have been studied recently motivated by applications such as DNA computing. Missing ma…
Semi-supervised Active Regression
Fnu Devvrit, Nived Rajaraman, Pranjal Awasthi
Labelled data often comes at a high cost as it may require recruiting human labelers or running costly experiments. At the same time, in many practical scenarios, one already has a…
Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally
Nived Rajaraman, Yanjun Han, Lin F. Yang +2
We study the statistical limits of Imitation Learning (IL) in episodic Markov Decision Processes (MDPs) with a state space . We focus on the known-transition setting w…
How good is Good-Turing for Markov samples?
Prafulla Chandra, Andrew Thangaraj, Nived Rajaraman
The Good-Turing (GT) estimator for the missing mass (i.e., total probability of missing symbols) in samples is the number of symbols that appeared exactly once divided by .…
FastSecAgg: Scalable Secure Aggregation for Privacy-Preserving Federated Learning
Swanand Kadhe, Nived Rajaraman, O. Ozan Koyluoglu +1
Recent attacks on federated learning demonstrate that keeping the training data on clients' devices does not provide sufficient privacy, as the model parameters shared by clients c…
Toward the Fundamental Limits of Imitation Learning
Nived Rajaraman, Lin F. Yang, Jiantao Jiao +1
Imitation learning (IL) aims to mimic the behavior of an expert policy in a sequential decision-making problem given only demonstrations. In this paper, we focus on understanding t…