Preference Optimization on Pareto Sets: On a Theory of Multi-Objective Optimization

Thank you to Reviewer i8uk for taking the time to review and for the detailed feedback. It seems that the reviewer found the theoretical contributions strong, but raises concerns about the applicability to practical multi-objective settings such as for LLM fine-tuning, specifically because of (a) strong convexity assumptions, (b) how sample complexity scales with different parameters of the problem, and (c) the computational costs of solving the inner optimization problem.

Main contributions: theoretical vs. practical

We agree that this work’s main contributions are theoretical, although practical problems such as LLM fine-tuning serves as a key motivation for our framework. But, in developing a principled approach, we found the problem to be highly non-trivial due to the non-convexity, non-smoothness, and the implicit nature of the constraint set (even when the objectives are simply quadratics). We greatly simplify the problem conceptually.

Prior to our work, there were only heuristics for this problem. The literature lacked a proper definition of stationarity and algorithms with provable behavior. Actually, intuitive heuristics easily go wrong. We proved that there is a large class of very natural stationary conditions—including one in existing literature, and another we had initially considered—that will reject the true preference-optimal solution. Practically, this means that the prior algorithm in literature provably avoids the correct solution, even in the strongly convex setting!

In contrast, our work is the first to establish a well-justified solution concept that is efficiently and provably achieved by a simple algorithm, under two forms of feedback. The issue of practicality, especially in the context of LLM fine-tuning, is certainly a valid one, but also in a sense beyond the scope of this work: each of the goals of going beyond non-convexity, significantly improving sample complexity, reducing computational complexity are quite non-trivial and can be papers in themselves (indeed, we are currently pursuing these directions, and know of other groups doing so). We believe that our work already makes a significant and meaningful contribution to the literature, and that it provides a solid theoretical foundation upon which to develop algorithms achieving the above goals. As the reviewer puts it, this work already presents quite a "dense" set of results.

Of course, we welcome differences of opinions from the reviewer, but if so, we would really appreciate it if the reviewer would also articulate more specifically what remaining results would make this work ready for publication.

In the following, we respond to more specific points.

Generalization to non-convex objectives

Extending to the non-convex setting is definitely an important future direction, and one we’ve found to be quite interesting and challenging. Some challenges:

1. Without strict convexity, linear scalarization can miss out on Pareto optimal solutions: not every Pareto solution $x^*$ is a (local) minimizer of $f_\beta$ for some convex combination $\beta \in \Delta^{n-1}$ of the objectives.

2. In fact, the Pareto optimal points can unintuitively even correspond to local maximizers of $f_\beta$! This can happen even if the objectives are quasiconvex (thus, not non-convex in an arbitrary way; an example below).

3. And if the objectives are arbitrarily non-convex, we also lose the diffeomorphism between the Pareto manifold and the simplex (though local diffeomorphisms may remain).

We have some ideas and are pursuing this direction, but it would probably be better to present results there in a separate paper.

Example of Pareto optimal point that is a local maximizer. Let $q_1, q_2 : \mathbb{R} \to \mathbb{R}$ be the quadratics $q_1(x) = (x - 1)^2$ and $q_2 = (x + 1)^2$. And let us aim to minimize the objectives $f_1, f_2 : \mathbb{R} \to \mathbb{R}$, where $f_i = \sigma \circ q_i$, and $\sigma$ is any strictly monotonic increasing function. Then, the Pareto set of $(f_1, f_2)$ coincides with the Pareto set of $(q_1, q_2)$, which is the interval $[-1, 1]$.

Consider $\sigma(z) = \exp(z/T)$, where $T > 0$ is some temperature parameter. For sufficiently small $T$, the Pareto optimal solution $x = 0$ will be the local maximizer of the weighted objective $\frac{1}{2} f_1 + \frac{1}{2} f_2$.

Computational cost of inner solve and practical heuristics

