Beyond Robust Aggregation: Certified Multi-Objective Descent under Byzantine Attacks

Robust aggregation limits Byzantine influence but does not ensure reliable decisions in distributed multi-objective optimization: residual task-gradient errors can distort the task weights and direction selected by the multiple-gradient descent algorithm (MGDA) or falsely signal Pareto stationarity. We propose Certified Robust MGDA (CR-MGDA), which converts task-wise error bounds into a necessary-and-sufficient common-descent test for every honest gradient consistent with these bounds. When a regularized MGDA proposal fails certification, a convex recovery problem searches for an alternative certified direction; if recovery fails, CR-MGDA returns a computable upper bound on the honest Pareto-stationarity gap. We establish non-asymptotic stationarity bounds for non-convex objectives and weighted objective-gap bounds for strongly convex objectives. For stochastic reports, local geometric median-of-means estimation supports trajectory-wide high-probability certificates and expected convergence without assuming independence between the reports and the resulting MGDA decisions. Experiments under multiple Byzantine attacks show that CR-MGDA improves descent safety while maintaining optimization progress.