Voronoi-grid-based Pareto Front Learning and Its Application to Collaborative Federated Learning

Comments 1. Eq. (14) defines the distance metric between the solution and the preference vector along the given direction. Although it is correct, the authors can explain this equation a bit more.

Response. Thanks for your suggestions. In the final version of this paper, we will formally show the derivation of Eq. (14). Specifically, we denote two points on the line by $l^i = (l_1^i, l_2^i, \ldots, l_J^i)$, and $r^i = (r_1^i, r_2^i, \ldots, r_J^i)$, respectively. The vector $\overrightarrow{r^i l^i} = l^i - r^i = (l_1^i - r_1^i, l_2^i - r_2^i, \ldots, l_J^i - r_J^i)$. Project the vector $\overrightarrow{r^i l^i}$ onto the direction vector $\mathbf{v}$, and the projection coefficient is $t$, where: $t = \frac{\overrightarrow{l^i r^i} \cdot \mathbf{v}}{\mathbf{v} \cdot \mathbf{v}} = \frac{\sum_{j=1}^{J} (r_j^i - l_j^i) \cdot 1}{\sum_{j=1}^{J} 1^2} = \frac{\sum_{j=1}^{J} (r_j^i - l_j^i)}{\sum_{j=1}^{J} 1}$. Eq. (14) is the distance from $r^i$ to the line, which can be computed by the magnitude of the vector $\overrightarrow{r^i l^i} - t\mathbf{v}$.

Comments 2. Specifically, the authors can give more details about Algorithm 1, such as the number of parents involved in the tournament selection, the mutation rate, and how the mutation steps are handled if the offspring exceed the predefined parameter range.

Response. Algorithm 1 uses Monte Carlo simulation to generate $m$ points located on hyperplane $\mathcal{H}$ in each round, and then searches for the nearest Voronoi site $p_i$ for these $m$ points. The genetic algorithm is applied to optimize the objective function in Eq. (12). In genetic algorithm, we randomly select three individuals and then choose the optimal individual from them. The intersection rate $\alpha$ is uniformly distributed within the range of (0,1). The mutation method is to randomly perturb a certain point, and the range of the mutation is controlled by the parameter mutation_std. In this article, mutation_std is 0.05. When a newly generated point exceeds the valid range [0,1] in any dimension, the algorithm calculates a scaling factor to project the point onto the nearest boundary while preserving its original direction, provided that the directional variation component in that dimension is non-zero. This ensures that the mutated points are within a reasonable range of values.

Notes: All the tables can be found at https://anonymous.4open.science/r/icml_rebuttal-E75A/rebuttal.pdf.

Response to Claims and Evidence:

In the context of this paper, a special metric, namely Maximum Spread (MS), can play a role similar to the standard deviation to better evaluate the solution's robustness [A1] below. We also carried out experiments to show the effectiveness of PHN-HVVS in terms of MS.

Specifically, as done in (Hoang et al., 2023), the Hyper-Volume (HV) metric can simultaneously evaluate the convergence and diversity of a set of solutions, which refer to how closely the solutions approximate the true Pareto front (PF), and how well the solutions are spread across the entire PF, respectively. For the MS metric, a larger value indicates a wider coverage of the entire PF, reflecting superior diversity in the solution set. Please refer to [A1] for the explanation of MS.

Table 2 presents the values of MS across 6 problems. Overall, PHN-HVVS has the best performance and can better cover the entire PF. Table 3 presents the values of MS across toy examples. On convex PFs, our method achieves the largest MS.

[A1] Comparison of multiobjective evolutionary algorithms: Empirical results, EVCO'00

Response to 'how do you sample point set s from it?':

Algorithm 1 applies a genetic algorithm to optimize the objective function in Eq. (12). The final partition approach yields n Voronoi grids and stores the Voronoi site P and simulation point set S in each grid. At this point, each s has a label for which partition it belongs to. Algorithm 2 directly utilizes the Voronoi grid structure generated by Algorithm 1, and then performs fast sampling in each round of these grids (simulated point sets with the same label) without the need for recalculation.

Response to 'baselines for comparison':

We conducted extended experiments on the Jura and SARCOS datasets, comparing our proposed method against multiple naive sampling techniques, including: Uniform random sampling, Latin hypercube sampling, Polar coordinate sampling, Dirichlet distribution sampling, K-means clustering-based representative selection. As shown in Table 4, the proposed approach outperforms other strategies.

Response to FL Part:

We appreciated your suggestions, which help enhance the paper quality. Roughly, some parameters are assumed to be known in FL, and are estimated by Pareto front learning (PFL) schemes. Optimization process is further taken in these existing FL algorithms for different purposes. The preciseness of these parameters directly affects the performance of these FL algorithms where the PFL scheme used previously is the one (i.e., PHN-LS) in (Navon et al., 2020). However, it can also be the scheme (i.e., PHN-HVVS) proposed in this paper. With PHN-HVVS, all these previous FL algorithms achieve a better performance since the PF is better covered.

Specifically, in FL, the $n$ clients correspond to $n$ learning tasks. The heterogeneity of data across clients entails evaluating the complementarity of data between clients. While PFL schemes are applied, there exists an optimal preference vector $p_{i}^{\ast}=${ $p_{i,1}^{\ast}, \cdots, p_{i,n}^{\ast}$} such that the model performance of $i$ can be maximized. $p_{i,j}^{\ast}$ can be used to evaluate the weight of the client $j$'s data to the model performance of client $i$. These weights define a benefit graph $G_{b}$, where there is a direct edge from $j$ to $i$ if and only if $p_{i,j}^{\ast}>0$. Several works assume that the values of $p_{1}^{\ast}, \cdots, p_{n}^{\ast}$ are known, and study how to determine a subgraph $G_{u}$ of $G_{b}$ that satisfies some desired properties to form stable coalitions, avoid conflicts of interests, or eliminate free riders. In $G_{u}$, there is a direct edge from $j$ to $i$ if $j$ will make a contribution to $i$ in the actual FL training process, and it defines the collaborative FL network.

