acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
multi-objective optimization, Byzantine robustness, distributed optimization, multi-gradient descent, robust aggregation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_zxHBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies multiple-gradient descent (MGDA) under Byzantine attacks and proposes Certified Robust MGDA (CR-MGDA), a method that uses task-wise error balls to apply an exact common-descent test to the regularized MGDA proposal. When the proposal fails, it searches the same convex-combination family for an alternative certified direction; if recovery yields no accepted direction, it returns an explicit upper bound on the honest Pareto-stationarity gap. The paper also establishes non-asymptotic stationarity bounds for non-convex objectives and weighted objective-gap bounds for strongly convex ones. For stochastic reports, it provides trajectory-wide high-probability certificates and convergence bounds from failure-probability budgets, plus expected convergence via a separate mean-square analysis.

Critical strengths

This paper tackles a timely and relevant problem in multi-objective optimization, where MGDA is a standard approach and is useful in settings such as multi-task federated learning. Under Byzantine attacks, standard MGDA can perform poorly: residual errors may destroy common descent, reverse the honest MGDA direction, and render Pareto-stationarity assessments unreliable. The proposed solution addresses these issues, and the paper evaluates its performance through several numerical results, in addition to theoretical analyses for both non-convex and strongly convex settings.

Critical weaknesses
  • CR-MGDA relies on a task-wise error bound r_s that must be estimated accurately; otherwise, the method becomes overly conservative. In the paper, r_s is derived via the triangle inequality, which may not yield a tight bound. As a result, r_s must be estimated empirically for each application (optimization objectives), setting, and attack type, limiting the method's practical usefulness. The gap between empirical and theoretical error radii can be very large, as shown in Table 2.
  • The paper provides convergence analysis for both non-convex and strongly convex settings. However, the analysis follows standard tools and does not appear challenging. The resulting bounds in Section IV and in the appendix increase with the error radii, further demonstrating sensitivity to precise estimation of the latter.
  • The numerical experiments do not convincingly establish the practical advantage of the proposed method. The considered settings involve small numbers of clients and Byzantine attacks, whereas in practice (e.g. in FL) the number of clients can be much larger. Moreover, UNSW-NB15 may not be the best choice for assessing the method's performance, since its attacks appear scarce and tool-generated, and thus do not necessarily represent recent complex attack techniques.
Questions for authors

The authors are invited to explain the challenges in the convergence analysis, given that the tools used are standard and widely employed in non-asymptotic convergence analysis. The authors may also comment on the empirical error radii estimation in practice : whether this must be done for each setting/application scenario and optimization objectives. In the convergence analysis, kappa appears in the denominator, suggesting it should not be close to 0 or very small. Also kappa cannot be high. What is the best value ? Is it problem dependent or it can be set for multiple settings (multiple optimization tasks and objectives) ?

Reviewer_cjwMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies distributed multi-objective optimization with MGDA when some clients send arbitrary (Byzantine) gradient reports. It introduces CR-MGDA that uses task-wise robust-aggregation error bounds to test whether the regularized MGDA direction is a common descent direction for all honest objectives. If the test fails, an SOCP searches the same convex-combination family for a certified alternative; if that also fails, the method skips the update and returns an upper bound on the honest Pareto-stationarity gap.

Critical strengths
  1. The paper identifies a relevant gap: robust aggregations do not guarantee safe MGDA decisions. This is also illustrated with attacks targeting MGDA.
  2. The certification and recovery steps are simple to implement on top of any robust aggregator with a known error radius.
  3. Theoretical guarantees under standard assumptions.
  4. The paper is sound and clearly written.
