Yujia Jin | DeepAI

AI Chat

Featured Co-authors

Stefano Ermon
168 publications
Aaron Sidford
79 publications
Yin Tat Lee
64 publications
Christopher Musco
33 publications
Kevin Tian
30 publications
Huan Li
29 publications
Arun Jambulapati
25 publications
Yair Carmon
23 publications
Vidya Muthukumar
23 publications
Zhongzhi Zhang
22 publications
Lantao Yu
22 publications

∙ 07/02/2023

Moments, Random Walks, and Limits for Spectrum Approximation

We study lower bounds for the problem of approximating a one dimensional...

0 Yujia Jin, et al. ∙

∙ 01/10/2023

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling

We give a quantum algorithm for computing an ϵ-approximate Nash equilibr...

0 Adam Bouland, et al. ∙

∙ 01/01/2023

ReSQueing Parallel and Private Stochastic Convex Optimization

We introduce a new tool for stochastic convex optimization (SCO): a Rewe...

0 Yair Carmon, et al. ∙

∙ 06/17/2022

RECAPP: Crafting a More Efficient Catalyst for Convex Optimization

The accelerated proximal point algorithm (APPA), also known as "Catalyst...

0 Yair Carmon, et al. ∙

∙ 05/30/2022

Optimal and Adaptive Monteiro-Svaiter Acceleration

We develop a variant of the Monteiro-Svaiter (MS) acceleration framework...

0 Yair Carmon, et al. ∙

∙ 04/27/2022

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Box-simplex games are a family of bilinear minimax objectives which enca...

0 Arun Jambulapati, et al. ∙

∙ 04/08/2022

The Complexity of Infinite-Horizon General-Sum Stochastic Games

We study the complexity of computing stationary Nash equilibrium (NE) in...

0 Yujia Jin, et al. ∙

∙ 02/09/2022

Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

We design accelerated algorithms with improved rates for several fundame...

0 Yujia Jin, et al. ∙

∙ 12/07/2021

A Unified Framework for Multi-distribution Density Ratio Estimation

Binary density ratio estimation (DRE), the problem of estimating the rat...

11 Lantao Yu, et al. ∙

∙ 06/17/2021

Stochastic Bias-Reduced Gradient Methods

We develop a new primitive for stochastic optimization: a low-bias, low-...

0 Hilal Asi, et al. ∙

∙ 06/13/2021

Towards Tight Bounds on the Sample Complexity of Average-reward MDPs

We prove new upper and lower bounds for sample complexity of finding an ...

0 Yujia Jin, et al. ∙

∙ 05/04/2021

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

We characterize the complexity of minimizing max_i∈[N] f_i(x) for convex...

0 Yair Carmon, et al. ∙

∙ 11/06/2020

Semi-Streaming Bipartite Matching in Fewer Passes and Less Space

We provide algorithms with improved pass and space complexities for appr...

0 Yujia Jin, et al. ∙

∙ 09/17/2020

Coordinate Methods for Matrix Games

We develop primal-dual coordinate methods for solving bilinear saddle-po...

0 Yair Carmon, et al. ∙

∙ 08/28/2020

Efficiently Solving MDPs with Stochastic Mirror Descent

We present a unified framework based on primal-dual stochastic mirror de...

0 Yujia Jin, et al. ∙

∙ 03/18/2020

Acceleration with a Ball Optimization Oracle

Consider an oracle which takes a point x and returns the minimizer of a ...

0 Yair Carmon, et al. ∙

∙ 10/15/2019

Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG

Given a data matrix A∈R^n × d, principal component projection (PCP) and ...

0 Yujia Jin, et al. ∙

∙ 07/03/2019

Variance Reduction for Matrix Games

We present a randomized primal-dual algorithm that solves the problem _x...

0 Yair Carmon, et al. ∙

∙ 09/13/2017

Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs

The Apollonian networks display the remarkable power-law and small-world...

0 Yujia Jin, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world