STIMULUS: Achieving Fast Convergence and Low Sample Complexity in Stochastic Multi-Objective Learning

2. The Merit Functions for Strongly-Convex Objectives: In this paper, the merit function $\sum _ {s \in [S]} \lambda _ t^{s} [ f _ s(\mathbf{x} _ t) - f _ s(\mathbf{x} _ *) ]$ is used for strongly convex objective functions. This merit functions measures the "pareto optimality" defined in Definition 1.

Also, recall from Defintions 1 and 2, Pareto optimality and Pareto stationarity are defined as follows:

3. Pareto Optimality: A solution $\mathbf{x}$ is Pareto-optimal if there is no other solution that is better in all objectives. Weak Pareto optimality relaxes this by not requiring improvement in all objectives simultaneously.

4. Pareto Stationarity: A solution $\mathbf{x}$ is Pareto-stationary if no common descent direction $\mathbf{d}$ exists such that $\nabla f_s(\mathbf{x})^{\top} \mathbf{d} <0$, $\forall s$.

It has been shown in [R1] that Pareto stationarity implies weak Pareto optimality if all objectives are convex. Further, Pareto stationarity implies Pareto optimality if all objectives are strongly convex. The relationships between the merit functions and the basic definitions of Pareto optimaltiy and Pareto stationarity are as follows:

• Relationship between $\|\sum _ {s \in [S]}\lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)\|^2$ and Pareto stationarity: From the quantity $\|\sum _ {s \in [S]}\lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)\|^2$, it is clear that if $\|\sum _ {s \in [S]}\lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)\|^2 \leq \epsilon$ at $\mathbf{x}$ for some small $\epsilon >0$, each objective function's gradient norm $\|\nabla f_s(\mathbf{x})\|$ is also small, which implies that $\mathbf{x}$ is a (near) Pareto stationary point. Thus, the merit function $\|\sum _ {s \in [S]}\lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)\|^2$ can be used as a convergence metric.

• Relationship between $\sum _ {s \in [S]} \lambda _ t^{s} [ f _ s(\mathbf{x} _ t) - f _ s(\mathbf{x} _ *) ]$ and Pareto optimality under strong convexity: To see their connection, note that from strong convexity, we have $f _ s(\mathbf{x} _ t) \geq f _ s(\mathbf{x} _ *) + \nabla f _ s^{\top}(\mathbf{x} _ *)(\mathbf{x} _ t-\mathbf{x} _ *) +\frac{\mu}{2}||\mathbf{x} _ t-\mathbf{x} _ *||^2$ for some $\mu>0$. Thus, for any $\lambda _ t^s>0$, $\forall s \in [S]$ with $\sum _ {s=1}^{S} \lambda _ t^s =1$, we have

  $\sum _ {s\in[S]} \lambda _ t^s[f _ s(\mathbf{x} _ t) - f _ s(\mathbf{x} _ *)]$ $\geq \sum _ {s \in [S]} \lambda _ t^s \nabla f _ s^{\top}(\mathbf{x} _ *)(\mathbf{x} _ t-\mathbf{x} _ *) + \frac{\mu}{2}||\mathbf{x} _ t-\mathbf{x} _ *||^2$ $= \sum _ {s \in [S]} \lambda _ t^s \nabla f _ s^{\top} \mathbf{d} + \frac{\mu}{2}||\mathbf{x} _ t-\mathbf{x} _ *||^2$,

  where we define $\mathbf{d} \triangleq \mathbf{x} _ t-\mathbf{x} _ *$ in the last equality for convenience. Since $\mathbf{x} _ *$ is Pareto-stationary and all objective functions are strongly convex, it follows that $\mathbf{x} _ *$ is also Pareto-optimal. Thus, there must exist at least one $\tilde{s} \in [S]$ such that $\nabla f _ {\tilde{s}}^{\top}(\mathbf{x} _ *) \mathbf{d} > 0$. Now, we show there always exist $\lambda _ t^s$, $\forall s\in [S]$ to make the merit function non-negative: For $\tilde{s}$, we choose a $\lambda _ t^{\tilde{s}}$-value that is close to 1. For all other $s \ne \tilde{s}$, we choose a small $\lambda _ t^s$-value that is close to 0. Then, by pushing the $\lambda _ t^{\tilde{s}}$-value toward 1 and other $\lambda _ t^s$-values towards 0 (whiling maintaining $\sum _ {s=1}^{S} \lambda _ t^s =1$), we can always make $\sum _ {s\in[S]} \lambda _ t^s[f _ s(\mathbf{x} _ t) - f _ s(\mathbf{x} _ *)]$ non-negative.

