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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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)