Comment by 317070 | Hacker News Reader

Comment by 317070 | Hacker News Reader

Parent Full thread

> for every λ there exists an M and for every M there exists a λ such that the resulting problems are equivalent

Sorry, this might be a tad off-topic. I have over the last month being thinking extensively on the topic.

As far as I can see, the above is actually not true. If the trade-off between l(θ) and r(θ) is concave (which might occur frequently for a lot of problems), you will not find all the solutions with the first approach you would find with the second approach. With the first approach you cannot find points on the concave parts of the pareto-curve, while with the second approach you can walk the whole pareto curve. When minimizing a linear combination of losses, you can only find the points on the ends of the concave part of a pareto curve.

Is there a reason the above is not correct? I.e. do you have some more explanation or a source on the "fairly general regularity conditions" you mentioned? It would help me out a lot.

Well, I'm not sure what you mean by "concave part of a Pareto curve." (Perhaps you meant convex?) Usually, the Pareto curve is the epigraph of the individual function evaluations at the optimal points, so, unless your problem is highly nonconvex, the Pareto curve is likely to be convex.

More specifically, the tradeoff curve is defined as the following: letting θ(λ) be the optimal solution of the first optimization problem at fixed λ, the Pareto optimal curve/frontier is the epigraph of the set of of all (l(θ(λ)), r(θ(λ))). I.e.,

    {(x, y) | x ≥ l(θ(λ)), y ≥ r(θ(λ)), λ ∈ ℝ}

If l and r are convex functions, then this curve is guaranteed to be convex. A similar curve can be defined for the second problem (over M instead of λ), and both curves are equal (in the sense that they both include the same points).

Note that this equivalency between both problems doesn't require convexity; for example, lower semi-continuity of l and r with r bounded from below [0], are sufficient conditions that would include essentially all functions used in ML.

-----

[0] Boundedness is needed in this case since, otherwise, we could just have r(θ) = -∞ for a bunch of points, in which case we would always choose this θ, no matter how large or small λ is (except at λ = 0) in problem (1), whereas it would have a different effect in problem (2).

See e.g. https://en.m.wikipedia.org/wiki/Lagrange_multiplier and https://en.m.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93... for the justification.

It’s essentially an example of duality in numerical optimization (https://en.m.wikipedia.org/wiki/Duality_(optimization)#Dual_...).

Reply on news.ycombinator.com