Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pareto Front

en.wikipedia.org

Post reply on HN
Print view View original

31–40 of 116 posts

Re: Pareto Front

#31

Post by matsemann »

chriswarbo wrote: post #17
bhanu786 wrote: post #4

may, anyone explain what is this

If we have a set of things (e.g. language models) and some measures we care about (e.g. cost, speed, whether weights are open, scores for a few benchmarks, etc.), then some of those things will be "pareto optimal" (see below) and some won't. The "pareto front" is the subset that is pareto optimal. Some thing is "pareto optimal" when there isn't another thing that's AT LEAST AS GOOD in ALL measures, and BETTER in at l…

I honestly think the wikipedia article is too complicated. My own image example here as an another attempt to explain: https://imgur.com/a/5ZQIJDb

Mapping the cost of something (like an algorithm), and the time it takes (so lower is better for both). 1, 3 and 5 are all optimal in their own sense. No one is strictly better than the other, just different tradeoffs you have to choose yourself. However, you would never choose 2, because for a lower cost you could get the same result choosing 3. Same with 4, 6 and 7, they all have something that's both faster and at the same time just as cheap you could choose.

A pareto front is a bit like the classical "fast, cheap, good, choose 2". There are always tradeoffs, but if something is both slow, expensive and not better than something that's faster and cheaper, it's a bad choice, and thus not on the "pareto front".

Re: Pareto Front

#32

Post by __s »

Aachen wrote: post #3

Misread the title and got excited about a Pareto font, that is, the best possible font (presumably: distinct l/I, O/0, scores within error margins of the top readability and reading speed scores, widely available, etc.) Maybe in vein but did anyone already figure this one out? The closest I got was PT sans, open-licensed commissioned by the Russian ministry for communication (I found it surprising that a country that…

Trouble with fonts is sometimes monospace good, sometimes monodpace bad

Anyways I'll namedrop Iosevka as perfect monospace font for working on 13" laptop

Re: Pareto Front

#35

Post by arduanika »

Aachen wrote: post #3

Misread the title and got excited about a Pareto font, that is, the best possible font (presumably: distinct l/I, O/0, scores within error margins of the top readability and reading speed scores, widely available, etc.) Maybe in vein but did anyone already figure this one out? The closest I got was PT sans, open-licensed commissioned by the Russian ministry for communication (I found it surprising that a country that…

No, it's far from the best possible font, but to its credit, it gets most aspects of typography right by just focusing on the ~1/5 of the requirements that actually really count.

Re: Pareto Front

#36

Post by voidhorse »

One nuance that people sometimes miss is that pareto optimality in the continuous case and discrete case are distinct. Using continuous case algorithms on discrete feasible set optimization problems will make you miss the interior optimal points--only extremal/supported points on the positive orthant hull are identified by the continuous algos.

Matthias Ehrgott's books on multicriteria optimization explain Pareto efficiency very well without sacrificing rigor. I think they do a better job than this article.

Re: Pareto Front

#37

Post by peesem »

Aachen wrote: post #3

Misread the title and got excited about a Pareto font, that is, the best possible font (presumably: distinct l/I, O/0, scores within error margins of the top readability and reading speed scores, widely available, etc.) Maybe in vein but did anyone already figure this one out? The closest I got was PT sans, open-licensed commissioned by the Russian ministry for communication (I found it surprising that a country that…

look at Atkinson Hyperlegible? commissioned by the Braille foundation for low-vision readers which means it's very readable

Re: Pareto Front

#38

Post by krapht »

bob1029 wrote: post #28

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…

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.

Re: Pareto Front

#39

Post by peri-cl »

bob1029 wrote: post #28

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…

> "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)
Post reply on HN