Chasing Convex Bodies and Functions with Black-Box Advice

2. Červenec 2022

Řečníci

O prezentaci

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.

Organizátor

O organizátorovi (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.

Uložení prezentace

Měla by být tato prezentace uložena po dobu 1000 let?

Jak ukládáme prezentace

Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %

Sdílení

Doporučená videa

Prezentace na podobné téma, kategorii nebo přednášejícího

Zajímají Vás podobná videa? Sledujte COLT