At least under our setting of strong convexity and Lipschitz smoothness, the cost of the inner solve is dimension-independent, with linear convergence rate. Moreover, our convergence analysis for the PMM algorithm quantifies how accurately the inner solve needs to be to achieve a target approximation error. In particular, to obtain $\epsilon$-approximate preference stationarity, Theorem 9 shows that it is sufficient to optimize the inner objective $f_\beta$ to approximate stationarity $\| \nabla f_\beta(\hat{x})\| < O(\epsilon)$. This takes around $O(\log \frac{1}{\epsilon})$ steps of gradient descent.

Improving sample efficiency in dueling feedback setting

We agree that a very practically-motivated problem is how to increase sample complexity of preference optimization under dueling feedback. Currently, we do not know how suboptimal the dependence on dimension is, nor on other parameters such as $\epsilon_0$. It would be of great interest to explore how to reduce these dependencies or to show that in fact they are necessary. Still, this work is the first to obtain meaningful convergence guarantees under either forms of feedback.

Relationship to prior works

Thank you for sharing these references to other works; we can contextualize our work among them. Classically speaking, methods in multi-objective optimization can be categorized as a priori, a posteriori, and interactive.

In a priori methods, the decision maker knows beforehand what their preference is, and the role of the MOO algorithm is to find the most-preferred Pareto-optimal solution. The bulk of our work falls under this category, with the exception of the section on dueling feedback, which is more interactive. The reference [6] is of this type, but their focus is on introducing one specific preference function motivated from game theory.

In a posteriori methods, the decision maker needs to first learn the Pareto set before deciding on their preference/making the final decision. In this case, the role of the MOO algorithm is to approximate the whole Pareto set. That is, to provide a shortlist of Pareto optimal options that would satisfy a wide variety of preferences of a downstream decision maker. The references [1,2,3,5] listed above fall under this category. (We do not operate under this setting).

And interactive methods are in between, where the decision maker repeatedly interacts with the MOO algorithm, where both can refine their search and preferences over time. Our section on dueling feedback is of this form, and so is the reference [4] provided. However, the goals are somewhat different. We aim to recover the most preferred solution, while [4] aims to sample a diverse set of solutions from the Pareto set related to a user-specified distribution/prior over solutions.

Thank you for your careful review and detailed feedback. We will especially take into account where it seems that the writing was unclear and improve our exposition. Besides that, there were two consistent concerns: (1) relationship/comparison to prior work, (2) practicality. We first address those now, before answering specific questions below.

Response to main concerns

Relationship to prior work/comparison with other methods

Thank you for sharing the related works. We are indeed familiar with [1], but it turns out that a comparison with [1] is not very meaningful. While [2] does consider a similar setting to us, there are no convergence guarantees provided for the proposed algorithms. [3] follows up on [1] and is also quite interesting; it was concurrent with our NeurIPS submission, but we will update our related works going forward. Besides these, the most related work to our setting is the PNG algorithm (Ye and Liu 2022), against which we theoretically compare in Appendix D.1.

Out of all of these references prior to our work, there were only heuristics for this problem. The literature lacked a proper definition of stationarity and algorithms with provable behavior. Actually, intuitive heuristics easily go wrong. We proved that there is a large class of very natural stationary conditions—including the one found by the PNG algorithm—that will reject the true preference-optimal solution. This means that the prior algorithm in literature provably avoids the correct solution, even in the strongly convex setting!

In contrast, our work is the first to establish a well-justified solution concept that is efficiently and provably achieved by a simple algorithm, under two forms of feedback. Theoretically, there is nothing to compare against. And since we proved that the closest prior algorithm in literature converges to the wrong solution, it is also not meaningful to compare against them experimentally.

Practicality: strongly convex objectives and second-order information

We agree that many practical problems have objectives that are not strongly convex. Indeed, such problems, such as LLM fine-tuning, serves as a key motivation for our framework. But, in developing a principled approach, we found the problem to be highly non-trivial due to the non-convexity, non-smoothness, and the implicit nature of the constraint set (even when the objectives are simply quadratics). Here, we have found that even the strongly convex setting is already theoretically very rich, and that it has helped us to significantly deepen our understanding of the nature and challenges of multi-objective optimization.