Examples of questions studied in the previous FL works are introduced in Table 5. Definitions of $G_{b}$ and $G_{u}$ can be found in (Tan et al., 2024; Chen et al., 2024). The way of generating $p_{i}^{\ast}$ is given in Section 5.3 of this paper. In the final version , we will better clarify the FL part, including Section 2.

Response to small comments:

We will rewrite the content in the beginning of Section 3 as you suggested. Eq. (1) presents the standard optimization process. We will better state Eq. (2). The hypernetwork is explicitly described in Section 4 of (Navon et al., 2020); we will add a rephrasing explanation in the appendix. Simulation points are introduced in Algorithm 1 of the paper.

A good ideal partition should be equivalent to Eq. (8) and f=1 in the Eq. (12) where the number of points fall in each grid is equal [A4].

[A4] De Berg M. Computational geometry: algorithms and applications

We will update the paper according to your suggestions above.

Notes: All the tables and figures can be found at https://anonymous.4open.science/r/icml_rebuttal-E75A/rebuttal.pdf.

Response to W1 & W2: We appreciated your insightful questions, which ever motivated us to develop the solution of this paper.

Specifically, there is a mapping of rays to solutions. We aim to find a set of Pareto-optimal solutions that can well cover the entire Pareto front (PF). We fully agree on that the Riesz s-energy based iterative optimization method in [1] can generate uniformly distributed points or rays in high-dimensional spaces. However, a set of uniformly distributed rays does not necessarily lead to a set of uniformly distributed solutions, as shown in [A1] below and Figure 1. When rays are generated in advance, using such fixed rays generated by [1] may fail to cover some parts of the PF.

Thus, we propose to dynamically sample the preference vector during the optimization process, so that the hypernetwork technology can continuously explore the uncovered areas of the target space. The method proposed in this paper does not directly generate a globally uniform point set, but instead performs preference vector re-sampling based on local units of Voronoi grids generated by Alg. 1. Even with a fixed set of points generated by [1], generating preference vectors within the cell formed by these points still faces challenges, such as the geometric complexity problem in high-dimensional space [A2].

Above, we explain why dynamic sampling of rays is used. In the ray sampling process, optimization is also taken in Alg. 1 and 2 to avoid recalculation, like your suggestion. Specifically, Alg. 1 uses Monte Carlo simulation to generate m simulation points S located on hyperplane $\mathcal{H}$ at each iteration: $\mathcal{H} =${$(x_1, \ldots, x_J) \in \mathbb{R}^J \mid x_1 + \ldots + x_J = 1$ } and then searches for the nearest Voronoi site $p_i \in P =$ {$p_1, p_2, \ldots, p_n$} for these m points. The genetic algorithm is used to find the partition method with the maximum objective function, ultimately obtaining n Voronoi grids (while storing the simulation point sets of each grid). Alg. 2 directly utilizes the Voronoi grid structure generated by Alg. 1 and performs fast sampling directly in each round of these grids (simulation point sets) without the need for recalculation.

[A1] Multi-objective deep learning with adaptive reference vectors, NeurIPS'22

[A2] An optimal convex hull algorithm in any fixed dimension, DCG'93

Response to W3：We have added experiments on the DTLZ1 benchmark problem [A3]: we measured the results for 4, 5, and 6 objectives, respectively, where the reference points were set as (2,..., 2). It can be seen from Table 1 that our method achieves the best result.

[A3] Deb et al. Scalable multi-objective optimization test problems

Response to W4：In high-dimensional space, HV can be effectively approximated [A4], and there is a standard indicators .hv in Python's Pymoo library used extensively for compute HV. For the error of HV, when J>3, the module in the library uses Monte Carlo method to sample about 10000 samples to estimate the HV value. The error rate decreases with the square root of the sample size (i.e. $\frac{1}{\sqrt{N}}$), and the actual error can be controlled within the range of 1% to 5%.

In this paper, the value of this HV is only computed once and used for the final evaluation of algorithm performance. We do not calculate the specific value of HV every round, but instead use gradient descent method to obtain the $\phi$ that minimize Eq. (13). The HV gradient computation of this paper follows (Hoang et al., 2023,Wang et al., 2017, Emmerich & Deutz, 2014).

[A4] HypE: An algorithm for fast hypervolume-based many-objective optimization, EVCO'11

Response to W5: To address your concern, we will better clarify in the final version that this paper focuses on the emerging paradigm of Pareto Front Learning (PFL). Compared with traditional MOEAs, PFL has its own challenges to be addressed specially.

Specifically, traditional MOEAs rely on the diversity of evolutionary population to search PF. Variants of MOEA/D and NSGA-III can address convex problems by adopting adaptive reference vectors. Differently, PFL typically uses a hypernetwork (HN) to approximate the PF. Existing PFL methods employ gradient optimization to maximize HV by approximating gradients with HV contributions. However, as shown in (Zhang et al., 2023), convex PF boundary solutions suffer weight decay: intermediate solutions have larger HV gradients, causing preferential fitting of central regions. In traditional MOO, such weight decay does not need to be addressed, and MOEAs directly search boundary solutions through population diversity maintenance, without gradient reliance in PFL.

Response to W6: We have optimized the visualization; please see Figure 2 in the link.

In the final version of this paper, we will better clarify the above contents.