25 citations · 98 across the 22 of their papers we have counts for
24 papers
Reusing Samples in Variance Reduction
Yujia Jin, Ishani Karmarkar, Aaron Sidford +1
We provide a general framework to improve trade-offs between the number of full batch and sample queries used to solve structured optimization problems. Our results apply to a broa…
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
Yujia Jin, Ishani Karmarkar, Christopher Musco +2
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an -node undirected graph. We provide a randomized algorithm that, with $O(nε^{-…
Truncated Variance Reduced Value Iteration
Yujia Jin, Ishani Karmarkar, Aaron Sidford +1
We provide faster randomized algorithms for computing an -optimal policy in a discounted Markov decision process with -state-action pairs, bounded rewards, and d…
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions
Yair Carmon, Arun Jambulapati, Yujia Jin +1
We design algorithms for minimizing over a -dimensional Euclidean or simplex domain. When each is -Lipschitz and -smooth, our method computes…
Moments, Random Walks, and Limits for Spectrum Approximation
Yujia Jin, Christopher Musco, Aaron Sidford +1
We study lower bounds for the problem of approximating a one dimensional distribution given (noisy) measurements of its moments. We show that there are distributions on th…
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
Adam Bouland, Yosheb Getachew, Yujia Jin +2
We give a quantum algorithm for computing an -approximate Nash equilibrium of a zero-sum game in a payoff matrix with bounded entries. Given a standard quantum orac…
ReSQueing Parallel and Private Stochastic Convex Optimization
Yair Carmon, Arun Jambulapati, Yujia Jin +4
We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probab…
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…
A Unified Framework for Multi-distribution Density Ratio Estimation
Lantao Yu, Yujia Jin, Stefano Ermon
Binary density ratio estimation (DRE), the problem of estimating the ratio given their empirical samples, provides the foundation for many state-of-the-art machine learni…
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
Yujia Jin, Aaron Sidford
We prove new upper and lower bounds for sample complexity of finding an -optimal policy of an infinite-horizon average-reward Markov decision process (MDP) given access to a gen…
Stochastic Bias-Reduced Gradient Methods
Hilal Asi, Yair Carmon, Arun Jambulapati +2
We develop a new primitive for stochastic optimization: a low-bias, low-cost estimator of the minimizer of any Lipschitz strongly-convex function. In particular, we use a…
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
Yair Carmon, Arun Jambulapati, Yujia Jin +1
We characterize the complexity of minimizing for convex, Lipschitz functions . For non-smooth functions, existing methods require $O(Nε^{-2…
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
Sepehr Assadi, Arun Jambulapati, Yujia Jin +2
We provide -pass semi-streaming algorithms for computing -approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods ar…
Coordinate Methods for Matrix Games
Yair Carmon, Yujia Jin, Aaron Sidford +1
We develop primal-dual coordinate methods for solving bilinear saddle-point problems of the form which contain linear p…
Efficiently Solving MDPs with Stochastic Mirror Descent
Yujia Jin, Aaron Sidford
We present a unified framework based on primal-dual stochastic mirror descent for approximately solving infinite-horizon Markov decision processes (MDPs) given a generative model.…
Acceleration with a Ball Optimization Oracle
Yair Carmon, Arun Jambulapati, Qijia Jiang +4
Consider an oracle which takes a point and returns the minimizer of a convex function in an ball of radius around . It is straightforward to show that rough…
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
Yujia Jin, Aaron Sidford
Given a data matrix , principal component projection (PCP) and principal component regression (PCR), i.e. projection and regression restrict…
Variance Reduction for Matrix Games
Yair Carmon, Yujia Jin, Aaron Sidford +1
We present a randomized primal-dual algorithm that solves the problem to additive error in time , fo…
Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
Yujia Jin, Huan Li, Zhongzhi Zhang
The Apollonian networks display the remarkable power-law and small-world properties as observed in most realistic networked systems. Their dual graphs are extended Tower of Hanoi g…