acceptodds
Under review as a conference paper at ICLR 2027

Fed-MOZOO: Federated Multi-Objective Online Zeroth-Order Optimization with Intermittent Communication

Abstract

Federated online learning provides a promising framework for sequential decision-making over distributed data, but its effectiveness is challenged by communication constraints, heterogeneous local data, and dynamically changing objectives. When multiple objectives must be optimized simultaneously, existing federated online methods mainly rely on first-order gradient information, which may be unavailable in black-box or gradient-inaccessible environments. This motivates the study of federated multi-objective online optimization with limited function-value feedback and intermittent communication. To this end, we propose \FedMOZOO, a two-point zeroth-order method that performs local preference-based scalarization and projected updates, followed by periodic model aggregation. For convex -Lipschitz losses over a radius- domain, we establish a dimension- and communication-dependent regret guarantee for the virtual global model: , where is the online horizon and is the number of communication rounds. The bound characterizes the effects of zeroth-order feedback and intermittent communication, and recovers the standard scaling when communication occurs at every round. Experiments on synthetic and convex multi-objective learning tasks evaluate regret, communication–accuracy trade-offs, preference tracking, Pareto-front quality, and the scaling behavior with dimension and communication frequency.

Primary area:
optimization
Keywords:
Federated Learning, Multi-Objective Optimization, Online Learning, Zeroth-Order Optimization, Regret Analysis

Reviews

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

The authors propose Fed-MOZOO, a federated method for multi-objective online convex optimization with intermittent communication and zeroth-order feedback. Clients scalarize loss vectors via preference vectors, compute two-point zeroth-order gradient estimates using shared random directions, and take projected local steps while the server aggregates models every KK steps. For convex Lipschitz losses under an oblivious adversary, they derive a global-model regret bound of O(BG(d/T+d1/4/R+1/T))O(BG(\sqrt{d/T} + d^{1/4}/\sqrt{R} + 1/T)), which recovers the standard d/T\sqrt{d/T} rate under full communication. They further establish Pareto optimality and approximate non-domination for the scalarized comparator. Experiments on synthetic quadratic streams and convex classification tasks (Adult, MNIST) evaluate regret, trade-offs, and Pareto fronts.

Critical strengths
  • The analysis distinguishes local-play regret from global-model regret. It then bounds the gap between them with an explicit consensus-drift term that vanishes when clients communicate every round. The proofs, including the dimension-linear second-moment bound for the two-point estimator, are correct, and each error term is easy to trace to its source: estimation, smoothing, or drift.

  • The paper states plainly that its guarantee is preference-conditioned, assumes an oblivious adversary, and gives no MM-dependent speedup. It also explains why, and it does not overstate what the result implies about each objective individually. This candor makes the theoretical contribution easy to evaluate.

Critical weaknesses

The contribution seems somewhat limited. With the preference vector fixed, the problem appears to reduce to single-objective federated bandit optimization, and the method is close to FedAvg with a two-point estimator, which Patel et al. (2023) already study with gains in the number of clients. The bound here does not depend on MM, and a synchronized minibatch scheme may achieve a better bound. Some experimental results are also hard to reconcile with the algorithm. At K=1K = 1, I would expect zero consensus error and identical results for Fed-MOZOO and Central-MOZO, but the reported results seem to show otherwise. The zeroth-order method also appears to beat the exact-gradient baselines. Since the experimental settings actually used are not clearly reported, I find the empirical claims difficult to assess.

Questions for authors

Clarification

  1. How does the bound compare with that of Patel et al. (2023), who analyze FedAvg with two-point feedback in the same intermittent-communication setting? Could a synchronized minibatch scheme, in which all clients query the same model and their estimates are averaged at each communication, achieve a better bound with the same queries and communication? If so, what advantage do local updates offer here?

  2. With K=1K = 1, Algorithm 1 synchronizes after every step, so I would expect zero consensus error and identical results for Fed-MOZOO and Central-MOZO. Could you explain why the reported results seem to show nonzero consensus error and a gap between the two methods? Is Central-MOZO defined differently from Fed-MOZOO with K=1K = 1?

  3. Fed-MOZOO appears to outperform Fed-MOGD, which uses exact gradients under the same federation. Were the step sizes tuned separately for each method? What explains this ordering, given Theorem 1?

