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
- 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) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation.
Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective.
We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
arXiv Detail & Related papers (2021-07-21T17:10:14Z) - 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) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
We propose a systematic method to transform operations into operations that are differentiable and never locally constant.
Our approach relies on perturbeds, and can be used readily together with existing solvers.
We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
arXiv Detail & Related papers (2020-02-20T11:11:32Z)
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.