論文の概要: Optimal and Efficient Algorithms for General Mixable Losses against
Switching Oracles
- arxiv url: http://arxiv.org/abs/2108.06411v1
- Date: Fri, 13 Aug 2021 21:48:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-17 15:24:28.499624
- Title: Optimal and Efficient Algorithms for General Mixable Losses against
Switching Oracles
- Title(参考訳): スイッチングオラクルに対する一般混合損失に対する最適かつ効率的なアルゴリズム
- Authors: Kaan Gokcesu, Hakan Gokcesu
- Abstract要約: 動的環境における混合損失関数のオンライン最適化について検討する。
我々の結果は、個々のシーケンス方式で強い決定論的意味を持つことが保証されている。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of online learning, which has gained significant
attention in recent years due to its applicability in a wide range of fields
from machine learning to game theory. Specifically, we study the online
optimization of mixable loss functions in a dynamic environment. We introduce
online mixture schemes that asymptotically achieves the performance of the best
dynamic estimation sequence of the switching oracle with optimal regret
redundancies. The best dynamic estimation sequence that we compete against is
selected in hindsight with full observation of the loss functions and is
allowed to select different optimal estimations in different time intervals
(segments). We propose two mixtures in our work. Firstly, we propose a
tractable polynomial time complexity algorithm that can achieve the optimal
redundancy of the intractable brute force approach. Secondly, we propose an
efficient logarithmic time complexity algorithm that can achieve the optimal
redundancy up to a constant multiplicity gap. Our results are guaranteed to
hold in a strong deterministic sense in an individual sequence manner.
- Abstract(参考訳): 近年,機械学習からゲーム理論まで幅広い分野に適用可能であることから,オンライン学習の課題が注目されている。
具体的には,動的環境における混合損失関数のオンライン最適化について検討する。
我々は,最適後悔冗長性を持つ切替オラクルの最適動的推定シーケンスの性能を漸近的に達成するオンライン混合スキームを導入する。
我々が競う最良の動的推定列は、損失関数の完全な観察とともに後から選択され、異なる時間間隔(セグメント)で異なる最適推定を選択できる。
私たちは仕事に2つの混合案を提案する。
まず, 難解なブリュート力アプローチの最適冗長性を実現するために, 抽出可能な多項式時間複雑性アルゴリズムを提案する。
第二に、最適冗長性を一定の多重度ギャップまで達成できる効率的な対数時間複雑性アルゴリズムを提案する。
私たちの結果は、個々のシーケンスで強い決定論的意味を持つことが保証されます。
関連論文リスト
- Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳(メタデータ) (2023-01-28T01:50:42Z) - Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
我々は車載OCCにおけるスペクトル効率最適化手法を提案する。
我々は最適化問題をマルコフ決定プロセス(MDP)としてモデル化し、オンラインで適用可能なソリューションの利用を可能にする。
提案手法の性能を広範囲なシミュレーションにより検証し,提案手法の様々な変種とランダムな手法との比較を行った。
論文 参考訳(メタデータ) (2022-05-05T14:25:54Z) - Learning to Schedule Heuristics for the Simultaneous Stochastic
Optimization of Mining Complexes [2.538209532048867]
提案したL2P(Learning-to-perturb)ハイパーヒューリスティックは,マルチ隣り合うシミュレートアニールアルゴリズムである。
L2Pは、効率、堅牢性、一般化能力に重点を置いて、いくつかの実世界の鉱業施設で試験されている。
その結果,反復回数を30~50%削減し,計算時間を30~45%削減した。
論文 参考訳(メタデータ) (2022-02-25T18:20:14Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.71361250701075]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応するのは, 既往の結果よりも厳密であり, 最悪の場合, 同一の値が保証されるためである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses [0.0]
動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。
文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
論文 参考訳(メタデータ) (2021-09-28T15:06:31Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳(メタデータ) (2021-03-10T03:16:12Z) - A closer look at temporal variability in dynamic online learning [19.468067110814808]
この作品は、完全な情報でオンライン学習の文脈でダイナミックな後悔の設定に焦点を当てています。
損失関数の列は時間とともに大きく変化しないと仮定することにより、既存の結果と比較して改善された後悔境界を導き出すことが可能であることを示す。
論文 参考訳(メタデータ) (2021-02-15T16:50:16Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳(メタデータ) (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。