And so while our main contributions are theoretical, we believe they are still of significance to the multi-objective optimization community, as we have greatly simplified the problem conceptually. We believe this may help researchers avoid the same pitfall as the PNG algorithm (which we also initially fell into). Additionally, we have already shared this work with part of the community (non-archival), and know of other groups that are developing further results on top of this.

Specifically regarding strong convexity, we are already working on extending these results to the non-convex setting, and we’ve found it to be quite interesting and challenging (see also our response to Reviewer 9L4B). And on second-order information, we have shown that second-order information is necessary. However, we are hopeful that there are computationally-efficient estimators (e.g. using ideas from [I,J]), and we are currently working on this as well.

The completion of either of these results would arguably be substantial enough to be published in separate papers; this paper is already packed with many results. We believe that our work already makes a significant and meaningful contribution to the literature, and that it provides a solid theoretical foundation upon which to develop algorithms that work under less restrictive conditions, and that are more sample and computationally efficient.

Of course, we welcome differences of opinions from the reviewer, but if so, we would really appreciate it if the reviewer would also articulate more specifically what results would be needed to make this work ready for publication.

Specific questions

Computation complexity

The iteration complexity and the convergence rate of our algorithm, $K \leq \frac{2 \mu_g\cdot \big(f^* - f_*\big)}{ c_1^2 \cdot \epsilon_0^2}$, are provided for the first-order feedback in Theorem 9 (page 8) and for the dueling feedback in Theorem 10 (page 9). The proofs of the theorems are provided in Appendix G and Appendix H.2 respectively.

Clarification for Section 6.3

What are $u_i,d,b,\gamma$?

In (16), {$u_i$}$_{i=1}^b$ are $b$ unit vectors chosen uniformly at random from the unit sphere $S^{d-1}$ where $d$ is the ambient dimension of the space - same as introduced in Section 2. $\gamma>0$ is a scalar. We will update this notations in the final version.

Equation (16).

Under zeroth-order feedback, i.e., when only $f_0(x)$ can be computed, one has the following gradient estimator:

$\tilde{\nabla} f_0(x)=\frac{d(f_0(x+\gamma u)-f_0(x-\gamma u))}{2\gamma}u,$

where $u\in S^{d-1}$ is chosen uniformly at random. Then, $\|\mathbb{E}[\tilde{\nabla} f_0(x)]-\nabla f_0(x)\|_2=O(d\gamma)$, which is small for small enough $\gamma$.

So estimating $\nabla f_0(x)$ only requires estimating function value differences which is implicitly encoded in the preference model. If $\mathbb{E}[Y(x+\gamma u, x-\gamma u)]$ were known, one has

$f_0(x+\gamma u)-f_0(x-\gamma u)=\sigma^{-1}(\mathbb{E}[Y(x+\gamma u,x-\gamma u)]).$

Estimating $\nabla f_0(x)$ reduces to estimating $\mathbb{E}[Y(x+\gamma u, x-\gamma u)]$, the mean of a Bernoulli random variable. A natural estimator is the empirical average

$\tilde{p} = \frac{1}{m} \sum_{j=1}^m q_j(x,u), \quad \text{where } q_j(x,u) = Y_j(x+\gamma u, x-\gamma u),$

interpretable as averaging the feedback from querying $m$ independent individuals for preferences between two points. The caveat is that for common preference models, $\sigma^{-1}(x)$ becomes unbounded as we approach $x = 0,1$ (e.g., Bradley–Terry with $\sigma^{-1}(x) = \log(x/(1-x))$). So we apply clipping:

$\hat{p} = \max(\alpha, \min(\tilde{p}_{x+\gamma u, x-\gamma u}, 1 - \alpha)).$

Here, $\alpha$ is chosen so that clipping error is balanced with the approximation error in $\mathbb{E}[\tilde{\nabla} f_0(x)]$ and the stochastic error $\text{err}_{\nabla f_0}$. This leads to the following estimator:

