Comment by bob1029

9 hours ago

Pareto front sounds like an interesting way to optimize, but it suffers from the curse of dimensionality just like anything else.

As the number of objectives (dimensions) increases, the number of samples you need to cover the frontier increases exponentially. You will very rarely find solutions that actually dominate other solutions in many practical optimization scenarios. With 2 dimensions you have a 25% chance of domination. With 10 dimensions it's a .098% chance.

The most useful cases I've seen tend to occur where we just optimize for two things at once. The chances of domination are high, it's easy to visualize and very efficient to implement. As we get into higher dimensional spaces, things get weird really fast.

3 comments

bob1029

peri-cl 9 hours ago

> "As we get into higher dimensional spaces, things get weird really fast."

The geometric problem of computing a d-dimensional Pareto set of cardinality n

https://en.wikipedia.org/wiki/Maxima_of_a_point_set

has a truly weird property not covered by the computational complexity discussion on that page. It says there's an algorithm achieving O(n log(n)^(d-3) log log n), which is true and also a lie. The algorithm that achieves that asymptotic form is a galactic algorithm; and not an ordinary one in the sense of "has a large constant multiplicative factor", but one with this property (I've never found any other algorithm which exhibits it):

The runtime is within a bounded constant factor of n^2, for all n up to some critical N whose size is exponential in d (I think it was exactly 2^d or something).

I.e. the runtime has "two shapes": it's purely quadratic up to a galactically-large constant, and thereafter has a transition into to a slower function. The asymptotic version in the textbooks isn't achievable in the real world (for all but very small dimension).

There's an elementary proof using generating functions.

edit to add: If anyone's curious about it, a simplified version of the recurrence relation that's enough to exhibit this behavior (you can instantly see it if you graph this numerically) is

    f(n,d=0) = 1
    f(n=1,d) = 1
    f(n,d)   = n + 2f(⌊n/2⌋, d) + 2f(⌊n/2⌋, d-1)

jonathaneunice 7 hours ago

The curse of dimensionality times the reality that good metrics are elusive or themselves a bit cursed. Many outcomes you're engineering or product-managing toward are quite squishy, hard to define, and hard to evaluate. "Easy to use" or "can be used within 10 minutes" or "cleans up this current order form" are easy to state but hard to rate and/or hard to actionably implement as metrics.

I've built large, deep product evaluation frameworks, and it is 100% of the time a running argument with stakeholders, inside and out, "well you should have measured it this way" or "I think we should be targeting X not Y" or "why didn't you consider Z in the metric??"

The Pareto Front in practice is squishy, fuzzy, and often quite moist and moldy.

krapht 9 hours ago

One I spent a few months working on was pathfinding for trucks. The goal is to find dominant solutions over {shortest time, lowest cost (tolls + fuel), avg road speed variance - traffic sensitivity} and then return 3-4 routes that are equal distance from each other in this dimensional space for users to pick from.

As you say, the most useful things happen in low-dimensional spaces.