Federated Distributionally Robust Optimization With Non-Convex Objectives: Algorithm and Analysis

Distributionally Robust Optimization (DRO), which aims to find an optimal decision that minimizes the worst case cost over the ambiguity set of probability distribution, has been widely applied in diverse applications, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e.g.</i>, network behavior analysis, risk management, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">etc.</i> Nevertheless, prevailing DRO techniques encounter three primary challenges in distributed environments: 1) addressing asynchronous updating efficiently; 2) leveraging the prior distribution effectively; 3) appropriately adjusting the degree of robustness based on varying scenarios. To this end, we propose an asynchronous distributed algorithm, named <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</b>synchronous <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</b>ingle-loo<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</b> alternat<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</b>ve g<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</b>adient proj<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</b>ction (ASPIRE) algorithm with the it<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</b>rative <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</b>ctive <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</b><bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</b>t method (EASE) to tackle the federated distributionally robust optimization (FDRO) problem. In addition, a new uncertainty set, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i.e.</i>, constrained <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$D$</tex-math></inline-formula>-norm uncertainty set, is developed to effectively leverage the prior distribution and flexibly control the degree of robustness. We further enhance the proposed framework by integrating various uncertainty sets and conducting a comprehensive theoretical analysis of the computational complexity associated with each uncertainty set. To expedite convergence speed, we also introduce ASPIRE-ADP, a method that can dynamically adjust the number of active workers. Finally, our theoretical analysis elucidates that the proposed algorithm is guaranteed to converge and the iteration complexity and communication complexity are also analyzed. Extensive empirical studies on real-world datasets validate that the proposed method excels not only in achieving fast convergence and robustness against data heterogeneity and malicious attacks but also in effectively managing the trade-off between robustness and performance.