Timezone: »
In this paper, we study distributed algorithms for large-scale AUC maximization with a deep neural network as a predictive model.
Although distributed learning techniques have been investigated extensively in deep learning, they are not directly applicable to stochastic AUC maximization with deep neural networks due to its striking differences from standard loss minimization problems (e.g., cross-entropy). Towards addressing this challenge, we propose and analyze a communication-efficient distributed optimization algorithm based on a {\it non-convex concave} reformulation of the AUC maximization, in which the communication of both the primal variable and the dual variable between each worker and the parameter server only occurs after multiple steps of gradient-based updates in each worker. Compared with the naive parallel version of an existing algorithm that computes stochastic gradients at individual machines and averages them for updating the model parameter, our algorithm requires a much less number of communication rounds and still achieves linear speedup in theory. To the best of our knowledge, this is the \textbf{first} work that solves the {\it non-convex concave min-max} problem for AUC maximization with deep neural networks in a communication-efficient distributed manner while still maintaining the linear speedup property in theory. Our experiments on several benchmark datasets show the effectiveness of our algorithm and also confirm our theory.
Author Information
Zhishuai Guo (The University of Iowa)
Mingrui Liu (The University of Iowa)
Zhuoning Yuan (The University of Iowa)
Ph.D. student in Machine Learning
Li Shen (Tencent AI Lab)
Wei Liu (Tencent AI Lab)
Tianbao Yang (The University of Iowa)
More from the Same Authors
-
2023 : Learning Better with Less: Effective Augmentation for Sample-Efficient Visual Reinforcement Learning »
Guozheng Ma · · Haoyu Wang · Lu Li · Zilin Wang · Zhen Wang · Li Shen · Xueqian Wang · Dacheng Tao -
2023 Oral: Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape »
Yan Sun · Li Shen · Shixiang Chen · Liang Ding · Dacheng Tao -
2023 Poster: Provable Multi-instance Deep AUC Maximization with Stochastic Pooling »
Dixian Zhu · Bokun Wang · Zhi Chen · Yaxing Wang · Milan Sonka · Xiaodong Wu · Tianbao Yang -
2023 Poster: Label Distributionally Robust Losses for Multi-class Classification: Consistency, Robustness and Adaptivity »
Dixian Zhu · Yiming Ying · Tianbao Yang -
2023 Poster: Generalization Analysis for Contrastive Representation Learning »
Yunwen Lei · Tianbao Yang · Yiming Ying · Ding-Xuan Zhou -
2023 Poster: Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization »
Zi-Hao Qiu · Quanqi Hu · Zhuoning Yuan · Denny Zhou · Lijun Zhang · Tianbao Yang -
2023 Poster: Learning Unnormalized Statistical Models via Compositional Optimization »
Wei Jiang · Jiayu Qin · Lingyu Wu · Changyou Chen · Tianbao Yang · Lijun Zhang -
2023 Poster: Are Large Kernels Better Teachers than Transformers for ConvNets? »
Tianjin Huang · Lu Yin · Zhenyu Zhang · Li Shen · Meng Fang · Mykola Pechenizkiy · Zhangyang “Atlas” Wang · Shiwei Liu -
2023 Poster: Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization »
Quanqi Hu · Zi-Hao Qiu · Zhishuai Guo · Lijun Zhang · Tianbao Yang -
2023 Poster: Improving the Model Consistency of Decentralized Federated Learning »
Yifan Shi · Li Shen · Kang Wei · Yan Sun · Bo Yuan · Xueqian Wang · Dacheng Tao -
2023 Poster: Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape »
Yan Sun · Li Shen · Shixiang Chen · Liang Ding · Dacheng Tao -
2023 Poster: FeDXL: Provable Federated Learning for Deep X-Risk Optimization »
Zhishuai Guo · Rong Jin · Jiebo Luo · Tianbao Yang -
2023 Poster: Learning to Learn from APIs: Black-Box Data-Free Meta-Learning »
Zixuan Hu · Li Shen · Zhenyi Wang · Baoyuan Wu · Chun Yuan · Dacheng Tao -
2023 Poster: CoCo: A Coupled Contrastive Framework for Unsupervised Domain Adaptive Graph Classification »
Nan Yin · Li Shen · Mengzhu Wang · Long Lan · Zeyu Ma · Chong Chen · Xian-Sheng Hua · Xiao Luo -
2022 : Paper 12: SafeRL-Kit: Evaluating Efficient Reinforcement Learning Methods for Safe Autonomous Driving »
· Li Shen · Bo Yuan · Xueqian Wang -
2022 Poster: Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance »
Zhuoning Yuan · Yuexin Wu · Zi-Hao Qiu · Xianzhi Du · Lijun Zhang · Denny Zhou · Tianbao Yang -
2022 Poster: A Simple yet Universal Strategy for Online Convex Optimization »
Lijun Zhang · Guanghui Wang · Jinfeng Yi · Tianbao Yang -
2022 Oral: A Simple yet Universal Strategy for Online Convex Optimization »
Lijun Zhang · Guanghui Wang · Jinfeng Yi · Tianbao Yang -
2022 Spotlight: Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance »
Zhuoning Yuan · Yuexin Wu · Zi-Hao Qiu · Xianzhi Du · Lijun Zhang · Denny Zhou · Tianbao Yang -
2022 Poster: Understanding Robust Overfitting of Adversarial Training and Beyond »
Chaojian Yu · Bo Han · Li Shen · Jun Yu · Chen Gong · Mingming Gong · Tongliang Liu -
2022 Poster: GraphFM: Improving Large-Scale GNN Training via Feature Momentum »
Haiyang Yu · Limei Wang · Bokun Wang · Meng Liu · Tianbao Yang · Shuiwang Ji -
2022 Poster: Optimal Algorithms for Stochastic Multi-Level Compositional Optimization »
Wei Jiang · Bokun Wang · Yibo Wang · Lijun Zhang · Tianbao Yang -
2022 Poster: DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training »
Rong Dai · Li Shen · Fengxiang He · Xinmei Tian · Dacheng Tao -
2022 Poster: Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence »
Zi-Hao Qiu · Quanqi Hu · Yongjian Zhong · Lijun Zhang · Tianbao Yang -
2022 Poster: Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications »
Bokun Wang · Tianbao Yang -
2022 Spotlight: GraphFM: Improving Large-Scale GNN Training via Feature Momentum »
Haiyang Yu · Limei Wang · Bokun Wang · Meng Liu · Tianbao Yang · Shuiwang Ji -
2022 Spotlight: Understanding Robust Overfitting of Adversarial Training and Beyond »
Chaojian Yu · Bo Han · Li Shen · Jun Yu · Chen Gong · Mingming Gong · Tongliang Liu -
2022 Spotlight: Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence »
Zi-Hao Qiu · Quanqi Hu · Yongjian Zhong · Lijun Zhang · Tianbao Yang -
2022 Spotlight: DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training »
Rong Dai · Li Shen · Fengxiang He · Xinmei Tian · Dacheng Tao -
2022 Spotlight: Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications »
Bokun Wang · Tianbao Yang -
2022 Spotlight: Optimal Algorithms for Stochastic Multi-Level Compositional Optimization »
Wei Jiang · Bokun Wang · Yibo Wang · Lijun Zhang · Tianbao Yang -
2022 Poster: DynaMixer: A Vision MLP Architecture with Dynamic Mixing »
Ziyu Wang · Wenhao Jiang · Yiming Zhu · Li Yuan · Yibing Song · Wei Liu -
2022 Poster: Improving Task-free Continual Learning by Distributionally Robust Memory Evolution »
Zhenyi Wang · Li Shen · Le Fang · Qiuling Suo · Tiehang Duan · Mingchen Gao -
2022 Poster: Deep Neural Network Fusion via Graph Matching with Applications to Model Ensemble and Federated Learning »
Chang Liu · Chenfei Lou · Runzhong Wang · Alan Yuhan Xi · Li Shen · Junchi Yan -
2022 Poster: When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee »
Dixian Zhu · Gang Li · Bokun Wang · Xiaodong Wu · Tianbao Yang -
2022 Spotlight: When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee »
Dixian Zhu · Gang Li · Bokun Wang · Xiaodong Wu · Tianbao Yang -
2022 Spotlight: Deep Neural Network Fusion via Graph Matching with Applications to Model Ensemble and Federated Learning »
Chang Liu · Chenfei Lou · Runzhong Wang · Alan Yuhan Xi · Li Shen · Junchi Yan -
2022 Spotlight: DynaMixer: A Vision MLP Architecture with Dynamic Mixing »
Ziyu Wang · Wenhao Jiang · Yiming Zhu · Li Yuan · Yibing Song · Wei Liu -
2022 Spotlight: Improving Task-free Continual Learning by Distributionally Robust Memory Evolution »
Zhenyi Wang · Li Shen · Le Fang · Qiuling Suo · Tiehang Duan · Mingchen Gao -
2021 Poster: Stability and Generalization of Stochastic Gradient Methods for Minimax Problems »
Yunwen Lei · Zhenhuan Yang · Tianbao Yang · Yiming Ying -
2021 Oral: Stability and Generalization of Stochastic Gradient Methods for Minimax Problems »
Yunwen Lei · Zhenhuan Yang · Tianbao Yang · Yiming Ying -
2021 Poster: Accelerate CNNs from Three Dimensions: A Comprehensive Pruning Framework »
Wenxiao Wang · Minghao Chen · Shuai Zhao · Long Chen · Jinming Hu · Haifeng Liu · Deng Cai · Xiaofei He · Wei Liu -
2021 Poster: LARNet: Lie Algebra Residual Network for Face Recognition »
Xiaolong Yang · Xiaohong Jia · Dihong Gong · Dong-Ming Yan · Zhifeng Li · Wei Liu -
2021 Poster: Federated Deep AUC Maximization for Hetergeneous Data with a Constant Communication Complexity »
Zhuoning Yuan · Zhishuai Guo · Yi Xu · Yiming Ying · Tianbao Yang -
2021 Spotlight: Federated Deep AUC Maximization for Hetergeneous Data with a Constant Communication Complexity »
Zhuoning Yuan · Zhishuai Guo · Yi Xu · Yiming Ying · Tianbao Yang -
2021 Spotlight: LARNet: Lie Algebra Residual Network for Face Recognition »
Xiaolong Yang · Xiaohong Jia · Dihong Gong · Dong-Ming Yan · Zhifeng Li · Wei Liu -
2021 Spotlight: Accelerate CNNs from Three Dimensions: A Comprehensive Pruning Framework »
Wenxiao Wang · Minghao Chen · Shuai Zhao · Long Chen · Jinming Hu · Haifeng Liu · Deng Cai · Xiaofei He · Wei Liu -
2020 Poster: Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints »
Runchao Ma · Qihang Lin · Tianbao Yang -
2020 Poster: Stochastic Optimization for Non-convex Inf-Projection Problems »
Yan Yan · Yi Xu · Lijun Zhang · Wang Xiaoyu · Tianbao Yang -
2019 Poster: Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence »
Yi Xu · Qi Qi · Qihang Lin · rong jin · Tianbao Yang -
2019 Oral: Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence »
Yi Xu · Qi Qi · Qihang Lin · rong jin · Tianbao Yang -
2019 Poster: Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number »
Zaiyi Chen · Yi Xu · Haoyuan Hu · Tianbao Yang -
2019 Oral: Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number »
Zaiyi Chen · Yi Xu · Haoyuan Hu · Tianbao Yang -
2018 Poster: An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method »
Li Shen · Peng Sun · Yitong Wang · Wei Liu · Tong Zhang -
2018 Poster: Dynamic Regret of Strongly Adaptive Methods »
Lijun Zhang · Tianbao Yang · rong jin · Zhi-Hua Zhou -
2018 Poster: SADAGRAD: Strongly Adaptive Stochastic Gradient Methods »
Zaiyi Chen · Yi Xu · Enhong Chen · Tianbao Yang -
2018 Poster: Level-Set Methods for Finite-Sum Constrained Convex Optimization »
Qihang Lin · Runchao Ma · Tianbao Yang -
2018 Oral: An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method »
Li Shen · Peng Sun · Yitong Wang · Wei Liu · Tong Zhang -
2018 Oral: Level-Set Methods for Finite-Sum Constrained Convex Optimization »
Qihang Lin · Runchao Ma · Tianbao Yang -
2018 Oral: SADAGRAD: Strongly Adaptive Stochastic Gradient Methods »
Zaiyi Chen · Yi Xu · Enhong Chen · Tianbao Yang -
2018 Oral: Dynamic Regret of Strongly Adaptive Methods »
Lijun Zhang · Tianbao Yang · rong jin · Zhi-Hua Zhou -
2018 Poster: Fast Stochastic AUC Maximization with $O(1/n)$-Convergence Rate »
Mingrui Liu · Xiaoxuan Zhang · Zaiyi Chen · Xiaoyu Wang · Tianbao Yang -
2018 Oral: Fast Stochastic AUC Maximization with $O(1/n)$-Convergence Rate »
Mingrui Liu · Xiaoxuan Zhang · Zaiyi Chen · Xiaoyu Wang · Tianbao Yang -
2018 Poster: Safe Element Screening for Submodular Function Minimization »
Weizhong Zhang · Bin Hong · Lin Ma · Wei Liu · Tong Zhang -
2018 Poster: End-to-end Active Object Tracking via Reinforcement Learning »
Wenhan Luo · Peng Sun · Fangwei Zhong · Wei Liu · Tong Zhang · Yizhou Wang -
2018 Oral: End-to-end Active Object Tracking via Reinforcement Learning »
Wenhan Luo · Peng Sun · Fangwei Zhong · Wei Liu · Tong Zhang · Yizhou Wang -
2018 Oral: Safe Element Screening for Submodular Function Minimization »
Weizhong Zhang · Bin Hong · Lin Ma · Wei Liu · Tong Zhang -
2017 Poster: GSOS: Gauss-Seidel Operator Splitting Algorithm for Multi-Term Nonsmooth Convex Composite Optimization »
Li Shen · Wei Liu · Ganzhao Yuan · Shiqian Ma -
2017 Poster: Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence »
Yi Xu · Qihang Lin · Tianbao Yang -
2017 Poster: A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates »
Tianbao Yang · Qihang Lin · Lijun Zhang -
2017 Talk: A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates »
Tianbao Yang · Qihang Lin · Lijun Zhang -
2017 Talk: GSOS: Gauss-Seidel Operator Splitting Algorithm for Multi-Term Nonsmooth Convex Composite Optimization »
Li Shen · Wei Liu · Ganzhao Yuan · Shiqian Ma -
2017 Talk: Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence »
Yi Xu · Qihang Lin · Tianbao Yang