Yujia Jin

I am a fourth-year 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

Preprints

Stochastic Bias-Reduced Gradient Methods [pdf]
with Hilal Asi, Yair Carmon, Arun Jambulapati and Aaron Sidford

"A low-bias low-cost estimator of subproblem solution suffices for acceleration! "

Semi-Streaming 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."

Conference Publications

Thinking Inside the Ball: Near-Optimal 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 first-order queries for solving \(\min_{x}\max_{i\in[n]}\ell_i(x)\)."

Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [pdf] [talk] [poster]
with Aaron Sidford
International Conference on Machine Learning (ICML), 2021

"Sample complexity for average-reward 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 (variance-reduced) 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

"Team-convex-optimization for solving discounted and average-reward 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 saddle-point problems & Improved runtimes for matrix games."

Workshop Publications

A Near-Optimal 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 Average-reward MDPs[pdf] [poster]
with Aaron Sidford
ICML Workshop on Reinforcement Learning Theory, 2021

"Collection of new upper and lower sample complexity bounds for solving average-reward 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 variance-reduced / 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."