We hope the explanations above help the reviewer see the relationship between the merit functions and the Pareto optimality/stationarity concepts.

[R1] Hiroaki Mukai. Algorithms for multicriterion optimization, IEEE Transactions on Automatic Control, 25(2): 177-186, 1980.

Your Comment 3: In proof of Lemma 1, the authors use Lemma 1 of Feng et al. (2018), yet it is hard to see how result in Feng et al. (2018) can be used here, since the problem setting in Feng et al. (2018) is single objective optimization.

Our Response: Thank you for your observation regarding the application of Lemma 1 from Feng et al. (2018) in our proof of Lemma 1. We appreciate the opportunity to clarify this aspect of our methodology. Although the problem setting in [Feng et al. (2018)] is focused on single-objective optimization, the underlying principles of their Lemma 1 can be appropriately applied to our multi-objective optimization (MOO) context. This is because the term $\mathbb{E}_t[\|\nabla f_s(\mathbf{x}_t) - \mathbf{u}_t^s\|]$ in Lemma 1 only involes one objective function $f_s(\mathbf{x}$) can be treated independently as a single-objective problem.

Your Comment 4: The choice of stepsize in Theorems is unclear. For example, how does one go from equation (13) to (14) (in proof provided in appendix) by the choice of step size?

Our Response: In Eq.(13), we have $f_s(\mathbf{x} _ {t+1}) \leq f _ s(\mathbf{x} _ t) + \frac{\eta}{2} || \nabla f _ s(\mathbf{x} _ t) - \mathbf{u} _ t^s ||^2 - \eta \left( \frac{1}{2}- \frac{1}{2}L \eta \right) || \mathbf{d} _ t ||^2$. As discussed in our paper, by setting $\left( \frac{1}{2} - \frac{1}{2} \eta \right) \geq \frac{1}{4}$, that is, $\eta \leq \frac{1}{2}$. This ensures that the term associated with $|| \mathbf{d} _ t ||^2$in the inequality is negative, which implies a descent in the objective value of $f_s(\cdot)$. Thus, we have $f _ s(\mathbf{x} _ {t+1}) \leq f _ s(\mathbf{x} _ t) + \frac{\eta}{2} || \nabla f _ s(\mathbf{x} _ t) - \mathbf{u} _ t^s ||^2 -\frac{\eta}{4} || \mathbf{d} _ t ||^2$ as shown in our Eq.(14). We we will include more detailed explanations and justifications for the choice of step size in the final version of our paper.

Your Comment 5: Minor comments: 1. $\mathcal{A}$ in equation (2) is not defined before using.2.Using index $s$ in equation (3) seems not necessary.

Our Response: Thanks for catching these issues. We have fixed them accordingly in the revision of this paper.

Your Comment 6: Can the authors explain the relationship between the merit functions used in Theorems 1-6, and the definitions of Pareto stationarity/optimality?

Our Response: Thanks for your questions. By "merit function," we assume you meant the convergence metrics used in Theorems 1-6. In the following, we will explain how these merit functions relate to the concepts of Pareto stationarity and Pareto optimality in multi-objective optimization (MOO). Recall that we have used the following merit functions in different problem settings:

1. The Merit Functions for Nonconvex Objectives: In this paper, the merit function $\|\sum _ {s \in [S]}\lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)\|^2$ is used for non-convex objective functions. This merit function meansurs the "Pareto stationarity" defined in Definition 2.

Your Comment 1: The definition of Pareto optimality and Pareto stationarity does not seem to align with the metrics used in the convergence results. For example, while the authors claim the convergence to a Pareto stationary point by STIMULUS due to the result obtained in Theorem 1, it is unclear why the merit function used in this result can measure the Pareto stationarity of iterates.