More

  • A guarantee that goes beyond preference-conditioned regret, such as Pareto regret or tracking of time-varying preferences.
  • An analysis that shows explicit gains in the number of clients MM.
  • Extensions to noisy function evaluations and nonconvex objectives.
Reviewer_6eHrOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Fed-MOZOO studies federated multi-objective online optimization with function-value feedback and intermittent communication. It combines preference-weighted scalarization, two-point gradient estimation, projected local updates, and periodic model averaging. For convex, Lipschitz losses under exact feedback, it derives a static regret bound for the virtual global model, quantifying estimation, smoothing, and communication effects. Experiments on synthetic problems and convex classification tasks examine communication trade-offs and preference adaptation.

Critical strengths
  • This paper provides an interpretable regret decomposition. The bound explicitly separates several components in the algorithm. The communication penalty vanishes when clients synchronize every round, providing a useful consistency check.
  • This paper studies a simple and well-specified algorithm.
Critical weaknesses
  • My first concern is the limited technical novelty of the multi-objective formulation. Once the prescribed preference weights are applied, the objectives reduce to a single convex, Lipschitz scalar loss. The subsequent two-point estimation, local updates, and regret analysis largely follow standard single-objective techniques. Consequently, the paper does not clearly establish what additional challenge requires a new algorithm or analysis beyond applying an existing federated zeroth-order online method to the scalarized loss.
  • This concern is reinforced by the gap between the motivation and the theoretical guarantee. Although the paper emphasizes tracking time-varying Pareto optimality, its main result establishes scalarized static regret against the best fixed comparator. This does not guarantee tracking of time-varying Pareto-optimal solutions. A stronger contribution would identify a limitation of existing methods and provide a guarantee that directly addresses it.
Questions for authors
  • What cannot be obtained by directly applying an existing federated zeroth-order online algorithm to the weighted scalar loss?
  • How does the static regret guarantee support the stated goal of tracking time-varying Pareto optimality? Could the algorithm achieve low static regret while remaining far from the instantaneous Pareto front?
Reviewer_TBr1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Fed-MOZOO, a federated multi-objective online zeroth-order optimization method under intermittent communication. The method involves preference-weighted scalarization, symmetric two-point zeroth-order gradient estimation, projected local updates, and periodic model averaging. The authors establish an expected regret bound for the virtual network-average model under convex Lipschitz objectives and evaluate the method on synthetic quadratic streams and convex classification.

Critical strengths

The problem itself is well-motivated, as the paper's target is to consider federated online optimization with multiple objectives, zeroth-order feedback, and intermittent communication. These constraints are usually studied individually, but their combination creates a relevant setting in which clients must optimize changing objectives without analytical gradients while limiting communication.

Critical weaknesses
  1. The proposed preference-weighted zeroth-order estimator is potentially mathematically equivalent to a standard two-point estimator for the scalarized objective. If this stands, it is unclear what algorithmic contribution distinguishes Fed-MOZOO from a direct application of existing federated zeroth-order online optimization methods.
  2. In the intro, the authors claim to track time-varying Pareto optimality. However, the authors seem to demonstrate the regret relative to a fixed solution, rather than the ability to track a time-varying optimal solution.
  3. The contribution of the proposed federated collaboration is unclear. The paper does not discuss the benefits of collaboration in several directions (e.g., can having multiple clients reduce estimator variance? Can having multiple clients improve regret?). While these are not critically necessary, they are some of the key motivations or contributions of introducing federated learning.
Questions for authors

Please see my above concerns, some of which critically challenge the current motivation and contribution of this paper. From my perspective, the paper might require fundamental revision.

Reviewer_kWQ7OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies federated online convex optimization with MM clients and PP objectives under intermittent communication (KK local steps between averaging steps, R=T/KR = T/K communication rounds) and two-point zeroth-order feedback. At each round a preference vector λt\lambda_t is given, and each client works with the linearly scalarized loss ⟨λt,Ftm(x)⟩\langle \lambda_t, F_t^m(x) \rangle. Fed-MOZOO combines three parts: a two-point estimator that shares one random direction across all objectives, projected local steps, and FedAvg-style periodic averaging.

