Timezone: »
Poster
NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
Davood Hajinezhad · Mingyi Hong · Tuo Zhao · Zhaoran Wang
We study a stochastic and distributed algorithm for nonconvex problems whose objective consists a sum $N$ nonconvex $L_i/N$-smooth functions, plus a nonsmooth regularizer. The proposed NonconvEx primal-dual SpliTTing (NESTT) algorithm splits the problem into $N$ subproblems, and utilizes an augmented Lagrangian based primal-dual scheme to solve it in a distributed and stochastic manner. With a special non-uniform sampling, a version of NESTT achieves $\epsilon$-stationary solution using $\mathcal{O}((\sum_{i=1}^N\sqrt{L_i/N})^2/\epsilon)$ gradient evaluations, which can be up to $\mathcal{O}(N)$ times better than the (proximal) gradient descent methods. It also achieves Q-linear convergence rate for nonconvex $\ell_1$ penalized quadratic problems with polyhedral constraints. Further, we reveal a fundamental connection between {\it primal-dual} based methods and a few {\it primal only} methods such as IAG/SAG/SAGA.
Author Information
Davood Hajinezhad (Iowa State University)
Mingyi Hong (iowa state university)
Tuo Zhao (Johns Hopkins University)
Zhaoran Wang (Princeton University)
More from the Same Authors
-
2021 : GPU-Podracer: Scalable and Elastic Library for Cloud-Native Deep Reinforcement Learning »
Xiao-Yang Liu · Zhuoran Yang · Zhaoran Wang · Anwar Walid · Jian Guo · Michael Jordan -
2021 : Exponential Family Model-Based Reinforcement Learning via Score Matching »
Gene Li · Junbo Li · Nathan Srebro · Zhaoran Wang · Zhuoran Yang -
2021 Poster: Pessimism Meets Invariance: Provably Efficient Offline Mean-Field Multi-Agent RL »
Minshuo Chen · Yan Li · Ethan Wang · Zhuoran Yang · Zhaoran Wang · Tuo Zhao -
2021 Poster: Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning »
Yingjie Fei · Zhuoran Yang · Yudong Chen · Zhaoran Wang -
2021 Poster: A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum »
Prashant Khanduri · Siliang Zeng · Mingyi Hong · Hoi-To Wai · Zhaoran Wang · Zhuoran Yang -
2021 Poster: BooVI: Provably Efficient Bootstrapped Value Iteration »
Boyi Liu · Qi Cai · Zhuoran Yang · Zhaoran Wang -
2021 Poster: Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Critic »
Yufeng Zhang · Siyu Chen · Zhuoran Yang · Michael Jordan · Zhaoran Wang -
2021 Poster: Offline Constrained Multi-Objective Reinforcement Learning via Pessimistic Dual Value Iteration »
Runzhe Wu · Yufeng Zhang · Zhuoran Yang · Zhaoran Wang -
2021 Poster: Dynamic Bottleneck for Robust Self-Supervised Exploration »
Chenjia Bai · Lingxiao Wang · Lei Han · Animesh Garg · Jianye Hao · Peng Liu · Zhaoran Wang -
2021 Poster: Provably Efficient Causal Reinforcement Learning with Confounded Observational Data »
Lingxiao Wang · Zhuoran Yang · Zhaoran Wang -
2020 Poster: AttendLight: Universal Attention-Based Reinforcement Learning Model for Traffic Signal Control »
Afshin Oroojlooy · Mohammadreza Nazari · Davood Hajinezhad · Jorge Silva -
2016 Poster: Agnostic Estimation for Misspecified Phase Retrieval Models »
Matey Neykov · Zhaoran Wang · Han Liu -
2016 Poster: Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes »
Chris Junchi Li · Zhaoran Wang · Han Liu -
2016 Poster: Blind Attacks on Machine Learners »
Alex Beatson · Zhaoran Wang · Han Liu -
2016 Poster: More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning »
Xinyang Yi · Zhaoran Wang · Zhuoran Yang · Constantine Caramanis · Han Liu -
2015 Poster: Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems »
Ruoyu Sun · Mingyi Hong -
2015 Poster: Optimal Linear Estimation under Unknown Nonlinear Transform »
Xinyang Yi · Zhaoran Wang · Constantine Caramanis · Han Liu -
2015 Poster: Non-convex Statistical Optimization for Sparse Tensor Graphical Model »
Wei Sun · Zhaoran Wang · Han Liu · Guang Cheng -
2015 Poster: High Dimensional EM Algorithm: Statistical Optimization and Asymptotic Normality »
Zhaoran Wang · Quanquan Gu · Yang Ning · Han Liu -
2015 Poster: A Nonconvex Optimization Framework for Low Rank Matrix Estimation »
Tuo Zhao · Zhaoran Wang · Han Liu -
2014 Poster: Accelerated Mini-batch Randomized Block Coordinate Descent Method »
Tuo Zhao · Mo Yu · Yiming Wang · Raman Arora · Han Liu -
2014 Poster: Multivariate Regression with Calibration »
Han Liu · Lie Wang · Tuo Zhao -
2014 Poster: Sparse PCA with Oracle Property »
Quanquan Gu · Zhaoran Wang · Han Liu -
2014 Poster: Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization »
Meisam Razaviyayn · Mingyi Hong · Zhi-Quan Luo · Jong-Shi Pang -
2014 Poster: Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time »
Zhaoran Wang · Huanran Lu · Han Liu -
2013 Poster: Sparse Inverse Covariance Estimation with Calibration »
Tuo Zhao · Han Liu -
2012 Poster: High-dimensional Nonparanormal Graph Estimation via Smooth-projected Neighborhood Pursuit »
Tuo Zhao · Kathryn Roeder · Han Liu