3 papers
cs.DS2026
An Exponent-Tight Conditional Lower Bound for Global Label Min-Cut
Yuanhao Wang, Wei Wang, Kehua 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)…
cs.GT2025
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,…
cs.LG2025
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…