Yujia Jin

activity

20172025

most citedVariance Reduction for Matrix Games

25 citations · 98 across the 22 of their papers we have counts for

collaborators

Showing cs.DSShow all

8 papers · 1 filter

cs.DS2025

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…

cs.DS2024

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 $n$ -node undirected graph. We provide a randomized algorithm that, with $O(nε^{-…

cs.DS2023

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 $max_{i \in [n]} f_{i} (x)$ over a $d$ -dimensional Euclidean or simplex domain. When each $f_{i}$ is $1$ -Lipschitz and $1$ -smooth, our method computes…

cs.DS2023★ 1 cited

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 $[- 1, 1]$ th…

cs.DS2022

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…

cs.DS2020

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space

Sepehr Assadi, Arun Jambulapati, Yujia Jin +2

We provide $O (ε^{- 1})$ -pass semi-streaming algorithms for computing $(1 - ε)$ -approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods ar…

cs.DS2020★ 1 cited

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 $min_{x \in X} max_{y \in Y} y^{⊤} A x$ which contain linear p…

cs.DS2019★ 3 cited

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

Yujia Jin, Aaron Sidford

Given a data matrix $A \in R^{n \times d}$ , principal component projection (PCP) and principal component regression (PCR), i.e. projection and regression restrict…