$\tilde{\nabla} f_0(x) = \frac{d}{2\gamma} \sigma^{-1}\left( \hat{p}_{x+\gamma u, x-\gamma u} \right) u.$

Now, to approximate $\mathbb{E}[\tilde{\nabla} f_0(x)] \approx \nabla f_0(x)$ (with error $O(d\gamma)$ ), we average over $b$ i.i.d. directions {$u_i$}$_{i=1}^b$, and arrive at (16):

$\hat{\nabla} f_0(x) = \frac{d}{2\gamma b} \sum_{i=1}^b \sigma^{-1}\left( \hat{p}_{x+\gamma u_i, x-\gamma u_i} \right) u_i.$

We plan to improve the intuition in the final version.

Assumption D.

Our preference model (Definition 5) assumes that the binary variable $Y(x_1, x_2)$ satisfies $\mathbb{E}[Y(x_1, x_2)] = \sigma(f_0(x_2) - f_0(x_1))$. The query points $x_1, x_2$ are non-random, so no distributional assumption is imposed on them. Characterizing the preference model reduces to specifying assumptions on $\sigma$, as in Assumption D.

Choice of link function

The choice of preference function is problem-specific. Our goal, however, is not to model preferences but to provide an algorithm for Pareto-constrained optimization which can be used as black-box by an user with any preference model (Definition 5) they may choose. As long as Assumption D holds—which is true for common models like logistic, softplus, and tanh—our algorithm converges at the rate stated in Theorem 10, ensuring broad applicability. However, some common preference models include Logistic (Bradley-Terry)/Softmax [A,B,C,D,E] and Tanh [F,G,H].

Lipschitz constant

By $L_\sigma (1 + (x(1 - x))^{-1})$-Lipschitz continuity, we mean that $\sigma^{-1}$ is locally Lipschitz, but we agree that this can be made less confusing. More precisely, we assume $\left| \frac{d}{dx} \sigma^{-1}(x) \right| \leq C(1 + (x(1 - x))^{-1})$ for some constant $C > 0$, which implies via the mean value theorem:

$|\sigma^{-1}(x) - \sigma^{-1}(y)| \leq L_\sigma \left(1 + \frac{1}{x(1 - x)} + \frac{1}{y(1 - y)}\right) |x - y|$

for some $L_\sigma > 0$. This is the bound used in Lemma 1 (Appendix H), and we will revise the terminology in the final version.

Definition of $\widehat{\mathrm{argmin}}$

The operator $\widehat{\arg\min}$ denotes the approximate minimizer from the black-box optimizer referenced in Theorem 9. As discussed in Section 6.1 and Remark 2, this can be any suitable off-the-shelf optimizer suitable, including (projected) gradient descent. We will clarify this in the paper.

[A]Maystre et.al, "Choicerank: identifying preferences from node traffic in networks." ICML 2017. [B]Chu et.al, "Preference learning with Gaussian processes." ICML 2005. [C]Hunter, "MM algorithms for generalized Bradley-Terry models." AOS 2004. [D]Chen et.al, "Pairwise ranking aggregation in a crowdsourced setting." ICWDM 2013. [E]Ouyang et.al, "Training language models to follow instructions with human feedback." NeurIPS 2022. [F]Orlando, "A discrete mathematical model for chaotic dynamics in economics: Kaldor’s model on business cycle." MCS 2016. [G]Tuev et.al, "Using modified hyperbolic tangent function to approximate the current–voltage characteristics of field–effect transistors." Tomsk Polytechnic University, 2009. [H]Giulio. "Power Exhaust Data Analysis and Modeling of Advanced Divertor Configurations." 2018. [I]Huang et.al, "Efficiently escaping saddle points in bilevel optimization." JMLR 2025. [J]Kwon et.al, "A fully first-order method for stochastic bilevel optimization." ICML 2023.

Dear Reviewer,

Since the discussion period is nearing the end, we wanted to make sure that our response fully addresses your questions. If you have any further questions/concerns we would love to address that. If we have answered your questions satisfactorily, please let us know.

Best, Authors

