論文の概要: Improving Adaptive Online Learning Using Refined Discretization
- arxiv url: http://arxiv.org/abs/2309.16044v2
- Date: Thu, 22 Feb 2024 05:09:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 18:41:34.410529
- Title: Improving Adaptive Online Learning Using Refined Discretization
- Title（参考訳）: Refined Discretization を用いた適応型オンライン学習の改善
- Authors: Zhiyu Zhang, Heng Yang, Ashok Cutkosky, Ioannis Ch. Paschalidis
- Abstract要約: リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
- 参考スコア（独自算出の注目度）: 44.646191058243645
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study unconstrained Online Linear Optimization with Lipschitz losses.
Motivated by the pursuit of instance optimality, we propose a new algorithm
that simultaneously achieves ($i$) the AdaGrad-style second order gradient
adaptivity; and ($ii$) the comparator norm adaptivity also known as "parameter
freeness" in the literature. In particular,
- our algorithm does not employ the impractical doubling trick, and does not
require an a priori estimate of the time-uniform Lipschitz constant;
- the associated regret bound has the optimal $O(\sqrt{V_T})$ dependence on
the gradient variance $V_T$, without the typical logarithmic multiplicative
factor;
- the leading constant in the regret bound is "almost" optimal.
Central to these results is a continuous time approach to online learning. 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（参考訳）: リプシッツ損失を伴うオンライン線形最適化について検討した。
インスタンス最適性の追求により,AdaGradスタイルの2次勾配適応度(i$)を同時に達成する新しいアルゴリズムを提案し,また文献において「パラメータ自由性」としても知られるコンパレータノルム適応度(ii$)を提案する。
特に、我々のアルゴリズムは非実用的二重化のトリックを使わず、時間一様リプシッツ定数の事前推定を必要としない; - 関連する後悔境界は、勾配分散に最適な$o(\sqrt{v_t})$依存性を持つ; - 典型的な対数乗因子を伴わずに; - 後悔境界のリード定数は「ほぼ」最適である。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
まず, 環境が任意の連続セミマーチンゲールによってモデル化される問題と同様の連続時間において, 目標とする同時適応性が比較的容易に達成できることを示す。
そして、我々の重要な革新は、離散時間対逆条件でそのような適応性を維持する新しい離散化論である。
これにより(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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。