Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds

• URL: http://arxiv.org/abs/2403.00715v2
• Date: Sun, 10 Mar 2024 15:12:16 GMT
• Title: Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds
• Abstract summary: Follow-The-Regularized-Leader (FTRL) is known as an effective and versatile approach in online learning. We formulate the problem of adjusting FTRL's learning rate as a sequential decision-making problem. We propose update rules for learning rate that achieves an upper bound within a constant factor of this lower bound.
• Score: 46.30750729936261
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Follow-The-Regularized-Leader (FTRL) is known as an effective and versatile approach in online learning, where appropriate choice of the learning rate is crucial for smaller regret. To this end, we formulate the problem of adjusting FTRL's learning rate as a sequential decision-making problem and introduce the framework of competitive analysis. We establish a lower bound for the competitive ratio and propose update rules for learning rate that achieves an upper bound within a constant factor of this lower bound. Specifically, we illustrate that the optimal competitive ratio is characterized by the (approximate) monotonicity of components of the penalty term, showing that a constant competitive ratio is achievable if the components of the penalty term form a monotonically non-increasing sequence, and derive a tight competitive ratio when penalty terms are $\xi$-approximately monotone non-increasing. Our proposed update rule, referred to as \textit{stability-penalty matching}, also facilitates constructing the Best-Of-Both-Worlds (BOBW) algorithms for stochastic and adversarial environments. In these environments our result contributes to achieve tighter regret bound and broaden the applicability of algorithms for various settings such as multi-armed bandits, graph bandits, linear bandits, and contextual bandits.

Related papers

• A Unified and Constrained View of Regularization-Based Robust Reinforcement Learning [9.258167884740898]
  Regularization-based methods have become a standard approach for training policies against adversarial input perturbations.<n>In this paper, we unify these methods by deriving new upper bounds on the performance gap between the nominal and worst-case policies.<n>We also conduct extensive adversarial evaluations across several continuous control tasks to validate our theoretical analysis.
  arXiv  Detail & Related papers  (2026-09-11T16:45:36Z)
• Class-Grouped Normalized Momentum and Faster Hyperparameter Exploration to Tackle Class Imbalance in Federated Learning [16.216002257704826]
  Class imbalance poses a critical challenge in federated learning (FL), where underrepresented classes suffer from poor predictive performance.<n>We propose FedCGNM, a client-side in FL that partitions classes into a small number of groups based on minimum within-group variance.<n>To efficiently optimize these rates in small-client regimes, we introduce FedHOO, an X-armed-bandit (XAB) based algorithm.
  arXiv  Detail & Related papers  (2026-07-01T21:09:50Z)
• Joint Training of Multi-Token Prediction in Reinforcement Learning via Optimal Coefficient Calibration [61.46060073417047]
  Multi-Token Prediction (MTP) has been a widely adopted module in pretraining.<n>We show that the per-step effect of MTP on the RL objective can be decomposed into two terms: a first-order correlation and a second-order penalty.<n>We propose an adaptive scheme that tracks the optimal coefficient online via a log-probability proxy at negligible cost.
  arXiv  Detail & Related papers  (2026-05-27T09:07:06Z)
• A Perturbation Approach to Unconstrained Linear Bandits [48.45987210959519]
  We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO)<n>We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem.
  arXiv  Detail & Related papers  (2026-03-30T09:17:46Z)
• DARC: Disagreement-Aware Alignment via Risk-Constrained Decoding [59.16244104797919]
  We propose **Disagreement-Aware Alignment via Risk-Constrained Decoding (DARC)**.<n>DARC frames response selection as distributionally robust, risk-sensitive decision making.<n>Experiments on alignment benchmarks show that DARC reduces disagreement and tail risk while maintaining competitive average quality.
  arXiv  Detail & Related papers  (2026-03-09T09:21:29Z)
• Alternating Reinforcement Learning for Rubric-Based Reward Modeling in Non-Verifiable LLM Post-Training [29.56905427210088]
  gradient-ARM is a framework that jointly optimize a rubric generator and a judge using reinforcement learning from preference feedback.<n>We show that gradient-ARM achieves state-of-the-art performance among baselines on benchmarks and significantly improves downstream policy alignment in both offline and online reinforcement learning settings.
  arXiv  Detail & Related papers  (2026-02-02T00:50:53Z)
• Coverage Improvement and Fast Convergence of On-policy Preference Learning [67.36750525893514]
  Online on-policy preference learning algorithms for language model alignment can significantly outperform their offline counterparts.<n>We analyze how the sampling policy's coverage evolves throughout on-policy training.<n>We develop principled on-policy schemes for reward distillation in the general function class setting.
  arXiv  Detail & Related papers  (2026-01-13T10:46:06Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model.<n>Our results rely on a combination of FTRL over occupancy measures, self-bounding techniques, and new loss estimators inspired by recent advances in online shortest path problems.
  arXiv  Detail & Related papers  (2025-10-20T02:28:08Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences.<n>To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model.<n>Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• Batched Nonparametric Contextual Bandits [21.031965676746776]
  We study nonparametric contextual bandits under batch constraints. We propose a novel batch learning algorithm that achieves the optimal regret. Our theoretical results suggest that for nonparametric contextual bandits, a nearly constant number of policy updates can attain optimal regret.
  arXiv  Detail & Related papers  (2024-02-27T18:06:20Z)
• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  We examine the long-run behavior of regularized, no-regret learning in finite games. We obtain an equivalence between strategic and dynamic stability. We show that methods based on entropic regularization converge at a geometric rate.
  arXiv  Detail & Related papers  (2023-11-04T14:07:33Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  Follow-the-regularized-leader (FTRL) has recently emerged as one of the most promising approaches for obtaining various types of adaptivity in bandit problems. We establish several algorithms with three types of adaptivity: sparsity, game-dependency, and best-of-both-worlds (BOBW)
  arXiv  Detail & Related papers  (2023-05-26T23:20:48Z)
• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [2.628557920905129]
  We establish novel regret bounds for online convex optimization in a setting that interpolates between i.i.d. and fully adversarial losses. In the fully i.i.d. case, our regret bounds match the rates one would expect from results in acceleration, and we also recover the optimalally accelerated rates via online-to-batch conversion.
  arXiv  Detail & Related papers  (2023-03-06T16:41:57Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  We show that the Decision-Estimation Coefficient is necessary and sufficient to obtain low regret for adversarial decision making. We provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures.
  arXiv  Detail & Related papers  (2022-06-27T06:20:37Z)
• Improved Multi-label Classification under Temporal Concept Drift: Rethinking Group-Robust Algorithms in a Label-Wise Setting [10.655403615541141]
  In document classification we often deal with hundreds of classes, including very infrequent ones. Class imbalance and drift can sometimes be mitigated by resampling the training data, but what if the target distribution is determined by unknown future events? We evaluate several group-robust optimization algorithms, initially proposed to mitigate group-level disparities. We find that Invariant Risk Minimization and Spectral Decoupling outperform sampling-based approaches to class imbalance and concept drift.
  arXiv  Detail & Related papers  (2022-03-15T13:08:03Z)
• 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)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation [77.7420231319632]
  We adapt contextual generation of categorical sequences to a policy gradient estimator, which evaluates a set of correlated Monte Carlo (MC) rollouts for variance control. We also demonstrate the use of correlated MC rollouts for binary-tree softmax models, which reduce the high generation cost in large vocabulary scenarios.
  arXiv  Detail & Related papers  (2019-12-31T03:01:55Z)

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.