Adversaries in Online Learning Revisited: with applications in Robust Optimization and Adversarial training

• URL: http://arxiv.org/abs/2101.11443v1
• Date: Wed, 27 Jan 2021 14:23:06 GMT
• Title: Adversaries in Online Learning Revisited: with applications in Robust Optimization and Adversarial training
• Authors: Sebastian Pokutta and Huan Xu
• Abstract summary: We revisit the concept of "adversary" in online learning, motivated by solving robust optimization and adversarial training problems. We establish a general approach for a large variety of problem classes using imaginary play.
• Score: 55.30970087795483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the concept of "adversary" in online learning, motivated by solving robust optimization and adversarial training using online learning methods. While one of the classical setups in online learning deals with the "adversarial" setup, it appears that this concept is used less rigorously, causing confusion in applying results and insights from online learning. Specifically, there are two fundamentally different types of adversaries, depending on whether the "adversary" is able to anticipate the exogenous randomness of the online learning algorithms. This is particularly relevant to robust optimization and adversarial training because the adversarial sequences are often anticipative, and many online learning algorithms do not achieve diminishing regret in such a case. We then apply this to solving robust optimization problems or (equivalently) adversarial training problems via online learning and establish a general approach for a large variety of problem classes using imaginary play. Here two players play against each other, the primal player playing the decisions and the dual player playing realizations of uncertain data. When the game terminates, the primal player has obtained an approximately robust solution. This meta-game allows for solving a large variety of robust optimization and multi-objective optimization problems and generalizes the approach of arXiv:1402.6361.

Related papers

• Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems [4.9826534303287335]
  We present learning-augmented algorithmic frameworks for two fundamental optimizations settings. For online packing with concave objectives, we present a simple but overarching strategy that switches between the advice and the state-of-the-art online algorithm. We show that our algorithms break impossibility results when the advice is accurate, while maintaining comparable performance with state-of-the-art classical online algorithms even when the advice is erroneous.
  arXiv  Detail & Related papers  (2024-11-13T04:27:25Z)
• A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
  We introduce and analyze a simple learning-augmented algorithm for online packing problems with linear constraints and concave objectives. We further raise the problem of understanding necessary and sufficient conditions for when such simple black-box solutions may be optimal.
  arXiv  Detail & Related papers  (2024-06-05T18:39:28Z)
• Learning Mixture-of-Experts for General-Purpose Black-Box Discrete Optimization [45.243090644194695]
  This article introduces MEGO, a novel general-purpose neural trained through a fully data-driven learning-to-optimize (L2O) approach. MEGO consists of a mixture-of-experts trained on experiences from solving training problems. MEGO actively selects relevant expert models to generate high-quality solutions.
  arXiv  Detail & Related papers  (2024-05-29T08:41:08Z)
• All by Myself: Learning Individualized Competitive Behaviour with a Contrastive Reinforcement Learning optimization [57.615269148301515]
  In a competitive game scenario, a set of agents have to learn decisions that maximize their goals and minimize their adversaries' goals at the same time. We propose a novel model composed of three neural layers that learn a representation of a competitive game, learn how to map the strategy of specific opponents, and how to disrupt them. Our experiments demonstrate that our model achieves better performance when playing against offline, online, and competitive-specific models, in particular when playing against the same opponent multiple times.
  arXiv  Detail & Related papers  (2023-10-02T08:11:07Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• On Computable Online Learning [8.655294504286635]
  We show that the Littlestone dimension no longer characterizes the optimal mistake bound of c-online learning. We show that c-online learning is as difficult as improper CPAC learning.
  arXiv  Detail & Related papers  (2023-02-08T22:09:06Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy. We consider general Bayesian games, where the payoffs of both the payoffs of both the learner and the learner could depend on the type.
  arXiv  Detail & Related papers  (2022-05-17T18:10:25Z)
• Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
  We use deep neural networks to learn an online algorithm for a resource allocation and pricing problem from scratch. Our work is the first using deep neural networks to design an online algorithm from the perspective of worst-case performance guarantee.
  arXiv  Detail & Related papers  (2021-11-19T15:48:43Z)
• Adversarial Robustness with Semi-Infinite Constrained Learning [177.42714838799924]
  Deep learning to inputs perturbations has raised serious questions about its use in safety-critical domains. We propose a hybrid Langevin Monte Carlo training approach to mitigate this issue. We show that our approach can mitigate the trade-off between state-of-the-art performance and robust robustness.
  arXiv  Detail & Related papers  (2021-10-29T13:30:42Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents. Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
  arXiv  Detail & Related papers  (2020-07-10T09:33:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.