137 citations · 656 across the 54 of their papers we have counts for
20 papers · 1 filter
Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods
Junchi Yang, Xiang Li, Ilyas Fatkhullin +1
The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize relies on well-tuned depending on problem parameters such as…
Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games
Batuhan Yardim, Semih Cayci, Matthieu Geist +1
Mean-field games have been used as a theoretical tool to obtain an approximate Nash equilibrium for symmetric and anonymous -player games. However, limiting applicability, exist…
Sharp Analysis of Stochastic Optimization under Global Kurdyka-Łojasiewicz Inequality
Ilyas Fatkhullin, Jalal Etesami, Niao He +1
We study the complexity of finding the global solution to stochastic nonconvex optimization when the objective function satisfies global Kurdyka-Lojasiewicz (KL) inequality and the…
TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization
Xiang Li, Junchi Yang, Niao He
Adaptive gradient methods have shown their ability to adjust the stepsizes on the fly in a parameter-agnostic manner, and empirically achieve faster convergence for solving minimiz…
Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization
Junchi Yang, Xiang Li, Niao He
Adaptive algorithms like AdaGrad and AMSGrad are successful in nonconvex optimization owing to their parameter-agnostic ability -- requiring no a priori knowledge about problem-spe…
Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization
Siqi Zhang, Yifan Hu, Liang Zhang +1
This paper takes an initial step to systematically investigate the generalization bounds of algorithms for solving nonconvex-(strongly)-concave (NC-SC/NC-C) stochastic minimax opti…
Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management
Xin Chen, Niao He, Yifan Hu +1
We study a class of stochastic nonconvex optimization in the form of , i.e., is a composition of a convex function and…
Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization
Kiran Koshy Thekumparampil, Niao He, Sewoong Oh
We study the bilinearly coupled minimax problem: , where and are both strongly convex smooth functions and admit first-order gra…
The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
Siqi Zhang, Junchi Yang, Cristóbal Guzmán +2
This paper studies the complexity for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) smooth minimax problems, in both general and averaged smooth finit…
A Discrete-Time Switching System Analysis of Q-learning
Donghwan Lee, Jianghai Hu, Niao He
This paper develops a novel control-theoretic framework to analyze the non-asymptotic convergence of Q-learning. We show that the dynamics of asynchronous Q-learning with a constan…
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
Junchi Yang, Negar Kiyavash, Niao He
Nonconvex minimax problems appear frequently in emerging machine learning applications, such as generative adversarial networks and adversarial learning. Simple algorithms such as…
Bregman Augmented Lagrangian and Its Acceleration
Shen Yan, Niao He
We study the Bregman Augmented Lagrangian method (BALM) for solving convex problems with linear constraints. For classical Augmented Lagrangian method, the convergence rate and its…
Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
Yifan Hu, Siqi Zhang, Xin Chen +1
Conditional stochastic optimization covers a variety of applications ranging from invariant learning and causal inference to meta-learning. However, constructing unbiased gradient…
A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
Donghwan Lee, Niao He
In this paper, we introduce a unified framework for analyzing a large family of Q-learning algorithms, based on switching system perspectives and ODE-based stochastic approximation…
Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization
Yifan Hu, Xin Chen, Niao He
In this paper, we study a class of stochastic optimization problems, referred to as the \emph{Conditional Stochastic Optimization} (CSO), in the form of $\min_{x \in \mathcal{X}} \…
Stochastic Primal-Dual Q-Learning
Narim Jeong, Donghwan Lee, Niao He
In this work, we present a new model-free and off-policy reinforcement learning (RL) algorithm, that is capable of finding a near-optimal policy with state-action observations from…
On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
Siqi Zhang, Niao He
In this paper, we investigate the non-asymptotic stationary convergence behavior of Stochastic Mirror Descent (SMD) for nonconvex optimization. We focus on a general class of nonco…
Dynamic Programming for POMDP with Jointly Discrete and Continuous State-Spaces
Donghwan Lee, Niao He, Jianghai Hu
In this work, we study dynamic programming (DP) algorithms for partially observable Markov decision processes with jointly continuous and discrete state-spaces. We consider a class…
Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization
Niao He, Zaid Harchaoui
We propose a new first-order optimisation algorithm to solve high-dimensional non-smooth composite minimisation problems. Typical examples of such problems have an objective that d…
Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems
Niao He, Anatoli Juditsky, Arkadi Nemirovski
In the paper, we develop a composite version of Mirror Prox algorithm for solving convex-concave saddle point problems and monotone variational inequalities of special structure, a…