論文の概要: Polyhedral Instability Governs Regret in Online Learning

• arxiv url: http://arxiv.org/abs/2605.13692v1
• Date: Wed, 13 May 2026 15:45:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:28.152548
• Title: Polyhedral Instability Governs Regret in Online Learning
• Title（参考訳）: オンライン学習における多面的不安定性
• Authors: Yuetai Li, Fengqing Jiang, Yichen Feng, Kaiyuan Zheng, Luyao Niu, Bhaskar Ramasubramanian, Basel Alomair, Linda Bushnell, Radha Poovendran,
• Abstract要約: このような問題における後悔は,活動領域の変化の回数という,多面的不安定性によって支配されることを示す。 合成および実問題に関する実験は、予測スケーリングを検証し、動作の明示的な列挙なしに、実際に低不安定が生じることを示す。
• 参考スコア（独自算出の注目度）: 23.46151626569377
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many online decision problems over combinatorial actions are addressed via convex relaxations, leading to online convex optimization with piecewise linear objectives and induced polyhedral structure. We show that regret in such problems is governed by \emph{polyhedral instability}: the number of changes of the active region. Under full information feedback and fixed partition assumptions, if $\mathrm{RS}_T$ denotes the number of region switches and $V_{\max}$ the maximum number of vertices per region, we prove $\Regret_T= Θ(\sqrt{(1+\mathrm{RS}_T)\,T\,\log V_{\max}})$ interpolating between experts-like and dimension-dependent OCO rates. For online submodular--concave games under Lovász convexification, this reduces to the permutation-switch count $\mathrm{SC}_T$, yielding the matching rate $\Regret_T= Θ(\sqrt{(1+\mathrm{SC}_T)\,T\,\log n})$. Experiments on synthetic and real combinatorial problems (shortest path, influence maximization) validate the predicted scaling and indicate that low-instability regimes can arise in practice without explicit enumeration of actions.
• Abstract（参考訳）: 組合せ行動に関する多くのオンライン決定問題は凸緩和(convex relaxation)によって解決され、断片的な線形目的と誘導多面体構造を持つオンライン凸最適化が導かれる。 このような問題における後悔は、活性領域の変化の回数である 'emph{polyhedral instability} によって支配されることを示す。 完全な情報フィードバックと固定分割仮定の下で、$\mathrm{RS}_T$ が領域スイッチの数を表し、$V_{\max} が領域ごとの頂点の最大数を表すなら、$\Regret_T= >(\sqrt{(1+\mathrm{RS}_T)\,T\,\log V_{\max}}) 専門家のようなOCOレートと次元に依存したOCOレートを補間する。 Lovász の凸化の下でのオンライン部分モジュラー-凹面ゲームの場合、これは置換-スウィッチ数 $\mathrm{SC}_T$ に還元され、マッチングレート $\Regret_T= (\sqrt{(1+\mathrm{SC}_T)\,T\,\log n})$ が得られる。 合成および実組合せ問題(ショートパス、影響の最大化)の実験は、予測されたスケーリングを検証し、動作の明示的な列挙なしに、実際に低不安定な状態が生じることを示す。

関連論文リスト

• Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
  普遍性と適応性の両方を達成する新しいアプローチであるUniGradを紹介し、UniGrad.CorrectとUniGrad.Bregmanの2つの異なる実現法を提案する。 どちらのメソッドも勾配の変動に適応し、強い凸関数に対する $mathcalO(log V_T)$ regret とexp-concave関数に対する $mathcalO(d log V_T)$ regret を同時に達成する。
  論文  参考訳（メタデータ） (2025-11-25T05:23:10Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Optimal Dynamic Regret in LQR Control [23.91519151164528]
  我々は、LQR制御という2次的損失の連続を伴う非確率的制御の問題を考察する。 我々は、$tildeO(textmaxn1/3 MathcalTV(M_1:n)2/3, 1)$の最適動的(政治的)後悔を実現するオンラインアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-06-18T18:00:21Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。 我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
  論文  参考訳（メタデータ） (2020-01-27T03:44:54Z)

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

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