Chasing Convex Bodies and Functions with Black-Box Advice

Jul 2, 2022

Sprecher:innen

Über

We consider the problem of convex function chasing with black-box advice, where an online decision-maker aims to minimize the total cost of making and switching between decisions in a normed vector space, aided by black-box advice such as the decisions of a machine-learned algorithm. The decision-maker seeks cost comparable to the advice when it performs well, known as consistency, while also ensuring worst-case robustness even when the advice is adversarial. We first consider the common paradigm of algorithms that switch between the decisions of the advice and a competitive algorithm, showing that no algorithm in this class can improve upon 3-consistency while staying robust. We then propose two novel algorithms that bypass this limitation by exploiting the problem's convexity. The first, Interp, achieves (√(2)+ϵ)-consistency and 𝒪(C/ϵ^2)-robustness for any ϵ > 0, where C is the competitive ratio of an algorithm for convex function chasing or a subclass thereof. The second, BdInterp, achieves (1+ϵ)-consistency and 𝒪(CD/ϵ)-robustness when the problem has bounded diameter D. Further, we show that BdInterp achieves near-optimal consistency-robustness trade-off for the special case where cost functions are α-polyhedral.

Organisator

Über COLT

The conference is held annually since 1988 and has become the leading conference on Learning theory by maintaining a highly selective process for submissions. It is committed in high-quality articles in all theoretical aspects of machine learning and related topics.

Präsentation speichern

Soll diese Präsentation für 1000 Jahre gespeichert werden?

Wie speichern wir Präsentationen?

Ewigspeicher-Fortschrittswert: 0 = 0.0%

Freigeben

Empfohlene Videos

Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind

Interessiert an Vorträgen wie diesem? COLT folgen