論文の概要: Lipschitz and Comparator-Norm Adaptivity in Online Learning

• arxiv url: http://arxiv.org/abs/2002.12242v2
• Date: Sat, 8 Aug 2020 14:14:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 07:47:49.553909
• Title: Lipschitz and Comparator-Norm Adaptivity in Online Learning
• Title（参考訳）: オンライン学習におけるLipschitzとComparator-Norm適応性
• Authors: Zakaria Mhammedi, Wouter M. Koolen
• Abstract要約: 予測も勾配も制約しない環境で,オンライン凸最適化について検討する。 まず、ヒント付き簡易設定のためのパラメータフリーかつスケールフリーなアルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 19.553882766422173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study Online Convex Optimization in the unbounded setting where neither predictions nor gradient are constrained. The goal is to simultaneously adapt to both the sequence of gradients and the comparator. We first develop parameter-free and scale-free algorithms for a simplified setting with hints. We present two versions: the first adapts to the squared norms of both comparator and gradients separately using $O(d)$ time per round, the second adapts to their squared inner products (which measure variance only in the comparator direction) in time $O(d^3)$ per round. We then generalize two prior reductions to the unbounded setting; one to not need hints, and a second to deal with the range ratio problem (which already arises in prior work). We discuss their optimality in light of prior and new lower bounds. We apply our methods to obtain sharper regret bounds for scale-invariant online prediction with linear models.
• Abstract（参考訳）: オンライン凸最適化を,予測も勾配も制約のない非有界環境で研究する。 目標は、勾配のシーケンスとコンパレータの両方に同時に適応することである。 まず,ヒント付き簡易設定のためのパラメータフリーでスケールフリーなアルゴリズムを開発した。 1つはコンパレータとグラデーションの両方の2乗ノルムに1ラウンドあたり$o(d)$の時間を使って別々に適応し、2つめは2乗内積(コンパレータ方向にのみ分散を測定する)に1ラウンドあたり$o(d^3)$の時間で適応する。 次に2つの事前還元を未境界設定に一般化する。1つはヒントを必要とせず、もう1つは範囲比問題(既に先行作業で発生している)に対処する。 先行および新しい下界を考慮した最適性について論じる。 本手法は,線形モデルを用いたスケール不変オンライン予測において,より鋭い後悔境界を求めるために適用する。

関連論文リスト

• Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization [32.939120407900035]
  私たちのアルゴリズムは、イテレーション毎に1つの線形システムだけを解決する必要のある、単純な更新ルールを備えています。 また,提案アルゴリズムの実用性能を,既存の2次アルゴリズムと比較して評価した。
  論文  参考訳（メタデータ） (2024-06-04T06:56:41Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。 本手法の主な考え方は,状況認識による$alphaの適応である。 これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
  論文  参考訳（メタデータ） (2023-09-12T14:36:13Z)
• Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm [12.579063422860072]
  我々は,この問題に対する2座標更新と,1ノルムにおける等式制約付き急降下との接続を利用する。 次に、サポートベクトルマシン双対問題において生じるような、和制約と有界制約の両方で最小化を検討する。
  論文  参考訳（メタデータ） (2023-07-03T17:27:18Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Unconstrained Dynamic Regret via Sparse Coding [46.85145189210752]
  オンライン凸最適化(OCO)を2つの問題構造の結合の下で検討した。 本稿では, スパースコーディングフレームワークを用いて, 適応的再帰境界を新たに実現した。
  論文  参考訳（メタデータ） (2023-01-31T00:52:14Z)
• Scale-free Unconstrained Online Learning for Curved Losses [1.5147172044848798]
  コンパレータのノルム$U$と勾配の最大ノルム$G$に同時に適応する可能性を検討する。 意外なことに、最近の研究では1ドル=Lipschitz損失の特定のケースにおいて、適応性に対するそのような価格が不要であることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T14:10:35Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Comparator-adaptive Convex Bandits [77.43350984086119]
  我々は,コンパレータのノルムが小さい場合,残差が小さい凸バンディットアルゴリズムを開発した。 アイデアを拡張して、リプシッツや滑らかな損失関数で包帯を凸する。
  論文  参考訳（メタデータ） (2020-07-16T16:33:35Z)

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

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