Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks

Abstract

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 parameters, our algorithm requires a much less number of communication rounds and still achieves a 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.

References in corpus (22)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Large Scale GAN Training for High Fidelity Natural Image Synthesis
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Parallel training of DNNs with Natural Gradient and Parameter Averaging
• Communication-Efficient Distributed Dual Coordinate Ascent
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Experiments on Parallel Training of Deep Neural Network using Model Averaging
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition

Cited by in corpus (6)

• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization