Joint Gradient Balancing for Data Ordering in Finite-Sum Multi-Objective Optimization

We would like to thank you for your recognition of our work as well as your valuable suggestions. Below we address your concerns point by point with detailed explanation and revision:

W1. line 65 typo "oerdering"

W6. typo at the end of line 19 of Algorithm 1

W7. typo in Assumption 3.3

Thank you for pointing out these typos. We have fixed them and also thoroughly checked the other parts of the whole submission.

W2. for better presentation, the balancing routine could be written as an algorithm instead of a definition

Thank you for your suggestion. In section 3.2 of this revised version, we added a new Algorithm 2 for the balancing routine $`Balancing`(s, g_{m,k,t})$. It uses a greedy procedure that works well in practice. Specifically, we compare the vector norm of $\|s+ g_{m,k,t}\|$ and $\| s-g_{m,k,t}\|$, where $s+ g_{m,k,t}$ corresponds to putting the gradient vector $g_{m,k,t}$ at the beginning, and $s- g_{m,k,t}$ corresponds to putting the gradient vector $g_{m,k,t}$ at the end. Then since the online vector balancing problem in Definition 3.1 tries to minimize the norm of vector sums, we choose the sample order that can lead to the smallest norm, as is indicated by the value of $\epsilon_{m,k,t}$: $\epsilon_{m,k,t}=1$ means putting the gradient vector $g_{m,k,t}$ at the beginning, while $\epsilon_{m,k,t}=-1$ means putting the gradient vector $g_{m,k,t}$ at the end.

W3. The authors need to better explain the balancing routine

Thank you for your suggestion. We have added more explanation on the motivation of using the balancing routine in line 64-65 in the introduction, as is highlighted in blue, and more details can be found in highlighted parts in Section 3.2. Briefly speaking, solving the online vector balancing problem allows us to control the maximum norm of model update sums within one epoch, ($A$ in Assumption 3.7 and Proposition 3.8), which is related to the convergence rate as is shown in Theorem 3.9. Then by solving the online vector balancing problem, we try to make maximum norm of parameter updates in one epoch smaller, which then leads to faster convergence rate. Similar intuition can also be found in the paper of GraB (Grab: Finding provably better data permutations than random reshuffling. NeurIPS 2022). Please also refer to our responses to W2 above for detailed procedure of the balancing routine.

W4. The algorithm is complicated, the authors should provide with more motivation, remarks, and discussion about the design of algorithm.

Thank you for your suggestion. In Section 3.2 of this revised version, we added more explanations on the design of the proposed JoGBa. Specifically, JoGBa follows the same procedure as existing gradient-based multi-objective optimization algorithms. The difference starts at step 8 where the sample is selected by an order (which can be different for different objectives). Steps 11-16 then find the optimal order of samples based on the online vector balancing problem. Please also refer to our responses to W2 for detailed procedure of the balancing routine and responses to W3 for the motivation of gradient balancing.

W5. Please provide a detailed analysis of the time and space complexity of solving the balancing problem, or to compare its complexity to existing methods.

W12. The authors need to discuss about the computation cost for the balance problem in the numerical section to make a fair comparison.

The newly added Algorithm 2 (that is used to solve the online vector balancing problem) only has a time complexity of $O(d)$ (computing the sum, difference and the vector norm of two $d$-dimensional vectors), where $d$ is the dimensionality of the model parameter $w$. This is much cheaper than each model training iteration (computing model gradient and model update, indexed by $k$ in Algorithm 1), which can take $O(d^2)$ time (from "The Fine-Grained Complexity of Gradient Computation for Training Large Language Models", NeurIPS 2024).

To further justify this, we have added a new Section 4.3 (highlighted in blue) to compare the time cost of each component on different multi-objective optimization problems. As is shown in the new Table 3, the per-iteration time cost of the balancing routine is almost negligible compared to the model update part.

W8. In the statement of Theorem 3.6 and 3.9, the definitions for $w$ and $\sigma$ are missing.

In the previous version, their definitions are buried in the main text. In this revised version, we state them more explicitly in Theorem 3.6: (highlighted in blue). Specifically, $w^{(1)}_t$ denotes the model parameter at training epoch $t$ and iteration 1, while $\sigma^2$ is defined as $\max_m \sigma^2_m$, where $\sigma^2_m$ is defined in Assumption 3.5 and is the gradient variance of the $m$-th objective.

Dear reviewer ntx7,

Thank you again for your valuable comments. As the discussion period is approaching its deadline, could you kindly take a moment to check our responses and let us know if we have adequately addressed your previous concerns? We would greatly appreciate any further feedback or comments you may have, and we are committed to addressing any outstanding issues that may have arisen.

Best,

Authors

We would like to first thank you for your recognition on the contribution of our work for proposing a novel approach to multi-objective optimization as well as our theoretical and empirical results. For your concerns on the presentation of this paper (including several unclear parts in the previous version) and the intuition of our method, here we answer them point by point with detailed explanation:

W1. Improved Convergence and Performance not clear: The authors claims that the method consistently outperforms existing data ordering strategies and dynamic weighting approaches. However, it seems the convergence rate for different algorithms are similar based on Theorem 3.6 and Theorem 3.7.

Q5-1. In Theorem 3.6 and Theorem 3.7, it seems the convergence rate of random sample ordering and the proposed algorithm are the same. Though in Theorem 3.6, the convergence rate is “=” while in Theorem 3.7, it is “<=”, one cannot conclude that the proposed algorithm converges faster than random sample ordering.

