論文の概要: Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
- arxiv url: http://arxiv.org/abs/2609.11207v1
- Date: Thu, 10 Sep 2026 08:13:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.250165
- Title: Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
- Title（参考訳）: 時間変化損失関数下でのNested Evolving Feasible Sets (CONES)による凸最適化
- Abstract要約: 損失関数を$f_t'$sに拡張して、時間とともに変更できるようにします。
サブリニアなオンラインアルゴリズムはいつでも、運動コストが$left(log Tright)$であることを示す。
- 参考スコア（独自算出の注目度）: 5.533296779866529
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function \(f\) remains fixed but the feasible region evolves over time as a nested sequence \(S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T\). The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost $M_\cA(T)$ while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known \emph{nested convex body chasing} (NCBC). In this paper, we extend CONES to allow for loss functions $f_t'$s to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves $O(T^{1-β}), O(T^β)$ simultaneous regret and movement cost, respectively, for any $β\in [0,1)$, over a time horizon of $T$. We also show that any {\it weakly adaptive} online algorithm with $O(T^β)$ regret has a movement cost of $Ω\left(T^{\frac{1-β}{2}}\right)$ for any $β\in [0,1)$. When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves $O(1)$ regret and a movement cost of $O(\log T)$. To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of $Ω\left(\log T\right)$.
- Abstract（参考訳）: Convex Optimization with Nested Evolving Feasible Sets (CONES) was introduced in \cite{CONESVaze} ここでは目的関数 \(f\) が固定されるが、実現可能な領域はネストシーケンス \(S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T\) として時間とともに進化する。
オンラインアルゴリズムの目標は、隠れた静的な最適ベンチマークに対する後悔を同時に最小化し、総移動コストが$M_\cA(T)$であり、常に実現可能であることを保証することである。
CONESは、よく知られた 'emph{nested convex body chasing} (NCBC) の最適化指向の一般化である。
本稿では、ConESを拡張し、損失関数を$f_t'$sで時間とともに変更できるようにします。
すべての損失関数が凸であるとき、投影された近位アルゴリズムは、それぞれ$O(T^{1-β}), O(T^β)$同時後悔と運動コストを、任意の$β\in [0,1)$に対して、T$の時間的地平線上で達成することを示す。
また、$O(T^β)$ regret のオンラインアルゴリズムが任意の$β\in [0,1)$に対して $Ω\left(T^{\frac{1-β}{2}}\right)$の運動コストを持つことを示す。
すべての損失関数が強く凸であるとき、投影された近位アルゴリズムは同時に$O(1)$後悔と$O(\log T)$の運動コストを達成する。
これを補うために、任意のオンラインアルゴリズムに部分線型な後悔がある場合、運動コストは$Ω\left(\log T\right)$であることを示す。
関連論文リスト
- Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets [0.0]
ネストした縮小可能な領域を2つの設定でオンライン最適化する。
懸念されている最小限の試験と累積余剰試験は、後悔の保証を保っている。
決定論的リセット可能なネスト付き凸体チェッカーは運動を制限する。
論文 参考訳（メタデータ） (2026-08-29T06:01:56Z) - Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO) [4.167459103689586]
目的は、静的な後悔と累積的な制約違反を同時に最小化することである。
本稿では,OGD+プロジェクションアルゴリズムのCCVが$(Tfracd-12d)$であることを示す。
論文 参考訳（メタデータ） (2026-07-12T15:36:04Z) - Convex Optimization with Nested Evolving Feasible Sets [4.67724003380452]
両ケースに対して$o(T)$ regretのオンラインアルゴリズムが$(logT)$の移動コストを持ち、Frugalの最適性を証明していることを示す。
また、$o(T)$ regretのオンラインアルゴリズムは、両方のケースに対して$(logT)$の移動コストを持ち、Frugalの最適性を証明することも示している。
論文 参考訳（メタデータ） (2026-05-08T07:42:15Z) - 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) - Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets [35.8717656676532]
オンライン線形最適化では、損失関数の平均勾配が一定の閾値を超えると、実現可能な集合の曲率を利用することができることが知られている。
本研究では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
論文 参考訳（メタデータ） (2024-02-20T09:59:33Z) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43:35Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。