- 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) ?