Optimal Dynamic Regret in Exp-Concave Online Learning

• URL: http://arxiv.org/abs/2104.11824v1
• Date: Fri, 23 Apr 2021 21:36:51 GMT
• Title: Optimal Dynamic Regret in Exp-Concave Online Learning
• Authors: Dheeraj Baby and Yu-Xiang Wang
• Abstract summary: We consider the problem of the Zinkevich (2003)-style dynamic regret minimization in online learning with exp-contrivial losses. We show that whenever improper learning is allowed, a Strongly Adaptive online learner achieves the dynamic regret of $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ where $C_n$ is the total variation (a.k.a. path length) of the an arbitrary sequence of comparators that may not be known to the learner ahead of time.
• Score: 28.62891856368132
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider the problem of the Zinkevich (2003)-style dynamic regret minimization in online learning with exp-concave losses. We show that whenever improper learning is allowed, a Strongly Adaptive online learner achieves the dynamic regret of $\tilde O(d^{3.5}n^{1/3}C_n^{2/3} \vee d\log n)$ where $C_n$ is the total variation (a.k.a. path length) of the an arbitrary sequence of comparators that may not be known to the learner ahead of time. Achieving this rate was highly nontrivial even for squared losses in 1D where the best known upper bound was $O(\sqrt{nC_n} \vee \log n)$ (Yuan and Lamperski, 2019). Our new proof techniques make elegant use of the intricate structures of the primal and dual variables imposed by the KKT conditions and could be of independent interest. Finally, we apply our results to the classical statistical problem of locally adaptive non-parametric regression (Mammen, 1991; Donoho and Johnstone, 1998) and obtain a stronger and more flexible algorithm that do not require any statistical assumptions or any hyperparameter tuning.

Related papers

• Highly Adaptive Ridge [84.38107748875144]
  We propose a regression method that achieves a $n-2/3$ dimension-free L2 convergence rate in the class of right-continuous functions with square-integrable sectional derivatives. Har is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion. We demonstrate empirical performance better than state-of-the-art algorithms for small datasets in particular.
  arXiv  Detail & Related papers  (2024-10-03T17:06:06Z)
• 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)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  We study reinforcement learning with linear function approximation and adversarially changing cost functions. We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback.
  arXiv  Detail & Related papers  (2023-01-30T17:26:39Z)
• Optimal Dynamic Regret in LQR Control [23.91519151164528]
  We consider the problem of nonstochastic control with a sequence of quadratic losses, i.e., LQR control. We provide an online algorithm that achieves an optimal dynamic (policy) regret of $tildeO(textmaxn1/3 mathcalTV(M_1:n)2/3, 1)$.
  arXiv  Detail & Related papers  (2022-06-18T18:00:21Z)
• Second Order Path Variationals in Non-Stationary Online Learning [23.91519151164528]
  We show that appropriately designed Strongly Adaptive algorithms achieve a dynamic regret of $tilde O(d2 n1/5 C_n2/5 vee d2)$. The aforementioned dynamic regret rate is shown to be optimal modulo dimension dependencies and poly-logarithmic factors of $n$.
  arXiv  Detail & Related papers  (2022-05-04T07:14:39Z)
• 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)
• Scale-free Unconstrained Online Learning for Curved Losses [1.5147172044848798]
  We investigate the possibility of adapting simultaneously to the norm $U$ of the comparator and the maximum norm $G$ of the gradients. Surprisingly, recent results show that no such price for adaptivity is needed in the specific case of $1$-Lipschitz losses.
  arXiv  Detail & Related papers  (2022-02-11T14:10:35Z)
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond [23.91519151164528]
  We show that in a proper learning setup, Strongly Adaptive algorithms can achieve the near optimal dynamic regret. We also derive near optimal dynamic regret rates for the special case of proper online learning with exp-concave losses.
  arXiv  Detail & Related papers  (2022-01-21T22:08:07Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  We show that Strongly Adaptive (SA) algorithms can be viewed as a principled way of controlling dynamic regret. We derive a new lower bound on a certain penalized regret which establishes the near minimax optimality of online Kernel Ridge Regression (KRR)
  arXiv  Detail & Related papers  (2021-11-22T21:52:47Z)
• Strongly Adaptive OCO with Memory [49.319621885036035]
  We propose the first strongly adaptive algorithm for online learning with memory. Our algorithm results in a strongly adaptive regret bound for the control of linear time-varying systems.
  arXiv  Detail & Related papers  (2021-02-02T17:26:08Z)
• 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)

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.