Browsing by Author "Xu, P"

Filter results by typing the first few letters
Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning
    (Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2023-02-28) Zhang, Y; Qu, G; Xu, P; Lin, Y; Chen, Z; Wierman, A
    We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their entropy-regularized long-term rewards. To overcome the curse of dimensionality and to reduce communication, we propose a Localized Policy Iteration (LPI) algorithm that provably learns a near-globally-optimal policy using only local information. In particular, we show that, despite restricting each agent's attention to only its κ-hop neighborhood, the agents are able to learn a policy with an optimality gap that decays polynomially in κ. In addition, we show the finite-sample convergence of LPI to the global optimal policy, which explicitly captures the trade-off between optimality and computational complexity in choosing κ. Numerical simulations demonstrate the effectiveness of LPI.
  • Thumbnail Image
    ItemOpen Access
    Stochastic nested variance reduction for nonconvex optimization
    (Journal of Machine Learning Research, 2020-05-01) Zhou, D; Xu, P; Gu, Q
    We study nonconvex optimization problems, where the objective function is either an average of n nonconvex functions or the expectation of some stochastic function. We propose a new stochastic gradient descent algorithm based on nested variance reduction, namely, Stochastic Nested Variance-Reduced Gradient descent (SNVRG). Compared with conventional stochastic variance reduced gradient (SVRG) algorithm that uses two reference points to construct a semi-stochastic gradient with diminishing variance in each iteration, our algorithm uses K + 1 nested reference points to build a semi-stochastic gradient to further reduce its variance in each iteration. For smooth nonconvex functions, SNVRG converges to an ε-approximate first-order stationary point within Oe(n∧ε−2 + ε−3 ∧n1/2ε−2)1 number of stochastic gradient evaluations. This improves the best known gradient complexity of SVRG O(n+ n2/3ε−2) and that of SCSG O(n∧ε−2 + ε−10/3 ∧n2/3ε−2). For gradient dominated functions, SNVRG also achieves better gradient complexity than the state-of-the-art algorithms. Based on SNVRG, we further propose two algorithms that can find local minima faster than state-of-the-art algorithms in both finite-sum and general stochastic (online) nonconvex optimization. In particular, for finite-sum optimization problems, the proposed SNVRG + Neon2finite algorithm achieves Oe(n1/2ε−2 + nε−H3 + n3/4ε−H7/2) gradient complexity to converge to an (ε, εH)-second-order stationary point, which outperforms SVRG+Neon2finite (Allen-Zhu and Li, 2018), the best existing algorithm, in a wide regime. For general stochastic optimization problems, the proposed SNVRG + Neon2online achieves Oe(ε−3 + ε−H5 + ε−2ε−H3) gradient complexity, which is better than both SVRG + Neon2online (Allen-Zhu and Li, 2018) and Natasha2 (Allen-Zhu, 2018a) in certain regimes. Thorough experimental results on different nonconvex optimization problems back up our theory.
  • Thumbnail Image
    ItemOpen Access
    Stochastic variance-reduced cubic regularization methods
    (Journal of Machine Learning Research, 2019-08-01) Zhou, D; Xu, P; Gu, Q
    We propose a stochastic variance-reduced cubic regularized Newton method (SVRC) for non-convex optimization. At the core of SVRC is a novel semi-stochastic gradient along with a semi-stochastic Hessian, which are specifically designed for cubic regularization method. For a nonconvex function with n component functions, we show that our algorithm is guaranteed to converge to an (ϵ; √ ϵ)-approximate local minimum within O (n4/5=ϵ3/2)1 second-order oracle calls, which outperforms the state-of-the-art cubic regularization algo- rithms including subsampled cubic regularization. To further reduce the sample complexity of Hessian matrix computation in cubic regularization based methods, we also propose a sample efficient stochastic variance-reduced cubic regularization (Lite-SVRC) algorithm for finding the local minimum more efficiently. Lite-SVRC converges to an (ϵ; √ϵ)-approximate local minimum within O (n + n2/3=ϵ3/2) Hessian sample complexity, which is faster than all existing cubic regularization based methods. Numerical experiments with different non- convex optimization problems conducted on real datasets validate our theoretical results for both SVRC and Lite-SVRC.