論文の概要: Computing Optimal Regularizers for Online Linear Optimization

• arxiv url: http://arxiv.org/abs/2410.17336v1
• Date: Tue, 22 Oct 2024 18:10:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-24 13:56:27.938540
• Title: Computing Optimal Regularizers for Online Linear Optimization
• Title（参考訳）: オンライン線形最適化のための最適正規化器の計算
• Authors: Khashayar Gatmiry, Jon Schneider, Stefanie Jegelka,
• Abstract要約: FTRL(Follow-the-Regularized-Leader)アルゴリズムはオンライン線形最適化(OLO)のための一般的な学習アルゴリズムである。 本稿では,最良学習アルゴリズムの一定要素内における後悔を実現するFTRLのインスタンス化が存在することを示す。
• 参考スコア（独自算出の注目度）: 38.72709491927979
• License:
• Abstract: Follow-the-Regularized-Leader (FTRL) algorithms are a popular class of learning algorithms for online linear optimization (OLO) that guarantee sub-linear regret, but the choice of regularizer can significantly impact dimension-dependent factors in the regret bound. We present an algorithm that takes as input convex and symmetric action sets and loss sets for a specific OLO instance, and outputs a regularizer such that running FTRL with this regularizer guarantees regret within a universal constant factor of the best possible regret bound. In particular, for any choice of (convex, symmetric) action set and loss set we prove that there exists an instantiation of FTRL which achieves regret within a constant factor of the best possible learning algorithm, strengthening the universality result of Srebro et al., 2011. Our algorithm requires preprocessing time and space exponential in the dimension $d$ of the OLO instance, but can be run efficiently online assuming a membership and linear optimization oracle for the action and loss sets, respectively (and is fully polynomial time for the case of constant dimension $d$). We complement this with a lower bound showing that even deciding whether a given regularizer is $\alpha$-strongly-convex with respect to a given norm is NP-hard.
• Abstract（参考訳）: FTRL(Follow-the-Regularized-Leader)アルゴリズムは、オンライン線形最適化(OLO)のための一般的な学習アルゴリズムであり、サブ線形後悔を保証する。 我々は,特定のOLOインスタンスに対して,入力凸および対称作用集合および損失集合を仮定し,この正規化器を用いてFTRLを動作させることで,最良な後悔境界の普遍的定数係数内で後悔が保証されるような正規化器を出力するアルゴリズムを提案する。 特に、(凸、対称)作用集合と損失集合の任意の選択に対して、最良の学習アルゴリズムの定数係数内で後悔を達成し、Srebro et al , 2011 の普遍性結果を強化する FTRL のインスタンス化が存在することを証明します。 我々のアルゴリズムはOLOインスタンスの次元$d$で前処理時間と空間指数を必要とするが、各アクションと損失集合に対するメンバシップと線形最適化のオラクルを仮定して、オンラインで効率的に実行することができる(そして、定数次元$d$の場合の多項式時間である)。 これを、与えられたノルムに関して与えられた正則化器が$\alpha$-strongly-convexであるかどうかを判断する下界で補う。

関連論文リスト

• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.7310264583128445]
  FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。 本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-30T16:00:23Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。 我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
  論文  参考訳（メタデータ） (2023-05-26T23:20:48Z)
• Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms [41.06668954462585]
  本研究では,適応型マルチアームバンディットアルゴリズムを設計する際の課題について検討する。 FTRLには多種多様な正規化要因と新たな学習率スケジュールが不要であることを示す。
  論文  参考訳（メタデータ） (2023-02-27T06:09:10Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
  定常分布補正を用いたオフラインRLアルゴリズムの分散正則化を提案する。 Fenchel双対性を用いることで、分散正規化器の勾配を計算するための二重サンプリング問題を回避することができることを示す。 オフライン分散正規化アルゴリズム(OVAR)は,既存のオフラインポリシー最適化アルゴリズムを拡張できる。
  論文  参考訳（メタデータ） (2022-12-29T18:25:01Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Screening for Sparse Online Learning [11.523471275501855]
  スパーシティ促進レギュラライザーは、低複素構造(例えば)を課すために広く使用されている。 l1-norm for sparsity) 教師付き学習の回帰係数に対する。 ほとんどのオンラインアルゴリズムは、ステップサイズと非消去の分散のためにプロパティを持っていません。 本稿では,オンラインアルゴリズムが生成するイテレートの不要な特徴を解消する方法を示し,有限なアクティビティ同定を強制する。
  論文  参考訳（メタデータ） (2021-01-18T10:40:47Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。