Timezone: »
Poster
Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function
Quoc Tran Dinh · Deyi Liu · Lam Nguyen
We develop a novel and single-loop variance-reduced algorithm to solve a class of stochastic nonconvex-convex minimax problems involving a nonconvex-linear objective function, which has various applications in different fields such as ma- chine learning and robust optimization. This problem class has several compu- tational challenges due to its nonsmoothness, nonconvexity, nonlinearity, and non-separability of the objective functions. Our approach relies on a new combi- nation of recent ideas, including smoothing and hybrid biased variance-reduced techniques. Our algorithm and its variants can achieve $\mathcal{O}(T^{-2/3})$-convergence rate and the best-known oracle complexity under standard assumptions, where T is the iteration counter. They have several computational advantages compared to exist- ing methods such as simple to implement and less parameter tuning requirements. They can also work with both single sample or mini-batch on derivative estimators, and with constant or diminishing step-sizes. We demonstrate the benefits of our algorithms over existing methods through two numerical examples, including a nonsmooth and nonconvex-non-strongly concave minimax model.
Author Information
Quoc Tran Dinh (Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, North Carolina)
Deyi Liu (University of North Carolina)
Lam Nguyen (IBM Research, Thomas J. Watson Research Center)
More from the Same Authors
-
2022 : c-MBA: Adversarial Attack for Cooperative MARL Using Learned Dynamics Model »
Nhan H Pham · Lam Nguyen · Jie Chen · Thanh Lam Hoang · Subhro Das · Lily Weng -
2021 Workshop: New Frontiers in Federated Learning: Privacy, Fairness, Robustness, Personalization and Data Ownership »
Nghia Hoang · Lam Nguyen · Pin-Yu Chen · Tsui-Wei Weng · Sara Magliacane · Bryan Kian Hsiang Low · Anoop Deoras -
2021 Poster: On the Equivalence between Neural Network and Support Vector Machine »
Yilan Chen · Wei Huang · Lam Nguyen · Tsui-Wei Weng -
2021 Poster: FedDR – Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization »
Quoc Tran Dinh · Nhan H Pham · Dzung Phan · Lam Nguyen -
2021 Poster: Ensembling Graph Predictions for AMR Parsing »
Thanh Lam Hoang · Gabriele Picco · Yufang Hou · Young-Suk Lee · Lam Nguyen · Dzung Phan · Vanessa Lopez · Ramon Fernandez Astudillo -
2020 Poster: A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees »
Haoran Zhu · Pavankumar Murali · Dzung Phan · Lam Nguyen · Jayant Kalagnanam -
2019 Poster: Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD »
Ha Nguyen · Lam Nguyen · Marten van Dijk -
2018 Poster: Non-Ergodic Alternating Proximal Augmented Lagrangian Algorithms with Optimal Rates »
Quoc Tran Dinh -
2017 Poster: Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization »
Ahmet Alacaoglu · Quoc Tran Dinh · Olivier Fercoq · Volkan Cevher -
2015 Poster: A Universal Primal-Dual Convex Optimization Framework »
Alp Yurtsever · Quoc Tran Dinh · Volkan Cevher