Non-exponentially weighted aggregation: regret bounds for unbounded loss functions

• URL: http://arxiv.org/abs/2009.03017v5
• Date: Thu, 17 Jun 2021 09:27:00 GMT
• Title: Non-exponentially weighted aggregation: regret bounds for unbounded loss functions
• Abstract summary: We tackle the problem of online optimization with a general, possibly unbounded, loss function. It is well known that when the loss is bounded, the exponentially weighted aggregation strategy (EWA) leads to a regret in $sqrtT$ after $T$ steps.
• Score: 8.22379888383833
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We tackle the problem of online optimization with a general, possibly unbounded, loss function. It is well known that when the loss is bounded, the exponentially weighted aggregation strategy (EWA) leads to a regret in $\sqrt{T}$ after $T$ steps. In this paper, we study a generalized aggregation strategy, where the weights no longer depend exponentially on the losses. Our strategy is based on Follow The Regularized Leader (FTRL): we minimize the expected losses plus a regularizer, that is here a $\phi$-divergence. When the regularizer is the Kullback-Leibler divergence, we obtain EWA as a special case. Using alternative divergences enables unbounded losses, at the cost of a worst regret bound in some cases.

Related papers

• Toward Simultaneously Optimal Regret in U-Calibration [41.366442572915496]
  Existing U-calibration algorithms achieve worst-case optimal $O(sqrtT)$ regret for every bounded proper loss.<n>We show, even for smooth losses such as squared loss, they incur $(sqrtT)$ regret instead of the optimal $O(log T)$ regret.<n>Specifically, we design a single forecast algorithm that simultaneously achieves $tilde O(sqrtT)$ regret for every bounded proper loss.
  arXiv  Detail & Related papers  (2026-06-16T22:44:37Z)
• Calibeating for general proper losses: A Bregman divergence approach [10.525701754548102]
  This work introduces a general framework for calibeating based on regret.<n>We consider a large family of proper losses that includes $$-Tsallis losses (for $in [1, 2]$) and Lipschitz losses.
  arXiv  Detail & Related papers  (2026-05-17T05:39:22Z)
• Non-Stationary Online Structured Prediction with Surrogate Losses [22.848052937383244]
  We prove a bound of the form $F_T + C (1 + P_T)$ on the cumulative target loss.<n>Our core idea is to synthesize the dynamic regret bound of the gradient online descent (OGD) with the technique of exploiting the surrogate gap.<n>Our analysis also sheds light on a new Polyak-style learning rate for OGD, which systematically offers target-loss guarantees and exhibits promising empirical performance.
  arXiv  Detail & Related papers  (2025-10-08T14:43:44Z)
• Non-stationary Bandit Convex Optimization: A Comprehensive Study [28.086802754034828]
  Bandit Convex Optimization is a class of sequential decision-making problems.<n>We study this problem in non-stationary environments.<n>We aim to minimize the regret under three standard measures of non-stationarity.
  arXiv  Detail & Related papers  (2025-06-03T15:18:41Z)
• When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses [12.39860047886679]
  We develop adaptive algorithms that do not require prior knowledge about the range or the second moment of the losses.<n>Existing adaptive algorithms have what is typically considered a lower-order term in their regret guarantees.
  arXiv  Detail & Related papers  (2025-06-02T14:29:05Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  We quantify the excess risk incurred using approximate posterior probabilities in batch binary decision-making. We identify regimes where recalibration alone addresses most of the regret, and regimes where the regret is dominated by the grouping loss. On NLP experiments, we show that these quantities identify when the expected gain of more advanced post-training is worth the operational cost.
  arXiv  Detail & Related papers  (2025-03-23T10:52:36Z)
• Any-stepsize Gradient Descent for Separable Data under Fenchel--Young Losses [17.835960292396255]
  We show arbitrary-stepsize gradient convergence for a general loss function based on the framework of emphFenchel--Young losses. We argue that these better rate is possible because of emphseparation margin of loss functions, instead of the self-bounding property.
  arXiv  Detail & Related papers  (2025-02-07T12:52:12Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  We study Online Convex Optimization (OCO) with adversarial constraints. We focus on a setting where the algorithm has access to predictions of the loss and constraint functions. Our results show that we can improve the current best bounds of $ O(sqrtT) $ regret and $ tildeO(sqrtT) $ cumulative constraint violations.
  arXiv  Detail & Related papers  (2024-12-11T03:06:42Z)
• A Unified Analysis for Finite Weight Averaging [50.75116992029417]
  Averaging iterations of Gradient Descent (SGD) have achieved empirical success in training deep learning models, such as Weight Averaging (SWA), Exponential Moving Average (EMA), and LAtest Weight Averaging (LAWA) In this paper, we generalize LAWA as Finite Weight Averaging (FWA) and explain their advantages compared to SGD from the perspective of optimization and generalization.
  arXiv  Detail & Related papers  (2024-11-20T10:08:22Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [58.967816314671296]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression. Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• 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)
• A note on generalization bounds for losses with finite moments [28.102352176005514]
  The paper derives a high-probability PAC-Bayes bound for losses with a bounded variance. It extends results to guarantees in expectation and single-draw PAC-Bayes.
  arXiv  Detail & Related papers  (2024-03-25T12:15:55Z)
• Cross-Entropy Loss Functions: Theoretical Analysis and Applications [27.3569897539488]
  We present a theoretical analysis of a broad family of loss functions, that includes cross-entropy (or logistic loss), generalized cross-entropy, the mean absolute error and other cross-entropy-like loss functions. We show that these loss functions are beneficial in the adversarial setting by proving that they admit $H$-consistency bounds. This leads to new adversarial robustness algorithms that consist of minimizing a regularized smooth adversarial comp-sum loss.
  arXiv  Detail & Related papers  (2023-04-14T17:58:23Z)
• Near-Optimal Adversarial Reinforcement Learning with Switching Costs [43.895798638743784]
  We show how to develop a provably efficient algorithm for adversarial RL with switching costs. Our lower bound indicates that, due to the fundamental challenge of switching costs in adversarial RL, the best achieved regret is no longer achievable. We propose two novel switching-reduced algorithms with regrets that match our lower bound when the transition function is known.
  arXiv  Detail & Related papers  (2023-02-08T23:41:29Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  We study the problem of regret minimization for episodic Reinforcement Learning (RL) We focus on learning with general function classes and general model classes. We show that a logarithmic regret bound is realizable by algorithms with $O(log T)$ switching cost.
  arXiv  Detail & Related papers  (2022-03-03T02:55:55Z)
• 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)
• Alpha-IoU: A Family of Power Intersection over Union Losses for Bounding Box Regression [59.72580239998315]
  We generalize existing IoU-based losses to a new family of power IoU losses that have a power IoU term and an additional power regularization term. Experiments on multiple object detection benchmarks and models demonstrate that $alpha$-IoU losses can surpass existing IoU-based losses by a noticeable performance margin.
  arXiv  Detail & Related papers  (2021-10-26T13:09:20Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback. Our main result is a computationally efficient algorithm with $O(sqrtK)$ regret for this setting, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2021-01-31T16:49:07Z)
• Gradient descent follows the regularization path for general losses [33.155195855431344]
  We show that for empirical risk minimization over linear predictors with arbitrary convex losses, the gradient-descent path and the algorithm-independent regularization path converge to the same direction. We provide a justification for the widely-used exponentially-tailed losses.
  arXiv  Detail & Related papers  (2020-06-19T17:01:25Z)

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.