Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems

• URL: http://arxiv.org/abs/2209.01608v1
• Date: Sun, 4 Sep 2022 12:40:57 GMT
• Title: Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems
• Authors: Parvin Nazari, Esmaile Khorram
• Abstract summary: We go through a variant of ADAGRAD (referred to as M-ADAGRAD) in a strong convex setting via the notion of dynamic regret. We demonstrate a regret bound in terms of the path-length of the minimizer sequence that essentially reflects the non-stationarity of environments.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Adaptive gradient algorithms such as ADAGRAD and its variants have gained popularity in the training of deep neural networks. While many works as for adaptive methods have focused on the static regret as a performance metric to achieve a good regret guarantee, the dynamic regret analyses of these methods remain unclear. As opposed to the static regret, dynamic regret is considered to be a stronger concept of performance measurement in the sense that it explicitly elucidates the non-stationarity of the environment. In this paper, we go through a variant of ADAGRAD (referred to as M-ADAGRAD ) in a strong convex setting via the notion of dynamic regret, which measures the performance of an online learner against a reference (optimal) solution that may change over time. We demonstrate a regret bound in terms of the path-length of the minimizer sequence that essentially reflects the non-stationarity of environments. In addition, we enhance the dynamic regret bound by exploiting the multiple accesses of the gradient to the learner in each round. Empirical results indicate that M-ADAGRAD works also well in practice.

Related papers

• Contextual Continuum Bandits: Static Versus Dynamic Regret [70.71582850199871]
  We study the contextual continuum bandits problem, where the learner sequentially receives a side information vector and has to choose an action in a convex set. We demonstrate that any algorithm achieving a sub-linear static regret can be extended to achieve a sub-linear dynamic regret. Inspired by the interior point method and employing self-concordant barriers, we propose an algorithm achieving a sub-linear dynamic regret.
  arXiv  Detail & Related papers  (2024-06-09T10:12:08Z)
• Expected Grad-CAM: Towards gradient faithfulness [7.2203673761998495]
  gradient-weighted CAM approaches still rely on vanilla gradients. Our work proposes a gradient-weighted CAM augmentation that tackles the saturation and sensitivity problem.
  arXiv  Detail & Related papers  (2024-06-03T12:40:30Z)
• Dynamic Regret of Online Markov Decision Processes [84.20723936192945]
  We investigate online Markov Decision Processes (MDPs) with adversarially changing loss functions and known transitions. We choose dynamic regret as the performance measure, defined as the performance difference between the learner and any sequence of feasible changing policies. We consider three foundational models of online MDPs, including episodic loop-free Shortest Path (SSP), episodic SSP, and infinite-horizon MDPs.
  arXiv  Detail & Related papers  (2022-08-26T07:42:53Z)
• Adam revisited: a weighted past gradients perspective [57.54752290924522]
  We propose a novel adaptive method weighted adaptive algorithm (WADA) to tackle the non-convergence issues. We prove that WADA can achieve a weighted data-dependent regret bound, which could be better than the original regret bound of ADAGRAD.
  arXiv  Detail & Related papers  (2021-01-01T14:01:52Z)
• Adaptive Gradient Method with Resilience and Momentum [120.83046824742455]
  We propose an Adaptive Gradient Method with Resilience and Momentum (AdaRem) AdaRem adjusts the parameter-wise learning rate according to whether the direction of one parameter changes in the past is aligned with the direction of the current gradient. Our method outperforms previous adaptive learning rate-based algorithms in terms of the training speed and the test error.
  arXiv  Detail & Related papers  (2020-10-21T14:49:00Z)
• Dynamic Regret of Policy Optimization in Non-stationary Environments [120.01408308460095]
  We propose two model-free policy optimization algorithms, POWER and POWER++, and establish guarantees for their dynamic regret. We show that POWER++ improves over POWER on the second component of the dynamic regret by actively adapting to non-stationarity through prediction. To the best of our knowledge, our work is the first dynamic regret analysis of model-free RL algorithms in non-stationary environments.
  arXiv  Detail & Related papers  (2020-06-30T23:34:37Z)
• Temporal Variability in Implicit Online Learning [15.974402990630402]
  tightest regret analyses only show marginal improvements over Online Mirror Descent. We prove a novel static regret bound that depends on the temporal variability of the sequence of loss functions. We present an adaptive algorithm that achieves this regret bound without prior knowledge of the temporal variability.
  arXiv  Detail & Related papers  (2020-06-12T22:50:34Z)
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
  We propose novel online algorithms that are able to minimize the dynamic regret and adaptive regret simultaneously. Our theoretical guarantee is even stronger in the sense that one algorithm is able to minimize the dynamic regret over any interval.
  arXiv  Detail & Related papers  (2020-02-06T03:32:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.