In this revised version, we use a larger step size $\alpha$ in Theorem 3.9. The resultant asymptotic convergence rate of JoGBa is $O(T^{-2/3})$, which is faster than that of random ordering (with convergence rate $O(T^{-1/2})$ in Theorem 3.6). This is also verified by the empirical results in Figures 2-4.

W2-1. Presentation and Clarity: Certain sections, especially the theoretical parts and Algorithm 1, could be more reader-friendly.

Thank you for your suggestion. In this revised version, we added clarifications (highlighted in blue) on the theoretical results and procedure of the proposed JoGBa. For the theoretical results, we clarified the definitions of several notations and added more detailed comparison on the convergence results of JoGBa (in Theorem 3.9) and random ordering (in Theorem 3.6). Please also refer to our responses to W1 for a detailed comparison on the theoretical advantages of JoGBa over random ordering. For the JoGBa procedure (Algorithm 1), we added clarifications on the symbol superscripts and subscripts to help better understand the proposed method. We also added a new Algorithm 2, which shows how to solve the online vector balancing problem as a subroutine in Algorithm 1.

W2-2. A more structured breakdown of steps and implications of theoretical results would enhance readability, making the technical details accessible to a broader audience.

Thank you for your suggestion. In Appendix C of this revised version, we added more detailed steps on the convergence analysis for both JoGBa and the random ordering baseline. Some implications from our theoretical results are discussed in Section 3.3, and we have highlighted them in blue for your easy reference.

W3-1. Intuitions not sufficient: the online vector balancing problem is the core of balancing the gradient, but the authors fail to give enough intuition

Q4. In Definition 3.1, the authors mentioned online vector balancing which is the core of how to balance the gradient. If possible, please try to explain more clearly about the intuition (e.g., online vector balancing problem tries to make the average of the centered gradient as close as to “zero”). This will make the reader have a smooth reading experience.

As suggested, in this revised version we added more motivation on why online vector balancing is useful for accelerating convergence at the beginning of Section 3.2 (highlighted in blue). The intuition is to control the maximum norm of parameter updates in one epoch ($A$ in Assumption 3.7 and Proposition 3.8), which is related to the convergence rate (Theorem 3.9). By solving the online vector balancing problem, we make the maximum norm of parameter updates in one epoch small, which then leads to faster convergence rate. Similar intuition can also be found in "Grab: Finding provably better data permutations than random reshuffling", NeurIPS 2022.

On how to perform gradient balancing, we added its procedure in the new Algorithm 2. Specifically, we use a simple greedy procedure to solve the online vector balancing problem in Definition 3.1. First, we compare the norms of $||s+ g_{m,k,t}||$ and $|| s-g_{m,k,t}||$, where $s+ g_{m,k,t}$ corresponds to putting the gradient vector $g_{m,k,t}$ at the beginning, and $s- g_{m,k,t}$ corresponds to putting the gradient vector $g_{m,k,t}$ at the end. Then since the online vector balancing problem in Definition 3.1 tries to minimize the norm of vector sums, we choose the sample order that leads to the smaller norm, as is indicated by the value of $\epsilon_{m,k,t}$: $\epsilon_{m,k,t}=1$ means putting the gradient vector $g_{m,k,t}$ at the beginning, while $\epsilon_{m,k,t}=-1$ means putting the gradient vector $g_{m,k,t}$ at the end.

We would like to first thank you for your recognition on the novelty and contribution of our work, including our theoretical and empirical results. For your concerns on the presentation of this paper, here we answer them point by point:

W1-1. how the JoGBa approach (Fig 1 Right) is different from data ordering on each objective separately (Fig 1 Middle). In other words, Figure might not be illustrative enough.

W1-2. a clearer description might help—for example, one or two sentences explaining how JoGBa differs from ordering data for each objective separately.

W1-3. From the current description in lines 176 to 178, "The sample ordering is then determined based on the results of solving the balancing problem (routine Balancing) with the gradient on each objective," it’s still unclear (at least for me) how this approach differs from the one illustrated in the middle of Figure 1.

To better show the differences across the three sample ordering approaches in Figure 1, we further provide the detailed procedures of the two approaches shown in Figures 1(a) and 1(b), along with their differences with JoGBa (Figure 1(c)) in Appendix B. Specifically, the key difference between JoGBa and the approach in Figure 1(b) is that JoGBa uses the same sum vector $s$ to order gradients from the different objectives, while the approach in Figure 1(b) uses different vectors $s_m$'s for each objective $m=1, \dots, M$. This is a key novelty of this work. By performing online vector balancing jointly on different objectives, we can obtain a tighter bound on the maximum norm of parameter updates $|| w^{(k)}_t - w^{(1)}_t ||$ (Proposition 3.8), while the upper bound for the approach in Figure 1(b) grows linearly with the number of objectives $M$ (Proposition 3.10). The tighter bound then leads to faster convergence in Theorem 3.9 (constant $A$ for JoGBa and $MA$ for the approach in Figure 1(b)). Empirical results are also provided in Figure 4 and Table 4, comparing the performance of JoGBa with ordering data for each objective separately. We can see that JoGBa outperforms all baselines that follow the approach in Figure 1(b), demonstrating the effectiveness of jointly balancing gradients from different objectives.

W2. Algorithm 1 contains numerous superscripts and subscripts, making it challenging to interpret (which is acceptable if it prioritizes rigor)

Thank you for your suggestion. We have added more descriptions on these superscripts and subscripts in Algorithm 1, highlighted in blue. In summary, there are three different indices: $t$ is for the epoch number, $m$ is for the objective, and $k$ is for the iteration number in each epoch.