Yujia Jin
I am a fourthyear PhD student in the Department of Management Science and Engineering at Stanford in
the Operations Research group, advised by Aaron Sidford.
I am broadly interested in optimization problems, sometimes in the intersection with machine learning
theory and graph applications. I enjoy understanding the theoretical ground of many algorithms that are
of practical importance.
Prior to coming to Stanford, I received my Bachelor's degree in Applied Math at Fudan
University, where
I was fortunate to work with Prof. Zhongzhi Zhang. From 2016 to 2018, I also worked in
Research Institute for Interdisciplinary Sciences (RIIS) at
SHUFE, where I was fortunate
to be advised by Prof. Dongdong Ge.
Email /
Google Scholar


Stochastic BiasReduced Gradient Methods
[pdf]
with Hilal Asi, Yair Carmon, Arun Jambulapati and Aaron Sidford
"A lowbias lowcost estimator of subproblem solution suffices for acceleration! "

SemiStreaming Bipartite Matching in Fewer Passes and Optimal Space
[pdf]
with Sepehr Assadi, Arun Jambulapati, Aaron Sidford and Kevin Tian
"Streaming matching (and optimal transport) in \(\tilde{O}(1/\epsilon)\) passes and \(O(n)\) space."

Thinking Inside the Ball: NearOptimal Minimization of the Maximal Loss
[pdf] [talk] [poster]
with Yair Carmon, Arun Jambulapati and Aaron Sidford
Conference of Learning Theory (COLT), 2021
"Improved upper and lower bounds on firstorder queries for solving \(\min_{x}\max_{i\in[n]}\ell_i(x)\)."

Towards Tight Bounds on the Sample Complexity of Averagereward MDPs
[pdf] [talk] [poster]
with Aaron Sidford
International Conference on Machine Learning (ICML), 2021
"Sample complexity for averagereward MDPs? A nearly matching upper and lower bound for constant error here!"

Acceleration with a Ball Optimization Oracle
[pdf] [talk] [poster]
with Yair Carmon, Arun Jambulapati, Qijia Jiang, Yin Tat Lee, Aaron Sidford and Kevin Tian
Neural Information Processing Systems (NeurIPS, Oral), 2020
"How many \(\epsilon\)length segments do you need to look at for finding an \(\epsilon\)optimal minimizer of convex function on a line?"

Coordinate Methods for Matrix Games
[pdf] [talk]
with Yair Carmon, Kevin Tian and Aaron Sidford
Symposium on Foundations of Computer Science (FOCS), 2020
"About how and why coordinate (variancereduced) methods are a good idea for exploiting (numerical) sparsity of data."

Efficiently Solving MDPs with Stochastic Mirror Descent
[pdf] [talk]
with Aaron Sidford
International Conference on Machine Learning (ICML), 2020
"Teamconvexoptimization for solving discounted and averagereward MDPs!"

Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
[pdf] [slides]
with Aaron Sidford
Neural Information Processing Systems (NeurIPS, Spotlight), 2019
"A special case where variance reduction can be used to nonconvex optimization (monotone operators)."

Variance Reduction for Matrix Games
[pdf] [poster]
with Yair Carmon, Aaron Sidford and Kevin Tian
Neural Information Processing Systems (NeurIPS, Oral), 2019
"General variance reduction framework for solving saddlepoint problems & Improved runtimes for matrix games."

A NearOptimal Method for Minimizing the Maximum of N Convex Loss Functions
with Hilal Asi, Yair Carmon, Arun Jambulapati and Aaron Sidford
BayLearn, 2021
"We characterize when solving the max \(\min_{x}\max_{i\in[n]}f_i(x)\) is (not) harder than solving the average \(\min_{x}\frac{1}{n}\sum_{i\in[n]}f_i(x)\)."

On the Sample Complexity of Averagereward MDPs
[pdf] [poster]
with Aaron Sidford
ICML Workshop on Reinforcement Learning Theory, 2021
"Collection of new upper and lower sample complexity bounds for solving averagereward MDPs."

Variance Reduction for Matrix Games
[pdf] [poster]
with Yair Carmon, Aaron Sidford and Kevin Tian
NeurIPS Smooth Games Optimization and Machine Learning Workshop, 2019
"Collection of variancereduced / coordinate methods for solving matrix games, with simplex or Euclidean ball domains."

Variance Reduction for Matrix Games
[pdf] [poster]
with Yair Carmon, Aaron Sidford and Kevin Tian
BayLearn, 2019
"A short version of the conference publication under the same title."

