Online Learning with Predictable Sequences

By Alexander Rakhlin, Karthik Sridharan. Annual Conference Computational Learning Theory, 2012

432 citations recorded by the source corpus.

We present methods for online linear optimization that take advantage of benign (as opposed to worst-case) sequences. Specically if the sequence encountered by the learner is described well by a known \predictable process", the algorithms presented enjoy tighter bounds as compared to the typical worst case bounds. Additionally, the methods achieve the usual worst-case regret bounds if the sequence is not benign. Our approach can be seen as a way of adding prior knowledge about the sequence within the paradigm of online learning. The setting is shown to encompass partial and side information. Variance and path-length bounds [11, 9] can be seen as particular examples of online learning with simple predictable sequences. We further extend our methods and results to include competing with a set of possible predictable processes (models), that is \learning" the predictable process itself concurrently with using it to obtain better regret guarantees. We show that such model selection is possible under various assumptions on the available feedback. Our results suggest a promising direction of further research with potential applications to stock market and time series prediction.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/cdfeb2c08a3b4f55f8813e6dd769612e6befd656

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “Extrapolation can also be related to optimistic methods (Chiang et al., 2012; Rakhlin and Sridharan, 2013) proposed in the online learning literature (see more details in §3.”
Online Convex Optimization in Dynamic Environments (2015, background): “Concurrent related work considers online algorithms where the data sequence is described by a “predictable process” [31].”
Online Optimization in Dynamic Environments (2013, background): “However, [30] only works with static regret (i.”
Provable Guarantees for Gradient-Based Meta-Learning (2019, result): “Furthermore, if Θ ∗ = Θ , i.e. if the tasks are not similar, then the algorithm will only do a constant factor worse than FTRL or OMD; this is similar to other “optimistic” methods that work well under regularity (Rakhlin & Sridharan, 2013; Jadbabaie et al., 2015).”
Training GANs with Optimism (2017, methodology): “…that Optimistic Mirror De-scent and its generalization of Optimistic Follow-the-Regularized-Leader (OFTRL), achieve faster convergence rates than gradient descent in convex-concave zero-sum games (Rakhlin & Sridharan, 2013a;b) and even in general normal form games (Syrgkanis et al., 2015).”
Dynamical Models and tracking regret in online convex programming (2013, background): “This bound scales with the compartor sequence’s deviation from the dynamical model Φt – a stark contrast to previous tracking regret bounds which are only sublinear for comparators which change slowly with time or at a small number of distinct time instances.”
Distributed Detection: Finite-Time Analysis and Impact of Network Topology (2014, background): “ound in Lemma 4 is evocative of numerous regret bounds developed for the well-known problem of prediction with expert advice corresponding to the centralized detection in an adversarial setting [24], [25]. However, such bounds are in terms of second moment, rather than variance which is a smaller qu”
Convergence of Value Aggregation for Imitation Learning (2018, methodology): “First, we use Assumption 5 to strengthen the bound ‖xn+1 − xn‖ = O( 1 n ) used in Theorem 1 by techniques from online learning with prediction (Rakhlin and Sridharan, 2013).”
Fast Convergence of Regularized Learning in Games (2015, methodology): “Rakhlin and Sridharan [15] also analyze an FTRL variant, but require a self-concordant barrier for the constraint set as opposed to an arbitrary strongly convex regularizer, and their bound is missing the crucial negative terms of the RVU property which are essential for obtaining Theorem 4.”
On the convergence of single-call stochastic extra-gradient methods (2019, methodology): “This algorithm was subsequently studied by, among others, Chiang et al. [10], Rakhlin and Sridharan [38, 39] and Gidel et al. [18]; see also [13, 25] for a “reﬂected” variant, [14, 30, 31, 36] for an “optimistic” one, and Section 3 for a discussion of the differences between these variants.”
Optimization, Learning, and Games with Predictable Sequences (2013, methodology): “The notions of a zero-sum matrix game and a minimax equilibrium are arguably the most basic and important notions of game theory.”
Online Learning via the Differential Privacy Lens (2017, neutral): “First-order regret bounds for multi-armed bandits have been obtained via specialized analysis several times [6, 26, 33, 38].”
Competitive Gradient Descent (2019, background): “, 2018), and optimism (Rakhlin and Sridharan, 2013; Daskalakis et al., 2017; Mertikopoulos et al., 2019) propose more sophisticated heuristics that the players could use to predict each other’s next move.”
Introduction to Multi-Armed Bandits (2019, background): “However, recent literature obtains Õ(1t ) convergence rates, under various assumptions about the game matrix, the feedback model, or the algorithms themselves (Rakhlin and Sridharan, 2013; Daskalakis et al., 2015; Syrgkanis et al., 2015; Foster et al., 2016; Wei and Luo, 2018).”
Predictor-Corrector Policy Optimization (2018, methodology): “One way to include predictable information is to develop specialized two-step algorithms based on mirrorprox or FTRL-prediction [32, 24, 33].”
A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach (2019, background): “In particular, Rakhlin & Sridharan (2013a,b) introduced the general version of the Optimistic Mirror Descent algorithm in the framework of online optimization.”
Adaptive Online Learning in Dynamic Environments (2018, background): “One regularity that involves the gradient of functions is where m 1 , . . . , m T is a predictable sequence computable by the learner [Chiang et al., 2012, Rakhlin and Sridharan, 2013].”