論文の概要: A Generalized Approach to Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2402.08621v1
• Date: Tue, 13 Feb 2024 17:42:27 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-14 14:15:17.124308
• Title: A Generalized Approach to Online Convex Optimization
• Title（参考訳）: オンライン凸最適化への一般化アプローチ
• Authors: Mohammad Pedramfar, Vaneet Aggarwal
• Abstract要約: 完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。 完全情報フィードバックを必要とする任意のアルゴリズムは、半帯域フィードバックを持つアルゴリズムに変換される可能性があることを示す。
• 参考スコア（独自算出の注目度）: 39.44092711734015
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we analyze the problem of online convex optimization in different settings. We show that any algorithm for online linear optimization with fully adaptive adversaries is an algorithm for online convex optimization. We also show that any such algorithm that requires full-information feedback may be transformed to an algorithm with semi-bandit feedback with comparable regret bound. We further show that algorithms that are designed for fully adaptive adversaries using deterministic semi-bandit feedback can obtain similar bounds using only stochastic semi-bandit feedback when facing oblivious adversaries. We use this to describe general meta-algorithms to convert first order algorithms to zeroth order algorithms with comparable regret bounds. Our framework allows us to analyze online optimization in various settings, such full-information feedback, bandit feedback, stochastic regret, adversarial regret and various forms of non-stationary regret. Using our analysis, we provide the first efficient projection-free online convex optimization algorithm using linear optimization oracles.
• Abstract（参考訳）: 本稿では,オンライン凸最適化の問題点を異なる設定で解析する。 完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。 また, 完全な情報フィードバックを必要とするアルゴリズムは, 半帯域フィードバックを持つアルゴリズムに変換される可能性があることを示す。 さらに, 決定論的半バンドフィードバックを用いた完全適応型敵に対するアルゴリズムは, 確率的半バンドフィードバックのみを用いて, 同様の境界を得ることができることを示した。 これを用いて、一般的なメタアルゴリズムを記述し、一階アルゴリズムを同様の後悔境界を持つゼロ階アルゴリズムに変換する。 本フレームワークは,全情報フィードバック,盗聴フィードバック,確率的後悔,反逆的後悔,非定常的後悔など,様々な場面でオンライン最適化を解析することができる。 解析により,線形最適化オラクルを用いたプロジェクションフリーオンライン凸最適化アルゴリズムを提案する。

関連論文リスト

• From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization [33.38582292895673]
  本稿では,モノトーン非線型やDR-サブモジュラリティなど,様々な環境での凹凸とDR-サブモジュラリティの概念を紹介する。 一般的なメタアルゴリズムは、線形/四進関数を上線形/四進関数を最適化するものに変換する。
  論文  参考訳（メタデータ） (2024-04-27T06:19:30Z)
• Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization [28.598226670015315]
  本稿では,DR-サブモジュラー最適化のための統合プロジェクションフリーのFrank-Wolfe型アルゴリズムを提案する。 非単調な設定で考慮されたすべての問題に対して、提案アルゴリズムは、証明されたサブ線形$alpha$-regret境界を持つ最初のものであるか、あるいは、最先端よりもより優れた$alpha$-regret境界を持つかのいずれかである。
  論文  参考訳（メタデータ） (2024-03-15T07:05:44Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods [20.118513136686452]
  一階最適化法は、未決定の訓練目標を最小化する際に、本質的に他よりも特定の解を優先する傾向がある。 本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。 私たちの加速速度は、このゲームフレームワークにおけるオンライン学習アルゴリズムの残念な部分を活用することによって導き出されます。
  論文  参考訳（メタデータ） (2023-05-27T18:16:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  このアルゴリズムは指数勾配と$p$-normアルゴリズムの組み合わせと解釈できる。 彼らはシーケンス依存の後悔の上界を達成し、スパース目標決定変数の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-08-08T11:29:55Z)
• Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting [21.584183030149084]
  パラメータフリーオンライン線形最適化アルゴリズムのクラスを提案する。 彼らは、いくつかの側情報を適用することによって、敵列の構造を利用する。 提案アルゴリズムは、全ての適応アルゴリズムに対して最高の性能を達成するためにさらに改良されている。
  論文  参考訳（メタデータ） (2022-02-04T21:56:29Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。