Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions

• URL: http://arxiv.org/abs/2006.05876v2
• Date: Wed, 14 Apr 2021 06:35:16 GMT
• Title: Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
• Authors: Peng Zhao and Lijun Zhang
• Abstract summary: Original analysis shows that the dynamic regret of OMGD is at most $mathcalO(minmathcalP_T,mathcalS_T)$, where $mathcalP_T$ and $mathcalS_T$ are path-length and squared path-length. We demonstrate that by an improved analysis, the dynamic regret of OMGD can be improved to $mathcalO(minmathcalP_T,mathcalS_T,mathcal
• Score: 24.445848532264307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present an improved analysis for dynamic regret of strongly convex and smooth functions. Specifically, we investigate the Online Multiple Gradient Descent (OMGD) algorithm proposed by Zhang et al. (2017). The original analysis shows that the dynamic regret of OMGD is at most $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T\})$, where $\mathcal{P}_T$ and $\mathcal{S}_T$ are path-length and squared path-length that measures the cumulative movement of minimizers of the online functions. We demonstrate that by an improved analysis, the dynamic regret of OMGD can be improved to $\mathcal{O}(\min\{\mathcal{P}_T,\mathcal{S}_T,\mathcal{V}_T\})$, where $\mathcal{V}_T$ is the function variation of the online functions. Note that the quantities of $\mathcal{P}_T, \mathcal{S}_T, \mathcal{V}_T$ essentially reflect different aspects of environmental non-stationarity -- they are not comparable in general and are favored in different scenarios. Therefore, the dynamic regret presented in this paper actually achieves a \emph{best-of-three-worlds} guarantee and is strictly tighter than previous results.

Related papers

• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties [21.141544548229774]
  We study the form $min_x max_y f(x, y) where $mathcalN$ are Hadamard. We show global interest accelerated by reducing gradient convergence constants.
  arXiv  Detail & Related papers  (2023-05-25T15:43:07Z)
• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  We investigate non-stationary projection-free online learning, and choose dynamic regret and adaptive regret to measure the performance. Our results are the first general-case dynamic regret bounds for projection-free online learning, and can recover the existing $mathcalO(T3/4)$ static regret. We propose a projection-free method to attain an $tildemathcalO(tau3/4)$ adaptive regret bound for any interval with length $tau.
  arXiv  Detail & Related papers  (2023-05-19T15:02:10Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  We investigate the dynamic regret of online Frank-Wolfe (OFW), which is an efficient projection-free algorithm for online convex optimization. In this paper, we derive improved dynamic regret bounds for OFW by extending the fast convergence rates of FW from offline optimization to online optimization.
  arXiv  Detail & Related papers  (2023-02-11T07:19:51Z)
• Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization [40.19608203064051]
  We investigate theoretical guarantees of optimistic online mirror descent (OMD) for the SEA model. For strongly convex and smooth functions, we establish an $mathcalO(sigma_max2 + Sigma_max2) log, better than their $mathcalO(sigma_max2 + Sigma_max2) log T. We establish the first dynamic regret guarantee for the model with convex and smooth functions, which is more favorable than static regret bounds in non-stationary scenarios
  arXiv  Detail & Related papers  (2023-02-09T10:42:11Z)
• Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP [46.86114958340962]
  We present regret algorithms for contextual MDPs under minimum reachability assumption. Our approach is the first optimistic approach applied to contextual MDPs with general function approximation.
  arXiv  Detail & Related papers  (2022-07-22T15:00:15Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• Combinatorial Semi-Bandit in the Non-Stationary Environment [27.394284055156795]
  We investigate the non-stationary semi-bandit problem, both in the switching case and in the dynamic case. By employing another technique, our algorithm no longer needs to know the parameters $mathcal S$ or $mathcal V$ but the regret bounds could become suboptimal.
  arXiv  Detail & Related papers  (2020-02-10T07:10:56Z)

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.