Introduction to Online Convex Optimization

By Elad Hazan. 2016

2,305 citations recorded by the source corpus.

This monograph portrays optimization as a process. In many practical applications the environment is so complex that it is infeasible to lay out a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary as well as beneficial to take a robust approach, by applying an optimization method that learns as one goes along, learning from experience as more aspects of the problem are observed. This view of optimization as a process has become prominent in varied fields and has led to some spectacular success in modeling and systems that are now part of our daily lives.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Optimization & Training

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 Computer Networks and Communications

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Memory-Efficient Adaptive Optimization for Large-Scale Learning (2019, background): “We henceforth assume the general online optimization setting (see [22, 13]).”
Measuring the Effects of Data Parallelism on Neural Network Training (2018, methodology): “Given a sequence of examples drawn i.i.d. from a data source, an upper bound on the performance of SGD applied to L -Lipschitz convex losses is (Hazan, 2016; Shalev-Shwartz 6.”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “, θt} (Hazan, 2019), and stochastic regret (Hazan & Kale, 2014), where the data samples in D are drawn i.”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “As for the convexity and the domain boundedness assumptions, they are quite common in online learning literature such as (Hazan et al., 2016).”
Adaptive Gradient-Based Meta-Learning Methods (2019, neutral): “It is well-known that OMD and the related Follow-the-Regularized-Leader (FTRL), for which our results also hold, generalize many important online methods, e.g. OGD and multiplicative weights [27].”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “The static regret of a sequential online convex optimization method can achieve O √ T and O (log T ) bounds for convex and strongly convex loss functions, respectively [Hazan, 2016, Shalev-Shwartz, 2012, Bubeck, 2011].”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “It is well-known that stochastic gradient descent (SGD) finds a point x with f(x)− f(x∗) ≤ δ in (see for instance textbooks [8, 18, 26])”
Online Continual Learning with Natural Distribution Shifts: An Empirical Study with Visual Data (2021, background): “Following the common definition of online learning [11, 28], we define OCL as a game between a learner and an environment.”
An Algorithmic Perspective on Imitation Learning (2018, background): “cally good on average over the data-sets they are presented, and are sufficiently stable between iterations [Hazan, 2016]. Data as Demonstrator: Venkatraman et al. [2015] extended DAGGER and proposed a framework called Data as Demonstrator (DaD) where the problem of multi-step prediction is formulat”
Online Meta-Learning (2019, neutral): “See Hazan (2016); Shalev-Shwartz (2012); Shalev-Shwartz & Kakade (2008) for algorithmic templates to derive sub-linear regret based algorithms.”
Calibration for the (Computationally-Identifiable) Masses (2017, methodology): “Note that the problem of ﬁnding an α -multi-AE predictor for some collection of sets C can be written as a linear program; the algorithm presented can be viewed as an instance of projected subgradient descent (see [Haz16]).”
XNAS: Neural Architecture Search with Expert Advice (2019, background): “In PEA theory, no statistical assumptions are made, as “simplicity is a merit” [14], and worst-case bounds are derived for the forecaster’s performance.”
A unified view of entropy-regularized Markov decision processes (2017, methodology): “…ﬁeld of online learning theory, the convex-optimization view has enabled a uniﬁed treatment of many existing algorithms and acts today as the primary framework for deriving new algorithms (see the progress from Cesa-Bianchi and Lugosi (2006) through Shalev-Shwartz (2012) to Hazan et al. (2016)).”
Continuous Meta-Learning without Tasks (2019, methodology): “Regularization approaches (Kirkpatrick et al., 2017; Hazan, 2016; Li & Hoiem, 2017) have been shown to be an effective method for avoiding forgetting in continual learning.”
Shampoo: Preconditioned Stochastic Tensor Optimization (2018, methodology): “In fact, we analyze Shampoo in the broader framework of online convex optimization (ShalevShwartz, 2012; Hazan, 2016), thus its convergence applies more generally.”
Adaptive Conformal Inference Under Distribution Shift (2021, background): “Then, one directly computes that Because the pinball loss is convex, this gradient descent update falls within a well understood class of algorithms that have been extensively studied in the online learning literature (see e.g. [17]).”