Optimization in Dynamic Environments : Improved Regret Rates for Strongly Convex Problems

By Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, Alejandro Ribeiro. 2016

How researchers see this paper

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

1. Yawei Zhao
2. Wendi Wu
3. Mikhail Khodak
4. Ji Liu
5. Zongren Li
6. Ameet Talwalkar
7. Zhi-Hua Zhou
8. Shuang Qiu

Citations in the corpus

• Adaptive Gradient-Based Meta-Learning Methods (2019, methodology): “We use a result showing that OGD with learning rate η ≤ 1 /β over α -strongly- convex, β -strongly-smooth, and L -Lipschitz functions has a bound of O ( L (1 + P Ψ )) on its dynamic regret [43, Corollary 1].”
• Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “References [3, 15, 25, 38, 43, 44] chooses the reference points {y∗ t }t=1 with y∗ t = argminz∈X ft (z), where ft is the loss function at the t th iteration.”
• Understand Dynamic Regret with Switching Cost for Online Decision Making (2019, unknown): “Many other previous researches investigate the regret under di‚erent de€nitions of dynamics such as parameter variation [19, 34, 44, 47], functional variation [7, 25, 46], gradient variation [17], and the mixed regularity [16, 24].”
• Dynamic Regret of Strongly Adaptive Methods (2017, unknown): “Thus, D-Regret(w∗1, . . . ,w ∗ T ) can be treated as the worst case of the dynamic regret, and there are many works that were devoted to minimizing D-Regret(w∗1, . . . ,w ∗ T ) (Jadbabaie et al., 2015; Mokhtari et al., 2016; Yang et al., 2016; Zhang et al., 2017).”
• Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis (2019, methodology): “In this paper, the performance of an online algorithm A is measured by 3 Regret(A) := J(A)− J∗ = J(x(A),u(A))− J∗, (3) which is sometimes called as dynamic regret [29, 51] or competitive difference [52].”
• Online Learning for Markov Decision Processes in Nonstationary Environments: A Dynamic Regret Analysis (2019, unknown): “online decision-making problems such as [18] [20].”
• Adaptive Online Learning in Dynamic Environments (2018, background): “We note that in the setting of the restricted dynamic regret, the curvature of functions indeed makes the upper bound tighter [Mokhtari et al., 2016, Zhang et al., 2017].”
• Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “Although the dynamic regret receives more and more attention recently [Mokhtari et al., 2016, Yang et al., 2016, Zhang et al., 2017a, Shahrampour and Jadbabaie, 2018, Hall and Willett, 2015, Jadbabaie et al., 2015] and some successive studies claim to improve this result by considering specific…”
• Competing with Automata-based Expert Sequences (2018, unknown): “One perspective has been the design of algorithms that maintain a guarantee against sequences that do not vary too much [Mokhtari et al., 2016, Shahrampour and Jadbabaie, 2016, Jadbabaie et al., 2015, Besbes et al., 2015].”
• Distributed Online Optimization in Dynamic Environments Using Mirror Descent (2016, background): “For the same problem, the authors of [15] develop an adaptive algorithm whose regret bound is expressed in terms of the variations of both cost function and minimizer sequence, while in [27], an improved rate is derived for strongly convex objectives.”
• Markov Decision Processes with Time-varying Transition Probabilities and Rewards (2019, unknown): “…transitions across time, the problem is actively studied, e.g. in online convex optimization (Hazan, 2016; Shalev-Shwartz, 2012; Zinkevich, 2003; Mokhtari et al., 2016; Jadbabaie et al., 2015; Li et al., 2018; Besbes et al., 2015; Hall & Willett, 2015; 2013; Zhang et al., 2017), in prediction…”
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, unknown): “Recent year have witnessed the development of theoretical guarantees in form of dynamic regret, where the performance of the learner is measured against that of an adaptive and time-varying adversary [11], [17], [18].”
• Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “Mokhtari et al. [24] obtained O ( D ∗ ) regret.”