論文の概要: Improving Adaptive Online Learning Using Refined Discretization
- arxiv url: http://arxiv.org/abs/2309.16044v1
- Date: Wed, 27 Sep 2023 21:54:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 18:38:36.886330
- Title: Improving Adaptive Online Learning Using Refined Discretization
- Title（参考訳）: Refined Discretization を用いた適応型オンライン学習の改善
- Authors: Zhiyu Zhang, Heng Yang, Ashok Cutkosky, Ioannis Ch. Paschalidis
- Abstract要約: リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
目標は、同時に(i$)2階勾配適応性を達成することである。
本研究は、新しい連続時間インスパイアされたアルゴリズムを用いて、最適レート$O(sqrtV_T)$に改善する。
- 参考スコア（独自算出の注目度）: 44.646191058243645
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study unconstrained Online Linear Optimization with Lipschitz losses. The
goal is to simultaneously achieve ($i$) second order gradient adaptivity; and
($ii$) comparator norm adaptivity also known as "parameter freeness" in the
literature. Existing regret bounds (Cutkosky and Orabona, 2018; Mhammedi and
Koolen, 2020; Jacobsen and Cutkosky, 2022) have the suboptimal $O(\sqrt{V_T\log
V_T})$ dependence on the gradient variance $V_T$, while the present work
improves it to the optimal rate $O(\sqrt{V_T})$ using a novel
continuous-time-inspired algorithm, without any impractical doubling trick.
This result can be extended to the setting with unknown Lipschitz constant,
eliminating the range ratio problem from prior works (Mhammedi and Koolen,
2020).
Concretely, we first show that the aimed simultaneous adaptivity can be
achieved fairly easily in a continuous time analogue of the problem, where the
environment is modeled by an arbitrary continuous semimartingale. Then, our key
innovation is a new discretization argument that preserves such adaptivity in
the discrete time adversarial setting. This refines a non-gradient-adaptive
discretization argument from (Harvey et al., 2023), both algorithmically and
analytically, which could be of independent interest.
- Abstract（参考訳）: リプシッツ損失を伴うオンライン線形最適化について検討した。
目標は、2階勾配適応性(i$)と、「パラメータ自由度」として知られるコンパレータノルム適応性(ii$)を同時に達成することである。
既存の後悔の限界 (cutkosky and orabona, 2018; mhammedi and koolen, 2020; jacobsen and cutkosky, 2022) は、勾配分散 $v_t$ に依存する部分オプティカル $o(\sqrt{v_t\log v_t}) を持つが、本研究は、新しい連続時間インスパイアされたアルゴリズムを用いた最適なレート $o(\sqrt{v_t})$ に改善される。
この結果は未知のリプシッツ定数の設定にまで拡張することができ、以前の作業から範囲比の問題を取り除くことができる(Mhammedi and Koolen, 2020)。
具体的には, 環境が任意の連続セミマーチンゲールによってモデル化される問題に類似した連続時間において, 目標とする同時適応性が比較的容易に達成できることを示す。
そして、我々の重要な革新は、離散時間対逆条件でそのような適応性を維持する新しい離散化論である。
これにより(harvey et al., 2023)から、アルゴリズム的にも分析的にも独立した興味を持つ可能性のある非勾配適応的離散化論を洗練する。
関連論文リスト
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳（メタデータ） (2024-08-17T02:22:08Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Efficient and Near-Optimal Smoothed Online Learning for Generalized
Linear Functions [28.30744223973527]
我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。
一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
論文 参考訳（メタデータ） (2022-05-25T21:31:36Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48:46Z) - Accelerated Learning with Robustness to Adversarial Regressors [1.0499611180329802]
本稿では,逆回帰器の存在下での安定性と収束性を保証する離散時間アルゴリズムを提案する。
特に、回帰器が一定である場合、我々のアルゴリズムは少なくとも $tildemathcalO (1/sqrtepsilon)$ において $epsilon$ 準最適点に達する。
論文 参考訳（メタデータ） (2020-05-04T14:42:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。