Re: [iccrg] Pareto frontier

Michael Welzl <michawe@ifi.uio.no> Thu, 09 January 2020 07:04 UTC

Return-Path: <michawe@ifi.uio.no>
X-Original-To: iccrg@ietfa.amsl.com
Delivered-To: iccrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C3422120025 for <iccrg@ietfa.amsl.com>; Wed, 8 Jan 2020 23:04:16 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 4qXC-1G9KfWI for <iccrg@ietfa.amsl.com>; Wed, 8 Jan 2020 23:04:13 -0800 (PST)
Received: from mail-out01.uio.no (mail-out01.uio.no [IPv6:2001:700:100:10::50]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8CD86120118 for <iccrg@irtf.org>; Wed, 8 Jan 2020 23:04:12 -0800 (PST)
Received: from mail-mx11.uio.no ([129.240.10.83]) by mail-out01.uio.no with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.92.3) (envelope-from <michawe@ifi.uio.no>) id 1ipRrW-0000a2-IG; Thu, 09 Jan 2020 08:04:10 +0100
Received: from boomerang.ifi.uio.no ([129.240.68.135]) by mail-mx11.uio.no with esmtpsa (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) user michawe (Exim 4.92.3) (envelope-from <michawe@ifi.uio.no>) id 1ipRrV-0009jb-JF; Thu, 09 Jan 2020 08:04:10 +0100
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\))
From: Michael Welzl <michawe@ifi.uio.no>
In-Reply-To: <CAMzhQmNRZN6+uzqm48rCmg78QDiomAJYDXVdL9aTiVedC35-yg@mail.gmail.com>
Date: Thu, 9 Jan 2020 08:04:07 +0100
Cc: iccrg IRTF list <iccrg@irtf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <0E122A72-8AEA-44AD-817A-2A6AD4EF8226@ifi.uio.no>
References: <510CB937-5E3B-4100-99E7-4F9AA3B81FEC@ifi.uio.no> <CAMzhQmNRZN6+uzqm48rCmg78QDiomAJYDXVdL9aTiVedC35-yg@mail.gmail.com>
To: Keith Winstein <keithw@cs.stanford.edu>
X-Mailer: Apple Mail (2.3445.9.1)
X-UiO-SPF-Received: Received-SPF: neutral (mail-mx11.uio.no: 129.240.68.135 is neither permitted nor denied by domain of ifi.uio.no) client-ip=129.240.68.135; envelope-from=michawe@ifi.uio.no; helo=boomerang.ifi.uio.no;
X-UiO-Spam-info: not spam, SpamAssassin (score=-5.0, required=5.0, autolearn=disabled, UIO_MAIL_IS_INTERNAL=-5, uiobl=NO, uiouri=NO)
X-UiO-Scanned: 1BDC594EACCF67E831D81E7B961308919956F925
Archived-At: <https://mailarchive.ietf.org/arch/msg/iccrg/EwvSHwuhlfMsxt2jSKWlAYMNj10>
Subject: Re: [iccrg] Pareto frontier
X-BeenThere: iccrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Discussions of Internet Congestion Control Research Group \(ICCRG\)" <iccrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/iccrg>, <mailto:iccrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/iccrg/>
List-Post: <mailto:iccrg@irtf.org>
List-Help: <mailto:iccrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/iccrg>, <mailto:iccrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 09 Jan 2020 07:04:17 -0000

That's a very useful answer, thanks a lot Keith!

Cheers,
Michael


> On 8 Jan 2020, at 16:40, Keith Winstein <keithw@cs.stanford.edu> wrote:
> 
> Hi Michael,
> 
> Formally speaking, given a set of feasible allocations (each the result of some strategy), the Pareto frontier is the subset of allocations that aren't strictly dominated by any other allocation. It's fashionable to show this by drawing the convex hull through the frontier -- see, e.g., the plots in the Wikipedia article on "Pareto efficiency." But the frontier is really the set of points, not the line drawn to connect them.
> 
> It's okay that the set considered is finite -- the Pareto frontier does not have to be taken only after evaluating the full (typically infinite) set of all possible strategies. (Of course it's important to compare with the right prior work or alternative strategies, but that's just true any time you want to have a comparative evaluation -- it doesn't come from the definition of Pareto frontier.) And in congestion control, it's not like we usually have access to a tight upper bound. If you look at, e.g., Figure 7 of https://cs.nyu.edu/~anirudh/contest-ccr.pdf (3,000 different congestion-control schemes run across the same time-varying emulated network path), there's a substantial gap between the apparent frontier-of-schemes-tested and the best known upper bound ("Omniscient"). Maybe there exists some scheme that comes very close to "Omniscient" and would remove most other points from the frontier, or maybe there isn't -- one can't know this just by plotting a frontier of a finite set of evaluated strategies.
> 
> Also, maybe the schemes on the frontier will still be on the frontier when evaluated over a different emulated network, or over a real-world Internet path, or maybe they won't -- one won't necessarily know this either. (Our Pantheon paper, https://pantheon.stanford.edu/static/pantheon/documents/pantheon-paper.pdf, tries to show how challenging it can be to match the real-world results of a variety of congestion-control schemes in an emulator.)
> 
> I assume when somebody says their scheme sits "outside the Pareto frontier", they mean that it strictly dominated some of the schemes that *had been* on the Pareto frontier before it was added to the set of available schemes. One does have to be cautious about how far you interpret these snapshot results -- some of my own results for schemes that strictly dominated other schemes have not held up when you run the experiment with different network paths, buffering regimes, workloads, figures of merit (dimensions of the "allocation"), etc. I talked about this a bit here: https://youtu.be/pzPy6VUuY-k?t=2474 .
> 
> But these problems belong, I think, more to the realm of computer networking and the hardness of reasoning about how to make resource allocation decisions under uncertainty in a decentralized manner, than in the concept of Pareto efficiency.
> 
> Sincerely,
> Keith
> 
> On Wed, Jan 8, 2020 at 5:53 AM Michael Welzl <michawe@ifi.uio.no> wrote:
> Hi,
> 
> Recently, it has become common in some congestion control papers, when showing plots with various congestion control mechanisms and a "better" arrow, to also draw a line through the presumably best mechanisms and call it a Pareto frontier.
> 
> I find it a bit of a stretch to just call this line a Pareto frontier - it MAY be one, but that's not proven, so I'm not sure this is a correct thing to state, strictly speaking. Anyway, I've recently seen cases where mechanism XY beats the others, as shown in the diagram, where it "sits comfortably outside the Pareto frontier".
> 
> Now, either I totally misunderstand something, or I never got the idea of Pareto efficiency, OR such a statement is utter nonsense.
> (because being better than the mechanisms on the Pareto frontier simply means that this line is indeed *NOT* the Pareto frontier, and it was wrong to call it that in the first place).
> 
> Can someone enlighten me please?
> 
> Cheers,
> Michael
> 
> _______________________________________________
> iccrg mailing list
> iccrg@irtf.org
> https://www.irtf.org/mailman/listinfo/iccrg