R. Narasimhan Workshop 2026
January 5-6, 2026 • Tata Institute of Fundamental Research, Mumbai
Theme: Online Learning and Optimization
View Program
January 5-6, 2026 • Tata Institute of Fundamental Research, Mumbai
Theme: Online Learning and Optimization
View Program
Prof. R Narasimhan (1926-2007), often referred to as the Bhisma of Computer Science and Technology in India, made a significant contribution to the development of computer science education, research, and technology in India in the early stages.
This R. Narasimhan Annual Workshop is supported by a generous endowment made by members of Prof. Narasimhan’s family: Mrs. Sita Narasimhan, Ms. Tanjam Jacobson, and Dr. Krishna Bharat, through The Bharat Family Fund.
The 2026 edition focuses on Online Learning and Optimization with a new two-talk format: a plenary-style introductory talk on Day 1 and a detailed technical talk on Day 2 from each speaker.
Georgia Institute of Technology
Ashwin Pananjady is the Gerald D. McInvale Early Career Professor and Assistant Professor at Georgia Tech, with a joint appointment between the H. Milton Stewart School of Industrial and Systems Engineering and the School of Electrical and Computer Engineering. His research in statistics, optimization and applied probability has been recognized by early-career awards from the Bernoulli Society and Institute of Mathematical Statistics, paper recognitions from the Mathematical Optimization Society and Algorithmic Learning Theory conference, and research fellowships/awards from the Simons Institute, Google, Amazon, and Adobe.
Long ago, Pananjady spent a summer building character in Mumbai. He has fond memories of trying to prove theorems in TIFR, negotiating monsoon rains in Colaba, and competing for standing room on the Virar Fast.
University of Southern California
Vatsal Sharan is a faculty at USC, where he tries to understand how learning and life works. He's made a teeny bit of progress on the former, but none on the latter. He also likes to run, meditate and eat.
Indian Institute of Science, Bengaluru
Gugan Thoppe is an Assistant Professor at IISc Bengaluru. With his students and collaborators, he builds reinforcement learning (RL) algorithms that behave even when the world doesn’t. They chase guarantees—monotonicity, sample complexity, and the occasional speedup—and apply them to problems that didn’t ask for RL but needed it, such as histopathology and blockchains.
Google Deepmind, Bangalore
Dheeraj is a Research Scientist at Google DeepMind. He is interested in theoretical machine learning, applied probability and statistics. His current theoretical work focuses on sampling, generative modeling with diffusion models and optimization in the Wasserstein space. Over the last year, He has been interested in making algorithmic improvements in large scale generative modeling. To this end, he spends most of his time debugging undocumented compiler/ API issues using LLMs.
He received his PhD in EECS from MIT in 2021 and his Dual Degree in EE from IIT Madras in 2016.
Indian Institute of Technology Bombay
Pranay is an Assistant Professor at IIT Bombay in the Centre for Machine Intelligence and Data Science (C-MInDS). Till January 2025, he was a Research Scientist in the Department of Electrical and Computer Engineering at Carnegie Mellon University. In August 2021, he finished his PhD in Electrical Engineering and Computer Science at Syracuse University. Before that, he finished his B.Tech-M.Tech dual-degree in Electrical Engineering from IIT Kanpur. His research interests include federated and collaborative learning, stochastic optimization, reinforcement learning, and differential privacy.
Indian Institute of Technology Delhi
Ashish Chiplunkar has been teaching at IIT Delhi for six years. In the past, he was a post-doctoral researcher at EPFL, Switzerland and Tel Aviv University, Israel. He did his PhD at IIT Bombay. When he is not teaching, Ashish pursues his research interests, which include problems involving uncertainty, which include online and stochastic problems. Outside work, Ashish spends likes to spend his time running, learning Indian classical music, and playing board games.
TIFR, Mumbai
Abhishek Sinha is a faculty member in the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai, India. Prior to joining TIFR, he had been on the faculty of the Dept. of Electrical Engineering at the Indian Institute of Technology Madras. He received his Ph.D. from the Massachusetts Institute of Technology, USA, where he was affiliated with the Laboratory for Information and Decision Systems. Thereafter, Abhishek worked as a senior engineer at Qualcomm Research, San Diego. He obtained his M.E. degree in Telecommunication Engg. from the Indian Institute of Science, Bangalore, and B.E. degree in Electronics and Telecommunication Engg. from Jadavpur University, Kolkata, India. He is a recipient of the Google India Research Award 2023, INSA Medal for Young Scientists 2021, Best Paper Awards in INFOCOM 2018 and MobiHoc 2016, and Jagadis Bose National Science Talent Search (JBNSTS) scholarship 2006, Kolkata, India. His areas of interest include theoretical machine learning, optimization, and information theory.
Title: Predicting the behavior of iterative algorithms in high dimensional, average-case settings
Abstract: Iterative algorithms are the workhorses of modern statistical signal processing and machine learning. Algorithm design and analysis is largely based on variational properties of the continuous optimization problem at hand, and the classical focus has been on obtaining worst-case convergence guarantees over classes of problems that possess certain types of geometry. However, modern optimization problems in statistical settings are high-dimensional, involve random data, and are therefore inherently average-case: consequently, algorithms often behave differently from what is suggested by classical theory. With the motivation of better understanding optimization in such settings, I will present a toolbox for deriving “state evolutions” for a wide variety of algorithms with random data. These are non-asymptotic, near-exact predictions of the statistical behavior of the algorithm, which apply even when the underlying optimization problem is nonconvex or the algorithm is randomly initialized. We will showcase these predictions on deterministic and stochastic variants of complex algorithms employed in some canonical statistical models, discussing applications to hyperparameter tuning and signal reconstruction in tomography.
Title: Memory as a lens to understand learning and optimization
Abstract: What is the role of memory in learning and optimization? The optimal convergence rates (measures in terms of the number of oracle queries or samples needed) for various optimization problems are achieved by computationally expensive optimization techniques, such as second-order methods and cutting-plane methods. We will discuss if simpler, faster and memory-limited algorithms such as gradient descent can achieve these optimal convergence rates for the prototypical optimization problem of minimizing a convex function with access to a gradient. Our results hint at a perhaps curious dichotomy—it is not possible to significantly improve on the convergence rate of known memory efficient techniques (which are linear-memory variants of gradient descent for many of these problems) without using substantially more memory (quadratic memory for many of these problems). Therefore memory could be a useful discerning factor to provide a clear separation between 'efficient' and 'expensive' techniques. This perspective can also be applied to understand mechanisms which transformers use to solve certain algorithmic tasks. We will show empirical evidence that transformers learn to achieve second-order convergence rates for solving linear-regression tasks, leveraging some of the theory of optimization and memory-limited learning.
This is mostly based on joint work with Annie Marsden, Aaron Sidford, Gregory Valiant, Deqing Fu, Tian-Qi Chen and Robin Jia.
Title: Policy Iteration and the Theory-Practice Gap in Reinforcement Learning
Abstract: Reinforcement learning (RL) studies how to compute optimal policies (or strategies) for sequential decisions under uncertainty. In this talk, I will give an overview of these concepts and follow it up with an in-depth discussion on Policy Iteration (PI) and Conservative PI (CPI), the idealized approaches for solving such problems. I will show that PI enjoys monotonic improvement in the value function, a performance measure, of the intermediate policies, while CPI, additionally, admits per-step performance-difference lower bounds. I will then contrast this theory with practice, where modern agents rely on sampled data, bootstrapping, and function approximation to evaluate and improve policies. These ingredients can break the idealized guarantees, causing non-monotonic updates, oscillations, divergence, or suboptimal convergence. The goal of this talk is to make this theory-practice gap precise, setting the stage for the second talk set for bridging it.
This talk is based on the following joint work:
Gopalan, A., & Thoppe, G. (2026). Does DQN learn?. IEEE Transaction on Automatic Control (To appear), arXiv: arXiv:2205.13617.
Title: Stochastic Algorithms for Sampling and Mean Field Optimization
Abstract: Sampling and mean field optimization can be seen as optimization in the space of probability distributions. Stochastic optimization algorithms like SGD have been immensely successful for optimization over Euclidean spaces. However the infinite dimensional space of probability distributions poses unique challenges. In this talk, I will discuss my recent work on design and analysis of stochastic algorithms to improve sampling and mean field optimization, by combining the probabilistic view in the path space and the PDE/ optimal transport view of probability flow.
Title: Natural Policy Gradient for Average Reward Non-Stationary RL
Abstract: We consider the problem of non-stationary reinforcement learning (RL) in the infinite-horizon average-reward setting. We model it by a Markov Decision Process with time-varying rewards and transition probabilities, with a variation budget of . Existing non-stationary RL algorithms focus on model-based and model-free value-based methods. Policy-based methods, despite their flexibility in practice, are not theoretically well understood in non-stationary RL. We propose and analyze the first model-free policy-based algorithm, Non-Stationary Natural Actor-Critic (NS-NAC), a policy gradient method with a restart-based exploration for change and a novel interpretation of learning rates as adapting factors.
Title: The Weighted k-Server Problem
Abstract: Abstract: The (unweighted) k-server problem is a cornerstone problem in online computation. The problem concerns moving k identical servers to serve requests in a metric space, while minimizing the total distance travelled by the servers. The weighted k-server problem is a variant where the servers are distinguishable due to their weight, and the cost of moving a server is the product of the distance and its weight. Surprisingly, this innocuous-looking introduction of weights makes the problem so hard that no competitive algorithm is known on metrics other than the uniform metric for k>2 (while for the unweighted problem, a (2k-1)-competitive algorithm is known for all metrics). On the uniform metric spaces, the competitive ratio of weighted k-server was known to be doubly exponential in k (while it is just k for the unweighted problem).
In this talk, I will present our recent result (https://arxiv.org/abs/2507.12130) which shows that the randomized compettitive ratio of weighted k-server is singly exponential in k. This is joint work with my undergraduate students Adithya Bijoy and Ankit Mondal.
Title: Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
Abstract: Constrained Online Convex Optimization (COCO) is a well-studied extension of the standard Online Convex Optimization framework, where at each round the learner selects an action before observing both a convex loss function and a convex constraint function. The goal is to design an online policy that achieves both low regret and low cumulative constraint violation (CCV) against an adaptive adversary over a horizon of length T. A fundamental open question in this area has been whether it is possible to simultaneously obtain O(√T) regret and Õ(√T) CCV without imposing any structural assumptions on the problem.
In this talk, I will present the first affirmative resolution of this question. We show that a simple first-order algorithm attains these bounds simultaneously. I will further discuss extensions of this result under strong convexity and smoothness conditions, an anytime version of the policy, and generalizations to long-term budget constraints and bandit feedback.
Joint work with Rahul Vaze (TIFR), Dhruv Sarkar (IIT Kharagpur), Subhamon Supantha (IIT Bombay), and Samrat Mukhopadhyay (IIT Dhanbad)
Title: Predicting the behavior of iterative algorithms in high dimensional, average-case settings
Abstract: Iterative algorithms are the workhorses of modern statistical signal processing and machine learning. Algorithm design and analysis is largely based on variational properties of the continuous optimization problem at hand, and the classical focus has been on obtaining worst-case convergence guarantees over classes of problems that possess certain types of geometry. However, modern optimization problems in statistical settings are high-dimensional, involve random data, and are therefore inherently average-case: consequently, algorithms often behave differently from what is suggested by classical theory. With the motivation of better understanding optimization in such settings, I will present a toolbox for deriving “state evolutions” for a wide variety of algorithms with random data. These are non-asymptotic, near-exact predictions of the statistical behavior of the algorithm, which apply even when the underlying optimization problem is nonconvex or the algorithm is randomly initialized. We will showcase these predictions on deterministic and stochastic variants of complex algorithms employed in some canonical statistical models, discussing applications to hyperparameter tuning and signal reconstruction in tomography.
Title: Memory as a lens to understand learning and optimization
Abstract: What is the role of memory in learning and optimization? The optimal convergence rates (measures in terms of the number of oracle queries or samples needed) for various optimization problems are achieved by computationally expensive optimization techniques, such as second-order methods and cutting-plane methods. We will discuss if simpler, faster and memory-limited algorithms such as gradient descent can achieve these optimal convergence rates for the prototypical optimization problem of minimizing a convex function with access to a gradient. Our results hint at a perhaps curious dichotomy—it is not possible to significantly improve on the convergence rate of known memory efficient techniques (which are linear-memory variants of gradient descent for many of these problems) without using substantially more memory (quadratic memory for many of these problems). Therefore memory could be a useful discerning factor to provide a clear separation between 'efficient' and 'expensive' techniques. This perspective can also be applied to understand mechanisms which transformers use to solve certain algorithmic tasks. We will show empirical evidence that transformers learn to achieve second-order convergence rates for solving linear-regression tasks, leveraging some of the theory of optimization and memory-limited learning.
This is mostly based on joint work with Annie Marsden, Aaron Sidford, Gregory Valiant, Deqing Fu, Tian-Qi Chen and Robin Jia.
Title: Monotone and Conservative Policy Iteration Beyond the Tabular Case
Abstract: Policy Iteration (PI) and Conservative PI (CPI) underpin many modern RL algorithms, yet their celebrated guarantees hold only in idealized settings. In this talk, I will introduce Reliable Policy Iteration (RPI) and Conservative RPI (CRPI)—function-approximation-compatible counterparts that retain the textbook guarantees. RPI replaces the Bellman-error minimization in value-function evaluation with a one-sided, Bellman-inequality-based constrained optimization. This design restores monotonicity of value estimates, yields computable lower bounds on the true return, and ensures that the limit partially satisfies the unprojected Bellman equation, aligning RPI with RL foundations. Building on RPI, CRPI updates policies by maximizing a performance-difference lower bound that explicitly accounts for function-approximation errors, thereby preserving conservative improvement in function-approximation regimes. Our work provides a principled basis for robust, next-generation RL that systematically bridges the gap between theory and practice.
This talk is based on the following joint work:
Eshwar S.R., Thoppe, G, Barua, A., Gopalan, A., & Dalal, G. Monotone and Conservative Policy Iteration Beyond the Tabular Case. Under review, arXiv:2506.07134.
Title: Stochastic Algorithms for Sampling and Mean Field Optimization
Abstract: Sampling and mean field optimization can be seen as optimization in the space of probability distributions. Stochastic optimization algorithms like SGD have been immensely successful for optimization over Euclidean spaces. However the infinite dimensional space of probability distributions poses unique challenges. In this talk, I will discuss my recent work on design and analysis of stochastic algorithms to improve sampling and mean field optimization, by combining the probabilistic view in the path space and the PDE/ optimal transport view of probability flow.
Title: Natural Policy Gradient for Average Reward Non-Stationary RL
Abstract: We consider the problem of non-stationary reinforcement learning (RL) in the infinite-horizon average-reward setting. We model it by a Markov Decision Process with time-varying rewards and transition probabilities, with a variation budget of . Existing non-stationary RL algorithms focus on model-based and model-free value-based methods. Policy-based methods, despite their flexibility in practice, are not theoretically well understood in non-stationary RL. We propose and analyze the first model-free policy-based algorithm, Non-Stationary Natural Actor-Critic (NS-NAC), a policy gradient method with a restart-based exploration for change and a novel interpretation of learning rates as adapting factors.
Title: The Weighted k-Server Problem
Abstract: Abstract: The (unweighted) k-server problem is a cornerstone problem in online computation. The problem concerns moving k identical servers to serve requests in a metric space, while minimizing the total distance travelled by the servers. The weighted k-server problem is a variant where the servers are distinguishable due to their weight, and the cost of moving a server is the product of the distance and its weight. Surprisingly, this innocuous-looking introduction of weights makes the problem so hard that no competitive algorithm is known on metrics other than the uniform metric for k>2 (while for the unweighted problem, a (2k-1)-competitive algorithm is known for all metrics). On the uniform metric spaces, the competitive ratio of weighted k-server was known to be doubly exponential in k (while it is just k for the unweighted problem).
In this talk, I will present our recent result (https://arxiv.org/abs/2507.12130) which shows that the randomized compettitive ratio of weighted k-server is singly exponential in k. This is joint work with my undergraduate students Adithya Bijoy and Ankit Mondal.
Title: Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
Abstract: Constrained Online Convex Optimization (COCO) is a well-studied extension of the standard Online Convex Optimization framework, where at each round the learner selects an action before observing both a convex loss function and a convex constraint function. The goal is to design an online policy that achieves both low regret and low cumulative constraint violation (CCV) against an adaptive adversary over a horizon of length T. A fundamental open question in this area has been whether it is possible to simultaneously obtain O(√T) regret and Õ(√T) CCV without imposing any structural assumptions on the problem.
In this second part of the talk, I will describe a different COCO algorithm that yields universal dynamic regret guarantees against arbitrary comparator sequences, along with corresponding CCV bounds. The key idea underlying both results is a clean synthesis of adaptive OCO methods with Lyapunov optimization, a classical tool from control theory. The resulting algorithms are conceptually simple, and the analysis is remarkably short and elegant.
Joint work with Rahul Vaze (TIFR), Dhruv Sarkar (IIT Kharagpur), Subhamon Supantha (IIT Bombay), and Samrat Mukhopadhyay (IIT Dhanbad)
TIFR, Colaba, Mumbai
Closest airport: Chhatrapati Shivaji Maharaj International Airport (BOM). Nearest major railway stations: Mumbai Central and CSMT. Local transport includes taxis, app-based rides, and BEST buses.
