論文の概要: Convex Optimization with Nested Evolving Feasible Sets

• arxiv url: http://arxiv.org/abs/2605.07386v1
• Date: Fri, 08 May 2026 07:42:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.89493
• Title: Convex Optimization with Nested Evolving Feasible Sets
• Title（参考訳）: ネスト展開可能な集合による凸最適化
• Authors: Karthick Krishna M., Haricharan Balasundaram, Rahul Vaze,
• Abstract要約: 両ケースに対して$o(T)$ regretのオンラインアルゴリズムが$(logT)$の移動コストを持ち、Frugalの最適性を証明していることを示す。 また、$o(T)$ regretのオンラインアルゴリズムは、両方のケースに対して$(logT)$の移動コストを持ち、Frugalの最適性を証明することも示している。
• 参考スコア（独自算出の注目度）: 4.67724003380452
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Convex Optimization with Nested Evolving Feasible Sets (CONES)} is considered 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 while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing problem. When the loss function is convex, we propose a lazy-algorithm and show that it achieves $O(T^{1-β}), O(T^β)$ simultaneous regret and movement cost for any $β\in (0,1]$, over a time horizon of $T$. When the loss function is strongly convex or $α$-sharp, we propose an algorithm Frugal that simultaneously achieves zero regret and a movement cost of $O(\log T)$. To complement this, we show that any online algorithm with $o(T)$ regret has a movement cost of $Ω(\log{T})$ for both cases, proving optimality of Frugal.
• Abstract（参考訳）: convex Optimization with Nested Evolving Feasible Sets (CONES) は目的関数 $f$ が固定されたままであるが、実現可能な領域はネストシーケンス $S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T$ として時間とともに進化する。 オンラインアルゴリズムの目標は、常に実現可能性を確保しつつ、隠れた静的な最適ベンチマークと総移動コストに対する後悔を同時に最小化することである。 CONESは、よく知られたネストされた凸体追尾問題の最適化指向の一般化である。 損失関数が凸であるとき、遅延アルゴリズムを提案し、それが$O(T^{1-β}), O(T^β)$を達成し、任意の$β\in (0,1]$に対する繰り返し後悔と移動コストを、T$の時間的地平線上で達成することを示す。 損失関数が強い凸あるいは$α$-シャープであるとき、ゼロ後悔と移動コスト$O(\log T)$を同時に達成するアルゴリズムFrugalを提案する。 これを補完するために、frugal の最適性を証明するために、$o(T)$ regret の任意のオンラインアルゴリズムが、両方のケースに対して $Ω(\log{T})$ の運動コストを持つことを示す。

関連論文リスト

• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets [35.8717656676532]
  オンライン線形最適化では、損失関数の平均勾配が一定の閾値を超えると、実現可能な集合の曲率を利用することができることが知られている。 本研究では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
  論文  参考訳（メタデータ） (2024-02-20T09:59:33Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• 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)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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