Vi anser algoritmer för "smoothed online konvex optimering" problem, en variant av klassen av online konvex optimering problem som är starkt relaterade till metriska uppgiftssystem. Tidigare litteratur om dessa problem har fokuserat på två prestandamått: ånger och konkurrensförhållandet. Det finns kända algoritmer med sublinjär ånger och kända algoritmer med konstanta konkurrensförhållanden; men ingen känd algoritm uppnår båda samtidigt. Vi visar att detta beror på en grundläggande inkompatibilitet mellan dessa två mätvärden - ingen algoritm (deterministisk eller randomiserad) kan uppnå sublinjär ånger och ett konstant konkurrensförhållande, även när de objektiva funktionerna är linjära. Men vi uppvisar också en algoritm som, för det viktiga specialfallet av endimensionella beslutsutrymmen, ger sublinjär ånger samtidigt som den bibehåller ett konkurrensförhållande som växer godtyckligt långsamt.
I synnerhet visar Ref att ingen algoritm kan få både sublinjärt beklagande och konstant konkurrensförhållande.
A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}