Second Order Path Variationals in Non-Stationary Online Learning
- URL: http://arxiv.org/abs/2205.01921v1
- Date: Wed, 4 May 2022 07:14:39 GMT
- Title: Second Order Path Variationals in Non-Stationary Online Learning
- Authors: Dheeraj Baby and Yu-Xiang Wang
- Abstract summary: 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$.
- Score: 23.91519151164528
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider the problem of universal dynamic regret minimization under
exp-concave and smooth losses. We show that appropriately designed Strongly
Adaptive algorithms achieve a dynamic regret of $\tilde O(d^2 n^{1/5} C_n^{2/5}
\vee d^2)$, where $n$ is the time horizon and $C_n$ a path variational based on
second order differences of the comparator sequence. Such a path variational
naturally encodes comparator sequences that are piecewise linear -- a powerful
family that tracks a variety of non-stationarity patterns in practice (Kim et
al, 2009). The aforementioned dynamic regret rate is shown to be optimal modulo
dimension dependencies and poly-logarithmic factors of $n$. Our proof
techniques rely on analysing the KKT conditions of the offline oracle and
requires several non-trivial generalizations of the ideas in Baby and Wang,
2021, where the latter work only leads to a slower dynamic regret rate of
$\tilde O(d^{2.5}n^{1/3}C_n^{2/3} \vee d^{2.5})$ for the current problem.
Related papers
- ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
We present a novel, fast (exponential rate), ab initio (hyper-free) gradient based adaption.
The main idea of the method is to adapt the $alpha by situational awareness.
It can be applied to problems of any dimensions n and scales only linearly.
arXiv Detail & Related papers (2023-09-12T14:36:13Z) - 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) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise.
Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret.
We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
arXiv Detail & Related papers (2023-02-21T00:17:24Z) - 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 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) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities.
Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
arXiv Detail & Related papers (2021-12-29T02:42:59Z) - Optimal Dynamic Regret in Exp-Concave Online Learning [28.62891856368132]
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.
arXiv Detail & Related papers (2021-04-23T21:36:51Z) - Adaptive Online Estimation of Piecewise Polynomial Trends [23.91519151164528]
We consider the framework of non-stationary optimization with squared error losses and noisy gradient feedback.
Motivated from the theory of non-parametric regression, we introduce a new variational constraint.
We show that the same policy is minimax optimal for several other non-parametric families of interest.
arXiv Detail & Related papers (2020-09-30T19:30:28Z) - 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.