Timezone: »
Poster
Efficient Mirror Descent Ascent Methods for Nonsmooth Minimax Problems
Feihu Huang · Xidong Wu · Heng Huang
In the paper, we propose a class of efficient mirror descent ascent methods to solve the nonsmooth nonconvex-strongly-concave minimax problems by using dynamic mirror functions, and introduce a convergence analysis framework to conduct rigorous theoretical analysis for our mirror descent ascent methods. For our stochastic algorithms, we first prove that the mini-batch stochastic mirror descent ascent (SMDA) method obtains a gradient complexity of $O(\kappa^3\epsilon^{-4})$ for finding an $\epsilon$-stationary point, where $\kappa$ denotes the condition number. Further, we propose an accelerated stochastic mirror descent ascent (VR-SMDA) method based on the variance reduced technique. We prove that our VR-SMDA method achieves a lower gradient complexity of $O(\kappa^3\epsilon^{-3})$. For our deterministic algorithm, we prove that our deterministic mirror descent ascent (MDA) achieves a lower gradient complexity of $O(\sqrt{\kappa}\epsilon^{-2})$ under mild conditions, which matches the best known complexity in solving smooth nonconvex-strongly-concave minimax optimization. We conduct the experiments on fair classifier and robust neural network training tasks to demonstrate the efficiency of our new algorithms.
Author Information
Feihu Huang (University of Pittsburgh)
Xidong Wu (University of Pittsburgh)
Heng Huang (University of Pittsburgh)
More from the Same Authors
-
2022 : FedGRec: Federated Graph Recommender System with Lazy Update of Latent Embeddings »
Junyi Li · Heng Huang -
2022 : Cooperation or Competition: Avoiding Player Domination for Multi-target Robustness by Adaptive Budgets »
Yimu Wang · Dinghuai Zhang · Yihan Wu · Heng Huang · Hongyang Zhang -
2023 Poster: Resolving the Tug-of-War: A Separation of Communication and Learning in Federated Learning »
Junyi Li · Heng Huang -
2023 Poster: Solving a Class of Non-Convex Minimax Optimization in Federated Learning »
Xidong Wu · Jianhui Sun · Zhengmian Hu · Aidong Zhang · Heng Huang -
2023 Poster: Domain Watermark: Effective and Harmless Dataset Copyright Protection is Closed at Hand »
Junfeng Guo · Yiming Li · Lixu Wang · Shu-Tao Xia · Heng Huang · Cong Liu · Bo Li -
2023 Poster: Federated Conditional Stochastic Optimization »
Xidong Wu · Jianhui Sun · Zhengmian Hu · Junyi Li · Aidong Zhang · Heng Huang -
2023 Poster: Finding Local Minima Efficiently in Decentralized Optimization »
Wenhan Xian · Heng Huang -
2023 Poster: Optimization and Bayes: A Trade-off for Overparameterized Neural Networks »
Zhengmian Hu · Heng Huang -
2023 Poster: Communication-Efficient Federated Bilevel Optimization with Global and Local Lower Level Problems »
Junyi Li · Feihu Huang · Heng Huang -
2022 Poster: MetricFormer: A Unified Perspective of Correlation Exploring in Similarity Learning »
Jiexi Yan · Erkun Yang · Cheng Deng · Heng Huang -
2022 Poster: Enhanced Bilevel Optimization via Bregman Distance »
Feihu Huang · Junyi Li · Shangqian Gao · Heng Huang -
2022 Poster: Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization »
Feihu Huang · Shangqian Gao · Jian Pei · Heng Huang -
2021 Poster: Optimal Underdamped Langevin MCMC Method »
Zhengmian Hu · Feihu Huang · Heng Huang -
2021 Poster: Fast Training Method for Stochastic Compositional Optimization Problems »
Hongchang Gao · Heng Huang -
2021 Poster: SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients »
Feihu Huang · Junyi Li · Heng Huang -
2021 Poster: A Faster Decentralized Algorithm for Nonconvex Minimax Problems »
Wenhan Xian · Feihu Huang · Yanfu Zhang · Heng Huang -
2019 Poster: Curvilinear Distance Metric Learning »
Shuo Chen · Lei Luo · Jian Yang · Chen Gong · Jun Li · Heng Huang -
2018 Poster: Bilevel Distance Metric Learning for Robust Image Recognition »
Jie Xu · Lei Luo · Cheng Deng · Heng Huang -
2018 Poster: Training Neural Networks Using Features Replay »
Zhouyuan Huo · Bin Gu · Heng Huang -
2018 Spotlight: Training Neural Networks Using Features Replay »
Zhouyuan Huo · Bin Gu · Heng Huang -
2017 Poster: Group Sparse Additive Machine »
Hong Chen · Xiaoqian Wang · Cheng Deng · Heng Huang -
2017 Poster: Regularized Modal Regression with Applications in Cognitive Impairment Prediction »
Xiaoqian Wang · Hong Chen · Weidong Cai · Dinggang Shen · Heng Huang -
2017 Poster: Learning A Structured Optimal Bipartite Graph for Co-Clustering »
Feiping Nie · Xiaoqian Wang · Cheng Deng · Heng Huang