25 citations · 98 across the 22 of their papers we have counts for
6 papers · 1 filter
VOL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation
Alekh Agarwal, Yujia Jin, Tong Zhang
We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q…
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
Yair Carmon, Arun Jambulapati, Yujia Jin +1
The accelerated proximal point algorithm (APPA), also known as "Catalyst", is a well-established reduction from convex optimization to approximate proximal point computation (i.e.,…
Optimal and Adaptive Monteiro-Svaiter Acceleration
Yair Carmon, Danielle Hausler, Arun Jambulapati +2
We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Consequently, for any $p\…
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching
Arun Jambulapati, Yujia Jin, Aaron Sidford +1
Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [She17], optimal transport [JST19], and bipartite mat…
The Complexity of Infinite-Horizon General-Sum Stochastic Games
Yujia Jin, Vidya Muthukumar, Aaron Sidford
We study the complexity of computing stationary Nash equilibrium (NE) in n-player infinite-horizon general-sum stochastic games. We focus on the problem of computing NE in such sto…
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
Yujia Jin, Aaron Sidford, Kevin Tian
We design accelerated algorithms with improved rates for several fundamental classes of optimization problems. Our algorithms all build upon techniques related to the analysis of p…