Our response: Thanks for your comments. The reviewer is correct that the definitions of Pareto optimality and Pareto stationarity in Defintion 1 and Defintion 2, respectively, are different from the convergence metric we use in Theorem 1, which follows from Definition 3. Here, we want to clarify their connections as follows:

The definitions of Pareto optimality and Pareto stationarity in Definition 1 and Definition 2, respectively, are their original and most general definitions. However, these definitions are based on the notion of "existence," which is not convenient and amenable for stopping criteria in algorithm design. Thus, we need equivalent definitions of Pareto optimality and Pareto stationarity, particularly when the problems are endowed with additional structural properties (differentiable objectives in this paper), which are more amenable for checking Pareto optimality and Pareto stationarity. Such equivalent equivalent conditions are stated in Definition 3, which is used as the convergence metric in Theorem 1.

As an analogy, Definition 3 is similar to the conventional definition of optimality in general optimization, where the most basic optimality concept is not useful for algorithm design and analysis in practice. Thus, when the problem has special structural properties, e.g., convexity and constraint qualifications, the famous KKT condition, which is both necessary and sufficient for optimality in this case, will be used to check whether we have achieved an optimal solution.

Your Comment 2: Due to the problem mentioned above, it is unclear whether the comparison for theoretical results provided in Table 1 is a fair one.

Our Response: Thank you for your comment regarding the fairness of our theoretical comparisons presented in Table 1. We understand your concern and would like to clarify the basis on which these comparisons are made, emphasizing the consistency of our metrics with those used in other referenced works.

1. Consistency with MGD and SMGD Metrics: In our comparison, we use the same the metrics as in MGD (Fliege et al., 2019) Theorem 3.1 and Theorem 4.1, and SMGD (Yang et al., 2022) Theorem 1, thus ensuring a fair comparison in terms of theoretical analysis.

2. Alignment with MoCo and CR-MOGM Metrics: Similarly, in MoCo (Fernando et al., 2023) Theorems 1-3 and CR-MOGM (Zhou et al., 2022b) Theorems 2 and 3, the metric $||\sum _ {s \in [S]} \lambda _ t^* \nabla F\left(\mathbf{x} _ t\right) ||^2$ is employed. In contrast, our metric is slightly different and we use $||\sum _ {s \in [S]}\lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)||^2$, which is not only compatible with (Fernando et al., 2023) but also avoids the limitation of making some subtle technical assumptions as in (Fernando et al., 2023). Due to this reason, the proposed metric in Definition 3 is also a novelty of this paper. Specifically, our metric satisfies $||\sum _ {s \in [S]} \lambda _ {t}^* \nabla F\left(\mathbf{x} _ t\right)||^2 \leq ||\mathbf{d} _ t||^2 = ||\sum _ {s \in [S]} \lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)||^2$, meaning that our metric is an even tighter convergence metric and implicitly showing the convergence of $\{ \lambda_t \} \rightarrow \lambda^*$. Thus, a convergence rate measured by our metric will also hold when measured by the metric in (Fernando et al., 2023), thus further substantiating the fairness of our comparison.

Your Comment 1: The comparison with existing algorithms in Table 1 may not be fair because they are not focused on the same settings. The setting analyzed in this paper is the finite-sum setting which is more restrictive.

Our Response: Thank you for your comments. However, it is inaccurate to state that "the setting analyzied in this paper is the finite-sum setting.". Thus, the comparison in Table 1 remains fair and justifiable for the following reasons:

1. The comparisons between STIMULUS/STIMULUS-M and MGD are fair: Both STIMULUS/STIMULUS-M involves computation of full gradients, which is typically feasible in the fnite-sum setting. To see this, note that the sample complexity results in MGD and STIMULUS/STIMULUS-M in Table 1 all depend on $n$, which is the size of the dataset.

