論文の概要: Distributed Online Non-convex Optimization with Composite Regret
- arxiv url: http://arxiv.org/abs/2209.10105v1
- Date: Wed, 21 Sep 2022 04:16:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 16:01:13.676507
- Title: Distributed Online Non-convex Optimization with Composite Regret
- Title(参考訳): 複合後悔を伴う分散オンライン非凸最適化
- Authors: Zhanhong Jiang, Aditya Balu, Xian Yeow Lee, Young M. Lee, Chinmay
Hegde, Soumik Sarkar
- Abstract要約: 本稿では,分散オンライン一般損失に対する新たなネットワーク後悔を伴う,新たな複合後悔を提案する。
我々の知る限り、オンラインの非線形学習における最初の後悔である。
- 参考スコア(独自算出の注目度): 31.53784277195043
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Regret has been widely adopted as the metric of choice for evaluating the
performance of online optimization algorithms for distributed, multi-agent
systems. However, data/model variations associated with agents can
significantly impact decisions and requires consensus among agents. Moreover,
most existing works have focused on developing approaches for (either strongly
or non-strongly) convex losses, and very few results have been obtained
regarding regret bounds in distributed online optimization for general
non-convex losses. To address these two issues, we propose a novel composite
regret with a new network regret-based metric to evaluate distributed online
optimization algorithms. We concretely define static and dynamic forms of the
composite regret. By leveraging the dynamic form of our composite regret, we
develop a consensus-based online normalized gradient (CONGD) approach for
pseudo-convex losses, and it provably shows a sublinear behavior relating to a
regularity term for the path variation of the optimizer. For general non-convex
losses, we first shed light on the regret for the setting of distributed online
non-convex learning based on recent advances such that no deterministic
algorithm can achieve the sublinear regret. We then develop the distributed
online non-convex optimization with composite regret (DINOCO) without access to
the gradients, depending on an offline optimization oracle. DINOCO is shown to
achieve sublinear regret; to our knowledge, this is the first regret bound for
general distributed online non-convex learning.
- Abstract(参考訳): 後悔は分散マルチエージェントシステムにおけるオンライン最適化アルゴリズムの性能を評価するための選択指標として広く採用されている。
しかし、エージェントに関連するデータ/モデルの変化は決定に大きな影響を与え、エージェント間のコンセンサスを必要とする。
さらに、既存の作品の多くは、(強くまたは非強固な)凸損失に対するアプローチの開発に焦点を当てており、一般的な非凸損失に対する分散オンライン最適化における後悔の限界に関する結果はほとんど得られていない。
そこで本研究では, 分散オンライン最適化アルゴリズムを評価するために, 新たなネットワークret-based metricsを用いた複合後悔モデルを提案する。
合成後悔の静的および動的形態を具体的に定義する。
複合後悔の動的な形態を活かし,疑似凸損失に対するコンセンサスに基づくオンライン正規化勾配(congd)手法を開発し,オプティマイザの経路変動に対する正規性項に関連するサブリニア挙動を示す。
一般の非凸損失に対しては,近年の進歩を踏まえて,分散オンライン非凸学習の設定に対する後悔を軽視し,決定論的アルゴリズムがサブ線形後悔を達成できないようにした。
次に,オフラインの最適化オラクルに依存することなく,複合的後悔 (DINOCO) を伴う分散オンライン非凸最適化を開発する。
私たちの知る限りでは、これは一般的な分散オンライン非凸学習における最初の後悔である。
関連論文リスト
- Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
論文 参考訳(メタデータ) (2023-09-27T21:54:52Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳(メタデータ) (2023-09-16T07:30:12Z) - Optimal Regularized Online Allocation by Adaptive Re-Solving [16.873430173722994]
本稿では、正規化されたオンラインリソース割り当て問題を解決するために、デュアルベースのアルゴリズムフレームワークを提案する。
資源制約を適応的に更新する戦略の下で、提案手法は経験的二重問題に対する近似解をある程度の精度で要求するのみである。
驚いたことに、二重目的関数の微妙な解析により、後悔境界における悪名高いログ係数を排除できる。
論文 参考訳(メタデータ) (2022-09-01T12:23:26Z) - Provably Efficient Reinforcement Learning for Online Adaptive Influence
Maximization [53.11458949694947]
本稿では,リアルタイムフィードバックに基づいてシードノードを逐次活性化する,コンテンツ依存型オンライン影響問題の適応バージョンについて検討する。
提案アルゴリズムは,最適政策を楽観的に改善しつつ,ネットワークモデルの推定を保守し,適応的にシードを選択する。
論文 参考訳(メタデータ) (2022-06-29T18:17:28Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳(メタデータ) (2022-05-02T08:48:22Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems [1.6709415233613623]
本稿では,分散的に不確実な力学系のクラスを対象とする最適化問題 (P) に対して,データ駆動型オンラインソリューションを構築するための新しい手法を提案する。
導入されたフレームワークは、パラメータ化された制御依存のあいまいさセットを通じて、分散システムの不確実性の同時学習を可能にする。
また、Nesterovの高速化段階アルゴリズムのオンライン版を導入し、その性能を分析して、分散性理論を用いてこの問題のクラスを解く。
論文 参考訳(メタデータ) (2021-02-18T01:49:06Z) - Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。
私たちは、後悔マッチングとヘッジを含むオンラインアルゴリズムのクラスであるLagrangian hedgingに楽観と適応的なステップを導入します。
論文 参考訳(メタデータ) (2021-01-23T23:32:40Z) - Regret minimization in stochastic non-convex learning via a
proximal-gradient approach [80.59047515124198]
機械学習やオペレーションの応用によって動機づけられた私たちは、オンラインで制約された問題を最小化するために、一階のオラクルフィードバックを後悔しています。
我々は、近位複雑性低減技術を保証する新しいプロキシグレードを開発する。
論文 参考訳(メタデータ) (2020-10-13T09:22:21Z) - Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
動的後悔と適応的後悔を同時に最小化できる新しいオンラインアルゴリズムを提案する。
我々の理論的保証は、あるアルゴリズムが任意の間隔で動的後悔を最小化できるという意味でさらに強い。
論文 参考訳(メタデータ) (2020-02-06T03:32:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。