Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses
- URL: http://arxiv.org/abs/2109.13786v1
- Date: Tue, 28 Sep 2021 15:06:31 GMT
- Title: Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses
- Authors: Kaan Gokcesu, Hakan Gokcesu
- Abstract summary: We study the online optimization of mixable loss functions with logarithmic static regret in a dynamic environment.
For the first time in literature, we show that it is also possible to achieve near-logarithmic regret per switch with sub-polynomial complexity per time.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of online learning, which has gained significant
attention in recent years due to its applicability in a wide range of fields
from machine learning to game theory. Specifically, we study the online
optimization of mixable loss functions with logarithmic static regret in a
dynamic environment. The best dynamic estimation sequence that we compete
against is selected in hindsight with full observation of the loss functions
and is allowed to select different optimal estimations in different time
intervals (segments). We propose an online mixture framework that uses these
static solvers as the base algorithm. We show that with the suitable selection
of hyper-expert creations and weighting strategies, we can achieve logarithmic
and squared logarithmic regret per switch in quadratic and linearithmic
computational complexity, respectively. For the first time in literature, we
show that it is also possible to achieve near-logarithmic regret per switch
with sub-polynomial complexity per time. Our results are guaranteed to hold in
a strong deterministic sense in an individual sequence manner.
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) - Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
This work introduces a new notion of complexity, the generalized bracketing numbers, which marries constraints on the adversary to the size of the space.
We then instantiate our bounds in several problems of interest, including online prediction and planning of piecewise continuous functions.
arXiv Detail & Related papers (2023-02-10T18:45:52Z) - Efficient and Near-Optimal Smoothed Online Learning for Generalized
Linear Functions [28.30744223973527]
We give a computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/sigma) regret for realizable K-wise linear classification.
We develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers.
arXiv Detail & Related papers (2022-05-25T21:31:36Z) - Damped Online Newton Step for Portfolio Selection [96.0297968061824]
We revisit the classic online portfolio selection problem, where at each round a learner selects a distribution over a set of portfolios to allocate its wealth.
Existing algorithms that achieve a logarithmic regret for this problem have per-round time and space complexities that scale with the total number of rounds.
We present the first practical online portfolio selection algorithm with a logarithmic regret and whose per-round time and space complexities depend only logarithmically on the horizon.
arXiv Detail & Related papers (2022-02-15T17:01:55Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
We provide the first oracle-efficient, no-regret algorithms in this setting.
We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
arXiv Detail & Related papers (2022-02-09T19:22:34Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
Pairwise learning refers to learning tasks where the loss function depends on a pair instances.
Online descent (OGD) is a popular approach to handle streaming data in pairwise learning.
In this paper, we propose simple and online descent to methods for pairwise learning.
arXiv Detail & Related papers (2021-11-23T18:10:48Z) - 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) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret.
We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
arXiv Detail & Related papers (2020-11-19T10:00:54Z) - 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.