論文の概要: Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints

• arxiv url: http://arxiv.org/abs/2510.22579v1
• Date: Sun, 26 Oct 2025 08:35:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 19:54:32.539764
• Title: Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints
• Title（参考訳）: 逆制約を考慮したオンライン凸最適化のための最適随時アルゴリズム
• Authors: Dhruv Sarkar, Abhishek Sinha,
• Abstract要約: 本稿では,対向凸コスト関数の列を学習する問題に対して,任意のオンラインアルゴリズムを提案する。 提案アルゴリズムは,標準的な倍数化手法を使わずに最適な性能バウンダリを実現する。 我々のアルゴリズムは、$O(sqrtt)$ regret と $tildeO(sqrtt)$ cumulative constraint violation bounds for any $tgeq 1$。
• 参考スコア（独自算出の注目度）: 7.798233121583888
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose an anytime online algorithm for the problem of learning a sequence of adversarial convex cost functions while approximately satisfying another sequence of adversarial online convex constraints. A sequential algorithm is called \emph{anytime} if it provides a non-trivial performance guarantee for any intermediate timestep $t$ without requiring prior knowledge of the length of the entire time horizon $T$. Our proposed algorithm achieves optimal performance bounds without resorting to the standard doubling trick, which has poor practical performance due to multiple restarts. Our core technical contribution is the use of time-varying Lyapunov functions to keep track of constraint violations. This must be contrasted with prior works that used a fixed Lyapunov function tuned to the known horizon length $T$. The use of time-varying Lyapunov function poses unique analytical challenges as properties, such as \emph{monotonicity}, on which the prior proofs rest, no longer hold. By introducing a new analytical technique, we show that our algorithm achieves $O(\sqrt{t})$ regret and $\tilde{O}(\sqrt{t})$ cumulative constraint violation bounds for any $t\geq 1$. We extend our results to the dynamic regret setting, achieving bounds that adapt to the path length of the comparator sequence without prior knowledge of its total length. We also present an adaptive algorithm in the optimistic setting, whose performance gracefully scales with the cumulative prediction error. We demonstrate the practical utility of our algorithm through numerical experiments involving the online shortest path problem.
• Abstract（参考訳）: 本稿では, 対向凸コスト関数の列を学習する上で, 対向凸制約の列をほぼ満たしながら, 対向凸コスト関数の列を学習する問題に対して, 任意のオンラインアルゴリズムを提案する。 シーケンシャルアルゴリズムは、任意の中間時間ステップ$t$に対して、時間軸全体の長さに関する事前の知識を必要とせずに、非自明な性能保証を提供する場合、 \emph{anytime} と呼ばれる。 提案アルゴリズムは,複数再起動による実用性能の悪い標準的な倍数化手法を使わずに,最適な性能境界を実現する。 我々の技術的な貢献は、制約違反の追跡に時間変化のLyapunov関数を使うことです。 これは、既知の地平線長$T$に調整された固定されたリャプノフ函数を使った以前の作品と対比しなければならない。 時変リプノフ函数の使用は、前述した証明がもはや保たない 'emph{monotonicity} のような性質として、ユニークな解析的問題を引き起こす。 新しい解析手法を導入することにより、我々のアルゴリズムは、$O(\sqrt{t})$ regret と $\tilde{O}(\sqrt{t})$ cumulative constraint violation bounds for any $t\geq 1$。 本研究は,コンパレータ列の経路長に適応する境界を,その全長さを事前に知ることなく,動的後悔設定に拡張する。 また,楽観的な設定において,累積予測誤差を優雅にスケールする適応アルゴリズムを提案する。 オンライン最短経路問題を含む数値実験により,本アルゴリズムの実用性を実証する。

関連論文リスト

• Online Conformal Prediction with Efficiency Guarantees [2.0305676256390934]
  新たなオンラインフレームワークにおける共形予測の問題について検討する。 この問題では、ターゲットの誤発見率$alpha > 0$と時間軸$T$が与えられる。
  論文  参考訳（メタデータ） (2025-07-03T10:00:50Z)
• Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints [31.526232903811533]
  我々はOCO(Optimistically Safe OCO)と呼ぶアルゴリズムを導入し、そのアルゴリズムが$tildeO(sqrtT)$ regretと制約違反がないことを示す。 静的線形制約の場合、これは同じ仮定の下で、以前の最もよく知られた $tildeO(T2/3)$ regret よりも改善される。 時間的制約の場合、当社の作業は、$O(sqrtT)$ regretと$O(sqrtT)$ cumulative violationを示す既存の結果を補完します。
  論文  参考訳（メタデータ） (2024-03-09T04:01:39Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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