Thank you for taking the time to write this detailed review and response. Regardless of outcome, we really appreciate how sincerely you have approached reviewing.

Prior work. Yes, we are quite aware that, except for the section on preference feedback, the results we present are extremely close to [1]. But to reiterate, it is not meaningful to compare ourselves to [1]. We cannot be more specific, but we can reassure the reviewer that the contents of our submission has never been published before at a conference/journal. And that prior to our work, there was no algorithm to our knowledge that obtained provable convergence. As we mentioned before, [3] was concurrent with our NeurIPS submission, following up on [1].

Thank you for sharing those additional references. Unfortunately, we aren’t able to provide a proper comparison here, since there isn’t enough time between receiving your comments and the end of the discussion period. But, we agree that it is definitely worthwhile to update our related work section, and we will do so.

Having quickly looked through these additional references, it does not seem that our claim that we provide the first algorithm with provable convergence is wrong. It will take more time to understand the relationship between prior notions of stationary conditions, and we will be careful not to overclaim in the paper (perhaps the claim in the rebuttal was too broad). In any case, we do believe that our definition of approximate preference stationarity (Definition 5) still makes a meaningful contribution: Proposition 6 shows that it has provable optimization-theoretic meaning, and Lemma 7 shows that it can be verified using approximate information (one does not need to exactly solve the lower level optimization problem to know whether it has been achieved). This latter point is important in terms of “usability” of the solution concept. Another aspect of our contribution regarding the solution concept is that we showed the insufficiency of first-order information, helping to explain why second-order terms appear in this notion of stationarity.

Experiments. Regarding experiments, we will include them in revisions (and other reviewers also asked for this). We have run toy experiments (and they reflected the behavior we proved: PNG converges to the wrong solution). But we agree that it is more convincing and helpful to visualize them, and that these experiments can help readers obtain an intuition about what our algorithm is doing.

Preference feedback section. Again, thank you for pointing out where we needed to improve the presentation. Hopefully, our rebuttal above helped clarify those definitions for you here? We will make that section more readable and make sure everything is clearly defined in the revisions.

Summary: At a high level, it seems that there is no issue concerning the importance of the problem, theoretical soundness, nor completeness of results. The main concerns are (a) whether our work is novel, (b) connection to related work, (c) providing experiments, and (d) improving clarity for the preference section.

We do believe our work (a) makes new and fundamental contributions to multi-objective optimization, and are aware of the works the reviewer has cited, and that other groups are already developing on top of our work. For the remaining critiques (b,c,d), we completely agree: we will iron out the specific relationship to past works/ideas, include experiments, and improve clarity. Since there isn’t a need to develop new results, these are all definitely doable by the deadline for final revisions. We would love to be able to publish our results sooner than later, and not wait for the next publication cycle. If this is adequate, we would really appreciate a positive score. In any case, thank you again for the time for giving us this feedback.

Thank you for your careful and positive review.

Generalization to non-convex objectives

Extending to the non-convex setting is definitely an important future direction, and one we’ve found to be quite interesting and challenging. Some challenges:

1. Without strict convexity, linear scalarization can miss out on Pareto optimal solutions: not every Pareto solution $x^*$ is a (local) minimizer of $f_\beta$ for some convex combination $\beta \in \Delta^{n-1}$ of the objectives.

2. In fact, the Pareto optimal points can unintuitively even correspond to local maximizers of $f_\beta$! This can happen even if the objectives are quasiconvex (thus, not non-convex in an arbitrary way; an example below).

3. And if the objectives are arbitrarily non-convex, we also lose the diffeomorphism between the Pareto manifold and the simplex (though local diffeomorphisms may remain).

We have some ideas and are pursuing this direction, but it would probably be better to present results there in a separate paper.

Example of Pareto optimal point that is a local maximizer.

Let $q_1, q_2 : \mathbb{R} \to \mathbb{R}$ be the quadratics $q_1(x) = (x - 1)^2$ and $q_2 = (x + 1)^2$. And let us aim to minimize the objectives $f_1, f_2 : \mathbb{R} \to \mathbb{R}$, where $f_i = \sigma \circ q_i$, and $\sigma$ is any strictly monotonic increasing function. Then, the Pareto set of $(f_1, f_2)$ coincides with the Pareto set of $(q_1, q_2)$, which is the interval $[-1, 1]$.

