Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.

By Alekh Agarwal, Ofer Dekel, Lin Xiao. 2010

397 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “In contrast, the current best-known upper bounds areO( 4 √ d2/T ),O( 3 √ d2/T ),O( √ d2/T ) for convex, strongly-convex, and strongly-convex-and-smooth functions respectively [11, 2]; And aO( √ d32/T ) bound for convex functions [3], which is better in terms of dependence on T but very bad in terms ”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The improved rate for the two-point model was later shown in [6].”
Simple random search provides a competitive approach to reinforcement learning (2018, methodology): “The convergence of random search methods for derivative free optimization has been understood for several types of convex optimization [1, 2, 14, 24].”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, methodology): “Without further assumptions on the feedback model, the bound is optimal up to log-factors, as shown byO( √ (d/b)T ) upper bounds for linear or coordinate measurements (where b is the number of measurements or coordinates seen3) [3, 42, 50].”
Stochastic Structured Prediction under Bandit Feedback (2016, methodology): “Work on stochasti p irwise learning has been formalized as derivative-free stochastic zeroth-order optimization [1, 9, 6].”
Reducing Dueling Bandits to Cardinal Bandits (2014, background): “There is yet more work on bandit games where the algorithm plays two bandits (or more) in each iteration, e.g. Agarwal et al. Agarwal et al. (2010), although there the feedback is cardinal and not relative in each step.”
Query Complexity of Derivative-Free Optimization (2012, background): “A related but fundamentally different problem that is somew hat related with the setting considered in this paper is described as online (or stochastic) convex o ptimization with multi-point feedback [18, 5, 19].”
An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback (2015, methodology): “The bandit optimization setting with two-point feedback wa s proposed and studied in [1].”
Simple random search of static linear policies is competitive for reinforcement learning (2018, methodology): “The convergence of random search methods for derivative free optimization has been understood for several types of convex optimization [1, 2, 13, 20].”
Random Gradient-Free Minimization of Convex Functions (2015, background): “Another important contribution is [1], where the authors consider a noisy zero-order oracle and obtain complexity results for different classes”
Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient (2016, methodology): “In order to have optimal dynamic regret bounds, we also consider two-point bandit setting and show that the previous algorithms in (Agarwal et al., 2010; Chiang et al., 2013) by adjusting the step size can achieve an O ( V T ) dynamic regret for general Lipschitz continuous loss functions and an O…”
Exploiting easy data in online optimization (2014, methodology): “A similar model has also been studied as a simpliﬁed version of online convex optimization with partial feedback [1].”
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations (2013, methodology): “2409256 In machine learning and statistics, this interest has centered around bandit optimization [3], [4], [8], where a player and adversary compete, with the player choosing points θ in some domain and an adversary choosing a point x , forcing the player to suffer a loss F(θ; x).”
Trading regret for efficiency: online convex optimization with long term constraints (2011, methodology): “…ζut)− g(xt − ζut))ut ] 8: Compute g̃λ,t = 1 2 (g(xt + ζut) + g(xt − ζut))− ηδλt 9: Receive the convex function ft(x) and experience loss ft(xt) 10: Update xt and λt by xt+1 = Π(1−ξ)B (xt − ηg̃x,t) λt+1 = Π[0,+∞)(λt + ηg̃λ,t) 11: end for Agarwal et al. (2010) by querying g(x) function at two points.”
Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective (2019, methodology): “…assume that J ( θ ) is G -lipschitz and L -smooth, i.e. for all Note that these assumptions are similar to the assumptions made in other zeroth-order analysis works, (Flaxman et al., 2005; Agarwal et al., 2010; Duchi et al., 2015; Shamir, 2013; Ghadimi and Lan, 2013; Nesterov and Spokoiny, 2017).”
A Tour of Reinforcement Learning: The View from Continuous Control (2018, background): “Several works have analyzed the complexity of this method [31, 5, 37], and the upper and lower bounds strongly depend on the dimension of the search space.”
Towards Minimax Policies for Online Linear Optimization with Bandit Feedback (2012, methodology): “In the particular cases ofsemi-bandit feedback —see [Audibert et al., 2011]— and two-points banditfeedback —see [Agarwal et al., 2010], we know how to use Mirror Descent to obtain optimal regret bounds.”
A Survey of Preference-Based Reinforcement Learning Methods (2017, methodology): “Related to dueling bandits is the use of two-point feedback for online convex optimization (Agarwal et al., 2010; Shamir, 2017), which has recently been extended to structured prediction problems (Sokolov et al., 2016).”
Non-Stationary Stochastic Optimization (2013, methodology): “2007), or other feedback structures such as multi-point access (Agarwal et al. 2010). A closer paper, at least in spirit, is that of Hazan and Kale (2010). It derives upper bounds on the regret with respect to the static single best action, in terms of a measure of dispersion of the cost functions c”