67 citations · 172 across the 19 of their papers we have counts for
7 papers · 1 filter
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…
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.…
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
Aaron Sidford, Mengdi Wang, Lin F. Yang +1
In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with d…
Memory-Sample Tradeoffs for Linear Regression with Small Error
Vatsal Sharan, Aaron Sidford, Gregory Valiant
We consider the problem of performing linear regression over a stream of -dimensional examples, and show that any algorithm that uses a subquadratic amount of memory exhibits a…
A Rank-1 Sketch for Matrix Multiplicative Weights
Yair Carmon, John C. Duchi, Aaron Sidford +1
We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor. Unlik…
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
Rong Ge, Chi Jin, Sham M. Kakade +2
This paper considers the problem of canonical-correlation analysis (CCA) (Hotelling, 1936) and, more broadly, the generalized eigenvector problem for a pair of symmetric matrices.…