Multi-objective optimization

1 Multi-objective optimization via Lagrange multipliers

HT Cheng Soon Ong for pointing out Jonas Degrave and Ira Korshunova’s illustrated explanation of a tricky thing, Why machine learning algorithms are hard to tune (and the fix). Their summary:

“Machine learning hyperparameters are hard to tune. One way to think of why it is hard, is because it is a Pareto front of multiple objectives. One way to solve that problem is to look at Lagrange multipliers, as proposed by a paper in 1988 (Platt and Barr 1987).”

A follow-up post describes how we can make machine learning algorithms tunable.

2 Perils of scalarization

We might wonder what goes wrong if we just treat multiple objectives as a single scalar objective by taking a weighted sum. Scalarizing by weighted sum is the default move because it gets us a total order.

The cost of scalarization has a lot of texture. Das and Dennis (1997) demonstrates that sweeping the weights \(\lambda\) over the simplex and solving \(\max_x \sum_i \lambda_i f_i(x)\) recovers only those Pareto-optimal points lying on the convex hull of the front. A point sitting in a concave stretch of the front is not the maximizer of any positive weighting, so no amount of weight-tuning will ever return it. All of which is to say, they leave some Pareto-optimal points on the table, depending on the problem.

Even on the convex part, evenly spaced weights do not produce evenly spaced points along the front, so weight sweep still leads to an annoying interpolation problem. Marler and Arora (Marler and Arora 2010) revisit both drawbacks at length.

3 Chebyshev scalarization

I just heard about this from Austin Tripp’s blog, and it looks cool. It is one of the standard tricks to escape from the convexity restriction, since (I am told) minimizing a weighted Chebyshev distance to a reference point can attain front points that no linear weighting reaches. 🚧TODO🚧

4 Scalar reward is not enough

Silver et al. (2021) argue that maximizing a scalar reward is sufficient machinery to generate everything we associate with intelligence — knowledge, perception, language, social behaviour — given a rich enough environment. Vamplew and colleagues (Vamplew et al. 2022) reply that the scalar part of that claim is false.

Their argument is threefold:

1. A scalar reward (\(n=1\)) is a special case of a vector reward (\(n \ge 1\)), so nothing is conceded by starting vector-valued.
2. The collapse from vector to scalar by linear weighting is exclusionary, not merely lossy as per the Das and Dennis (1997) geometry argument.
3. An agent retaining a vector value can do things a scalar agent cannot.

The third point has interesting operationalizations. Preferences shift, and an agent that keeps its value function vector-valued can carry a set of policies covering the front and switch between them as needed, instead of retraining under each new weighting. The scalar agent must have already baked one weighting into its policy; changing the trade-off means retraining the agent. Multi-objective RL (Roijers et al. 2013; Hayes et al. 2022; Rădulescu et al. 2020) is largely the study of this manoeuvre.

A vector-valued reward is also more informative. It says which objective a bad outcome sacrificed. A scalar agent reporting a low number cannot tell us whether it traded safety for speed or the reverse.

Maybe scalarization also describes one way that Goodharting can arise. Unbounded maximization of a scalar proxy is our cautionary tale (“paperclipping”). Perhaps the problem here is that a plural value vector was flattened?

I’m not convinced that is a complete solution. While un-flattening might change the rank of the problem, it does not change the category. An event outside the ontology can still miss parameterization.

5 Pareto sets and incomplete preferences

The cost of vector-valued rewards is that if we train directly for them we lose total order. Maximizing over a partial order returns a set — the Pareto set — rather than a point, and at inference time we still need to choose from that Pareto frontier somehow.

If we don’t wish scalarization, the other response is to work with incomplete decisions. Aumann (1962) dropped the completeness axiom from von Neumann–Morgenstern and asked what survives. Quite a lot, it turns out: an agent whose preferences form a partial preorder satisfying the remaining axioms still admits a linear utility representation, only a weaker one — the utility respects the comparisons the agent actually can make unambiguously, and leaves others unresolved. A vector-valued objective and an incomplete preference relation seem then to be two views of one object, the Pareto set being the maximal set of the partial order.

Incomplete-preference theory thus establishes that declining to choose is coherent, descriptively. It does not say, normatively, what a bounded agent should do with the freedom left over once the Pareto set has been narrowed as far as its preferences narrow it. Maybe spend it on keeping futures reachable, treating the unchosen dimensions as a resource?

6 References