📊 statistics

Capacity-Constrained Online Convex Optimization with Delayed Feedback

Dit artikel introduceert een raamwerk voor capaciteitsbeperkte online convexe optimalisatie met vertraagde feedback, waarbij een semi-clairvoyant model en een scheduler-gebaseerde reductie naar "vertraagde en gewogen" OCO worden voorgesteld die de eerste regret-garanties bereikt voor zowel convexe als sterk convexe verliezen onder eindige tracking-bronnen.

Oorspronkelijke auteurs: Alexander Ryabchenko, Idan Attias, Daniel M. Roy

Gepubliceerd 2026-06-11

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Alexander Ryabchenko, Idan Attias, Daniel M. Roy

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een chef bent die een drukke keuken runt (het Online Convex Optimization probleem). Elke minuut komt er een bestelling binnen voor een gerecht (jij doet een voorspelling). Je kookt het gerecht, maar je weet pas veel later of de klant het lekker vond of dat ze het verschrikkelijk vonden. Soms komt de feedback 5 minuten later, soms 50 minuten later. Dit is Vertraagde Feedback (Delayed Feedback).

In de meeste eerdere onderzoeken werd ervan uitgegaan dat je keuken over een oneindig groot aanrecht beschikt. Je kon elk bestelbonnetje op het aanrecht laten liggen terwijl je wachtte op de beoordeling van de klant, ongeacht hoeveel bestellingen er tegelijkertijd openstonden.

Het Probleem: De Realiteit van een "Klein Aanrecht"
In de echte wereld is de ruimte op je aanrecht beperkt. Je hebt slechts ruimte voor C bonnetjes tegelijkertijd. Als er een nieuwe bestelling binnenkomt en je aanrecht is vol, moet je een harde keuze maken: gooi je een openstaand bonnetje weg (en zie je de beoordeling voor dat gerecht nooit meer) of stop je met het aannemen van nieuwe bestellingen. Als je een bonnetje weggooit, is die feedback voor altijd verloren. Dit is de Capaciteitsbeperking (Capacity Constraint).

De paper vraagt zich af: Hoe leer je beter koken wanneer je niet elk bonnetje kunt bijhouden en de feedback die je wel krijgt te laat is en soms ontbreekt?

De Oplossing: Een Slimme "Bonnetjesbeheerder"
De auteurs stellen een tweeledig systeem voor om dit probleem op te lossen:

1. De "Proxy Delay" Scheduler (De Bonnetjesbeheerder)

Omdat je niet precies weet wanneer een beoordeling zal arriveren (de vertraging is onbekend), kun je niet simpelweg wachten. In plaats daarvan introduceert het paper een slimme "Scheduler" die fungeert als een bonnetjesbeheerder.

Hoe het werkt: Wanneer er een nieuwe bestelling binnenkomt, gooit de beheerder een muntje (willekeurig) om te beslissen hoe lang het bonnetje op het aanrecht blijft liggen.
- Als de beheerder besluit dat het bonnetje "voor altijd" moet blijven liggen (of totdat de beoordeling arriveert), blijft het op het aanrecht liggen.
- Als de beheerder besluit dat het bonnetje "te riskant" is om te bewaren, wordt het direct weggegooid.
De Truc: De beheerder gebruikt een specifieke waarschijnlijkheidsregel. Als het aanrecht voller wordt, wordt de beheerder agressiever in het weggooien van bonnetjes. Als het aanrecht leeg is, houdt de beheerder meer bonnetjes vast.
De "Belangrijkheidsweging" (Importance Weight): Hier zit de magie. Als de beheerder een bonnetje wel behoudt en je uiteindelijk de beoordeling krijgt, zegt het systeem: "Deze beoordeling telt meer!" Het vermenigvuldigt de belangrijkheid van die beoordeling om wiskundig te compenseren voor alle andere beoordelingen die zijn weggegooid. Het is alsof je zegt: "Aangezien we slechts 1 van de 10 beoordelingen hebben gezien, vertegenwoordigt deze ene beoordeling de mening van alle 10."

2. De "Weighted Learner" (De Chef)

Zodra de beheerder de bonnetjes filtert en de "belangrijkheidswegingen" toekent, gaat de Chef (het leeralgoritme) aan het werk.

De Chef kijkt niet alleen naar de beoordeling; hij kijkt naar de gewogen beoordeling.
Het paper ontwikkelt een nieuw wiskundig recept (een algoritme genaamd DW-FTRL voor volledige feedback en DW-FTBL voor gedeeltelijke feedback) dat weet hoe het met deze vertraagde, gewogen beoordelingen moet omgaan zonder in de war te raken.