2. The comparisons between STIMULUS$^+$/STIMULUS-M$^+$ and SMGD/MOCO/CR-MOGM are fair: All these methods, including our STIMULUS$^+$/STIMULUS-M$^+$ do not require full gradient evaluation. Thus, our proposed STIMULUS$^+$/STIMULUS-M$^+$ methods are also applicable to the same expectation minimization MOO problems (batch size is chosen as $|\mathcal{N} _ s| = \min \\{ c _ \gamma \sigma^2\gamma _ {t}^{-1}, c _ \epsilon \sigma^2 \epsilon^{-1} \\}$. Specifically, in STIMULUS$^+$/STIMULUS-M$^+$, we propose a adaptive batch approach, which allows STIMULUS$^+$/STIMULUS-M$^+$ to work with expectation minimization MOO problems as those studied by SMGD/MOCO/CR-MOGM.

Your Comment 2: The benefit of the proposed method over linear scalarization in MOO is unclear. This is because linear scalarization can also achieve convergence to Pareto stationary points. Therefore, only providing convergence to Pareto stationary points is not enough to show the benefit of the proposed method over the simplest linear scalarization. More discussion should be provided.

Our Response: It is worth pointing out that linear scalarization methods are limited to identifying the convex hull of the Pareto front ([R5,R6]), whereas (stochastic) multi-gradient methods, including our proposed algorithms, have the capability to uncover the Pareto front. Essentially, this represents a distinct advantage for all multi-gradient algorithms over linear scalarization methods. This paper contributes by demonstrating that variance reduction can significantly enhance the complexity of stochastic multi-gradient methods by improved convergence.

Thank you for your insightful comment regarding the comparison of our proposed method with linear scalarization in MOO. We agree with the reviewer that linear scalarization is a commonly used and relatively straightforward approach in MOO. However, working with vector-valued objectives in MOO offers unique benefits that do not exist in linear scalarization:

Specifically, our method is built upon the multi-gradient descent approach (MGDA), which dynamically calculates the weights for each task based on the gradient information in each iteration. Compared to the linear scalarization method that uses fixed or pre-defined weights for each objective, the dynamic weighting approach adapts much better to the landscapes of different MOO problems, which enables a much more flexible exploration on the Pareto front.

[R5] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004.

[R6] M. Ehrgott. Multicriteria optimization, volume 491. Springer Science & Business Media, 2005).

Your Comment 1: The presentation of adaptive-batching versions is a bit ambiguous. I am not sure whether the adaptive batch is applied to the periodic full gradient or to each step. Adding more background knowledge on adaptive batch technique or a diagram for STIMULUS would be helpful. In addition, it is unclear how to decide the batch size in experiments.

Our Response: Thank you for your comments regarding the presentation of the adaptive-batching versions in our algorithms, STIMULUS+/STIMULUS-M+. We would like to clarify our adaptive batch size approach:

1. To periodic full gradient or to each step: The adaptive batch size is applied to replace the periodic full gradient. Specifically, we modify the gradient estimators in Line 5 Algorithm 1 in the t-th iteration that satisfies $\mathrm{mod}(t, q) = 0$ as follows (i.e., every $q$ steps): $\mathbf{u} _ t^s = \frac{1}{|\mathcal{N} _ s|} \sum _ {j\in \mathcal{N} _ s}\nabla f _ s(\mathbf{x} _ {t};\xi _ {sj} )$, $\forall s \in [S],$ where $\mathcal{N} _ s$ represents an $\epsilon$-adaptive batch sampled from the dataset uniformly at random. In the revision, we will provide more background knowledge on the adaptive batch technique as you suggested.

2. How to decide the batch size: We choose the batch size adaptive to $\epsilon$ as: $|\mathcal{N} _s| = \min \\{ c _ \gamma \sigma^2\gamma _{t}^{-1}, c _ \epsilon \sigma^2 \epsilon^{-1}, n \\}$, where we use $c _ \gamma \geq 8$, $c _ {\epsilon}\geq \eta$ for the non-convex case and use $c _ {\gamma}\geq \frac{8\mu}{\eta}, c _ {\epsilon}\geq \frac{\mu}{2}$ for the strongly-convex case. In our experiments, as shown in our paper, we choose constant $c _ {\gamma}=c _ {\epsilon}=c = 32$ and solution accuracy $\epsilon = 10^{−3}$.

Your Comment 2: Besides SMGD and MOCO, CR-MOGM (Zhou et al., 2022b) should also be considered in experiments as a SOTA method.