Consider $\sigma(z) = - \exp(- z/T)$, where $T > 0$ is some temperature parameter (the objectives $f_i$ look like upside-down Gaussians). For sufficiently small $T$, the Pareto optimal solution $x = 0$ will be the local maximizer of the weighted objective $\frac{1}{2} f_1 + \frac{1}{2} f_2$ (which looks like an upside-down mixture of Gaussians).

Visualization of algorithm/comparison with prior definitions of stationarity

We agree that visualizing the algorithm would be helpful, especially in helping demonstrate the issues with earlier definitions of stationarity. We will update the paper with experiments and visualizations.

Impact of (anti)-correlation across objectives

Our convergence guarantees are independent of the correlation across objectives. While we’re not ruling out the possibility that (anti)-correlation can have some effect on convergence speed, from our analysis, it seems that the more fundamental quantities are the condition number of Hessians $\nabla^2 f_i$ for each of the objectives.

In fact, in the extreme zero-sum setting, where two objectives are perfectly anti-correlated $f_1 = - f_2$, every point is Pareto optimal. In that case, the preference optimization over the Pareto set is “easy” since it becomes an unconstrained optimization problem (of course, this example is excluded from our setting since we require all objectives to be strongly convex).

In any case, we think this is a good type of question to pursue and refine in further research, since the goal of multi-objective optimization is to provide guidance on how to navigate conflicting objectives.

Thank you. We appreciate it.

Authors

Thank you to Reviewer H4W1 for taking the time to review and for the detailed feedback. It seems that the reviewer found the problem we study well-motivated, but is mainly concerned about the practicality of the setting we study theoretically. We address this first, and more specific concerns below.

Main contributions: theoretical vs. practical

We agree that this work’s main contributions are theoretical, although practical problems such as LLM fine-tuning serves as a key motivation for our framework. But, in developing a principled approach, we found the problem to be highly non-trivial due to the non-convexity, non-smoothness, and the implicit nature of the constraint set (even when the objectives are simply quadratics). We greatly simplify the problem conceptually.

Prior to our work, there were only heuristics for this problem. The literature lacked a proper definition of stationarity and algorithms with provable behavior. Actually, intuitive heuristics easily go wrong. We proved that there is a large class of very natural stationary conditions—including one in existing literature, and another we had initially considered—that will reject the true preference-optimal solution. Practically, this means that the prior algorithm in literature provably avoids the correct solution, even in the strongly convex setting!

In contrast, our work is the first to establish a well-justified solution concept that is efficiently and provably achieved by a simple algorithm, under two forms of feedback. The issue of practicality, especially in the context of LLM fine-tuning, is certainly a valid one. But, we believe that our work already makes a significant and meaningful contribution to the literature, and that it provides a solid theoretical foundation upon which to develop algorithms that work under less restrictive conditions, and that are more sample and computationally efficient.

Question 1: concrete examples of objectives

Portfolio optimization

Let $x=[x_1, x_2, \cdots, x_n]^\top$ and let $\Sigma\in\mathbb{R}^{n\times n}\succ \mu I$ ($\mu>0$), i.e., $\Sigma$ is positive definite.

Consider the objectives: uncertainty regularized expected return $f_a(x)=-\sum_{i}r_ix_i+ x^\top \Sigma x$ (In your notation $-f_1+f_2$, the minus sign is needed as we are minimizing)[1], and the quadratic transaction cost $f_b(x)=\|x-x_p\|_2^2$ [2,3]. $\nabla^2 f_a(x)=\Sigma\succ \mu I$, and $\nabla^2 f_b(x)=I\succ I$.

Then, the norm of Σ is bounded as $\sigma_{ij}$ are constants. Since, $\nabla^2 f_a(x),\nabla^2 f_b(x)$ are constants it satisfies Assumption B. Since Assumption C is on $f_0$, we address it in our answer to your Q2.

