TL;DR
Standard multi-objective optimization (MOO) often settles for "Pareto stationarity," a condition that can leave significant performance on the table when objectives depend on different subsets of variables. This paper introduces Refined Pareto Stationarity (RPS) and an efficient graph-based partitioning algorithm that exploits variable sparsity to reach superior solutions without increasing computational complexity.
The Problem: The Trap of Standard Pareto Stationarity
In Multi-Objective Optimization, the ultimate goal is to find a "Pareto optimal" solution—a point where you cannot improve one objective without degrading another. Because finding the absolute global Pareto front is computationally intractable in deep learning, most gradient-based algorithms (like the Multiple Gradient Descent Algorithm, or MGDA) aim for Pareto Stationarity (PS). This is a first-order necessary condition: at a PS point, there is no single direction that improves all objectives simultaneously.
However, the authors reveal a major "trap" in this approach. In sparse settings—where different tasks or objectives depend on different parameters—standard Pareto stationarity is too weak. You might reach a point that is technically "stationary" for the system as a whole, yet you could still improve individual objectives by adjusting their specific variables without harming others. Because standard algorithms treat all parameters as one giant block, they effectively get "stuck" in sub-optimal solutions that are not truly Pareto optimal.
Methods: Bridging the Gap Between Stationarity and Optimality
The authors propose a two-part solution to overcome the limitations of standard PS:
- Refined Pareto Stationarity (RPS): A new solution concept that leverages the underlying "function-variable" dependency structure. It requires stationarity not just globally, but across specific, decoupled partitions of variables.
- The
REFINED_PARTITIONAlgorithm: To find these partitions, the authors model the problem as a bipartite graph where nodes represent functions and variables. They use a cycle-detection approach: if a group of variables and functions forms a cycle in the graph, they are coupled and must be optimized together. If no cycle exists, those variables can be decoupled.
- RP-MGDA: The authors enhance the standard MGDA by applying it to these refined partitions. Instead of solving one massive, complex quadratic program to find a descent direction for all parameters at once, RP-MGDA solves several smaller ones. These smaller problems can often be computed in parallel.
Key Insights and Theoretical Guarantees
- The "Sandwich" Theorem: The authors mathematically prove that RPS is strictly stronger than standard Pareto Stationarity, but still a necessary condition for Pareto Optimality. It effectively "trims" away the low-quality stationary points that plague standard MOO.
- Sparsity as a Tool for Decoupling: Usually, sparsity is viewed as a challenge in optimization. Here, the authors turn it into an advantage. By identifying which variables do not affect certain functions, they can optimize those variables more aggressively without fear of negative transfer.
- Efficiency Gains: Interestingly, RP-MGDA is often theoretically cheaper than vanilla MGDA. The most expensive part of MGDA (solving the dual subproblem) scales superlinearly with the number of objectives. By breaking the problem into smaller blocks, the total computation time can actually decrease.
- Strict Convexity Bridge: Under "partial strict convexity" (where functions are strictly convex relative to their own variables), RPS actually collapses into true Pareto Optimality, whereas standard PS does not.
Experimental Validation and Results
The authors validated their approach across several distinct architectural structures:
- Synthetic Quadratic Problems: Using randomly generated sparse adjacency matrices, RP-MGDA consistently found solutions that "Pareto-dominated" those found by standard MGDA. In many cases, vanilla MGDA stopped at points where objectives were 10x higher than those reached by the refined version.
- Personalized Federated Learning (MTL Structure): Using MNIST and CIFAR-10, where a global model is shared but clients have local "personalized" layers, RP-MGDA showed much smoother convergence and reached lower final cross-entropy losses across almost all client objectives.
- Hierarchical Classification (Ladder Structure): Tested on CIFAR-10, where different tasks (e.g., coarse vs. fine labels) branch off at different depths of a neural network.
- Partial Information Learning (Chain Structure): Simulated using the California Housing dataset, where different parties only have access to specific subsets of features.
Crucially, the authors proved that RP-MGDA maintains the $O(1/\sqrt{t})$ convergence rate typical of first-order MGDA, meaning the performance boost comes at no cost to the theoretical speed of the algorithm.
Limitations and Future Work
While highly effective, the algorithm currently requires knowing the "adjacency matrix"—i.e., explicitly knowing which variables affect which objectives. While this is clear in many architectures like Multi-Task Learning or Federated Learning, it might be harder to determine in a standard "black-box" dense neural network without additional analysis.
Future work could explore extending the "Refined Partition" concept to other MOO solvers like PCGrad or CAGrad. Additionally, exploring how to handle dynamic sparsity—where the dependency structure changes during training through pruning or architectural search—remains an exciting open question.
Summary updated