8 citations · 8 across the 5 of their papers we have counts for
5 papers
An Exponent-Tight Conditional Lower Bound for Global Label Min-Cut
Yuanhao Wang, Kehua Wang, Wei Wang
Let and denote the numbers of vertices and labels, respectively, in an undirected edge-labeled graph. Previous work showed that, under the Exponential Time Hypothesis (ETH)…
Tie-breaking Agnostic Lower Bound for Fictitious Play
Yuanhao Wang
Fictitious play (FP) is a natural learning dynamic in two-player zero-sum games. Samuel Karlin conjectured in 1959 that FP converges at a rate of to Nash equilibrium,…
Directional Smoothness and Gradient Methods: Convergence and Adaptivity
Aaron Mishkin, Ahmed Khaled, Yuanhao Wang +2
We develop new sub-optimality bounds for gradient descent (GD) that depend on the conditioning of the objective along the path of optimization rather than on global, worst-case con…
Online Learning in Unknown Markov Games
Yi Tian, Yuanhao Wang, Tiancheng Yu +1
We study online learning in unknown Markov games, a problem that arises in episodic multi-agent reinforcement learning where the actions of the opponents are unobservable. We show…
Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen +1
We study the problem of regret minimization for distributed bandits learning, in which agents work collaboratively to minimize their total regret under the coordination of a ce…