Aligned Multi Objective Optimization
Authors: Yonathan Efroni
Ben Kretzu
Daniel Jiang
Jalaj Bhandari
Zheqing Zhu
Karen Ullrich
Venue: ICML 2025 poster (2025)
Keywords: Multi objective optimization
optimization
multi-task learning
Primary area: optimization
TL;DR: We develop gradient descent algorithms for solving optimization problems with multiple aligned objectives and providing provable improved performance guarantees of our adaptations.

Abstract: To date, the multi-objective optimization literature has mainly focused on conflicting objectives, studying the Pareto front, or requiring users to balance tradeoffs. Yet, in machine learning practice, there are many scenarios where such conflict does not take place. Recent findings from multi-task learning, reinforcement learning, and LLMs training show that diverse related tasks can enhance performance across objectives simultaneously. Despite this evidence, such phenomenon has not been examined from an optimization perspective. This leads to a lack of generic gradient-based methods that can scale to scenarios with a large number of related objectives.  To address this gap, we introduce the Aligned Multi-Objective Optimization framework, propose new algorithms for this setting, and provide theoretical guarantees of its superior performance compared to naive approaches.

Aligned Multi Objective Optimization
Yonathan Efroni'
Ben Kretzu 2 Daniel R. Jiang'
Jalaj Bhandari Zheqing Zhu'
Karen Ullrich'
Abstract
proved performance across all tasks has been observed in several settings (Lin and Zhang 2023 Lee et al.) [024]) suggesting that perhaps there may not always be significant trade-offs between objectives. Similar observations appear in meta-learning (Ravi and Larochelle| 2017 Finn et al.) 2017 Hospedales et al., (021)). where the goal is to learn representations that enable quick adaptation to new tasks with minimal additional training, as well as in reinforcement learning (Jaderberg al.
To date, the multi-objective optimization litera- ture has mainly focused on conflicting objectives, studying the Pareto front, or requiring users to balance tradeoff's Yet, in machine learning prac- tice, there many scenarios where such con- flict does not take place. Recent findings from multi-task learning, reinforcement learning, and LLMs training show that diverse related tasks can enhance performance across objectives simultane- ously. Despite this evidence, such phenomenon has not been examined from an optimization per- spective. This leads lack of generic gradient- based methods that can scale to scenarios with a large number of related objectives. To address this gap, we introduce the Aligned Multi-Objective Optimization framework, propose new algorithms for this setting, and provide theoretical guarantees of their superior performance compared naive approaches.
2016 Teh et al.) 2017: Veeriah et al., 2019 Dann et al. 2023 where practitioners use multiple reward functions to better specify the policy or its representation.
In this work, we explicitly study a setting where objectives are aligned, namely, that the different objectives share a common solution. This situation arises frequently in prac- tice. For example, when using reinforcement learning (RL) to augment large language models (LLMs) with reason- ing capabilities, there are often multiple options for the choice of reward model to use. Lightman et al.; (2023) and Uesato et al. (2022) consider both outcome and process- based rewards, and, recently [uuo et al. (2025); Team et al. (2025) discuss the use of accuracy, format rewards, length of response, and reward on math problems as additional reward functions. In training text-to-image models using
1. Introduction
In many real-world optimization problems, have access to multi-dimenssonal feedback rather than single scalar ob- jective. The multi-objective optimization (MOO) literature has largely focused on the setting where these objectives conffict with each other, which necessitates the Pareto domi- nance notion of optimality. closely related area of study is
RL. Lee et al. (2024) use four reward models (aesthetic quality, human preference, text-image alignment, and image sentiment) and show results where all rewards are increased. Although the method of et al. (2024) is designed for finding Pareto-optimal solutions (implying the existence of trade-offs), the numerical results suggest that the objectives may actually be aligned to good degree.
multi-task learning (Caruana 1997: Teh et al., 20117
Sener
and Koltun 2018 Yu et al. 2020; Lin et al.
202
Liu et al.
These observations are also related to more general phe- nomenon in RI. discussed by Dann et al. (002). where learning can be accelerated by exploiting several alternative reward specifications that all lead to the same optimal policy. This concept builds on prior work showing that the choice of reward function (e.g., dense versus sparse reward) can have dramatic effect on training time (Ng et al. 1999 Luo
2021 1
Navon et al.
2022
Zhou et al.
2022
Lin and Zhang
2023
Liu et a 2023a Chen et al.
2023
Achituve et al.
2024
He et al. 2024 Liu and Vicente 2024), where mul-
tiple tasks are learned jointly, typically with both shared and task-specific parameters. The hope is that the model can perform better on individual tasks by sharing common information across tasks. Indeed, the phenomenon of im-
et al. 2020 Waag et al./ 2019 Hu et al. 2020). A related idea in statistics is that when labeled data is sparse, practi- tioners can rely on closely-related proxy tasks to improve prediction accuracy (Bastani 202T).
"quaal contribution 'Meta Al Technion. Correspondence to: Yonathan Efroni <yonathanc @ mom..
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
To our knowledge, there no work that studies such a

---

Aligned Multi Objective Optimization
Algorithm
Asymptotic Convergence
method of (Liu et al. 202T CAGrad generalizes MGDA:
its main idea is to minimize notion of "conflict" between gradients from different tasks, while staying nearby the gradient of the average loss. Notably. CAGrad maintains convergence toward a minimum of the average loss. Another way to handle gradient conflicts is the Nash-MTL method of Navon et al. (0022). where the gradients are combined using a bargaining game. Very recently, Achituve al. (2024) introduced Bayesian approach for gradient aggregation by incorporating uncertainty in gradient dimensions. Other optimization techniques for MTL include tuning gradient magnitudes so that all tasks train at a similar rate (Chen et al. 2018 taking the geometric mean of task losses (Chennupati et al. 2019), and random weighting (Lin et al., 2021). On the meta learning front, the MAML algorithm (Fin et al.
CAMOO
0 (1 - pc/3)*
PAMOO
o (1 1x.//))*
Table 1: The main results introduced in this work. 3 is the smoothness parameter; both [rG and (L, are structural quantities introduced in Section I and Section These char- acterize notions of optimal curvature of weighted function and satisfy PL 2 PG.
framework from an optimization perspective. We ask the following question:
Can gradient descent rype of algorithms benefit from mulii-ojeective feedback when the objectives are aligned?
2019 aims to learn a useful representation such that the model can adapt to new tasks with only small number of training samples. Since fast adaptation is the primary goal in meta learning, MAML's loss calculation differs from those found in MTL.
Previous work in multitask learning had provided conver- gence guarantees for gradient descent-type algorithms for MOO (Sener and Koltun
2018 Yu et al. 2020; Liu et al.] Navon et al. 2022 He et al. 2024). However, since
2021
Few prior works provided provable convergence guarantees of the different existing multi-objective optimization meth- ods. Without additional assumption on the alignment of dif- ferent objectives, these guarantces quantified convergence to a point on the Pareto front. Unlike our work, there the convergence guarantees depended on worst-case structural quantities such as the maximal Lipschitz constant among
these consider general multi-objective framework, their al- gorithms converge with worst-case guarantees with no mean- ingful convergence improvement of MOO.
We provide a positive answer to the aforementioned ques- tion. We formally introduce the aligned multi-objective optimization (AMOO) framework. Subsequently, we de- sign new gradient descent-type algorithms and establish their provable improved convergence in the AMOO setting. These can be interpreted as parameter- algorithms to han- dle multi-objective feedback when objectives are aligned. Lastly, we conclude by providing empirical evidence of the improved convergence properties of the new algorithms.
all objectives (Liu et al., 2021 Navon et al.
2022
Zhou
et al. 2022 Chen et al.) [003] Liu and Vicente 2024 or the
maximal generalized smoothness (Zhang al. 2024).
The algorithms introduced in the following are similar to existing ones in that they construct a weighted loss to com- bine information from different sources of feedback. Unlike previous work, we focus on exploiting the prior knowl- edge that the objectives are aligned. We introduce new -eeeedden structural quantities that reflect how aligned multi-objective feedback can improve GD perfor- mance, improving convergence that depends on worst-case structural quantities, as in prior works.
2. Related Work
2.1. Gradient Weights in Multi-task & Meta Learning
Our work is closely related to optimization methods from the multi-task learning (MTL) and meta learning literature, particularly those that integrate weights into the task gra- dients or losses. The multiple gradient descent algorithm (MGDA) approach of Fliege and Svaiter (2000); Désidéri (2012); Sener and Koltun (2018); Zhang et al. 2024) is one of the first works along this direction. It proposes an optimization objective that gives rise to a weight vector that implies a descent direction for all tasks and converges point on the Pareto set. The PCGrad paper (Yu et al. (2020) identified that conflicting gradients can be detrimental to MTL. The authors then propose to modify the gradients to remove this conflict (by projecting each task's 's gradient to the normal plane of another task), forming the basis for the PCGrad algorithm. Another work that tackles conflicting gradients is the conflict-averse gradient descent (CAGrad)
2.2. Proxy & Multi-fidelity Feedback
Other streams of related work are (1) machine learning us- ing proxies and (2) multi-fidelity optimization. These works stand out from MTL in that they both focus on using closely related objectives, while traditional MTL typically consid- ers a set of tasks that are more varied in nature. Proxy-based machine learning attempts to approximate the solution of a primary "gold" task (for which data is expensive or sparsely available) by making use of a proxy task where data is more abundant (Bastani, 2021 Dzyabura et al., 2019). Sim- ilarly, multi-fidelity optimization makes use of data sources of varying levels of accuracy (and potentially lower com-
2

---

Aligned Multi Objective Optimization
The Specificaation Example
The Selection Example
The Local Curvature Example
#2222
011+2222
function value
function velue
Lunce rani
Figure 1: Visualization of AMOO instances in which it is possible to obtain improved convergence compared to optimizing individual functions or the average function: (left) the specification example, (center) simpler instance of the selection example, and (right) 3D example of the local curvature example, in which (11, = exp(x1) + exp(x22 - I1 T2 and (2(1 x2) = f((-11, -I2). This example highlights the need to toggle between functions according to their local curvature.
putational cost) optimize target objective (Forrester ett.l 2007). In particular, the idea of using multiple closely- related tasks of varying levels of fidelity has seen adoption in settings where function evaluations are expensive, including bandits (Kandasamy et al. 2016bla), Bayesian optimization
Descent (GD) be improved when the functions are aligned?
A common algorithmic approach in the multi-objective set- ting is using weight vector E R" that maps the vector F(x) to a single objective fw (x) == w F(x). and apply a gradient descent step on the weighted function ge.g.. Sener and Koltun (2018) Yu et al. 2020); Liu et al. (2021)) I). Ex- isting algorithms suggest alternatives for choosing w via different weight optimizers. We follow this paradigm and refer to it as Weighted-GD (see Algorithm D
(Kandasamy et al. 7:17; Song et al. 2019 Wu al. 2020
Takeno et al. ).20). and active learning Yi al. 2021
Li al. 2020 2022). The motivations behind the AMOO
setting clearly similar to those of proxy optimization and multi-fidelity optimization. However, our papers takes a pure optimization and gradient-descem perspective, which to our knowledge, novel the literature.
We provide definitions of useful structures from convex optimization that will be used in this work.
Definition 3.1 (Smoothness). f(x) Ih" + R is called
3. Aligned Multi Objective Optimization
8-smooth if Vx,y E R the following holds:
Consider unconstrained multi-objective optimization where F _ > RT is a vector valued function, F(x)= f2(), ... (x())) and all functions (fr fe(m) are convex where [m] == {I...., m). Without additional as- sumptions the components of F(x) cannot be minimized simultaneously. To define meaningful approach to opti- mize Fxx) one can study the Pareto front, or to properly define how trade-off the objectives. In the AMOO setting make the assumption the functions aligned in spe- cific sense: we assume that the functions {fi hiemm] share an optimal solution Namely, there exists point x, that minimizes all functions in F(-) simultaneously,
+ 3
fly) - f(x) + Vf(x) xx)
2 ||x 1 y12.
Detinition 3.2 (Self-concordant). f(x) :R R is called
self celf-concordant with parameter Mj Of Vx,y R the following holds:
(x))(x)() 2M llyl
where {*)())] == lim V2 v2I(xtay) is
X. E arg min fxx Vi E [m]. x
(1)
the directional derivative of the hessian in y, and || ||
With this assumption one may hope get quantitative bene- fits from the multi objective feedback. How can Gradient
Next, towards developing algorithmic intuition for the AMOO setting, we consider few examples in which align- ment between different objective function may be useful.
We also study extension of AMOO where the functions can only be approximately simultaneously minimized. See Section
3

---

Aligned Multi Objective Optimization
(i) The Specification Example.
Consider the case
Algorithm Weighted-GD
F(x)= (xx))) E RR22 where
initialize:
Learning rate 17, We deighttOptiiizer
[x(x= = (1 - 4) + Ang. [2(x) = Ar} + (1 A) A)=3
while k = 2, ... do
Wa < Seightt-ptimizzen ((f(()))
gk f V Vw (xx)
for some small A E [0,0.1] It is clear that Fxx) can be simultaneously minimized in x, (0, 0), hence, this is AMOO setting. This example, as demonstrate, illustrates an instance in which each individual function does not specify the solution well, but with proper weighting the optimal solution is well specified.
X = X -
end while
namely, f2(2) f((-()) Both functions are simultane- ously minimized in x 0. This example depicts scenario in which different functions have a larger curvature in differ- ent segments of the parameter space; for x > 0, fi (x) has a larger curvature, and for x < 0 f2 has a larger curvature.
First, observe both fi and f2 are A-strongly convex and -mm)-hho functions. Hence, GD with properly tuned learning rate, applied to either Si or f2 converges with linear rate of (()). This rate can be dramatically improved by proper weighting of the functions. Let fwo be function with equal weighting of both f1 and f2. namely, choosing We = (0.5, 0.5). We get Swy (x) = 0.5z² + 0.5x3 which is (tt)soyyyy convex and mmmoooo., Hence, GD applied fwy converges with linear rate of 2?(1)-much faster than ((A) since A can be arbitrarily small.
For such a setting, it is natural to toggle between the two functions, namely to set the weight vector as W1 (1,0) for x and as W2 = (0, 1) for x < 0. This approach, in- tuitively, should result in faster convergence to the optimal solution compared to applying GD to an individual function or the average function, since it effectively applies GD to a function which is uniformly more curved.
(ii) The Selection Example. Consider the case F(x) (x)),, E R", where
The three aforementioned examples highlight a key take- away: the curvature of the functions has a vital role in im- proving convergence guarantees for GD in AMOO. Indeed, all examples provided arguments as of how to improve the convergence of GD based on curvature information. In next sections we formalize this intuition. We introduce quantities that characterize notions of best curvature, and develop new GD based algorithms that provably converge with rates that depend on these quantities.
Vi E [m - (mm-1]:ffa f(x))(()==)))))))))))));)))))f (1 A)
j=2
fm(x)=
Σ
2 3j
1=1
and A E 0.5). The common minimizer of all functions is x, = 0 RR, and, hence, the objectives are aligned. Unlike the specification example, in the selection example, there is a single objective function among the m objectives we should select to improve the convergence rate of GD. Further, in the selection example, choosing the uniform weight degrades the convergence rate.
4. The CAMOO Weight Optimizer
We start by introducing and analyzing the Curvature Aligned Multi Objective Optimizer (CAMOO). CAMOO (Algorithm ( directly optimizes the curvature of the weighted function. Towards developing it, we define the global adaptive strong convexity parameter, PG. Later we show that when the weighted loss is determined by CAMOO GD converges in rate that depends on J4G.
Indeed, setting the weight vector to be uniform we
(1/m...,, 1/m) E R leads to the function Swo (x) =
A2/A + Ez + 1)/mm=z33 which is 0(1/m)-
We start by defining the optimal adaptive strong convexity over the class of weights:
strongly convex. Hence, GD applied to fwo converges in a linear rate of O11mm). On the other hand, GD applied to fm converges with linear rate of 2(1). Namely, setting the weight vector to be (O,..., O, 1) E " improves upon taking the average when the number of objectives is large.
Definition 4.1 (Global Adaptive Strong Convexity pc). The global adaptive strong convexity parameter, HG E R4, is the largest value such that Vx E RR" exists a weight vector w E Am such that
(ii) Local Curvature Example. Consider the case
F(x) = (f((z), f((()) x E R where
Amin Σ w. fi(x))
2 HG-
(2)
f = exp(x) x2
f2(x) = exp(- +
For each x E RR"" there may be a different weight vector that
4

---

Aligned Multi Objective Optimization
solves arg max Amin (V2 and locally maximizes the curvature. The global adaptive strong convexity parame- ter μu is the largest lower bound in I.. The specification and selection examples (Section 3 demonstrate PG can be much larger than both the strong convexity parameter of the average function or of each individual function; for both NG = O(1) whereas the alternatives may have arbitrarily small strongly convex parameter value. Further, the local curvature example highlights case in which the optimal weight may have dependence on
Algorithm 2 CAMOO
inputs: (xx()) initialize: Wmin = HG/ (8m3)
Get Hessian matrices (xx](
E arg max Amin C Wi V2 (xx))
WEAm.wmin
return: W
turns out as flawed from theoretical perspective: the function [w)(x)) = =>i [m] (x,,(x) is not necessarily convex nor smooth due to the dependence on a weight vector that has an x dependence (see Appendix B.2 for an example).
Additionally, this structural definition implies that there is a unique point x, that simultaneously minimizes the objec- tives. Due to this observation, in the following, we aim to design provable GD methods that converge to this optimal point x,. The following result formalizes this by showing that under a weaker condition compared to Pa > 0 there is unique minimizer (see Appendix F.T for a proof).
Next, we provide a positive result. When restricting the class of functions the set of self-concordant and smooth func- tions (see Appendix for formal definitions) we provide convergence guarantee for Weighted-Gu instantiated with CAMOO that depends on PG. Further, the result shows that close to the optimal solution the convergence has lincar rate in Opa// (3) (see Appendix Door proof details).
Proposition 4.1 (Unique Optimal Solution). Assume there exists X, E R that simultaneously minimizes [fiteemm namely, solves Eq. ① If maxwea,.. Amin (V2 (w(w) > 0 then x, is unique.
Theorem 4.2 (uG Convergence of CAMOO). Suppose ([)re()) are B smooth, Mr self-concordant, share an optimal solution x. and that PG > 0. Let ko == 166 [|x00 10000xx,1133 1x11..11//... /Pp) where ||-I| the Euclidean- 3pe
Definition 4.1 not only quantifies an optimal notion of cur-
vature, but also directly results with the CAMOO algorithm. CAMOO sets the weights according to Eq. (2) namely, at the 1th iteration, it finds the weight vector for which fw((x) (xx) has the largest local curvature. Then, a gradient step is ap- plied in the direction of V V (see Algorithm[]] []. Indeed, CAMOO seems as a natural algorithm to apply AMOO. Nevertheless, the analysis of CAMOO faces key challenges that make its analysis less trivial than what one may expect.
norm. Then, Weighted-Gi GD instantiated with CAMOO weight-optimizer and 1U- = 1 1/2,3 converges with rate:
| x+1l (1
3uc
(k- ko)/2
k > ko
| x+I1 S
||x0 - x, - k Ma 3/2
16,39 MmM
O.W.
Challenge (i): sw, is not strongly convex function. One may hope that standard GD analysis for strongly convex and smooth functions can be applied. It is well known that if a function f(x) is 3 smooth and Vx E R", Amin (x)(x)) 2 l then GD converges with n/3 linear rate. Unfortunately, a careful examination of this argument shows it fails.
Importantly, Theorem 4.2 holds without making strong con- vexity assumption on the individual functions, but only re- quires that the adaptive strong convexity parameter JaG to be positive, as, otherwise, the result is vacuous.
The proof follows few key observations. The self- concordance property, we find, implies a useful inequality that depends only on local curvature (see Appendix(C)
Even though Xmin (V2Sw, (xx)) 2 MG at each iteration & of CAMOO it does not imply that fw: is pC strongly convex for a fixed X4- Namely, it does not necessarily hold that for all x E R", Amiu (V2 fwe (x)) 2 fag. but only pointwise at X5 (E.g., the local curvature example highlights this issue. See Appendix [.]] details). This property emerges natu- rally in AMOO, yet such nuance is inherently impossible in single-objective optimization.
c ly - x x
2 f()
Mj yyy - x 1| (x)
(3)
for some constant C > 0. This inequality share similarity with the more standard inequality used in analysis of GD convergence for strongly convex function (Boyd and Van denberghe 2004), however, unlike the former, it depends on local curvature. In order to satisfy the assumption the weighted function fw, is self-concordannt we rely on the fact min.e(m) [m] Wk,; > Wmin by design of CAMOO. Then, addi- tional analysis leads to recurrence relation of the residual
Challenge (ii): Weighted function is not necessarily con- vex. A naive reduction may be to apply GD to the function fw. (x) where wx(x) E arg max Amin (Σm w; (x))). Namely, to apply GD to a new weighted function that is determined by optimizing the eurvature. Such an approach
5

---

Aligned Multi Objective Optimization
Mi : ||x: x.12 with the form of
has a closed form update rule and its computational cost scales linearly with number of parameters.
rh+ S 5 a/rg/11 a2rx).
(4)
5. The PAMOO Weight Optimizer
We provide a bound on this recurrence relation in Ap- pendix to to arrive to the final result of Theorem 4.2
In previous section, we introduced the global adaptive strong convexity parameter, Jlg, the CAMOO weight optimizer that chooses the weight vector adaptively and showed it has asymptotic linear convergence guarantees that depend on Pg. In this section we explore an additional adaptive mech- anism for choosing the weight vector based on Polyak step-size design. We introduce the Polyak Aligned Multi- Objective Optimizer (PAMOO). Unlike CAMOO, it only re- quires information on the gradient, without requiring access to the Hessians. Interestingly, even though computationally much cheaper, PAMOO exhibits improved convergence rate compared to CAMOO.
4.1. Practical Implementation
We now describe a scalable approach for implementing CAMOO that we experiment with in next sections. Towards large scale application of CAMOO with modern deep learn- ing architectures we approximate the Hessian matrices with their diagonal. Prior works used the diagonal Hessian approximation as pre-conditioner (Chapelle et al. 2011 Schaul et al.] 2013] Yao et al.) [022]] Liu et al., 2023b Achituve et al. 2024). Notably, with this approximation the computational cost of CAMOO scales linearly with num- ber of parameters in the Hessian calculation, instead of quadratically. The following result establishes that the value of optimal curvature, and, hence the convergence rate of Weighted-CD instantiated with CAMOO, degrades con- tinuously with the quality of Hessian approximation (see Appendix
P PAOOO (Algorithm 3 generalizes the Polyak step-size de- sign to AMOO. As such, it requires access to the optimal function values, fx.) for all i E [m²] This informa- tion may not be readily available in general. However, in modern machine learning applications this value is often zero (oiizou et al.] 2021 Wang et al.
F2 for proof details).
2023). Further, there
are variations of Polyak step-size in which the optimal value is estimated (Gower et al. 2021 Orvieto et al.) 2022). We leave potential extensions of these to AMOO for future work. Compared to CAMOO, PAMOO only requires access to the gradients of the objectives, and does not assume access to the Hessians. Further, it only requires solving a simple convex quadratic optimization problem in dimension Rm This problem is simpler than maximization of the smallest eigenvalue, required to solve by CAMOC.
Proposition 4.2. Assume that for all i E [m] and X E _R [(x) - Diag f. ll2 S ||^|| where ||Al|| is the spectral norm of A E Raxa, Let W. arg maxweam Amin (E, m. Daag (Ix()))). Then, Aminn Σ, w. V2 fi(x)) 2 HG 2 |||
Next we provide high-level details of our implementation (also see Appendix A)
Diagonal Hessian estimation via Hutchinson's Method. We use the Hutchinson method (Hutchinson) 1989 Chapelle let al. 2011 Yao et al. (02T) which provides an estimate to the diagonal Hessian by averaging products of the Hessian with random vectors. Importantly, the computational cost of this method scales linearly with number of parameters.
We now define the local strong convexity parameter over a class of weights. As we later show, this parameter controls the convergence rate of PAMOO:
Definition 5.1 (Local Strong Convexity PL). The local strong convexity parameter, 141 E RR,,, is the largest value such that exists a weight vector E Am such that
Maximizing the minimal eigenvalue. Maximizing the
m2
minimal eigenvalue of symmetric matrices is convex prob-
Amin
Σ
Wi (w.VP
2 PL.
(5)
lem (Boyd and Vandenberghe (2004), Example 3.10) and can be solved via semidefinite programming. For diago- nal matrices the problem can be cast as simpler max-min bilinear problem, arg wax m w A'q where n the dimension of parameters, A E Rmxx and its 2th row is the diagonal Hessian of the 2th objective, namely, vi [m]; Ali, || diag( 2 fx))..
where x, simultancously minimizes (filiejm)
Notice that Proposition 4.1 implies that x, is necessarily unique, and, hence μr, is unique and well defined. Fur- ther, unlike the global adaptive strong convexity parameter, the local strong convexity parameter only depends on the curvature at x,, namely, at the optimal solution. From Defi- nition 4.1 and Definition 5.1 we directly get that jr, 2 PGG-
This bilinear optimization problem is well studied (Rakhlin and Sridharan 2013; Mertikopoulos et al. 2018: Daskalakis and Panageas, 2018). We implemented the PU method of Cen et al. (2021) which, loosely speaking, executes iter- ative updates via exponential gradient descent/ascent. PU
The PAMOO algorithm is inspired by the Polyak step-size de- sign (Polyak 1987; Hazan and Kakade 2019) for choosing the learning rate in a parameter-fres way. To provide with
6

---

Aligned Multi Objective Optimization
Algorithm 3 PAMOO
5.1. Practical Implementation
inputs: {f((x)]]
PAMOO can be implemented in a straightforward and scal- able way. It requires access to the Jacobian matrix, which can be readily calculated by accessing the gradients. Cal- culating the matrix Jx E Rmxm has a computational cost of O where n is the dimension of the param- eter space and m is the number of objectives, and can be parallelized. Lastly, requires solving a quadratic convex optimization problem in RT where m is expected to be of the order of 10. This can be done efficiently with different convex optimization algorithms, e.g., projected GD. In practice, we initialize the weight vector w using the weight vector of the previous iterate. Hence, approximate optimal solution is found within a few projected gradient descent iterations. PAMOO as a potential advantage over CAMOO due to its scalability and its simple implementa- tion. Lastly, generalizing it to methods in which the optimal value is estimated instead of being given is left for future work (Orvieto et al. 2022 Gower et al., 202
2: arg wER 2w SwTAx Ax -w J
3: Ax == [Ax11 ... Axml. Ax, == f((x)) fi(x.)
4: Jx= = [Vi(x) ... VJm(x) E Ruxm
5: return:
intuition for our derivation, consider the GD update rule in single objective optimization problem, x X2 7 To derive the Polyak step-size design, observe that by con- vexity and the GD update rule we have that
|x++ x.
(6)
|x - x,12 2 1 27J (f(x)) - f(x))) + n (
Minimizing the upper bound on the decrease with respect
to 7h leads to T7K- = (fx)) - f(x.)) [V which is the Polyak step-size design choice.
Building on this derivation we develop the PAMOO weight optimizer (see Algorithm B As now show, interestingly, its convergence rate has the same functional form as CAMOO, while depending on the local strong convexity parameter jr, instead in Mg.. Hence, PAMOO has an improved upper bound on its convergence rate compared to CAMOO (see Appendix D for proof details).
6. E-AAMOO: Robustness to Alignment Assumption
We have analyzed CAMOO and PAMOO assuming perfectly aligned objectives (Eq. (... However, in practice. objec- tives may be 'similar' rather than perfectly aligned. Next, we extend AMOO to address this more realistic scenario and assume that the alignment assumption approximately correct. We show that both algorithms are robust to such an approximation and remain effective under these conditions.
Theorem 5.2 (jL Convergence of PAMOO). Suppose [ft)iemm] are B smooth, Mj self-concordant, share an optimal solution x, and PL. > 0. Let kn == 613( (1xx000xxx -x, [|3/mmMM VHL) where |1-1| is the Euclidean- 3p1
Instead of assuming the objectives are perfectly aligned, we consider the e-Approximate AMOO (AAMOO) framework, in which there exists a near-optimal solution with respect to all objectives. Let C. be the set of e-approximate solutions:
norm. Then, neighted-CD instantiated with PAMOO weight- and = converges with rate:
(k- Ro) ko)/2
C. (x (xx() [(xx) Se e Vi E [m]]. (7)
| x.|l
3pm
1 2 kn
|xx: - xx 5
32
|1x00 -x,
6492 M
3/2
O.w.
where x E arg minger= [x().. In c-AAMOO setting we assume that C, not the empty set. This corresponds to case in which exists point that is a near-optimal solu- tion for all objectives and can be understood generalization of the stricter AMOO setting in which 0.
This result is established by generalizing the Polyak step- size method analysis (see Eq. (6) while using key ob- servation. In the analysis, we upper bound the resid- ual | - x. 2 by quantity that depends on the curva- ture of the optimal weight vector at X., which is lower bounded by μn. by definition. This valid since we can replace We with an alternative weight vector only used in the analysis- since Wa an optimal solution of m 2w Ax w J&w. This flexibility allows us to upper bound expressions that depend on W by any nonnegative weight vector w E RT Furthermore, we use similar tools as were developed in the analysis of CAMOO:
natural
The main result of this section shows that for both CAMOO and PAMOO the distance between X and an e-approximate solution x E Cc, converges to capp- Further, capp is a poly- nomial function of e, structural quantities of the problem, and vanishes + 0. This provides an approximate con- vergence guarantee of both algorithms. For CAMOO, the result depends on the μa curvature, as in the AMOO setting. For PAMOOthe convergence depends on the best curvature within the set C. defined as follows:
the property of cenf-conn functions (Eq. 3) and the recurrence relation bound (Eq. (4) ).
Definition 6.1 (e-Local Strong Convexity (f.)) The e-local strong convexity, μL, E R4, the largest value such that
7

---

Aligned Multi Objective Optimization
100
10a
10
10-2
10-2
Mean Squared Error
Squared
10-3
10:4
10-4
10.5
EW-SGD
10-6
EW-SGD
CAMOO-SGD
CAMOO-SGD
10-6
PAMOO-SGD
PAMOO-SGD
EW-ADAM
10-0
EW ADAM
10
CAMOO-ADAM
AAMOO-ADAM
PAMOO-ADAM
PAMOO-ADAM
10-9
25
100
125
150
200
150
175
Gradient Steps
Gradient Steps
Figure 2: MSE (see Eq.
9
versus gradient steps. (left) local curvature example instance, (right) selection example instance
3x E C, exists weight vector w E Am such that
objectives (EW) 2 We tested these three algorithms as the Weight -Op imi zers in Weighted-GD (see Algo- rithm D We experimented with SGD and ADAM as the optimizers of the weighted loss. the learning problem we consider one network is required match the outputs of a second fixed network. We denote the fixed network with parameters 0, as he, Rd4 + Rd and the second network with parameters 0 as he Rdd + Rdd, Both are 2-layer neural networks with relu-activation and 512 hidden units.
m
Amin Σ w. vi(x)
2 HL.
(8)
Let (t, (x) maXwEA.. Amin (E we V (i()) be the largest curvature at point x. Then, pf. is defined as the maximal largest curvature in the set of near optimal solutions Ce, namely, maXxec, μ. (x). Unlike μrg that depends on the worst case curvature at all points, PL depends on the best- case curvature in C.. PAMOO convergence depends on this quantity, which also satisfies μf. 2 PG for any c.
We draw data from a uniform distribution D = {x:} where X E Uniform (1-1, 1. We consider three loss functions:
Sc(0) DD1 XED
((ha())-ha (x)) He(ho(x) -x)) -ho,
(x))
We now provide an informal description of an approximate convergence guarantee for both CAMOO and PAMOO (see Appendix B for the formal theorems and proofs):
for all E [3]. where H, E Rd. is positive definite matrix and a; 2 1. All loss functions are minimized when hæ(x) = heg (x), and, hence, We investigated two instances. First, a selection example in which a; and H, diag(1, 0.01', ... 0.01') for E {0, 1, 2). There we expect the algorithms to adapt the first loss function, f1. Second, a local curvature example where H, = I, and E [1, 1.5, 2). For such choice fi has larger curvature for large losses whereas f2 and fa have larger curvature for small losses.
Theorem 6.2 (Anformall Approximate Convergence in 6-AAM0O). Suppose (Ji)ve(m) are B smooth and Mr self-concordant. Let P.a be PG and pl, for CAMOO and PAMOO, respectively. Assume that e-AAMOO holds and that e S poly (HA.1/B. 1/m, Mt). Then, exists x,, E C. such that for both CAMOO and PAMOG iterates satisfy
an instance of AMOO.
f1 cua ) kk- + f/c//4 k ko ||xo
||x xx1I 5
x; fzk
o.w.
We track the performance by measuring the mean- mean-squared error between the networks:
Where e E (0, 1), fi | - x and f2, fa and ko are polynomial functions of B. n. m and Mf.
MSE = D
Σ XED
[1(ha(x) - ho, (x))l--
(9)
Namely, the performance of CAMOO and PAMOO degrades continuously with e, as the alignment assumption is violated. This holds without modification to the algorithms.
Figure 2 shows the convergence plots of our experiments.
These highlight the potential of using GD algorithms that designed for AMOO: both CAMOO and especially PAMOO
7. Toy Experiment
We implemented CAMOO, PAMOO and compared them to a weighting mechanism that uses equal weights on the
Al (iigeedlluttt00ppeecireeeeeennne
8

---

Aligned Multi Objective Optimization
show improved convergence rate. We provide additional experimental results and details in Appendix The results show that CAMOO modifies the weights, expected, by adapting them to the local curvature; i.e., it changes the weights gradually during the optimization phase.
on Deep Learning and Unsupervised Feature Learning, volume 201. Citeseer, 2011.
Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidance. Ad- vances in Neural Information Processing Systems, 36: 70045-70093, 2023.
8. Conclusions
In this work, we introduced the AMOO framework to study how aligned approximately aligned multi-objective feed- back can improve gradient descent convergence. We de- signed the CAMOO and PAMOO algorithms, which adaptively weight objectives and offer provably improved convergence guarantees. Future research directions include determining optimal rates for AMOO and conducting comprehensive empirical studies in different domains. Additionally, in this work, have not explored stochastic non-convex op- timization frameworks of AMOO, which we believe is of interest for future work. We conjecture that algorithmic advancements in AMOO will improve our ability to scale learning algorithms to handle large number of related tasks efficiently with minimal hyper-paramete tuning: goal much needed in modern machine learning practice.
Zhao Chen, Vijay Badrinarayanan, Chen- Yu Lee, and An- drew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In International conference machine learning, pages 794 803. PMLR, 2018.
Sumanth Chennupati, Ganesh Sistu, Senthil Yogamani, and Samir A Rawashdeh. Multinet++: Multi-stream feature aggregation and geometric loss strategy for multi-task learning. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition workshops, pages 0-0, 2019.
Christoph Dann, Yishay Mansour, and Mehryar Mohri. Re- inforcement learning can be more efficient with multiple rewards. In International Conference on Machine Learn- ing, pages 6948-6967. PMLR, 2023.
Impact Statement
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv: N00::0887704222 2018 8.
This paper presents work whose goal is to advance the field of Machine Learning and optimization. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Jean-Antoine Désidéri. multiple-gradiens descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathemaaique, 350(5-6):313-33 318, 2012.
References
Idan Achituve, Idit Diamant, Arnon Netzer, Gal Chechik, and Ethan Fetaya. Bayesian uncertainty for gradi- ent aggregation in multi-task learning. arXiv preprint arXiv:2402.04005, 2024.
Daria Dzyabura, Srikanth Jagabathula, and Eitan Muller. Accounting for discrepancies between online and offline product evaluations. Marketing Science, 38(1):88-106, 2019.
Chelsea Finn, Picter Abbeel, and Sergey Levine. Model- agnostic meta-learning for fast adaptation of deep net- works. In International conference on machine learning. pages 1 1112-11335 PMLR, 2017.
Hamsa Bastani. Predicting with proxies: Transfer learning in high dimension. Management Science, 6765):29 2984, 2021.
Stephen Boyd and Lieven Vandenberghe. Convex optimiza- fion. Cambridge university press, 2004.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In Interna- tional conference on machine learning, pages 1920-1930. PMLR, 2019.
Rich Caruana. Multitask learning. Machine learning, 28: 41-75, 1997.
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical methods of operations research, 51:479 494, 2000.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy ex- tragradient methods for competitive games with entropy regularization. Advances in Neural Information Process- ing Systems, 34:27952-2796A 2021.
Alexander IJ Forrester, András Sóbester, and Andy J Keane. Multitfidelity optimization via surrogate modelling. Pro- ceedings of the royal society a: mathematical, physical and engineering sciences, 463(20883:3251-32222 2007.
Olivier Chapelle, Dumitru Erhan, et al. Improved precondi- tioner for hessian free optimization, In NIPS Workshop

---

Aligned Multi Objective Optimization
Robert M Gower, Aaron Defazio, and Michael Rabbat. Stochastic polyak stepsize with moving target. arXiv preprint 10..112200.11851,, 2021.
Junfeng He, et al. Parrot: Pareto-optimal multi-reward reinforcement learning framework for text-to-image gen- eration. arXiv preprint arXiv:2401.05673 2024.
Daya Guo, Dejian Yang, Haowei Zhang. Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, al. Deepseek-rl: Incentivizing reason- ing capability in Ilms via reinforcement learning. arXiv preprint ar arXiv:2501. 129488 2025.
Shibo Li, Robert M Kirby, and Shandian Zhe. Deep multi- fidelity active learning of nigh-dimensional outputs. arXiv preprint arXiv:2012.0090) 2020.
Shibo Li, Jeff M Phillips, Xin Yu, Robert Kirby, and Shan- dian Zhe. Batch multi-fidelity active learning with budget constraints. Advances Neural Information Processing Systems, 35:995-1007, 2022.
Elad Hazan and Sham Kakade. Revisiting the polyak step 2019.
size. arXiv preprini
Yifei He, Shiji Zhou, Guojun Zhang, Hyokun Yun, Yi Xu, Belinda Zeng, Trishul Chilimbi, and Han Zhao. Robust multi-task learning with excess risks. arXiv preprint arXiv:2402.02009 2024.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Ed- wards, Bowen Baker, Teddy Lee, Jan Leike, John Schul- man, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint urXiv:2305.20050 2023.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A sur- vey. IEFE transactions on pattern analysis and machine intelligence, 44(9):5149-5169) 2021.
Baijiong Lin and Yu Zhang. Libmtl: A python library for deep multi-task learning. The Journal of Machine Learning Research, 24(1 24(1):9999-10005 2023.
Baijiong Lin, Feiyang Ye, Yu Zhang, and Ivor W Tsang, Reasonable effectiveness of random weighting: A litmus test for multi-task learning. arXiv preprint arXiv:2111.10611 2021.
Yujing Hu, Weixun Wang, Hangtian Jia, Yixiang Wang, Yingfeng Chen, Jianye Hao, Feng Wu, and Changjie Fan.
Learning to utilize shaping rewards: new approach of reward shaping. Advances in Neural Information Pro- cessing Systems, 33:15931-15944 2020.
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learn- ing. Advances in Neural Information Processing Systems, 34: 18888888--880, 2021.
Michael F Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics- Simulation and Computa- fion, 180)):005--1076, 1989.
Statistics-Simulation
Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. Famo: Fast adaptive multitask optimization. Advances in Neu- ral Information Processing Systems, 36:57226-57243, 2023a.
Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czar- necki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukeuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611 1.05399, 2016.
Hong Liu, Zhiyuan Li, David Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-order opti- mizer for language model pre-training. arXiv preprint arXiv:2305.14333 2023b.
Kirthevasan Kandasamy, Gautam Dasarathy, Junier B Oliva, Jeff Schneider, and Barnabás Póczos. Gaussian pro- cess bandit optimisation with multi-fidelity evaluations. Advances in neural information processing systems, 29, 2016a.
Suyun Liu and Luis Nunes Vicente. The stochastic multi- gradient algorithm for multi-objective optimization and its application to supervised machine learning. Annals of Operations Research, (3903):111991141 2024.
Kirthevasan Kandasamy, Gautam Dasarathy, Barnabas Poc- multi-armed
zos, and Jeff Schneider. The bandit. Advances in neural information processing sys- fems, 29, 2016b.
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pages 1306-1314. PMLR, 2021.
Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schnei- der, and Barnahás Póezos. Multi-fidelity bayesian op- timisation with continuous approximations. Interna- tional conference on machine learning, pages 1799-1808. PMLR. 2017.
Sha I Luo, Hamidreza Kasaei, and Lambert Schomaker. Ac- celerating reinforcement learning for reaching using con- tinuous curriculum learning. In 2020 International Joint Conference on Neural Networks (IJCNN, pages 1-8. IEEE, 2020.
Seung Hyun Lee, Yinxiao Li, Junjie Ke, Innfarn Yoo, Han Zhang, Jiahui Yu, Qifei Wang, Fei Deng, Glenn Entis,
10

---

Aligned Multi Objective Optimization
Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Chandrasekhar, and Geor- gios Piliouras. Mirror descent in saddle-point prob- lems: Going the extra (gradient) mile. arXiv preprint /rX7v:/807.02622 2018.
Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changju Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chen- zhuang Du, Chonghua Liao, et al. Kimi kl. 5: Scal- ing reinforcement learning with llms. arXiv preprint arXiv:2501. 12599, 2025.
Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and Ethan Fetaya. Multi- task learning as a bargaining game. arXiv preprint arXiv:2202.01017. 2022.
Yee Teh, Victor Bapst, Wojciech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Raz- van Pascanu. Distral: Robust multitask reinforcement learning. Advances in neural information processing systems, 30, 2017.
Yurii Nesterov. Introductory lectures on convex optimiza- tion: A basic course, volume 87. Springer Science & Business Media, 2013.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geof- frey Irving, and Irina Higgins. Solving math word prob- lems with process-and outcome- based feedback. arXiv preprint arXiv:2211 2022.
Yurii Nesterov et al. Lectures on convex optimization, vol- ume 137. Springer, 2018.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. Icml, volume 99, pages 278-287, 1999.
Vivek Veeriah, Matteo Hessel, Zhongwen Xu, Janarthanan Rajendran, Richard L Lewis, Junhyuk Oh, Hado P van Hasselt, David Silver, and Satinder Singh. Discovery of useful questions auxiliary tasks. Advances in Neural Information Processing Systems, 32, 2019.
Antonio Orvieto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. Ad- vances in Neural Information Processing Systems, 35: 2022.
Xiaoyu Wang, Mikael Johansson, and Tong Zhang. Gener- alized polyak step size for first order optimization with momentum. International Conference on Machine Learning, pages 35836-35863. PMIR, 2023.
Boris T Polyak. Introduction to optimization. 1987.
Yijia Wang, Matthias Poloczek, and Daniel Jiang. Dy- namic subgoal-based exploration via bayesian optimiza- tion. arXiv preprint arXiv: 2019.
Sasha Rakhlin and Karthik Sridharan. Optimization, learn- ing, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
Jian Wu, Saul Toscano-Palmerin, Peter I Frazier, and An- drew Gordon Wilson Practical multi- multi-fidelity bayesian optimization for hyperparameter tuning. In Uncertainty in Artificial Intelligence, pages 788-798. PMLR, 2020.
Sachin Ravi and Hugo Larochelle. Optimization as a model for sew-shot learning. In International conference on learning representations, 2017.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney. Adahessian: An adaptive second order optimizer for machine learning. In proceedings of the AAAI conference artificial intelli- gence, volume 35, pages 10665-10673, 20211.
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. In International conference on machine learning, pages 343-351. PMLR, 2013.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Advances in neural infor- mation processing systems, 31, 2018.
Jiaxiang Yi, Fangliang WI, Qi Zhou, Yuansheng Cheng, Hao Ling, and Jun Liu. An active-lcarning method based on multi-fidelity kriging model for structural reliability analysis. Structural and Mulidisscppinary Optimization, 63:173-195. 2021.
Jialin Song, Yuxin Chen, and Yisong Yue. A general frame- work for multi-fidelit, bayesian optimization with gaus- sian processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3158-3167. PMLR. 2019.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 33:5824-5R8 5836, 2020.
Shion Takeno, Hitoshi Fukuoka, Yuhki Tsukada, Toshiyuki Koyama, Motoki Shiga, Ichiro Takeuchi, and Masayuki Karasuyama. Multi-fidelity bayesian optimization with max-value entropy search and its parallelization. In Inter- national Conference on Machine Learning, pages 9334 9345. PMLR, 2020.
Qi Zhang, Peiyao Xiao, Kaiyi Ji, and Shaofeng Zou. On the convergence of multi-objectivee optimization under gen- eralized smoothness. arXiv preprint (tt::2005.19440 2024.

---

Aligned Multi Objective Optimization
Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu. On the convergence of stochastic multi-objective gradient manipulation and be- yond. Advances in Neural Information Processing Sys- tems, 35:381 03-38115 15, 2022.
12

---

Aligned Multi Objective Optimization
A. Additional Experimental Details
We share an IPython notebook in which we implement our algorithms and was used to generate all plots accompanies this submission.
Dataset. We sample 200 points from independent uniform distribution x; Uniform([-1, 1)20). We generate target data from randomly initialized network ((r,) = he, (x,) + 10. The target dimension is 7.
Network architecture. We choose the ground truth network and target network to have the same architecture. Both are 2 layer neural networks with 512 hidden dimensions and ReLu activation. The neural network outputs vector in dimension 7.
Training. For both problems, we set the learning rate of SGD to 0.0005 and ADAM to 0.005, we use the same learning rates for PAMOO. For CAMOOWe multiply the learning rate by the number of loss functions, 3. While equal weighting sets all weights 1, CAMOCis constrained
the sum of all weights to one, our adjustment accounts for this normalization.
General parameters for CAMOO. We set the number of samples for the Hutchinson method to be NHuthh = 10. Namley, we estimate the Hessian matrices by averaging NHtthh 10 estimates obtained from the Hutchnison method. Further, at each training step we perform single update of the weights based on the PU update rule of Cen et al. 2 to solve the max-min Bilinear optimization problem (see Section 4.1). We use their primal-dual algorithm, and choose the learning rate as they specified 1 (2 max;,j AA + Tсaтоо) where A is the matrix the Bilinear optimization problem and Tсамоо = 0.01 a regularization parameter we choose. Additionally, we set the number of iterations of the primal-dut algorithm to 100 per-step. We did not choose either parameter with great care, exploring best settings part of future explorations.
General parameters for PAMOO. We solved the constraint convex optimization problem in PAMOO (see Algorithm via the projected GD algorithm, where the projection on BT is done by clipping negative values to 10-6, We set the learning rate to be 3e-3, and added small regularization J Jx + J Jx + Tramoo to avoid exploding weights, where Teaооo = Le
Additional Plots of Experiments in Section 7 For completeness, we present the three loss functions of the objectives 3 depicts the losses for the local curvature example
[ft) and the weighted loss function of GD iterates. Figure instance, and Figure 4 depicts the losses for the selection example instance. Unlike EW, CAMOO and PAMOO adaptively modify the weight vector and adjust it to current parameters.
We measured the weight vector as a function of GD iterates and present the results in Figure
Local curvature example instance. For the local curvature example instance expect to see switching behavior in CAMOO (see Figure 5). Namely, when the loss is large, the weight vector of CAMOO should assign most of its weight to the quartic loss function, fa, since it has the largest curvature for large deviations from optimality. For small deviations, we expect CAMOO to assign weights to the quadratic loss, f1-
Selection example instance. For the selection example instance expect CAMOO to set the weights 1-hot vector fi, since its the quadratic function with largest curvature across all dimensions. Figure exxmplifies this.
13

---

Aligned Multi Objective Optimization
f((x) (1y - HH 2)
F(x) (y- 1 6)as
10-1
10"1
10
30
20'5
14
10
CAMOO-SGD
20-7
CAMOO-SOI
EW-ADAM
EW-ADAM
10
10-9
PAMOO-ADAM
RAMDO-ADAM
75
100
125
175
200
75
100
125
150
175
200
f(())
HyH 8)
ftxi
Σwif(x)
101
10
10a
10-3
10
10
10"7
EW-50D
EW-SOD
10
CAMOO-SGD
30
CAMOO-SCI
PAMOO-SOD
PAMOO-SOD
10-13
EW-ADAM
EW-ADAM
CAMOO-ADAM
10-5
CAMOO-ADAA ADAM
13
PANOO-ADAM
IMMOO-ADAM
25
50
75
100
125
150
175
200
50
75
100
125
150
175
200
Figure 3: Local curvature example, all loss functions.
4(x) = -yy==yy-)m(ly-
f20x) = (y Ho.o0
10-1
10-1
10-3
10-3
10 5
EW-SGD
EW
SGD
CAMOO-SGD
PAMOO SGD
10-7
RAMOO-SGE
10
EW-ADAM
EWADDAM
CAMOO ADAM
CAMMO-ADAM
RAMOO
10'9
RAMOO-ADAM
75
175
200
50
125
150
((x) ly - 1) Mo c001y
fix) Σw.f(x)
102
10-1
201
10-5
10-3
RW-SGD
CAMOO-SGD
10.5
CAMOO-SGD
10
JAMOO-S0R
EW-ADAM
7
EWADDAM
1
CAMOO-ADAM
CAMOO-ADAM
PAMOO-ADAM
IMMOO-ADAM
25
Figure Selection example, all loss functions.
14

---

Aligned Multi Objective Optimization
150
500 (y- 095
fyla--1y t/
w:. scales 7000 = (0 07
Weight for respectiive Loos Functonn
1.50
My scales (1x0-1y r/ f)15
1.25
My scales dP
Mian Squardd Frrer
1.25
W
1.00
0.
0.75
0.75
0.30
0.25
50
125
200
Gradient Steps
25
75
200
125
150
175
200
Gradkent Steps
Figure 5: Local curvature example, CAMOO. The weights flip when the curvature of the loss function changes.
Figure 6: Local curvature example, PAMOO.
tyx--ty- d'Hyty-D
1.0
scalss (y- oFMiyy
My stales (ll)mmy-d"faaa of
Wy scales fgle) - 0faay--0
Mj scales (y dTHocealy 0
Weight for respective Loss Function
scales hud -y- Bf (/
Moan Moann Squard Fror Fror
22.5
1.5
Squared
1.5
10-
0.4
7.5
5.0
0.0
30
100
125
150
175
200
300
175
Gradient
Gradient Steps
Figure 7: Selection example, CAMOO.
Figure 8: Selection example, PAMOO.
Figure 9: Weight vector evolution versus GD iterates.
A.1. Toy Experiments: Approximate AMOO
We include additional experiment for the approximate AMOO setting, in which there exists a near-optimal solution for all objectives. We consider loss functions of the local curvature example and add an approximation error as follows:
1
fe(0)
D E((h(x - ho, (x) + ei) H (h, - ho. (x)) + E;)
where we H, 7 and 6 {0,e, -e} where & 0.01.
15

---

Aligned Multi Objective Optimization
f(X) (y - Ht
6(x)= 10t
10a
10:
100
10"2
10-1
10
10-2
10'5
CAMDO-SOD
10
CAMDO-SGD
10-5
EW-ADAM
10
EW-ADAM
10
PAMO0-ADAM
PAMOO-ADAM
10
50
125
150
175
25
100
125
175
200
f(x) -t- -i
fx)
Wwif(x
107
10a
10
EW-S0D
10-1
EW-SOD
CAMDO-SGD
CAMOO-SGD
PAMOO-SOD
PAMOO-SGO
10-5
EWAADAM
EW-ADAM
CAMOO-ADAM
CAMOO-ADAM
PAMOO-ADAM
10-3
PAMOO-ADAM
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Figure 10: Local curvature example for e-approximate AMOO, all loss functions.
A.2. Toy Experiments: Reducing Computational Complexity of PAMOO
Both CAMOO and PAMOO solve convex optimization problems in their inner loop to update the weight vector w. In our implementations we use simple first-order algorithms that apply N gradient-descent updates as detailed in Section 4 and Section [5] The results in the main paper depicts the performance of CAMOO and PAMOO when N 100 and N 1000, respectively. For these values, both CAMOO and PAMOO are significantly more costly compared to the algorithm.
Here experiment cheaper variations of both CAMOO and PAMCO in which set N 10, and, hence, reduce the number of updates to the weight vector. Table shows the improvement in running time of CAMOO and PAMOO as well as comparing their running time to EW. As observed, the running time of PAMOO can be significantly improved whereas the running time of CAMOO is worse than E... This is caused by the need to estimate Hessian information which can be costly without careful optimization. Figure II depicts the performance CAMOO and PAMOO when N = 10. The performance of both algorithms degraded on the expense of improved running time. This shows that as the running time is improved algorithm designer may expect experience performance degradation.
16

---

Aligned Multi Objective Optimization
Algorithm
Runtime (s)
EW Algorithms
EW-SGD
0.408452
EW-ADAM
0.480058
CAMOO and PAMOO
PAMOO-SGD
8.654938
CAMOO-SGD
6,695782
PAMOO-ADAM
8.435489
CAMOO-ADAM
7.466246
CAMOO and PAMOO with N
10
PAMOO-SGD
0.715199
CAMOO-SGR 3,674786
CAMOO-ADAM 3.598157
PAMOO-ADAM 0.726002
Table 2: Runtime in seconds.
f(X) = (ly -YYHY 0)
fx() -yy''Hly-t7
10a
164
100
EW-SGD
EW-SGD
CAMDO-S6D
10
CAMDO-SGD
RAMOO-SGD
PAMOO-SGD
20
CAMOO-AN ADAM
CAMGO-ADAM
BAMDO-ADAM
10-2
50
125
150
175
25
100
125
200
f(x) = (ly H7Hlly 0)}
Rx) Ewif(x)
10a-
EW-SGD
PAMOO-SCC
10a-
104-
CAMOO ADAM
PAMDO-ADAM
101
100
EW-SGD
109
CAMDO-SGD
PAMOO-SDD
10
RWADAM
CDAM
10-1
RAMOO-DDMM
200
Figure 11: Local curvature example with reduced computational complexity (N 10).
17

---

Aligned Multi Objective Optimization
B. Challenges in Analyzing CAMOO
B.1. fw: is not a Strongly Convex Function
We provide an example that shows that for the AMOO setting, when μl > O, the fact that Amin (V2 (xx)) 2 PG
throughout the iterates of CAMOO does not imply that each fw, fug-strongly convex.
The counter example is the local curvature example (see Section namely,
f1 exp(x) I, f2(x) exp(-x) x.
and x E R. The minimum point of both fi and f2
0. The Hessians of the functions are:
v f)( (2) = exp(x), v (2x) - exp(-
(10)
We see that f1)) V fz(r) for x 0, fz
(z) for x <= O, and V ===()==='(()]]
This implies that μa and CAMOO will set the weight vector W+ (1,0) for x > and w = (0. for However, it is readily observed that neither fw or sw, are 1-strongly convex functions. The smallest value of the individual
Hessians is zero since
inf 2 fw (x) inf exp(x) 0 sER
.ER
inf V fww (x) SER
inf exp( -x) 0,
SER
by Eq. 10
Hence, the functions fw, produced in the iterates of CAMOO not strongly convex.
B.2. Weighted function is not necessarily convex
We provide a simple counter example that shows failure of a naive reduction in which we construct fw)(x) E, W (xxxxx where (x) optimizes the curvature each point via,
(x) E arg max Amin WEAm
ws f((e)) (m(m)
and apply gradient descent to the function (x). The reason such approach is problematic the fact that fw.(x) may no longer be a convex function. This result of the extra dependence of (x).).
A counter example can be established for simple scenario in which
fi 2², f2(x) = x² 22+
where E R, for some 0. The two functions convex, and have minimizer 0. However, since the Hessians of the functions are equal, (z)) 4 f2()), the solution of the optimization problem
Σ w w (E
(x) E arg max Amin
(1I)
w
arbitrary. Namely, each point on the simplex a solution of this optimization problem. For example, choosing
w. (x) = (sin? (z), (sin?(xx) cos (z)),
is a solution of Eq. With this, the function fw.(2) takes the form of
fw,(z) x² + cos (0))
which is not convex function if, for example, |c| >
18

---

Aligned Multi Objective Optimization
Additionally, choosing w, (x) as non-smooth function, for example
w.(x) f (0, x (1,0)
x - 0,
results with non-smooth function (w). This highlights that differentiating the function fw.(x) flawed from a theoretical perspective: (w.(e) not necessarily convex nor smooth.
C. Preliminaries and Basic Properties
In this section, we formally provide our working assumptions. We assume access to multi-objective feedback with m objectives F(x)= = (/i (x),..., fm (x)), when Vi E [m/] the function [x() is smooth and self-concordant. Considering two scenarios AMOO, and e-AAMOO. In AMOO we assume the functions are aligned in the sense of Eq. (T). namely, that they
share an optimal solution. c-AAMOO we assume there (non-empty) set of approximate solutions in the sense of Eq. 7 i.e. every solution in the set has maximum value gap of from the minima of every function.
We define the following quantities, for the single and multi objective settings:
|y = [yxlva35()) == (V)y))) | == lyyll = (V fw(xxy
smooth function satisfies the following:
Lemma C.1 (Standard result, E.g., 9.17 Boyd and Vandenberghe 2004)). Lel f R" - IR a 8-smooth over Ik", and let x, E arg min fxx). Then, for every x R= holds that
self-concordant function satisfies the following:
Lemma C.2 (Theorem 5.1.8 & Lemma 5.1.5, Nesterov 2013 Let f 1. - I. be an M; self-concordant functioon Let
x,y E R" we have
f(y) 2 f(x) (Vf(x). x)
MF Mp (Mr Iyy - xx112)
where w(t) In(1 t), and, for any w(t)
12
2(1+)))
Lemma C.3 (Theorem 5.1.1, Nesterov et al. Then, f = wh f1 + W2/2 is maxi yoy Mr self-concordun function.
2018)). Let f1, f2 - R be Mi fincooo Let W1, 0.
Proposition C.1 (Weighted sum of self-concordant functions). Let (f: R + be Mr self-concordant functions. Let [w, > 0}. Then, f = Ei= wift is M = max; J MMr self self-concordant function.
The proof of the last proposition proof is found in Section F
Theorem C.1 (Weyl's Theorem). Let A and A be symmetric matrices in Raxn, Let (, be the jth largest eigenvalue of a matrix A. Then, for all j E [n]] holds that (A)((A) - (, + A)l < ||||, where |All 1 the spectral norm of A.
C.1. Auxiliary Results
Further, we have the following simple consequence of the AMOO setting.
Lemma C.4. For all E Am and _ it holds that fw (x) fw (x.) 0.
Proof. Observe that fw (x) - -w((x.) = Emh wy (f((x) fx(x))) Since x, is the optimal solution for all objectives holds that f((x) - f((x)) ) 2 0. The lemma follows from the fact w; 2 for e [m].
19

---

Aligned Multi Objective Optimization
Lemma C.5 (Recurrence bound AMOO). Lel (rk}az0 be sequence of non-negalive real numbers that satisfy the recurrence relation
2 R++ S
2
k
1 022k
where 01 [0, 2) and 02 R4. Let ko
1(100g-1)
Then, The bounded by
Q1
rko
01 k
224 ko
The S
ro
400
aL
O.W.
The proof of the lemma is found in Appendix The next lemma is for the e-AAMOO setting. We separate them since the recursion and the result of c-AMMO0 have more details, making it less readable.
F.3
Lemma C.6 (Recurrence bound A-MMO)).. Let fraha2o be a sequence of non-negative real numbers that satisfy the recurrence relation
o
k++ S
2 k a1
as + aatk:
1
02rkk
where 01 E (0, 02 E RR,.000, 0z S 2500?
aj
and 04 S
01
Let Ko
16(romg
Then, Th bounded by
2ag
a1
k
Tho (1
+
k 2 Ko
rk
D1
0.02
ro
01 k
O.W.
D. Proofs of AMOO Results
See Section 4 for a highlevel description of key steps in the proof.
We first describe two useful lemmas that are used across the section.
Lemma D.1 (Weighted Function is Self-Concordant). For any iteration l of CAMOO, the function Jwy. is // WWmin self-concordant.
Proof. This direct consequence of Proposition C.T and the fact Algorithm T sets the weights by optimizing over a set where the weight vector is lower bounded by Wmin.
Lemma D.2 (Continuity of Minimal Eigenvalue of Hessian). Let X R", Further, let w. E arg max Amain (V2f WEA,.
W E arg max Amiin (v2 It holds that Amin (V2 2 Amin (V-Sw, (x)) 2m.wnin....
A Main
With these two results, we are ready to prove Theorem 4.2 and Theorem 5.2
D.1. Proof of Theorem 4.2
Restate first:
Theorem 4.2 (μG Convergence of CAMOO). Suppose [fi are 3 smooth, Mr self-concordant, share an optimal solution
X. and that pG 0. Let kn = 1663 [|x0 - 1xxxx|13// m33 /PG) where ||-I] is the Euclidean-norm Then, Weighted-GD
3pc
instantiated with CAMOO weight-optimizzr and 1/2 converges with rate:
||xko - xx (1
3prrs 8,3
(A- ho)/2
k: kg
|x x.11 5
||x0
x. k 168 //
O.W.
20

---

Aligned Multi Objective Optimization
Proof. At each iteration Algorithm
gets Wi
arg max Amin (E, wj [[x)))(((x))
Using the assumption that
We WeAmiwmin
Amin (V2 (xx)) PG. Lemma D.2 and since we Wmin = PG/ (8m.3) we have that
WEAm
Amin (V (w=) 2 Amin (V fw)
2mmmmin 2 MG PG/ / (3/4)
(12)
for all iterations t. Recall that the update rule is given by Xx+1 Xx 1) V Sw (xx), where v is the step size. Then, for every E _n we have
X x|2== = || S/W (xx) x12
|xXs= - x||² 2n V Swo (Xx), - x3 r² V| Sw, (xx)1l
(13)
By Lemma D.1 it holds that Swy
Mf 1/V Wimin Mr S 33/m3M; VPG
(14)
self-concordant. Then, from Lemma
C.2
by properties of self-concordant functions, for every x E IR we have
1
(V (Xx), Xx
Swo (xx) Swn (x)
Mi ||x xx xxllxa.wa)
Mr
Plugging this inequality into Eq. 13)
implies that
| - x|| Xx
x||² 2n
Swe (x+)) Swa (x) + 2 Me ||x
X xxllxx.
+ r² [[ (xx)11
(15)
Mr
Recall that x. E arg minx fix for every E [m]] Since Swy B-smooth, by using Lemma have
C.I and plugging in x, we
| x,
$ |x|
x.112
2n
Swa (xxx) - -Swa (x.) + 2w
Mi ||x, xx xxllxe..e))) + 2,31² (Swe (xx) - sw.. (xx))
Mr
1
-|x x,11
2n
zw (Mellxx ||x, x xkllxa.wx) + 20( (Swa, (xx) Swa. (xx)))
Mr
By using Lemma
C.4 it holds that Swe (xx) fwx (x.) 2 0, and since 0 < I 1/23, it holds that 2m(3n
1) (Swn (xx) Swa (x.)
0. Then, by using the lower bound from Lemma C.2 i.e. w (1)
21+0] the following
holds
||x, Xx 1x
||xx+1 - x=11== < ||x6 - 2- 2n
1 + Mr ||x. xx xxllx
Note that Amin (V2Sun (x+) 1|x, - xxe12 |x+
xx 12. S Amax (V2 Iw. (xx)xxx)) |x, x111. By using the following:
Amnin 2 fwa (xx)) 2 (3/4)μG (Eq. (22 Amax
V22 (xx)) S (smoothness), Mf S <3/mBM/ VPG (Eq. (4 ), and
17 1/23, we obtain
3uc
Xx. Xx 1|
|x++1 xx11 < X1 x.1
433 + (3/mBM// VPG) ||x, xxll
Now, we are ready for the last step. Denote 0ı
3um and a2
3/mBM, vPG
Since aj E (0, 1]. a2 E R,, and
|x - x.| E R4 for every x R", we arrive to the recurrence relation analyzed Lemma C.5
Then, we obtain
(o)2
||xko - -x+ll
3/c 8,
k ko
|x x+11 5
||x0 x. -k 1655
ug
O.W.
where ko : 1699 [Ixo
M )Pa)
3nc 3/2
21

---

Aligned Multi Objective Optimization
D.2. Proof of Theorem 5.2
Restate it first:
Theorem 5.2 (Ji, Convergence of PAMOO). Suppose [ftieemm are 3 smooth, Mj self-concorlant, share an optimal solution
x, and PL O. Let ko := 64,3(1 x. 11.111/8/MM vPu.) where II-II is the Euclidean-none Then, Weighted-G2
3/,,
instantiated with PAMOO weight-optimizer and converges with rate:
| -x+ll (1
3pm
(k
k2)
k
kp
|
x.11
32333
3/2
||x0- x.11
648" v WMM,
O.W.
Proof. Recall that for every w E RT it holds that fw is a convex function. Hence, for every x, E R" it holds that
fw(() (w()) (y
(xw
Recall that the step size = 1, then the update rule is given by Xx+1 Xx V.wa (xx).
Then, by using the previous
equation, for every x R" we have
|x++1 x|2= [x -xxl) x|| - fwo (xx), X5 x) + V V (xx
S
x - x||² - 2 (fw. (xx+) - Swa (x)) + fw.. (xx)
(16)
Recall that x, arg mix" fi(x) for every i [mr]]. Since the update rule of PAMOO is
W& E arg max 2 (fwa (xx)) (x.)) V. (xxx)())) (xx)]l? WERV
the following holds
| x11125 S | x-11-
max
(f(w(())) - 5w (x,)).) - [w
(17)
WEST
Denote arg Amin (ETh W/ (xx.)).)) ag fw. (xx) fw. (x.), and by V. (xx)]] Let wxxx))
WE P'EAm. Mimin
W. Gk by
E R. we can lower bound the last expression as follows
(x) - (w.(x)) -
| / (x6))| 2 2 2 (Sw(xc) (x.))) |/ (w(xx)
(xx))l (xx)))))))1
max WER"
(fw, (xx) - Sw. -x.((x)))
IV (xx3.(xx)1))
Since w. A om it holds that fw. is 3 smooth. Then, it holds that [W,, (x)112 < 23 (fw. (x) fw. (x.)) for every x, and we have
max WER" (fw F (x.))) -I (x+))1 Sw, (xx) Sw. (x+)
25
Plugging this in Eq. we arrive to
|x xx112 S |xx x. Sw. (xx) fww (xx)
2,3
By Lemma D.I it holds that Sw, is Mr = 1/ Wiiin Mf self concordant. Then, From Lemma C.2 and its lower bound i.e.
w (t) 2 2(1+t)+ we have
|| |x* x. 11x...
[ X. 11.12 112..
Sw, (xx) (xx) 2 (V,w, (xx), - -x.)
Mc |x x. llx.
( + Mr || X. lxxe,,
22

---

Aligned Multi Objective Optimization
The equality is due the optimality condition, Vx((x)) for every [m]] thus, V.w. (x.) 0. Combining the last two equations, we have
1x x, 1| x..
1
X x+11² S Xx x.11
439
+ Mi ||x: - X.llx,...
Note that Amin (V2 (x+)) ||=, xx 21 |x. xx stllxx, xlllx...
Amax (V2 sw. (x+)) ||x, xx|1..
Since
Amax (V2 fw. (x,) S B (smoothness), and since Wmin /L/ then Mr 3/mBM1// VAL. Thus, it holds
that
Amin (V2 Sw. (x+))
||x, xxl1?
|x++1 - x, 12 & ||x: - x.1." 4
1 3/mM: | xx11l
VPL
Using the assumption that max Amin weAm
2 LLl, Lemma
D.2 we have that
Amin
( (x+))
max Amin (V2 (x.)) WEA...
mmm 2 MI. /L// /4 = (3/4)/L.
Finally, we obtain the recurring equation we wish:
3pL
X.
Xx.l
X++1 - x111
x.
163
+
3/mM,
||X
V/T.
Denote a1 to the recurrence relation analyzed in Lemma C.5
3 16
and 02
3 3ymBMM
Note that aq E (0, 1]. 02 E R_ and ||x x.11 E R+ for every x R", we arrive
Then, we obtain
k2)/2
| x.|l
3p1
k Ko
| x.
323
|150
x.Il
k 648 /mMi
O.W.
(1x0 xx 118/m//M 1 /AL)
where ko
3p1, 3/2
E. c-Approximation Solution
In this section, we represent the formal theorems of the Informal Theorem 6.2 for CAMOO and PAMOO. First, we rewrite the definition of approximate solutions set. Definition E.1 (e-Approximate Solution Set). Let O. C. is e-Approximate Solution Set (e-ASS) if for every i [m] holds that fxx - f((x() I i.e.
C. = fxERX fi(x) - fi(x)) S vi E [m]}.
where x arg min (f((x).
We show in the following formal theorem that for > 0 CAMCO converges for any chosen point from the set C., i.c. the e- approximate solutions set.
Theorem E.2 (JG Approximation Convergence of CAMOO). Suppose (Ji)se(m) are 3 smooth, Mf self-concordant, C. is (l
649
pG. 0. Then, for every point x E C., Weighted GD instantiated with CAMOO weight-optimizer and 1/23 converges with rate:
e-ASS and that μc O. Let kn
JPG
where ||:|| is the 2-norm. Let
3pG
3mmM M7
/a-ka//2
|xko - -x(l
3uc 8D
k: 2 ko
1x x111 5
3uG
|x0 x
O.W.
23

---

Aligned Multi Objective Optimization
Proof. Let X C. Denote x arg minlERR Swa (x) for every k, then since Swa is 3-smooth, by using Lemma C.1 it holds that || [ I 23 (f(x)- - f(x+)). Plugging in x = x in Eq. (15), we have
|xx+1 x11
$ <||x* - -x,12 2n
fwe (xxk) - fww (xx)
zW
MM ||x; - Xx xxllbxe.we) + 2,31² (fwe (xxs) fwe (xx+)
Mr
- -1|x; - xt11? 211
1 zW [M ||x; - xx xxllxa. w..
Mf
+ 2n/ (w (xx) - Swe (xx)) ) + 2n((n - 1) (fwe (xx) - [we (xx)).
Since fw. (xx) - Sw, (xx) 2 0, and since 0 <) S 11/28, it holds that 27( (1 - 11 [Jw (xx) - Swa (xx)) S 0. In addition,
by using the lower bound from Lemma C.2 i.e. w (1) 211ty and Definition E.1 with the fact that E, wi 1, the following holds
||x X1c X
|x - x,11 S [ x11 2n
2ne..
1 Mf || Xx xxllxxw
Note that Amin (V fwn. (xx)) ||x; - xx 2 < |x xx xx, S max (v2 (xx)) ||x; - xx112 By using the following:
w. w
Amii ( ww (xx)) 2 (3/4)²G (Eq. 12. Amaax
(V² (xx)
(smoothness), Mr <3/mBBM// VPG (Eq. [1 ), and
7 1/28, we obtain
XK+1 - x 1 ||x: - = 3/G
x xx
43 1 + (3/mBM; vHG ||x| - Xx
3
Now, we are ready for the last step. Denote 0i
3yc 13
3/mBM and 03 = 3. Since E (0,2), a2 E R4, /PG
03 S a² and |X
xf E IR, for every x E IR",, we arrive to the recurrence relation analyzed in Lemma C.6 Then, we
2560g
obtain
(ks /2)/
12ko - -x1ll
3pG 83
+
k N ko
||*
xill= 5
3pG
||00- x511 k 1, 12 pop.//l Mr
O.W.
618
By/mMM xg
x5|1
-1)
where kn
vPG
3pG
Before we continue to PAMOO, we recall Definition 6. which defines 14.-- This parameter is the maximum eurvature over the c-approximate solutions set, which can be much greater than JaG, and fL. Before we show the formal theorem of PAMOO, we define x E C, which is the point with the maximum curvature, s.t.
arg max max Amnin X,EC. WEAm
Σ Wi [ixx))
ML max Amin WEA...
W
f((x
Now, we show the formal theorem that for 0 PAMCO converges to X Theorem E.3 (uf, Approximation Convergence of PAMOO). Suppose (ilve(mi are 3 smooth, Mf self-concordant, C, is an
4'9 ||x0-
x:
3umma ouf.
e-ASS and that pf, > 0, where min
8 g 23
2 E >>>>0 O. Let ko =
where ||-11 is the
41 M?
3u4.
Euclidean-norm. Then, Weighted GD instantiated with PAMOO weight-optimizer and 1 converges to X with rate:
k-
Xko - -xxl
3
16c
+
32v28e 9/PLMM
k 2 Ko
Xx
x
5
32
Xo
x
64,3 o M
O.W.
24

---

Aligned Multi Objective Optimization
Proof. Combining Eq.
(66
with the update rule of PAMOO, and plugging in x5, i.e.
arg max (fwe (xx) - fw (xx)) V[ (x+)]?
We
WERV
the following holds
xk+1
x
Xk
x
max WER
(f - fw (x,)) 1IV f/ (xx))1
(18)
Denote w arg max Amin (2i-)
wi V (x ag Sw: (xx)) Sw: (x5) and by Vw (xx))l Let wxxx)
wumin
W by
E [R4, we can lower bound of the last expression as follows
- -
V (xx))) 2 2 (fw(x)) fw((x.)) (xC)
V fw((x)) (xxs) 1l
WERn
(Sw: (xx) Sws (xE))
fw: (xx)) 1|
Denote x, E arg minl Jws (x). Then, it holds that
(fw: (xx) - Sw (xt)
V.ww (xx) 1
(Fw; (xxx) fwu (xx, + fw; (x,) fw: (x²)) (fws (xx) sw: (xx)
/wwc (xx))l²
(Jw: (xx) - Swy (xx)) (Jw: (xx) Swu (XG)) (Sws (x+) Sws (xG) )) (Jws (xx) Sw: (xE)
V/ Swo (xx)
V sw: (xx))l
(Jw: (xx) - fww; (xx)) (fws (Xx) - sw: (Xx)
(fwz (x,) fws (xx) (Jwe (xx) Swy (xx))
fw: (x<=] 1
V fws (xxs)]
+ (sw: (xx) - sw: )x
2
|| V/s (xx) ?
(fw: (xx: - fws (xx)) (Fws (xx) - fw: (xx))
(fwy (x.) Sws (x4) (fwe (Xx) fww (xx))
V fw: (xx) |
|| V (xxe)]
Since w E Am Am it holds that fwy is 3 smooth. Then, it holds that V (x) x, and we have
s 2/3 (Jwy (x) - Swe (x.)) for every
2 (fw(Xx) - for (x5)
| V/ (xx))1? >
Sww (xx) - Sww (xx)
Sw, (xx)
Swi X
max W
2,3
2/3
Plugging this Eq. 18
we arrive to
2
fw: (Xxs
fwe [
fw: (x²)
fww (x.,)
X4
<
xx - x
28
2,3
Sw: (xx)
-ww x
x
x
2
2
By Lemma D.1 it holds that Sw. is Mr 1/1lll///a WWiin Mj self concordant. Then, From Lemma
C.2 and its lower bound i.e.
25

---

Aligned Multi Objective Optimization
w (t) 2 -0)+ we have
2
xx
k?.w
swo (xx)
Iw: (xi)
(V Vww -x,,xx= Xx=
x5)
+ MM
Xx
15,11,,,0 w.
||X0
x 12, wt
2 - | ww (x5) || -x x +
2 1 + My || - x3 11,,, w
By Lemma C.1 we have that Ww (x:)
$ 2,3 (Sw: (xx)
Sw: (x.)) S 2Bc, and, hence, - -1 Sw: (x:) 2 2Bc.
Plugging this back results with the following
xx x ww
xx+1 x
x5| 21
/2
Xx 14-x3 xx
46
1 + M1
23
Note that
Amin (V2 fw: (x5)
X
| xx
S
Amax (v2 sws (xx))
xx Xx
Since
Amax (V² sw: (x5) < 8 (smoothness), and since Wmin = ML (8mB), then Mr S 3/m3.MM VVG. Thus, it holds
that
|xX+1 x xx
x 1|
1 Amin (V2 Sw:
x
Xx
22e X x31
4,
1 3/mM/
23
Vuf.
Using the assumption that max Amnin (V2 fw (
L Lemma D.2
we have that
wEAm m
Amin
V
max Amin WEAm
wx())( 2mmmmin 3 2 pL - 11L/4 (3/4)zf.
Finally, we obtain the recurring equation we wish:
3
x
X
|
x
<
x
-
x
163
1 1+
3/
Vai
X
+
2
+ 2,e
|x X
Denote
01
344 16
Q2
3ymmMM
V
a3
2 and a1
V23..
Note that a1 E (0, 02 R., 03 S
256a
a² and
04 S
01
and |x x
RR for every x E R", we arrive the recurrence relation analyzed in Lemma
C.6 Then, we
4mg
obtain
[kk
x
16c
32.28E
k Ko
X - x
5
323
3/F
9/PLMM
[xo
x
64/9
Lm
O.W.
54
||x0xx]|
x
Vol
where kg
F. Missing Proofs
F.1. Proof of Proposition 4.1
Let us restate the claim:
Proposition 4.1 (Unique Optimal Solution). Assume there exists x, BD that simultaneously minimizes [.. namely, solves Eq. If max Amin (V2 (x.)) > then x, unique.
26

---

Aligned Multi Objective Optimization
Proof. Let x, be a minimizer of all functions (Aiie(m) which exists due the AMOO assumption, namely, solution of (19)
X, E arg min (x) Vi E [m]]
By assumption, it holds that for the weight vector arg max wEAm Amin C m Zisl Wy (x.)) it holds that
Amin (Ei=) V fw. (x.) > O, namely,
V Sw. (x.) >
(20)
Notice that x, minimizer of Sw, (Lemma C.4 and that Jw, convex function, since fi are convex and w, has non-negative components. Combining with Eq. 20 it implies that x, is unique minimizer of fw..
Assume, by way of contradiction. there exists an additional minimizer that solves Eq. (19), denote by x. Since it is solution of Eq. (19). it is also minimizer Sw, This contradicts the fact sw, has a unique optimal solution x,.
E.2. Proof of Proposition 4.2
The proof of Proposition 4.2 is a corollary of Theorem C.1 (Weyl's Theorem). We establish the result for a general deviation
in Hessian matrices without requiring it to be necessarily diagonal.
Let us restate the result:
Proposition 4.2. Assume that for all i E [m]] and E IR" spectral norm of A E RRaxn, Let w. arg maxwea... Amin (E; wi D2 (Ji(x))). Then, Amin (E, W V2 f((x)) 2
[i(x(x) Diag (V))((x) ||2 S || where ||A|| ll is the
MG |||
Proof. Denote A; = (25((x) + A; for every i E [m], and E A, = A. Let and w, denote the solution of,
Σ Ewi [ivv'f((x))
[Ew,Ar w; (usAA))
w. arg max Amiu WEA
and
W, E arg max Aminn WEA
respectively.
Let g(w.), and ((w.) denote the optimal value, g(w.) = Amin (E, W. V fx()). and g(w.) Amni A.). Then, since ((w.) ) - g(w.) s O by the optimality of w. on 9. the following holds g(w.) = g(w.) - (((w) + ((w.) g(w.) + ((.) g(w.) + g(w.) S (g(w.) -((w(w)w+ + - -((ww) ( g(w,)
Using Theorem C.1 (Weyl's Theorem) the followings hold: (g(w.) o(w.)) ) A, and ((w.) g(w.)l & A. Then, obtain
g( g(w.) 2 2 + ((W,)
Finally, since g(w.) 2 pc. by Definition 4.1 we obtain the proof.
F.3. Proof of Lemma C.S
Let us restate the claim:
Lemma C.5 (Recurrence bound AMOO). Let fralazu be a sequence of non-negative real numbers that satisfy the recurrence relation
r
r
I r
a1 I + a2Tk
1(r002-1)
where 0i [0, 2) and ag R4, Let ko
Then, Th bounded by
α1
rko
k k21 ko
Th S
ro
01 k 4e0
O.W.
27

---

Aligned Multi Objective Optimization
Proof.
We split the proof into two regimes, the incremental convergence and linear convergence regime.
Incremental convergence, rh 1/a2- With this assumption we have + r202 < 2r Then, the following bound
holds:
Tk+1 S Tky 1- a1
20nTk
Recall that vI y 1 2 for every y S Since
1 < 1 have
1. Hence,
a2t
2ngrr
Q1 (1-4c00) Q1 rk
Tk+1 S rk
4ar
402
For every K < the recursive equation is still in the incremental convergence regime. Thus, for every < k holds that TR 1/02-
By solving 1/02 ro / we conclude the maximal iteration after which r 1/a2, namely, after most ki iterates Ta from the incremental convergence regime.
Linear convergence, S 1/a2. With this assumption we have the following bound on the recursive equation:
2 S
r
Further, since for every k' 2 k it holds that TH S Tæ S 1/a2 the recursive equation continues in the linear convergence regime. Thus, after at most ko iterations Th is in the linear convergence regime.
F.4. Proof of Lemma C.6
Let us restate the claim:
Lemma C.6 (Recurrence bound e-AAMOO). Let {rx]a20 be a sequence of non-negative real numbers that satisfy the recurrence relation
r
r
S r
01 1
0's + aaTk:
022
where 01 (0, a2 R4, 03
of
and 04 S
01, 40m""
Let ko
16(roag-1)
Then, T& bounded by
2500
01
Tho
20g
201
k 2 No
<
0102
ro
01 K 1602
O.W.
Proof.
We split the proof into two regimes, the incremental convergence and linear convergence regime.
Incremental convergence, nh 1/a2- With this assumption we have + T&02 < 2r Then, the following bound holds:
Tk+1
+ a4rk a3 a3==
=
r 1
011 2012044
) + 0z S STy/ 402Tk
an Vag.
20z
202rk
The third relation holds since a4 < a, 2 0.
a dag
by assumption which implies 01/2 2 20204 and by va+b S Va + Vb for
Recall that VI y S 1 4/2 for every y S Since
we have
an 1. Hence,
agrk
202r4
2
Tk+1 S Tk (1-
On
+ Vas
an
/a3 S rk
01
80
160g
28

---

Aligned Multi Objective Optimization
since 03 S
256 16 by assumption. For every k' < the recursive equation still in the incremental convergence
regime. Thus, for every k' holds that Tw 1/ag.
By solving 1/a2 ro kyon / /6022 we conclude the maximal iteration after which r& I 1/02, namely, after most An iterates Ta out from the incremental convergence regime.
Linear convergence, Th S 1//22.
With this assumption we have the following bound on the recursive equation:
r a3 as/a2 = (1 01 r +a',
(21)
where a3 a4/02. We will first show that rx S 1/22 for all k' 2 k. Observe that
r - (1 2 2 a + +a's
1
ap
since a' = 03 + The I T 1 1/2 for all 2 k
by assumption and by the fact an E 2). Hence, Th+1 S 02
which inductively implies that
20
2 kp-
Since in this regime, for all K' 2 le Eq. holds, we can upper bound the recursive relation by
S a
(1
ai 2
o' S
r (1
(k1 W
k
20
2
t=
where the last inequality holds by summing the geometric series and since result since
a1/2 E (0, 1). This inequality implies the
2a
Tko (1
203
204
T 1ko
an
a1
Q102
by Va b va+ vb for a, 2 0. Finally, since for every 1/ it holds that ri my S 1/00 the recursive equation
continues in the linear convergence regime. Thus, after at most ky iterations rx is in the linear convergence regime.
F.5. Proof of Lemma
Let us restate the claim:
Lemma D.2 (Continuity of Minimal Eigenvalue of Hessian). Let X E R Further, let w. E arg max Amin (V2 (x))), w
W E
arg max Amin (V2 (x))). It holds that Amin (v) > Amin (V (x)) 2m
WE WEAm. Marin
Proof. To establish the lemma we want to show that for any w E Am there exists W E Am,umin such that Amin (E, W; f(((x) 2 Ami (E, we (xx))) 2m We start by bounding the following term f2 [x) for any x E IR.. By the triangle inequality and the positive homogeneity, we have
2 (x)
S
Σ (ww th
V. six))l2 Σ
Elu di |||[|
8 Σ lwu: -
while the last incquality holds since [fihee are smooth. Since for any E Am there exist w A Am,uaia such that E, |wm dh < 2m we obtain that for every x E I2 it holds that
| v2 = Σ (w ,,)(
< 2mm B.
2
Thus, by using Theorem C.I we obtain that for any w E Am
Amin 2 (x)) Amni (V S fw())
vz
2
By setting w, conclude the result.
29


Reviews:
[{"review_id": "VazVjmKxZB", "reviewer": "Reviewer_V24E", "summary": "This paper study a setting called aligned multi objective optimization (AMOO), which they define as a setting where objectives share a common solution. It studies how aligned multi-objective feedback can improve gradient convergence. The authors propose a framework for AMOO (aligned multi objective optimisation) and provide two ways of aligning multiple objectives, one by using the Hessian (CAMOO) and the other by choosing the Polyak step-size method (PAMOO). The proposed algorithms adaptively weight objectives and offer provably improved convergence guarantees. The proposed methods have been applied on SGD and ADAM and have been compared with the cost function carrying equal weightage. Experimental results show that the ADAM version of CAMOO & PAMOO shows improved convergence than the rest. Lastly, the authors point out that PAMOO is more practical than CAMOO as there is no hessian calculation involved and an approximate solution can be found by taking a few steps of projected gradient descent. The paper also proves robustness of the proposed algorithms for aligned approximately aligned objectives. The authors have experimented with a simulated setting with three loss functions. They have tested with SGD and ADAM as the optimizers of the weighted loss. These results are compared against equal-weights(EW) on the objectives. The variants suggested by the authors achieve betters score as compared to EW baseline.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and recognizing the positive aspects of our work! We will address the questions that were raised in their chronological order.\n\n1. Since prior work did not directly investigate the Aligned Multi-Objective Optimization (AMOO) setting, we focused on comparing our performance to the equal-weights baseline, which is an intuitive algorithmic approach in the multi-objective setting. We also note that recent work showed the equal-weights baseline is competitive compared to other multi-task learning algorithms on multi-task benchmarks (see https://dl.acm.org/doi/pdf/10.5555/3648699.3648908).  We also provided an extensive discussion about prior work on multi-task learning research and prior results are different from ours in Section 2.\n\n2. Thank you for this suggestion! We include here additional results for the approximate AMOO setting in which objectives are only approximately aligned (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub). We will include new results these in the final version of the paper.\n\n3. In this work we focused on foundational work, namely, properly defining the setting, developing intuitive understanding, and theoretically grounded algorithms. Additionally, the empirical investigation we made is already outside the scope of the theory work: we test the new algorithms on non-convex optimization problems, with SGD and ADAM optimizer.  We believe our empirical investigation and open source implementation of the algorithms lay the ground for more extensive empirical investigation in different domains (multi task, LLM, RL, computer vision, etc.).\n\n4. We will explain the results more explicitly for readers' understanding. These results reflect the Mean Squared Error (MSE) metric (that measures distance between current iterate and optimal point) of different algorithms. Interestingly,  PAMOO-ADAM, where the weights are chosen via PAMOO and the optimizer is the ADAM optimizer, has the best performance by a significant margin compared to other alternatives. \n\nAdditional comments: Thank you for these comments, we will adjust the paper accordingly.", "claims_and_evidence": "The claims are supported by experiments on a simulated setting which suffice to show the advantages of the proposed algorithm to the equal weightage (EW) based baseline. The results for the simulated dataset highlight the potential of using GD algorithms designed for AMOO. However, I believe that more empirical evidence for the proposed algorithms could be more convincing. Comparison with more baseline e.g. MGDA based algorithms could be helpful. Involvement of more datasets could also strengthen the results. Empirical evidence on approximately aligned objectives could also strengthen the paper.", "methods_and_evaluation_criteria": "The proposed method and the evaluation criteria does make sense for the mentioned problem.", "theoretical_claims": "Checked proof of theorem 4.2, 5.2 & E.3 in Appendix and seems well written and correct.", "experimental_designs_or_analyses": "The experimental design consists of a simulated data with a setting on three objective functions. The experiments validate the theoretical justification of the proposed using aligned MOO optimizer.", "relation_to_broader_scientific_literature": "The literature on MOO considers multiple objectives in a conflicting sense. There are multiple problems in ML literature which consisting of aligned multiple objectives. Including methods like CAMOO and PAMOO will certainly be useful in a broader perspective.", "essential_references_not_discussed": "References seems to be sufficient, to the best of my knowledge", "other_strengths_and_weaknesses": "Strengths:\n1. The authors have addressed an interesting and novel problem of aligned multiple objective optimization. \n2. A very well-structured and well-written paper. \n3. The paper clearly describes the literature, and the differences between the proposed and existing methods, and the experimental details are easy to follow.\n4. The paper is theoretically strong. \n5. Convergence and robustness to alignment of algorithms have been theoretically established.\n\nWeakness:\n1. Despite writing a rich literature review, the paper misses comparison with other related works, which weakens the experimental section of the paper. \n2. Empirical evidence on approximately aligned multiple objectives will be much appreciated. \n3. Extensive experiments are needed to check the feasibility of these solutions in DNNs with real-world datasets.\n4. Weak results and analysis section of the paper. A more elaborate explanation of the results of the results in Fig 2 will help readers to understand the results in a better way.", "other_comments_or_suggestions": "1. Missing line numbers from the paper. \n2. In algorithm 1, the updation might look like x_{k+1} = x_k - \\eta g_k instead of x_{k+1} = x_k - \\eta g_t", "questions_for_authors": "Please see weakness section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hWeD2z0nG1", "reviewer": "Reviewer_YY6M", "summary": "This paper studies an interesting problem, i.e., aligned multi-objective optimization (MOO) where different objectives could share the same optimal solution. The paper introduces new algorithms for this setting, and provides theoretical convergence guarantees of the new algorithm under convexity assumptions of the objectives.\n\n## update after rebuttal\n\nI increase my score since the authors have addressed most of my concerns. A few suggestions are listed below.\n\n1. It is strongly suggested that the authors include the run time comparison of different algorithms discussed in the rebuttal. \n2. For the discussion on the extension to the nonconvex setting, the key concern I have is that the faster convergence rate of the proposed method compared to fixed weighting is achieved only in the convex setting. In the nonconvex setting, which is more common in modern machine learning, the proposed method generally no longer achieves a faster convergence rate compared to fixed weighting. This limits its practical use. More discussions should be provided.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and recognizing the positive aspects of our work. We appreciate the detailed and useful feedback. \n\nWe wish to mention additional contributions of this work, beyond those that were mentioned in the review:\n\n1. In Section 6 we study the approximate AMOO framework. There we showed that both CAMOO and PAMOO are robust to violations of the alignment assumptions (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub).\n\n2. The implementation of the CAMOO and PAMOO algorithms (see the supplementary material) showcases the feasibility of both algorithms. Additionally, our experiments go beyond the theoretical results when using neural networks with SGD or ADAM optimizers. This implementation allows future researchers to build upon our work and provides evidence for the usefulness of CAMOO and, even more so, of PAMOO, as the empirical results show.\n\nWe will address the comments in their chronological order.\n\nReferences. \nThank you for sharing the references. We will include them in the final draft (we also point out that reference [5] is included in the current draft and mentioned in Section 2).\n\nWeakness (1).\n1. We agree that modern machine learning applications are not well described by a convex optimization framework. Nevertheless, the design of all modern optimization algorithms – SGD, ADAM and many more – is motivated by algorithms from the convex optimization framework. For example, ADAM is intimately related to the AdaGrad algorithm, which is designed for the convex setting (see https://arxiv.org/abs/1412.6980). Similarly, we believe that establishing the correctness of optimizers in the convex optimization framework is useful towards designing practical algorithms.\n\nWeakness Major.\n1. Yes, you are correct and we will add this clarification to the paper. Since there is no tradeoff – by assumption all objectives can be simultaneously optimized – the Pareto front is a point. We provided a formal description of the general setting in Section (3), as well as a more nuanced description in Section (4) (e.g., Proposition (1) is an additional structural result about the setting).\n2. In the specification example, the functions are strongly convex and smooth; for this case, the convergence of GD is (1-\\Delta)^k. We will use this precise description in the text. Thank you!\n\nMinor.\n1. This is one of the interesting findings in the paper in our opinion. The convergence rate does not dependent on $m$, the number of objectives. We will add clarification about this in the caption of Table (1) as it seems it is not properly conveyed to the reader.\n2. We provided a formal definition in the Appendix. We will move it to the main text for improved clarity.\n3. Most practical algorithms in multi-task learning specify different ways for choosing weights to output weighted loss (e.g., \"Multi-task learning as multi-objective optimization\" by Sener et al., \"Conflict-averse gradient descent for multi-task learning\" by Liu et al., and \"Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics\" by Kendall et al.).", "claims_and_evidence": "1. The authors claim that aligned MOO is common for machine learning in modern settings, but they provide a theoretical analysis of convex objectives without connecting the assumptions to some modern machine learning examples.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I mainly checked Appendix B and C and found no errors. Other results also seem reasonable.", "experimental_designs_or_analyses": "No significant issues. \n\nOne minor issue is that the experiments are rather toy, and it is unclear how the experiments connect with modern machine learning in the introduction.", "relation_to_broader_scientific_literature": "Compared to existing MOO works, the paper considers aligned MOO settings rather than the Pareto trade-off settings. \n\nCompared to multi-fidelity optimization, this paper considers gradient-based optimization.", "essential_references_not_discussed": "There are several references that are not accurately referenced or properly discussed.\n\n### MGDA related works\nThe discussion of MGDA related works in Section 2 is not accurate. The first works on MGDA is [1] by Fliege et al., followed by some other works in the stochastic settings, e.g., [2-4].\n\n[1] Jorg Fliege and Benar Fux Svaiter. \"Steepest descent methods for multicriteria optimization,’’ Mathematical methods of operations research, 2000.\n\n[2] Suyun Liu and Luis Nunes Vicente. \"The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning,’’ Annals of Operations Research, 2021.\n\n[3] Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu, \"On the convergence of stochastic multi-objective gradient manipulation and beyond,’’ NeurIPS, 2022.\n\n[4] Lisha Chen, Heshan Fernando, Yiming Ying, Tianyi Chen. \"Three-way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidance,” NeurIPS, 2023.\n\n### Fast algorithms for MOO\nThere are some other algorithms for fast implementation of MOO, which should be discussed and compared. See below.\n\n[5] Ozan Sener, Vladlen Koltun, \"Multi-Task Learning as Multi-Objective Optimization,\" NeurIPS 2018.\n \n[6] Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. \"Famo: Fast adaptive multitask optimization,” NeurIPS, 2023.", "other_strengths_and_weaknesses": "### Strengths\n\n1. The studied problem is very interesting in the aligned MOO setting.\n2. Theoretical results and empirical evaluations are provided.\n\n### Weaknesses\n\n1. The analyzed settings and the experiment settings are rather simple (convex objectives). It is unclear how they relate to modern machine learning. Can the assumptions made in the theoretical results be justified in some modern machine learning examples?\n\n2. The descriptions of the theoretical results lack clarity and can be improved. See details in Questions.", "other_comments_or_suggestions": "No.", "questions_for_authors": "### Major\n\n1. It would be better if the authors first provide a formal definition of aligned MOO, and how it connects to existing works. For example, does it mean that the Pareto front reduces to a single point?\n2. On page 3, the authors discuss the linear convergence rate in $\\Omega(\\Delta)$ for example (i). This is confusing to me. As far as I know, $\\Delta$ does not affect the convergence rate depending on the number of iterations, but it will affect the constant ratio in the convergence or optimization error bound. The discussion of convergence in $\\Omega(\\Delta)$ should be clearly defined and explained.\n\n\n### Minor\n\n1. Where is $m$ in Table 1?\n2. In Theorem 6.2, what is \"self-concordant\"? Please move the definition in the appendix to the main text.\n3. On Page 3, second column, \"Existing algorithms suggest alternatives for choosing w\", could you add some references to support this and add discussions on which paradigm you use?\n\nI will consider raising my score if the questions and weaknesses above are properly addressed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5iCWD5LFZR", "reviewer": "Reviewer_ZyHT", "summary": "The paper introduces Aligned Multi-Objective Optimization (AMOO), addressing scenarios where multiple objectives share a common solution. Traditional MOO focuses on conflicting objectives, but here, aligned objectives enable simultaneous optimization. The authors propose CAMOO (curvature-aware weighting) and PAMOO (Polyak step-size-inspired weighting), both adaptively combining gradients. Theoretical guarantees show improved convergence rates over naive methods, with rates depending on problem-specific curvature parameters.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your interest in this work and the questions you raised! We will address them in their chronological order.\n\n1. We will make the local curvature example figure clearer – thank you for pointing this out!\n\n2. We provided results on inaccuracy of $f_i(x_{\\star})$ in Section 6, where we assume the multi-objectives are only approximately aligned (we derived two results, one for the PAMOO and one for CAMOO algorithms). We conducted additional experiments, for providing additional empirical evidence, for the approximate AMOO to be included in the final version of the paper (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub). Lastly, we note several prior works explored the question on designing gradient-descent based methods in which the learning rate is chosen via a Polyak method and the optimal value of a function is estimated adaptively (Hazan and Kakade 2019, Gower et al., 2021; Orvieto et al., 2022). We believe that generalizing these to the AMOO setting is a fertile ground for future research work, which we also mentioned in the main text.", "claims_and_evidence": "Claims are supported by theory (Theorems 4.2, 5.2) and experiments. The convergence analysis assumes self-concordance and smoothness, with proofs outlined in appendices. And Theorem 6.2 addresses approximate alignment.", "methods_and_evaluation_criteria": "Methods are sensible: CAMOO uses Hessian-based curvature, PAMOO leverages Polyak steps. Evaluation uses synthetic alignment scenarios (specification, selection, curvature) and a neural network matching task. Maybe broader benchmarks (e.g., standard multi-task datasets) can help to assess its practical impact.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Experiments validate CAMOO/PAMOO on synthetic tasks. Missing are tests on standard multi-task benchmarks and non-convex settings.", "relation_to_broader_scientific_literature": "Connects well with multi-task learning (MTL) and MOO literature (e.g., MGDA, PCGrad), differentiating via aligned objectives.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "The local curvature example (Figure 1) could benefit from clearer visualization.", "questions_for_authors": "For PAMOO, how does inaccuracy in $f_i(x_*)$ affect performance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s255Z2qNNB", "reviewer": "Reviewer_54gT", "summary": "This paper focuses on multi-objective optimization (MOO). Differently from the typical MOO studies that focus on dealing with conflicts among objectives, this paper considers a so-called aligned MOO settings, where objectives align well with each other and no conflict occurs. This paper wants to develop methods that are able to improve aligned MOO from an optimization perspective. More specifically, the authors assume all objectives have the same optimal solution. In the meanwhile, three toy examples are provided to illustrate that a careful weight selection should be provided to achieve faster convergence as well as better scalability. As motivated by these findings, the authors first propose CAMOO by exploiting the so-called global adaptive strong convexity (it also guarantees the unique solution that minimizes all objectives). A convergence analysis is provided under a self-concordant assumption. Secondly, the authors  follow the similar idea from CAMOO, but choose the weight vector based on Polyak stepsizes, and propose PAMOO, which requires only gradients rather than Hessians as in CAMOO. The analysis is provided given the local strong convexity assumption (made at x* rather than any x).", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and recognizing the positive aspects of our work. We appreciate the detailed and useful feedback. We will address the questions in their chronological order.\n\n1. In Section 6 – where we generalize AMOO to approximate AMOO – we are not assuming a unique minimizer for all objectives. In addition, the linear convergence without dependence on the number of objectives is not natural; for example, if one chooses the weights to be uniform (1/m), the linear convergence depends on the number of objectives. Since this wasn't clear, we will add a section in the appendix that demonstrates this. Also, see section B in the appendix.\nFurther, we believe that this work offers a new and rigorous perspective on the multi-task setting that becomes increasingly important in machine learning applications (e.g., in LLMs and RL research practitioners often use multiple reward functions or datasets).\n\n2. It is a good question, thanks for raising it. Yes, in Section 6 we provide results for the setting in which functions are only approximately aligned, and show CAMOO and PAMOO both converge to an approximately optimal point for all objectives. The additional experiments we attached to the rebuttal corroborate these theoretical findings (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub).\n\n3. We agree that CAMOO is less practical compared to PAMOO. However, such an algorithm is very natural for the AMOO setting, given the intuition we provide in Figure 1, and gives useful intuition that may help deriving algorithmic improvements. Additionally, as the open source implementation we shared showcases, it is possible to make use of modern approaches for Hessian estimation (e.g., Hutchinson method) for implementing such an approach.\n\n4. Our work focused on foundational work: formulating the AMOO setting, developing intuition and providing new algorithms with provable guarantees for the setting, as well as showing these algorithms are robust to the alignment assumption. The code we share with the research community showcases the feasibility of implementing the algorithms. We believe the next step of our work is conducting large-scale experiments in different domains (e.g., LLM, RL and computer vision) while also developing the theoretical foundations of the AMOO setting.\n\n5. We also believe the stochastic setting is of interest and importance. Due to the significant contributions this work has put forward (see response to question 4) we believe such extension is proper for future work. We will expand the existing discussion on such a future extension further (see the Conclusions section) to highlight the importance of this direction. Thank you for raising this point.", "claims_and_evidence": "Yes, most claims are clear to me.", "methods_and_evaluation_criteria": "There are not enough experiments to validate the proposed algorithms. Only synthetic datasets are provided.", "theoretical_claims": "I checked some proofs, and they look good to me.", "experimental_designs_or_analyses": "There are not enough experiments to validate the proposed algorithms. Only synthetic datasets are provided. More large-scale datasets and models need to be tested. In addition, the efficiency of the methods should be analyzed.", "relation_to_broader_scientific_literature": "Study aligned MOO rather than previous works on MOO with conflicts.", "essential_references_not_discussed": "No key references are missing, but some discussions on related works with convergence analysis of MOO should be provided. I suggest three important ones in the 'Other Strengths And Weaknesses'", "other_strengths_and_weaknesses": "Strength:\n\n1.\tAligned MOO has not been well studied and understood, the authors start this problem from an interesting optimization perspective. The toy examples present the high-level ideas, which are easy to understand.\n\n2.\tThe proposed methods that utilize either global or local strong convexity (for weighted average of objectives) are interesting and the linear convergence result makes senses. The analysis seems to be nontrivial by developing a inequality that follows from the self-concordance property.\n\n3.\tTwo practical versions are provided for large-scale applications.\n\nWeakness:\n\n1.\tAlthough studying aligned cases is important, the problems studied in this paper seems to oversimplify the problem. For example, the assumption that all objectives share the same unique minimizer might be hard to hold in practice. Perhaps some experiments could be provided to support this assumption. In addition, the global adaptive strong convexity requires to hold for any x and requires the existence of weights to ensure the strong convexity. This is also very restrictive. The self-concordant condition is also strong. In other words, although the theoretical results are encouraging (linear convergence without dependence on objective number), the results seem to be more natural under these additional assumptions. \n\n2.\tFollowing the previous point, I want to understand if the results hold, that says, when the assumptions are partially satisfied? For example, we can assumption only a subset of objectives satisfy these conditions, whereas for others, conflict could happen. Or the authors can think about more practical settings, where the assumptions could be justified. \n\n3.\tCAMOO is not practical. Computing the Hessian matrices and their smallest eigenvalue in each iteration can introduce non-trivial computional and momery cost. Thus, to me, PAMOO makes more sense as it uses only gradients. However, for PAMOO, solving argmax over w in each iteration K is not efficient, due to the O(K) cost in computing and storing the Jacobians (matrix of individual gradients). Although Section 5.1 discusses the practical implementation, e.g., running several steps of PGD, I am wondering how many steps to choose? If a similar convergence analysis can be developed for this practical version? \n\n4.\tThe experiments are not convincing. Only simple synthetic experiments are provided. More experiments on large-scale MTL or MOO applications and real-world datasets should be provided.\n\n5.\tThe paper focuses on GD. I wonder can the analysis be extended to stochastic settings. The following three important papers on the convergence  analysis of stochastic MOO could be helpful. I suggest a discussion could be provided.  \n\n(1)\tThe stochastic multi-gradient algorithm for multi-objective  optimization and its application to supervised machine learning  \n\n(2)\tMitigating gradient bias in multi-objective learning: A provably convergent approach.\n\n(3)\tDirection-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms", "other_comments_or_suggestions": "See 'Other Strengths And Weaknesses'.", "questions_for_authors": "See 'Other Strengths And Weaknesses'.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces Aligned Multi-Objective Optimization (AMOO), addressing scenarios where multiple objectives share a common solution. Traditional MOO focuses on conflicting objectives, but here, aligned objectives enable simultaneous optimisation. The authors propose CAMOO (curvature-aware weighting) and PAMOO (Polyak step-size-inspired weighting), both adaptively combining gradients. Theoretical guarantees show improved convergence rates over naive methods. 

The reviewers have mixed feelings about the paper: while they agree that the Aligned Multi-Objective Optimization is  reasonably motivated in practice. There were concerns:  1) the analysis is restricted to the convex which might be not well connected to modern machine learing tasks; 2)  the experiments are rather toy. 

Nevertheless, all the reviewers agree that the paper considered  an interesting problem and the algorithms were theoretically and empirical proved to be useful in certain settings.
Decision: Accept (poster)