論文の概要: PDE-Based Optimal Strategy for Unconstrained Online Learning
- arxiv url: http://arxiv.org/abs/2201.07877v1
- Date: Wed, 19 Jan 2022 22:21:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-22 02:40:07.886546
- Title: PDE-Based Optimal Strategy for Unconstrained Online Learning
- Title（参考訳）: pdeに基づくオンライン学習の最適戦略
- Authors: Zhiyu Zhang, Ashok Cutkosky, Ioannis Paschalidis
- Abstract要約: 部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。
我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。
これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
- 参考スコア（独自算出の注目度）: 40.61498562988079
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Unconstrained Online Linear Optimization (OLO) is a practical problem setting
to study the training of machine learning models. Existing works proposed a
number of potential-based algorithms, but in general the design of such
potential functions is ad hoc and heavily relies on guessing. In this paper, we
present a framework that generates time-varying potential functions by solving
a Partial Differential Equation (PDE). Our framework recovers some classical
potentials, and more importantly provides a systematic approach to design new
ones.
The power of our framework is demonstrated through a concrete example. When
losses are 1-Lipschitz, we design a novel OLO algorithm with anytime regret
upper bound $C\sqrt{T}+||u||\sqrt{2T}[\sqrt{\log(1+||u||/C)}+2]$, where $C$ is
a user-specified constant and $u$ is any comparator whose norm is unknown and
unbounded a priori. By constructing a matching lower bound, we further show
that the leading order term, including the constant multiplier $\sqrt{2}$, is
tight. To our knowledge, this is the first parameter-free algorithm with
optimal leading constant. The obtained theoretical benefits are validated by
experiments.
- Abstract（参考訳）: unconstrained online linear optimization(olo)は、機械学習モデルのトレーニングを研究するための実用的な問題設定である。
既存の研究はいくつかの潜在的なアルゴリズムを提案しているが、一般にそのようなポテンシャル関数の設計はアドホックであり、推測に大きく依存している。
本稿では,PDE(Partial Differential Equation)を解くことにより,時間変化ポテンシャル関数を生成するフレームワークを提案する。
我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。
私たちのフレームワークのパワーは、具体例で示されています。
損失が 1-Lipschitz である場合、我々は新しい OLO アルゴリズムを設計し、いつでも後悔する上界 $C\sqrt{T}+||||\sqrt{2T}[\sqrt{\log(1+||||||/C)}+2]$ を設計する。
一致する下界を構成することによって、定数乗算器 $\sqrt{2}$ を含む主順序項が密であることを示す。
我々の知る限り、これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
得られた理論的利点は実験によって検証される。
関連論文リスト
- Online non-parametric likelihood-ratio estimation by Pearson-divergence
functional minimization [55.98760097296213]
iid 観測のペア $(x_t sim p, x'_t sim q)$ が時間の経過とともに観測されるような,オンラインな非パラメトリック LRE (OLRE) のための新しいフレームワークを提案する。
本稿では,OLRE法の性能に関する理論的保証と,合成実験における実証的検証について述べる。
論文 参考訳（メタデータ） (2023-11-03T13:20:11Z) - Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
論文 参考訳（メタデータ） (2023-10-03T17:51:42Z) - Target-based Surrogates for Stochastic Optimization [26.35752393302125]
我々は(おそらく)勾配を計算するのに費用がかかる関数の最小化を考える。
このような機能は、計算強化学習、模倣学習、および敵の訓練で広く用いられている。
我々のフレームワークは、最適化アルゴリズムを用いて、効率的に最小化できるサロゲートを構築することができる。
論文 参考訳（メタデータ） (2023-02-06T08:08:34Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T09:03:24Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。