論文の概要: Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
- arxiv url: http://arxiv.org/abs/2608.29074v1
- Date: Sat, 29 Aug 2026 06:01:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:30.832165
- Title: Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
- Title（参考訳）: 実現可能な集合を進化させるオンライン最適化のためのNested Convex-Body Chasing
- Abstract要約: ネストした縮小可能な領域を2つの設定でオンライン最適化する。
懸念されている最小限の試験と累積余剰試験は、後悔の保証を保っている。
決定論的リセット可能なネスト付き凸体チェッカーは運動を制限する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study online optimization with nested shrinking feasible regions in two settings: convex optimization with nested evolving feasible sets (CONES) and adversarial constrained online convex optimization (COCO). Our algorithms separate loss control from geometric movement: constrained minimizers and cumulative-loss tests preserve regret guarantees, while a deterministic resettable nested convex-body chaser limits movement. For CONES with a $G$-Lipschitz, $μ$-strongly convex objective on a diameter-$D$ domain, we chase intersections of the current feasible set with adaptive objective sublevel sets. Using the Euclidean chasing ratio $O(\sqrt{d\log(1+d)})$, we obtain nonpositive regret at every prefix and movement $O(\sqrt{d\log(1+d)\,GD\log(eT)/μ})$. The bound adapts to the increase in the constrained optimum value. In dimension two, with all other parameters fixed, every randomized algorithm with terminal expected regret $O(T^β)$, $β<1$, suffers $Ω(\sqrt{\log T})$ expected movement on some deterministic nested sequence, proving optimal horizon dependence. Under linear growth away from the constrained minimizer set, Steiner-point tracking yields movement independent of $T$. For general convex COCO, one-step-delayed chasing with regularized-leader resets gives regret $O(G_fD\sqrt{d\log(1+d)T})$ and cumulative constraint violation $O(G_gD\sqrt{d\log(1+d)T})$. For strongly convex losses, both are $O(d\log(1+d)\log(eT))$ when other parameters are fixed. These reductions replace the $O(d^{d/2})$ projection-path factor in prior analyses by the polynomial dimension dependence of Euclidean nested convex-body chasing.
- Abstract（参考訳）: 本研究では, ネスト型縮小可能領域を用いたオンライン最適化について, ネスト型拡張可能集合(CONES)を用いた凸最適化と, 対向型制約付きオンライン凸最適化(COCO)の2つの設定で検討した。
我々のアルゴリズムは、損失制御を幾何学的運動から切り離し、制約された最小化器と累積余剰試験は後悔の保証を保ち、決定論的に再設定可能な凸体追尾器は運動を制限する。
G$-Lipschitz,$μ$-strongly convex objective on a diameter-D$ domain を持つ CONES に対し、適応的目的部分レベル集合を持つ現在の実現可能集合の交叉を追及する。
ユークリッド追跡比$O(\sqrt{d\log(1+d)})$ を用いて、すべての接頭辞における非正の後悔と運動 $O(\sqrt{d\log(1+d)\,GD\log(eT)/μ})$ を得る。
境界は制約された最適値の増加に適応する。
次元 2 では、他の全てのパラメータを固定した全てのランダム化アルゴリズムは、終末予測された後悔$O(T^β)$, $β<1$, suffereds $Ω(\sqrt{\log T})$ 決定論的ネスト列上の期待運動を生じさせ、最適地平面依存性を証明している。
制限された最小値集合から離れる線形成長の下で、スタイナー点追跡は$T$とは無関係に動きを生じる。
一般的な凸 COCO に対して、正規化リーダリセットによるワンステップの追跡は、後悔$O(G_fD\sqrt{d\log(1+d)T})$と累積制約違反$O(G_gD\sqrt{d\log(1+d)T})$を与える。
強い凸損失の場合、どちらも他のパラメータが固定されたときに$O(d\log(1+d)\log(eT))$である。
これらの還元は、ユークリッドネスト凸体追尾の多項式次元依存性による事前解析において$O(d^{d/2})$プロジェクションパス因子を置き換える。
関連論文リスト
- 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) - Online Convex Optimization with Sublinear Noisy Probes [6.998574163422056]
オンライン凸最適化(OCO)を凸集合として$Ksubseteq mathbb Rd$で検討する。
我々は最近の2つの作業の行を一般化する統一された探索モデルを導入する: 専門家設定におけるサブ線形ベストエキスパートクエリと、OCOの各ラウンドで利用できるペアワイズフィードバックである。
本研究の主目的は, サブリニアでノイズの多いプローブ予算であっても, OCO体制の完全なフィードバックにおける最悪の後悔を確実に改善できることである。
論文 参考訳（メタデータ） (2026-06-12T17:05:08Z) - Convex Optimization with Nested Evolving Feasible Sets [4.67724003380452]
両ケースに対して$o(T)$ regretのオンラインアルゴリズムが$(logT)$の移動コストを持ち、Frugalの最適性を証明していることを示す。
また、$o(T)$ regretのオンラインアルゴリズムは、両方のケースに対して$(logT)$の移動コストを持ち、Frugalの最適性を証明することも示している。
論文 参考訳（メタデータ） (2026-05-08T07:42:15Z) - A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。
バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
論文 参考訳（メタデータ） (2026-02-02T18:17:34Z) - 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) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。