Classification with sub-populations

Consider classification using regularized logistic regression where the population has $k$ subpopulations, i.e., $(x_j^i,y_j^i) \sim D_i$ for $j = 1,\ldots, n$ where $D_i$ is the data distribution of the $i$-th subpopulation. This is a $k$ objective MOO where $f_i(\theta)=\frac1n\sum_{j=1}^n\log (1+\exp(-y_j^i{x_j^i}^\top\theta))]+\|\theta\|_2^2$, $i=1,\cdots,k$. Then, $(2+m_2^i)I\succ \nabla^2f_i(\theta)\succ 2I$ which implies Assumption A, and $\nabla^2 f_i(\theta)$ is $0.1m_3^i$-Lipschitz continuous implying Assumption B where $m_2^i,m_3^i$ are 2nd and 3rd sample moments of the $i$-th population.

[1]DeMiguel et. al., "Optimal versus naive diversification: How inefficient is the 1/N portfolio strategy?." The review of Financial studies 22, no. 5 (2009): 1915-1953.

[2]Chen et. al., "A note on portfolio optimization with quadratic transaction costs." arXiv preprint arXiv:2001.01612 (2020).

[3]DeMiguel et. al., "Multiperiod portfolio optimization with general transaction costs." Available at SSRN (2013).

[4]Han et. al., "Merton’s portfolio problem under Volterra Heston model." Finance Research Letters 39 (2021): 101580.

[5]Tong et. al., "A smoothing method for solving portfolio optimization with CVaR and applications in allocation of generation asset." Applied Mathematics and Computation 216, no. 6 (2010): 1723-1740.

[6]Zafar et. al., Fairness Beyond Disparate Treatment & Disparate Impact (2017).

Question 2: Concrete examples of preferences

Portfolio optimization

Several popular preference function $f_0$ choices satisfy Assumption C:

1. Constant Relative Risk Aversion in Merton’s portfolio problem, $f_0(x)=\frac{1}{\gamma}\exp(-x^\top r)$, $\gamma>0$ [4].

2. Smoothed version of Conditional Value-at-Risk (CVaR) $f_0(x) = \min_{\zeta \in \mathbb{R}} \{ \zeta + \frac{1}{\alpha} \mathrm{E} [ \phi(-x^\top r - \zeta) ] \}$ where $\phi(u) = \frac{1}{\beta} \log(1 + e^{\beta u})$[5].

Classification with sub-populations

There are several social utility functions that satisfy Assumption C:

1. User-defined social utility for public policy making $f_0 = \sum_{i=1}^n w_i^* f_i(\theta)$ where $w_i^*$ for $i = 1,\ldots, k$ are a given set of weights.

2. Demographic parity fairness $f_0(\theta)=\mathrm{E}[(z-E(z))(\sigma(\theta^\top x)-E(\sigma(\theta^\top x)))]$ where $\sigma(\cdot)$ is the logit function [6].

Question 3: practicality of assumptions

We agree that it is of practical importance to extend our work to less restrictive settings, especially to non-convex objectives. However, this criticism can in a sense be leveled against the whole field of (single-objective) convex optimization. But, as it is with convex optimization, here we have found that even the strongly convex setting is already theoretically very rich, and that it has helped us to significantly deepen our understanding of the nature and challenges of multi-objective optimization.

We are already working on extending these results to the non-convex setting, and we’ve found it to be quite interesting and challenging (see also our response to Reviewer 9L4B for specifics). We believe that the completion of those results would be substantial enough to be published in a separate paper; this paper is already packed with many results.

Of course, we welcome differences of opinions from the reviewer, but if so, we would really appreciate it if the reviewer would also articulate more specifically what results would be needed to make this work ready for publication.

Dear Reviewer,

Since the discussion period is nearing the end, we wanted to make sure that our response fully addresses your questions. If you have any further questions/concerns we would love to address that. If we have answered your questions satisfactorily, please let us know.

Best, Authors