The analysis shows that the estimator is unbiased for the gradient of the ball-smoothed scalarized loss, with second moment at most 2dG22dG^2. With a tuned step size, it bounds the average regret of the locally played iterates by O(BGd/T)O(BG\sqrt{d/T}). Using a client-drift bound of order ηQ(K−1)\eta Q(K-1), it bounds the average regret of the virtual network average xˉt\bar x_t by O(BG(d/T+d1/4/R+1/T))O\big(BG(\sqrt{d/T} + d^{1/4}/\sqrt{R} + 1/T)\big). For a fixed, strictly positive preference, the scalarized comparator is Pareto optimal.

Experiments use synthetic conflicting quadratic streams and convex models on Adult and MNIST. They compare against Fed-MOGD, Central-MOZO and Local-MOZO, and, for fixed-preference trade-offs, FMGDA.

Critical strengths

The derivations in the main text and in Appendices A–C are correct; I found no errors, and the analysis cleanly separates zeroth-order variance, smoothing bias and communication drift. The authors are also candid about the scope of the result (no MM-dependent speedup, a preference-conditioned guarantee, an oblivious adversary). However, correctness is not the issue: the results are standard (see Weaknesses), so these points do not support acceptance.

Critical weaknesses

W1. Limited novelty and significance. Once λt\lambda_t is given, the problem reduces to single-objective federated online convex optimization with loss ⟨λt,Ftm⟩\langle \lambda_t, F_t^m \rangle; beyond the linearity of the scalarization, the multi-objective structure plays no role in the algorithm or the analysis. The analysis combines standard components (the ball-smoothing two-point estimator, Zinkevich's potential argument, and a drift bound of step size times the number of local steps), and the resulting bound shows no benefit from federation: it is independent of MM (acknowledged in Appendix B.7), and the local-play guarantee (Eq. 5.10) holds even without any communication. The only communication-dependent result concerns the virtual average xˉt\bar x_t, with no lower bound or discussion of optimality.

W2. The experiments cannot be verified and are inconsistent with the paper's own analysis. The configurations of the reported runs (e.g., MM, TT, heterogeneity level, selected η\eta and δ\delta, number of seeds) are not given; Appendix D is written as a checklist of instructions rather than a record of what was run, and code is only offered on request. Several results are hard to reconcile with the paper itself. The zeroth-order Fed-MOZOO beats the exact-gradient Fed-MOGD in Fig. 1 and Supp. Fig. 2(a). At K=1K = 1 (Supp. Fig. 2(a)), Fed-MOZOO and Central-MOZO, which should essentially coincide given the description of Central-MOZO, differ by about a factor of two. Supp. Fig. 2(d) shows a strong U-shape in δ\delta, although the paper states that the second moment of its estimator does not depend on δ\delta, so small δ\delta should not hurt. As the theory is a straightforward combination of known results, the experiments are the main remaining evidence, and they do not provide reliable support.

Questions for authors
  1. For every panel of Fig. 1 and Supp. Fig. 2, please give the exact configuration: MM, dd, TT, KK, the heterogeneity level, the Dirichlet parameter, the Adult attribute used to define the objectives, the η\eta and δ\delta selected for each method, and the number of seeds.
  2. Please define Central-MOZO and Fed-MOGD precisely. How does Fed-MOZOO with K=1K = 1 differ from Central-MOZO, why do the two differ in Supp. Fig. 2(a), and how is Central-MOZO evaluated at different RR in Supp. Fig. 2(b)?
  3. Why does the zeroth-order method outperform the exact-gradient Fed-MOGD? Were the step sizes tuned separately for each method?
  4. How do you explain the U-shaped dependence on δ\delta in Supp. Fig. 2(d), given that the second moment of your estimator does not depend on δ\delta?
  5. With λt\lambda_t given, what is technically new relative to single-objective federated zeroth-order online convex optimization (e.g., Patel et al., 2023)? Is there any result in which the multi-objective structure changes the algorithm or the analysis (e.g., unknown or learned preferences, per-objective or Pareto-stationarity guarantees), or in which more clients provably help?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.