Distributed Minimax Fair Optimization over Hierarchical Networks

In modern applications, the underlying computation and communication networks are often hierarchical, which is typified by the three-layer client-edge-cloud system that has become prominent in recent times. We study minimax fairness in distributed optimization over such systems, to provide robust performance guarantee for the worst-case mixture of loss functions. We propose HierMinimax, a communication efficient distributed algorithm to solve the minimax optimization problem. We provide convergence analysis for both convex and non-convex loss functions, leading to performance bounds that enable tuning the tradeoff between the communication complexity and the optimization convergence rate. Our experiments on classification problems with canonical datasets show that HierMinimax substantially improves the fairness in learning accuracy and reduces the communication overhead compared with the current best alternatives.