A closer look at temporal variability in dynamic online learning
- URL: http://arxiv.org/abs/2102.07666v1
- Date: Mon, 15 Feb 2021 16:50:16 GMT
- Title: A closer look at temporal variability in dynamic online learning
- Authors: Nicol\`o Campolongo and Francesco Orabona
- Abstract summary: This work focuses on the setting of dynamic regret in the context of online learning with full information.
By assuming that the sequence of loss functions does not vary much with time, we show that it is possible to incur improved regret bounds compared to existing results.
- Score: 19.468067110814808
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work focuses on the setting of dynamic regret in the context of online
learning with full information. In particular, we analyze regret bounds with
respect to the temporal variability of the loss functions. By assuming that the
sequence of loss functions does not vary much with time, we show that it is
possible to incur improved regret bounds compared to existing results. The key
to our approach is to use the loss function (and not its gradient) during the
optimization process. Building on recent advances in the analysis of Implicit
algorithms, we propose an adaptation of the Implicit version of Online Mirror
Descent to the dynamic setting. Our proposed algorithm is adaptive not only to
the temporal variability of the loss functions, but also to the path length of
the sequence of comparators when an upper bound is known. Furthermore, our
analysis reveals that our results are tight and cannot be improved without
further assumptions. Next, we show how our algorithm can be applied to the
setting of learning with expert advice or to settings with composite loss
functions. Finally, when an upper bound to the path-length is not fixed
beforehand we show how to combine a greedy strategy with existing
strongly-adaptive algorithms to compete optimally against different sequences
of comparators simultaneously.
Related papers
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
gradient-variation online learning aims to achieve regret guarantees that scale with variations in gradients of online functions.
Recent efforts in neural network optimization suggest a generalized smoothness condition, allowing smoothness to correlate with gradient norms.
We provide the applications for fast-rate convergence in games and extended adversarial optimization.
arXiv Detail & Related papers (2024-08-17T02:22:08Z) - LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner.
We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
arXiv Detail & Related papers (2024-08-12T17:08:31Z) - Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
We study unconstrained Online Linear Optimization with Lipschitz losses.
Motivated by the pursuit of instance optimality, we propose a new algorithm.
Central to these results is a continuous time approach to online learning.
arXiv Detail & Related papers (2023-09-27T21:54:52Z) - Ordering for Non-Replacement SGD [7.11967773739707]
We seek to find an ordering that can improve the convergence rates for the non-replacement form of the algorithm.
We develop optimal orderings for constant and decreasing step sizes for strongly convex and convex functions.
In addition, we are able to combine the ordering with mini-batch and further apply it to more complex neural networks.
arXiv Detail & Related papers (2023-06-28T00:46:58Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.
An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
arXiv Detail & Related papers (2023-02-01T08:50:48Z) - 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 and Efficient Algorithms for General Mixable Losses against
Switching Oracles [0.0]
We study the online optimization of mixable loss functions in a dynamic environment.
Our results are guaranteed to hold in a strong deterministic sense in an individual sequence manner.
arXiv Detail & Related papers (2021-08-13T21:48:55Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order.
We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
arXiv Detail & Related papers (2021-06-29T09:48:46Z) - 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) - 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)
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.