The computational power of optimization in online learning

DOI10.1145/2897518.2897536zbMath1373.68456arXiv1504.02089OpenAlexW1522619327MaRDI QIDQ5361824

Elad Hazan, Tomer Koren

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.02089

zbMATH Keywords

local searchzero-sum gamesonline learninglearning in gamesbest-response dynamicsoptimization oracles

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Approximation methods and heuristics in mathematical programming (90C59) Rationality and learning in game theory (91A26) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Learning in auctions: regret is hard, envy is easy ⋮ Online learning for min-max discrete problems ⋮ Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability

This page was built for publication: The computational power of optimization in online learning