Our Response: Thank you for your suggestion to include CR-MOGM (Zhou et al., 2022b) in our experimental comparisons. We note that that CR-MOGM can be viewed as a momentum version of the SGD method tailored for solving MOO problems. Also, both MOCO and CR-MOGM utilize a similar approach in employing momentum-based SGD for MOO.

However, there are key distinctions between these two methods. More specifically, CR-MOGM can be viewed as a special case of the more general MOCO framework. By contrast, MOCO not only tackles the general MOO problem formulation, but also considers MOO problems with special structures, such as regularization and bilevel structures. Given the facts that i) MOCO is more recent and state-of-the-art and ii) The similarities in foundational technique between MOCO and CR-MOGM provide a reasonable basis to anticipate comparable experimental outcomes. In future work, we aim to conduct additional experiments specifically focusing on CR-MOGM to further explore and validate this hypothesis.

Your Comment 1: As far as I see, the theoretical analysis seems to be problematic. For example, Theorem 1 gives convergence rates on $\frac{1}{T} \sum _ {t=0}^{T-1}\left||d _ t\right||^2$. However, the terms are just common descent directions built based on stochastic gradients (which is similar to the stochastic gradient in SGD). According to Definition 3 and the paragraph above, the quantity to our interest is $d=\lambda^{\top} \nabla F(\mathbf{x})$. note that $F(\mathbf{x})$ are the true objective functions, instead of the stochastic functions randomly sampled in the optimization process. Therefore, Theorem 1 does not give convergence rates on the $\epsilon$-stationarity, and the convergence in terms of does not show the real behavior of the algorithm. Furthermore, as far as I see from the proof of Theorem 1, one can get convergence rates of if only, even if is very small. In this case, one can choose very to derive the same convergence rates for , but with much less sample complexity. Can we derive convergence rates in terms of $d _ t=\lambda^{\top} \nabla F\left(\mathbf{x} _ t\right)$ ? Indeed, the convergence of $\lambda^{\top} \nabla F\left(\mathbf{x} _ t\right)$ reflects the convergence behavior of the algorithm.

Our Response: Thank you for your detailed observations regarding the theoretical analysis in our paper, particularly concerning the convergence rates and the interpretation of $||\mathbf{d} _ t||^2$in Theorem 1. Your insights have led us to reconsider and refine our approach:

In our initial submission, we derived the convergence rate for $||\mathbf{d} _ t||^2=||\sum _ {s \in [S]}\lambda _ {t}^{s} \mathbf{u} _ {t}^s||^2$, where $\mathbf{u} _ {t}^s$ represents the gradient-estimation-based moving direction with VR-adjustment, which can be seen in Line 4-11 in Algorithm 1.

We understand your concern that this might not fully capture the convergence behavior in terms of the true gradient. Based on your feedback, we have revised our approach to derive the convergence rate for $||\sum _ {s \in [S]}\lambda _ {t}^{s} \nabla F\left(\mathbf{x} _ t\right)||^2$, which more accurately reflects the convergence behavior in terms of the true objectives. We have updated our proofs to reflect this new metric, ensuring that our theoretical results align more closely with the actual behavior of the algorithm in converging to $\epsilon$-stationarity.

Your Comment 2:
Definition 3 implicitly assumes that all $f _ s$ should have the same minimizer, which is a very strong assumption. In multi-objective optimization, it is very unlikely that we have the same minimizer for all tasks. Then, the convergence rates for strongly convex problems are restrictive.

Our Response: Thanks for your comments. It appears that there is some misunderstanding on the notation $\mathbf{x} _ *$, which represnts a Pareto-stationary point, not a common minimizer for all $f _ s(\cdot)$. In the strongly convex setting, a Pareto-stationary solution further implies Pareto-optimal solution [R4]. More specifically, a solution $\mathbf{x} _ *$ is considered Pareto-optimal if there is no other feasible solution that would improve one objective without causing at least one other objective to worsen. Essentially, a Pareto-optimal solution represents a point of equilibrium where no objective can be improved without compromising others.

Also, we want to clarify Definition 3 in our initial submission by restating it as follows (with further elaborations):

