Convex Optimization: Algorithms and Complexity

By Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, Aviv Tamar. 2015

738 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

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

In Reinforcement Learning

Citations in the corpus

RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning (2016, background): “Although Bayesian reinforcement learning provides a solid framework for incorporating prior knowledge into the learning process (Strens, 2000; Ghavamzadeh et al., 2015; Kolter & Ng, 2009), exact computation of the Bayesian update is intractable in all but the simplest cases.”
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])”
Zeno: Byzantine-suspicious stochastic gradient descent (2018, background): “2 Strongly convex functions The following lemma is from [3].”
Reinforcement Learning in Healthcare: A Survey (2019, methodology): “traditional RL community, proposing a wealth of exploration strategies including simple heuristics such as ε-greedy and Boltzmann exploration, Bayesian learning [22], [23], countbased methods with Probably Approximately Correct (PAC) guarantees [24], [25], as well as more expressive methods of intri”
Safe Policy Improvement with Baseline Bootstrapping (2017, background): “Two notions of uncertainty: the internal and the parametric, are defined in (Ghavamzadeh et al., 2016): internal uncertainty reflects the uncertainty of the return due to stochastic transitions”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “In the Bayesian case the natural quantity to consider is the Bayes regret, which is the expected regret under the agents prior information [17].”
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning (2016, neutral): “Bayesian RL methods [9, 11, 16, 35], which keep track of a distribution over MDPs, are an alternative to optimism-based methods.”
Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction (2017, background): “…Online Gradient Descent (OGD) (Zinkevich, 2003) and a natural gradient update (Kakade, 2002; Bagnell & Schneider, 2003) which we show is closely related to Exponential Gradient Descent (EG), another popular no-regret algorithm that enjoys an almost dimension-free property (Bubeck et al., 2015).”
EPOpt: Learning Robust Neural Network Policies Using Model Ensembles (2016, methodology): “The broad field of model-based Bayesian RL maintains a belief over models for decision making under uncertainty [8, 13].”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “Inevitably for PSRL, the act of posterior sampling for policy or value is computationally intractable in large systems, so PSRL can not be easily leveraged to high dimensional problems (Ghavamzadeh et al., 2015; Engel et al., 2003; Dearden et al., 1998; Tziortziotis et al., 2013).”
A Tutorial on Thompson Sampling (2017, background): “It is worth mentioning that PSRL fits in the broader family of Bayesian approaches to efficient reinforcement learning; we refer interested readers to the survey paper (Ghavamzadeh et al., 2015).”
Private Stochastic Convex Optimization with Optimal Rates (2019, methodology): “We will now show that if one uses SVRG (Stochastic Variance Reduced Gradient Descent Optimizer) from [JZ13, XZ14, Bub15] as the optimizer O , then one can achieve an error of at most α using O (( n + β/λ ) log(1 /α )) calls to the gradients of (cid:96) ( · , · ) , for any α ∈ (0 , 1] .”
Learning Awareness Models (2018, methodology): “A sea of other methods have been proposed for exploration (MacKay, 1992; Ghavamzadeh et al., 2015; Asmuth et al., 2009; Gal, 2016; Stachniss et al., 2005; Plappert et al., 2017; Fu et al., 2017).”
Deep Exploration via Randomized Value Functions (2017, background): “There is a literature on heuristics that aim to approximate Bayes optimal policies (see [1] for a survey).”
Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, background): “…wide range of branches in the RL ﬁeld, such as transfer RL [99], meta RL [197], federated RL [198], inverse RL [37], integral RL [13], Bayesian RL [199], hierarchical RL [200], interpretable RL [201], etc., can improve the learning efﬁciency and tackle speciﬁc problems in suitable application…”
Offline Meta Reinforcement Learning (2020, background): “We refer the reader to [15] for a comprehensive survey.”
Learning Curve Theory (2021, background): “The error of most stochastic/online optimization algorithms scales as a power law i − 1 / 2 or i − 1 for convex functions [Bub15, Haz16].”