First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints

Zhankun Luo, Antesh Upadhyay, Sang Bin Moon, Abolfazl HashemiarXiv 2026 · arXiv

TL;DR

This paper introduces the Softmax-Weighted Switching Gradient method, a novel primal-only algorithm designed to solve constrained minimax optimization problems in federated learning. By replacing traditional dual variables with a smooth softmax approximation and a logic-based switching mechanism, the algorithm stabilizes training and guarantees worst-case client performance under strict local constraints. This approach effectively eliminates the severe "dual drift" and hyperparameter sensitivity common in traditional primal-dual or penalty-based methods.

What Problem Does This Paper Address?

Standard Federated Learning (FL) typically minimizes the average loss across all participating clients. While this works well on average, it often biases the global model against underrepresented or "hard" client distributions. Minimax optimization fixes this by focusing on the worst-performing client, ensuring uniformly good performance across all devices.

However, real-world FL deployments must also satisfy strict client-specific operational constraints, such as fairness mandates, safety limits, or resource budgets. Tracking distinct stochastic constraints across a massive network using traditional primal-dual methods is prohibitively expensive. When clients participate only partially, their corresponding dual variables become stale, leading to severe optimization instability known as dual drift.

The authors tackle this challenge by asking: How can we optimize for the worst-case client objective while strictly satisfying worst-case stochastic constraints, without relying on unstable dual variables?

Methods

The authors propose a single-loop, first-order algorithm that completely bypasses explicit dual variables:

  1. Softmax-Weighted Approximation: Instead of tracking a non-smooth "hard" maximum over clients, the algorithm applies a temperature-controlled softmax function controlled by a hyperparameter $\alpha$. This smooths the gradient landscape while maintaining sensitivity to the worst-performing clients.
  2. Switching Gradient Mechanism: Rather than using a dual update loop, the algorithm uses a primal-only switching rule. At each global round, it evaluates the softmax-weighted constraint violation. If the constraints are satisfied within a tightened tolerance threshold ($\lambda$), the algorithm prioritizes minimizing the objective function. If the constraints are violated, it adaptively switches to reducing constraint violations.
  3. Masked Softmax for Partial Participation: To accommodate practical scenarios where only a subset of clients participate per round, the server applies a masked softmax operator restricted strictly to the active clients.

Datasets

The algorithm was evaluated across three distinct tasks and datasets:

  • Neyman-Pearson Classification: Conducted on the Breast Cancer Wisconsin (Diagnostic) Dataset to minimize empirical loss on a majority class while bounding minority class loss (convex setup).
  • Fair Classification: Evaluated on the Adult income dataset using a deep neural network to minimize binary cross-entropy subject to a demographic parity constraint (highly non-convex, non-smooth setup).
  • Federated Safe Reinforcement Learning: Evaluated on a heterogeneous Constrained Markov Decision Process (CMDP) CartPole environment where 10 clients operate under different simulated physics parameters (Earth, Mars, and Jupiter gravity/mass variations).

Key Insights and Ideas

  • Ditching Dual Variables for Stability: Primal-dual methods inherently struggle with partial client participation because inactive clients cause their dual variables to become stale. A logic-based switching mechanism avoids this entirely by relying on a trigger condition rather than optimization variables.
  • The Alpha ($\alpha$) Trade-off: A high $\alpha$ value perfectly mimics a hard maximum but creates a steep, non-differentiable loss landscape prone to permanent oscillations and limit cycles (visualized via the cobweb plots in Figure 5). Conversely, a low $\alpha$ smooths the landscape but loses worst-case sensitivity. The authors establish a tighter, generalized lower bound for $\alpha$ ($\alpha \ge \frac{2\ln n}{\epsilon'}$) that balances this trade-off without requiring restrictive bounded loss assumptions.
Cobweb plot for trajectories
  • Quantifying Client Sampling Noise: To prove convergence under partial participation, the authors introduce the concept of First-Order Stochastic Dominance (FSD) to bound the relative gap between subset maximums and global maximums, proving that partial client sampling remains theoretically sound if clients share structural proximity.

Key Results

  • Theoretical Guarantees: Under full client participation, the algorithm achieves the standard $\tilde{\mathcal{O}}(\epsilon^{-4})$ oracle complexity to satisfy a unified bound $\epsilon$ for both the optimality gap and feasibility tolerance. It also sharpens the high-probability convergence guarantee to $\mathcal{O}(\log \frac{1}{\delta})$, improving upon the $\mathcal{O}(\log^2 \frac{1}{\delta})$ dependency found in prior switching-gradient literature.
  • Empirical Performance: In both Neyman-Pearson and Fair Classification experiments, the proposed method converged faster and achieved a lower objective value for a comparable level of constraint satisfaction than traditional penalty-based and primal-dual baselines.
NP Classification Results
  • Safe RL Excellence: On the heterogeneous CartPole benchmark, the Softmax-SGM method significantly outperformed Parallel CRPO in both return maximization and constraint satisfaction, successfully keeping the most vulnerable clients within their safety envelopes.

Limitations and Future Work

  • Bounded Noise Assumption: To guarantee scalable convergence under partial participation, the current theoretical framework assumes that client noise distributions have strictly upper-bounded support (essential supremum). The authors note that this limitation could be resolved in future work by dynamically standardizing the objective gap using generalized extreme value theory (EVT).
  • Algorithmic Extensions: The authors suggest that future iterations of this framework could incorporate momentum-based variance reduction techniques and extend the analysis to broader classes of weakly convex objectives.

Summary updated

Abstract

This paper addresses the distributed stochastic minimax optimization problem subject to stochastic constraints. We propose a novel first-order Softmax-Weighted Switching Gradient method tailored for federated learning. Under full client participation, our algorithm achieves the standard $\tilde{\mathcal{O}}(ε^{-4})$ oracle complexity to satisfy a unified bound $ε$ for both the optimality gap and feasibility tolerance. We extend our theoretical analysis to the practical partial participation regime by quantifying client sampling noise through a stochastic superiority assumption. Furthermore, by relaxing standard boundedness assumptions on the objective functions, we establish a strictly tighter lower bound for the softmax hyperparameter. We provide a unified error decomposition and establish a sharp $\mathcal{O}(\log\frac{1}δ)$ high-probability convergence guarantee. Ultimately, our framework demonstrates that a single-loop primal-only switching mechanism provides a stable alternative for optimizing worst-case client performance, effectively bypassing the hyperparameter sensitivity and convergence oscillations often encountered in traditional primal-dual or penalty-based approaches. We verify the efficacy of our algorithm via experiment on the Neyman-Pearson (NP) classification, fair classification, and federated safe reinforcement learning tasks.
BibTeX
@misc{luo2026first,
  author = {Zhankun Luo and Antesh Upadhyay and Sang Bin Moon and Abolfazl Hashemi},
  title = {{First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints}},
  year = {2026},
  eprint = {2603.05774},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.05774},
}
Figure