Definition 3 ($\epsilon$-Pareto stationarity). In MOO, a point $\mathbf{x} _ t$ is $\epsilon$-Pareto-stationary if for any $\epsilon>0$, there exists a set $\{ \lambda _ t^s>0, \forall s \in [S]: \sum _ {s=1}^{S} \lambda _ t^s =1\}$, such that the following conditions hold: 1) $\mathbb{E}||\sum _ {s\in [S]}\lambda _ t^s\nabla f _ s(\mathbf{x} _ t)||^2 \leq \epsilon$ for non-convex MOO problems; or 2) $\mathbb{E}[\sum _ {s \in [S]} \lambda _ t^s [ f _ s(\mathbf{x} _ t) - f _ s(\mathbf{x} _ *) ] \in [0,\epsilon]$ for strongly-convex MOO problems.

Your Comment 1: Eq. (23) sums both sides of Eq. (22) weighted with $\lambda_t^s$ from $s \in S$. But why $\frac{1}{2 \delta}\left|\nabla f_s\left(x_t\right)-u_t^s\right|^2$ is not weighted with $\lambda_t^s$ ?

Our Response: Thanks for your question. To see this, note that $\sum_{s \in [S]} \lambda_t^{s}=1$ and $\|\nabla f_s(\mathbf{x}_{\left(n_t-1\right) q}) - \mathbf{u}_{\left(n_t-1\right) q}^s \|^2 =0$.

It then follows that:

$\sum_{s \in [S]} \lambda_t^{s} || \nabla f_s(\mathbf{x}_t)-\mathbf{u}_t^s||^2$

$\leq \frac{L^2}{|\mathcal{A}|} \sum _{s \in [S]} \lambda _t^{s}\sum _{i=\left(n _t-1\right) q}^t ||\mathbf{x} _{i+1}-\mathbf{x} _{i}||^2 + \sum _{s \in [S]} \lambda _t^{s}||\nabla f _s(\mathbf{x} _{\left(n _t-1\right) q}) - \mathbf{u} _{\left(n _t-1\right) q}^s ||^2$

$=\frac{L^2}{|\mathcal{A}|} \sum _{i=\left(n _t-1\right) q}^t ||\mathbf{x} _{i+1}-\mathbf{x} _{i}||^2 + \sum _{s \in [S]} \lambda _t^{s}||\nabla f _s(\mathbf{x} _{\left(n_t-1\right) q}) - \mathbf{u} _{\left(n _t-1\right) q}^s ||^2$

$= \frac{L^2}{|\mathcal{A}|} \sum_{i=\left(n_t-1\right) q}^t ||\mathbf{x} _{i+1}-\mathbf{x} _{i}||^2.$

Thus, we conclude our results outlined in Eq. (23). Further proof details and expanded explanations can be found in the updated version of our paper.

Your Comment 2: Why does it hold that $\left|\nabla f_s\left(x_t\right)-u_t^s\right|^2=\sum_{\ldots}\left|x_{i+1}-x_i\right|^2+\left|\nabla f_s\left(x_{\left(n_t-1\right) q}\right)-u_{\left(n_t-1\right) q}^s\right|^2$ in Eq.(23）

Our Response: Thanks for your question. There appears to be some misunderstandings. We want to clarify that the equality relationship $\left|\nabla f_s\left(x_t\right)-u_t^s\right|^2=\sum_{\ldots}\left|x_{i+1}-x_i\right|^2+\left|\nabla f_s\left(x_{\left(n_t-1\right) q}\right)-u_{\left(n_t-1\right) q}^s\right|^2$ mentioned by the reviewer is never used in Eq. (23).

Rather, in the latest version of our paper as shown in Eq. (25), we have used the following inequality relationship: $\left||\nabla f _s\left(\mathbf{x} _t\right)-\mathbf{u} _t^s\right||^2 \leq \frac{L^2}{|\mathcal{A}|} \sum _{i=\left(n _t-1\right) q}^t\left||\mathbf{x} _{i+1}-\mathbf{x} _i\right||^2+||\nabla f_s\left(\mathbf{x} _{\left(n_t-1\right) q}\right)-\mathbf{u} _{\left(n_t-1\right) q}^s||^2$. This inequality is stated and proved in Lemma 1 (cf. Eq. (8)).