De Resultaten: Hoe groot moet je aanrecht zijn?
Het paper berekent exact hoeveel aanrechtruimte (C) je nodig hebt om bijna net zo goed te presteren als wanneer je een oneindige ruimte zou hebben.

Voor Simpele Feedback (First-Order): Als je volledige details krijgt over waarom een gerecht goed of slecht was (zoals een gedetailleerde kritiek), heb je slechts een aanrecht nodig dat zeer langzaam groeit met de tijd (ongeveer de grootte van de logaritme van de totale tijd, log T). Zelfs een klein aanrecht is voldoende om de prestaties van een gigantisch aanrecht te evenaren.
Voor Harde Feedback (Bandit): Als je alleen een simpele "Goed/Slecht" score krijgt (zoals een duim omhoog of omlaag) zonder details, is de wiskunde moeilijker. Hier hangt de prestatie af van hoe druk het aanrecht wordt (σ_max) versus hoe groot je aanrecht is (C).
- Als je aanrecht groot genoeg is, doe je het geweldig.
- Als je aanrecht te klein is, verslechtert je prestatie, maar dit gebeurt geleidelijk. Het stort niet in; het wordt alleen iets slechter op basis van een specifieke formule die de verhouding tussen "drukte" en "capaciteit" bevat.

De "Semi-Clairvoyant" Twist
Eerdere methoden gingen ervan uit dat de chef precies wist hoe lang de vertraging zou zijn voordat het gerecht werd bereid. Dit paper versoepelt dat. De chef vindt de vertraging pas achteraf wanneer de beoordeling eindelijk arriveert (of wanneer de tijd van het bonnetje is verstreken). Dit maakt het probleem veel realistischer, zoals wachten op een recensie per post die ergens tussen 1 dag en 30 dagen kan duren, zonder dat je vooraf de vertraging kunt weten.

Samenvatting
Dit paper slaat een brug tussen de ideale wereld (oneindig geheugen, perfecte tracking) en de rommelige echte wereld (beperkt geheugen, verloren data). Het bewijst dat door een slimme, gerandomiseerde "bonnetjesbeheerder" te gebruiken die sommige data weggooit maar de resterende data zwaar weegt, je nog steeds effectief kunt leren, zelfs wanneer je "aanrecht" klein is en de feedback laat is.

Technische Samenvatting: Capaciteitsbeperkte Online Convex Optimization met Vertraagde Feedback

1. Probleemstelling

Dit artikel behandelt Online Convex Optimization (OCO) en Bandit Convex Optimization (BCO) onder twee gelijktijdige beperkingen: vertraagde feedback en een beperkte trackingcapaciteit.

In standaard vertraagd online leren kiest een leerder op tijdstip $t$ een actie $x_t$ , waarbij een verlies $f_t(x_t)$ wordt geleden, maar de feedback (gradiënt of scalaire verlies) pas op tijdstip $t + d_t$ wordt ontvangen. De traditionele literatuur gaat ervan uit dat de leerder over onbeperkte capaciteit beschikt om alle lopende ronden te volgen totdat hun feedback arriveert. Echter, in praktische scenario's (bijv. klinische studies met beperkte monitoringsbronnen), kan de leerder slechts een begrensd aantal lopende ronden volgen, aangeduid met capaciteit $C$ . Als een ronde niet wordt gevolgd, gaat de feedback voor die ronde permanent verloren.

Het artikel formaliseert dit als een spel waarbij:

De tegenstander (adversary) convexe verliezen $f_t$ en vertragingen $d_t$ vastlegt.
De speler een tracking-set $S$ onderhoudt van grootte maximaal $C$ .
De speler op elk tijdstip bestaande gevolgde ronden mag onderbreken (verwijderen) of de huidige ronde aan $S$ kan toevoegen.
Feedback voor ronde $s$ wordt waargenomen op $s + d_s$ indien en alleen indien $s \in S$ op dat moment.
Het doel is om de regret $R_T = \sum_{t=1}^T (f_t(x_t) - f_t(x^*))$ te minimaliseren ten opzichte van de beste vaste actie $x^*$ in hindsight.

Het artikel beschouwt twee informatiemodellen met betrekking tot vertragingen:

Clairvoyant (Alwetend): Vertragingen $d_t$ zijn bekend op het moment van voorspelling.
Semi-Clairvoyant: Vertragingen worden pas onthuld bij expiratie (op $t+d_t$ ), wat consistent is met de standaard settings voor vertraagd online leren.

2. Methodologie

De auteurs stellen een reductie-gebaseerde aanpak voor die het capaciteitsbeperkte probleem decomponeert in twee componenten: een scheduler en een base learner.

2.1 Het Reductiekader

De kern van het idee is om het capaciteitsbeperkte probleem te reduceren tot een nieuw "delayed and weighted" OCO probleem.

Scheduler: Een wrapper-algoritme beheert de tracking-set $S$ . Het gebruikt een proxy-delay scheduling mechanisme. Voor elke ronde $t$ samplet de scheduler een "proxy-vertraging" $d'_t$ uit een distributie $D_t$ . Ronde $t$ wordt toegevoegd aan $S$ als $d'_t \ge 0$ en de capaciteit dit toelaat. Het wordt uit $S$ verwijderd op $t + d'_t + 1$ indien de feedback nog niet is gearriveerd.
Belangrijkheidsweging (Importance Weighting): Indien de feedback voor ronde $s$ wordt waargenomen (d.w.z. $s \in S$ en $d'_s \ge d_s$ ), stuurt de wrapper de feedback naar de base learner met een belangrijkheidsgewicht $w_s = 1 / P(d'_s \ge d_s)$ . Indien feedback verloren gaat (door capaciteitssaturatie of vroege proxy-timeout), wordt het gewicht op 0 gezet.
Base Learner: De leerder ontvangt een stroom van vertraagde, gewogen feedback. Het artikel introduceert algoritmen die specifiek zijn ontworpen voor deze gewogen, vertraagde stroom.

2.2 Base Algoritmen: Delayed-Weighted FTRL

Het artikel introduceert en analyseert twee base algoritmen voor de gewogen, vertraagde setting:

DW-FTRL (Delayed-Weighted Follow-the-Regularized-Leader): Voor first-order (gradiënt) feedback. Het werkt de iteratie bij door een regulariserend objectief te minimaliseren dat gewogen gradiënten van alle geobserveerde ronden aggregeert.
DW-FTBL (Delayed-Weighted Follow-the-Bandit-Leader): Voor bandit (scalaire verlies) feedback. Het gebruikt de standaard single-point gradiëntschatter (door het middelpunt te verstoren) maar past deze toe op de gewogen, vertraagde feedbackstroom.

Theoretische analyse van deze base algoritmen stelt regret-bounds vast die expliciet rekening houden met de interactie tussen tijdvariërende gewichten en de achterstand (backlog) van openstaande observaties. Een belangrijke bevinding is dat de regret afhangt van de paargewijze interacties van gewichten voor ronden met overlappende vertragingen.

2.3 Proxy Delay Schedulers

Om de reductie werkend te laten zijn, moet de scheduler twee concurrerende doelen balanceren: het dekken van ware vertragingen (om feedback te observeren) en het vermijden van capaciteitssaturatie. Het artikel stelt twee specifieke schedulers voor:

Pareto Scheduler: Past zich aan individuele vertragingen $d_t$ aan. Het samplet proxy-vertragingen uit een verschoven Pareto-distributie, waardoor de kans op tracking omgekeerd evenredig is aan de vertraging. Dit is geschikt voor algemene convexe verliezen.
Bernoulli Scheduler: Gecalibreerd op de maximale backlog $\sigma_{max}$ (het maximale aantal openstaande observaties op enig gegeven moment). Het samplet een proxy-vertraging van $\infty$ met een kans $p \approx C / \sigma_{max}$ en $-1$ daarenteke. Dit levert uniforme belangelijkheidsgewichten op, een eigenschap die cruciaal is voor het behalen van strakke bounds in sterk convexe en bandit settings.

3. Belangrijkste Bijdragen

Eerste Regret Guarantees voor Capaciteitsbeperkte OCO/BCO: Het artikel biedt de eerste sublineaire regret bounds voor capaciteitsbeperkt online leren met vertraagde feedback in zowel convexe als sterk convexe domeinen, voor zowel first-order als bandit feedback.
Delayed-Weighted OCO Framework: Het introduceert een nieuwe probleemsetting (vertraagde en gewogen feedback) en analyseert FTRL-varianten hiervoor. Dit framework is van onafhankelijke interesse voor schaalvrij online leren onder vertragingen.
Verenigde Proxy-Delay Scheduling: De auteurs verenigen eerdere scheduling-ideeën en introduceren een nieuwe scheduler (Bernoulli) die uniforme gewichten oplevert, wat sterkere garanties mogelijk maakt voor sterk convexe en bandit settings.
Afhandeling van Onbekende Parameters: Het framework faciliteert het semi-clairvoyant model (vertragingen onbekend op het moment van voorspelling) en gebruikt de doubling trick om onbekende $\sigma_{max}$ te behandelen zonder voorafgaande kennis.

