論文の概要: 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つの混合案を提案する。
まず, 難解なブリュート力アプローチの最適冗長性を実現するために, 抽出可能な多項式時間複雑性アルゴリズムを提案する。
第二に、最適冗長性を一定の多重度ギャップまで達成できる効率的な対数時間複雑性アルゴリズムを提案する。
私たちの結果は、個々のシーケンスで強い決定論的意味を持つことが保証されます。
関連論文リスト
- Constrained Hybrid Metaheuristic Algorithm for Probabilistic Neural Networks Learning [0.3686808512438362]
本研究では、確率論的ニューラルネットワーク(PNN)のトレーニングを強化するためのハイブリッドメタヒューリスティックアルゴリズムの可能性について検討する。
勾配に基づくアプローチのような伝統的な学習手法は、しばしば高次元で不確実な環境を最適化するのに苦労する。
本稿では,複数の個体群に基づく最適化手法を組み合わせた制約付きハイブリッドメタヒューリスティック(cHM)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2025-01-26T19:49:16Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳(メタデータ) (2023-12-28T23:15:18Z) - An Expandable Machine Learning-Optimization Framework to Sequential
Decision-Making [0.0]
逐次的意思決定問題を効率的に解決する統合予測最適化(PredOpt)フレームワークを提案する。
本稿では,機械学習(ML)における逐次依存,実現可能性,一般化といった課題に対処し,インスタンス問題に対する最適解の予測を行う。
論文 参考訳(メタデータ) (2023-11-12T21:54:53Z) - Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。
ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。
提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
論文 参考訳(メタデータ) (2023-10-10T00:21:10Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - 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 [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔の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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。