論文の概要: 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（参考訳）: ネスト展開可能な集合による凸最適化
• 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})$ の運動コストを持つことを示す。

関連論文リスト

• Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions [5.533296779866529]
  損失関数を$f_t'$sに拡張して、時間とともに変更できるようにします。 サブリニアなオンラインアルゴリズムはいつでも、運動コストが$left(log Tright)$であることを示す。
  論文  参考訳（メタデータ） (2026-09-10T08:13:27Z)
• Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets [0.0]
  ネストした縮小可能な領域を2つの設定でオンライン最適化する。 懸念されている最小限の試験と累積余剰試験は、後悔の保証を保っている。 決定論的リセット可能なネスト付き凸体チェッカーは運動を制限する。
  論文  参考訳（メタデータ） (2026-08-29T06:01:56Z)
• Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension [80.40589035328607]
  我々は、ガウス雑音の零次オラクルを用いて凸関数 $f : [0,1] から [0,1] への最小化の問題を研究する。 計算効率のよいO(1/sqrtT)$収束率を求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-07-14T16:10:33Z)
• 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)
• Online Convex Optimization with a Separation Oracle [10.225358400539719]
  本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。 我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
  論文  参考訳（メタデータ） (2024-10-03T13:35:08Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)

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

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