4. Hoofdresultaten

De regret bounds zijn afhankelijk van de horizon $T$ , dimensie $k$ , totale vertraging $d_{tot}$ , maximale backlog $\sigma_{max}$ , en capaciteit $C$ .

4.1 First-Order Feedback (OCO)

Convex Losses: Met capaciteit $C = \Omega(\log T)$ , komt de regret overeen met de optimale onbeperkte vertraagde rate, met uitzondering van logaritmische factoren:
$\tilde{O}\left( G D \sqrt{d_{tot} + T} \right)$
Strongly Convex Losses: De regret is:
$\tilde{O}\left( \frac{G^2}{\lambda} (\sigma_{max} + 1) \log T \right)$
Dit komt overeen met de optimale afhankelijkheid van $\sigma_{max}$ gevonden in onbeperkte settings.

4.2 Bandit Feedback (BCO)

Voor bandit feedback komt de capaciteitsbeperking binnen in de dimensie-afhankelijke termen via factoren van $(1 + \sigma_{max}/C)$ .

Convex Losses:
$\tilde{O}\left( GD \left( \sqrt{T \sigma_{max}} + T^{3/4} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/4} \sqrt{\nu k} \right) \right)$
waarbij $\nu$ de schaalfactor is van functiewaarden tot gradiënten. De bound degradeert gracieus naarmate $C$ afneemt.
Strongly Convex Losses:
$\tilde{O}\left( \frac{G^2}{\lambda} \left( \sigma_{max} \log T + (T^2 \log T)^{1/3} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/3} (\nu k)^{2/3} \right) \right)$

Belangrijke Observatie: Wanneer $C \ge \sigma_{max}$ , herstellen de bounds de onbeperkte rates. Wanneer $C < \sigma_{max}$ , neemt de regret toe maar blijft deze sublineair. De afhankelijkheid van $\sigma_{max}$ (piek-concurrency) blijkt natuurlijker dan de afhankelijkheid van $d_{max}$ (maximale vertraging) in wachtrij-achtige systemen.

5. Betekenis en Claims

Het artikel claimt de eerste te zijn die regret garanties afleidt voor capaciteitsbeperkte OCO en BCO. De betekenis ligt in:

Brug slaan tussen Theorie en Praktijk: Het adresseert de realistische beperking dat tracking-bronnen eindig zijn, een beperking die door de meeste eerdere vertraagde leerliteratuur wordt genegeerd omdat zij uitgaan van oneindige capaciteit.
Verfijning van het Vertragingsmodel: Door een semi-clairvoyant model te adopteren (vertragingen onthuld bij expiratie), sluit het werk dichter aan bij standaard vertraagd leren en de realiteit van online job scheduling dan eerdere "clairvoyant" aannames.
Gracieus Degraderen: De resultaten tonen aan dat een logaritmische capaciteit ( $C = \Omega(\log T)$ ) voldoende is om standaard vertraagde rates te herstellen voor first-order feedback, terwijl voor bandit feedback de prestaties gracieus degraderen wanneer de capaciteit onder de piek-backlog zakt.
Theoretische Vernieuwing: De introductie van het "delayed and weighted" OCO probleem en de specifieke analyse van de interactie tussen gewichten en vertragingen in FTRL biedt nieuwe instrumenten voor het analyseren van online leren onder middelenbeperkingen.

De auteurs merken op dat hoewel hun bounds voor convex bandit feedback schalen met $\sqrt{T \sigma_{max}}$ in plaats van de optimale $\sqrt{d_{tot}}$ van de onbeperkte setting, ze nog steeds verbeteren ten opzichte van eerdere bounds die afhankelijk zijn van $\sqrt{T d_{max}}$ . Zij identificeren het dichten van deze kloof als een openstaand probleem. Daarnaast suggereren zij dat de structurele gelijkenis tussen hun model en finite-buffer wachtrijsystemen verdere exploratie verdient.