Abstract

We investigate the problem of online optimization under adversarial perturbations. In each round of this repeated game, a player selects an action from a decision set using a randomized strategy, and then Nature reveals a loss function for this action, for which the player incurs a loss. The game then repeats for a total of T rounds, over which the player seeks to minimize the total incurred loss, or more specifically, the excess incurred loss with respect to a fixed comparison class. The added challenge over traditional online optimization, is that for k of the T rounds, after the player selects an action, an adversarial agent perturbs this action arbitrarily. Through a worst case adversary framework to model the perturbations, we introduce a randomized algorithm that is provably robust against such adversarial attacks. In particular, we show that this algorithm is Hannan consistent with respect to a rich class of randomized strategies under mild regularity conditions.

Original languageEnglish (US)
Article number7314886
Pages (from-to)256-269
Number of pages14
JournalIEEE Journal on Selected Topics in Signal Processing
Volume10
Issue number2
DOIs
StatePublished - Mar 2016

Keywords

  • Adversarial perturbations
  • online optimization
  • randomized algorithms
  • repeated games
  • robustness

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Cite this