Critical weaknesses
  1. Every certification decision requires radii that depend on the heterogeneity bound ζs\zeta_s and honest weights, which a server cannot obtain without knowing the honest set.

  2. Assumption 3.1 is stated in terms of client weights that are defined by the authors to be proportional to the data held by the clients. Although its the standard in Byzantine robustness to assume honest majority (in number of clients), bounding αsH\alpha_s^H requires clients' private data sizes, which a single Byzantine client could inflate if they are self-reported.

  3. Potential leakage (privacy): Reporting per-task data proportions can reveal clients' label distributions, since the UNSW-NB15 objectives are class-conditional.

  4. All learning experiments calibrate radii from clean client reports and the calibration formula is not fully specified.

  5. The calibrated radii do not reliably cover the true error, with all-task coverage as low as 44.3% (Table 2).

  6. Clean calibration effectively assumes trusted data, which gives CR-MGDA side information the baselines do not have.

  7. The Analytic rows of Table 2 are decisions recomputed offline along the empirical trajectory, the paper does not state how teh degree of heterogeneity was obtained for them.

  8. The four MGDA-specific attacks that motivate the method are evaluated only on UNSW-NB15 with a small MLP. Whereas CelebA and CIFAR-100 are evaluated only under naive attacks (sign flip, Gaussian noise, zero gradient) and without baseline defenses, so they do not show a benefit from the method.

  9. Missing baseline attacks and defenses: (i) strong model-poisoning attacks (ALIE, IPM, Min-Max/Min-Sum) are not evaluated. Additionally, attacks targeting the method are not studied, such as forcing repeated rejections ... (ii) also baseline defenses are limited to Krum, coordinate median and trimmed mean, without pre-aggregation methods such as NNM or bucketing (cited), when its well established that a pre-aggregation is mandatory under heterogeneity.

  10. The TWGM radius does not fall below 2ζ+ϵ,2 \zeta+ \epsilon,even with no Byzantine clients.


[Bucketing] Byzantine-robust learning on heterogeneous datasets via bucketing. In ICLR 2022.

[Min-Max/Min-Sum] Shejwalkar et al. Manipulating the byzantine: Optimizing model poisoning attacks and defenses for fl. In NDSS, 2021

[NNM] Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity, AISTATS 2023

Questions for authors
  1. How can valid radii be obtained in practice without knowing the honest set or clients' private data sizes?
  2. How are the honest client weights αs,i\alpha_{s,i} obtained, and what prevents a Byzantine client from inflating them? And how was ζs\zeta_s obtained for the Analytic rows of Table 2?
  3. Why are the four MGDA-specific attacks not evaluated on CelebA and CIFAR-100, and can you add baselines there especially with the standard non-IID pre aggregations ?
  4. Can you evaluate ALIE, IPM, Min-Max/Min-Sum, and attacks targeting the certifier against all baselines? or at least explain why these are left out ?

I am willing to increase my score if the rebuttal resolves the concerns (see Critical Weaknesses) or clarifies points I have misread.

Reviewer_29YtOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

CR-MGDA addresses Byzantine attacks in distributed multi-objective optimization through descent certification, recovery of alternative directions, and stationarity-gap bounds. The paper provides deterministic and stochastic guarantees and evaluates safety and optimization progress.

Critical strengths

• The paper identifies meaningful MGDA failure modes, including unsafe directions and false stationarity. • Certification, recovery, and stationarity assessment form a coherent framework. The stochastic analysis accounts for decisions that depend on the same gradient estimates. • The controlled quadratic examples and recovery ablation are informative. Reporting rejected updates makes the trade-off between safety and progress visible.

Critical weaknesses

• Table 2 reports only 44.3% all-task coverage in mini-batch GMOM rounds. Recomputing decisions with valid full-gradient radii on the same states and reports would reject 72.1% of rounds. Although no unsafe directions were observed with empirical radii, useful learning progress with valid certification remains insufficiently demonstrated. • The descent condition closely resembles Peitz and Dellnitz’s for convex-combination directions. A sharper comparison would clarify the additional contribution. • Figure 5 lacks uncertified TWGM-MGDA, despite matched-aggregator comparisons in Figures 3 and 6. Attacks occur every third round, leaving progress under persistent attacks unclear.

Questions for authors

• Can you specify the calibration procedure and demonstrate useful learning progress with valid radii, including the stochastic sampling term omitted from Table 2’s analytic comparisons? • How does the method compare with the closest uncertainty-aware approach using identical gradient estimates and radii? • Can you add TWGM-MGDA to Figure 5 and evaluate persistent attacks? • What numerical checks and solver tolerances are used to determine whether recovery succeeds or fails?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.