論文の概要: Constrained Online Learning with Noisy Constraint Values

• arxiv url: http://arxiv.org/abs/2609.06921v1
• Date: Mon, 07 Sep 2026 01:38:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.336614
• Title: Constrained Online Learning with Noisy Constraint Values
• Title（参考訳）: ノイズのある制約値による制約付きオンライン学習
• Abstract要約: LEDGERは、非負のバランスでネット消費を観測した。 LEDGERは、$O(sqrt T/V)$期待の後悔と$O(sqrt V,T3/4+sqrt T)$期待の予算違反を$Vin[T-1/2,1]$で達成する。
• 参考スコア（独自算出の注目度）: 55.29259818039367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study constrained online convex optimization with adversarial constraints when constraint values and gradients are observed through unbiased noise. Gaussian value noise of standard deviation $σ$ yields a worst-case lower bound of $Ω(\min\{σ,1\}T/\log^7T)$ on the maximum of expected regret and expected hard violation, even with known gradients. This rules out any jointly $O(T^{1-δ})$ guarantee for fixed $δ>0$ and fixed positive noise level. We therefore study budget violation: the largest cumulative overspend over any window within a fixed horizon. We introduce \LEDGER, which tracks observed net consumption in a nonnegative balance and sets constraint weights before the current feedback noise. Under common feasibility and conditional finite-variance feedback, for fixed problem parameters, \LEDGER\ achieves $O(\sqrt T/V)$ expected regret and $O(\sqrt V\,T^{3/4}+σ\sqrt T)$ expected budget violation for $V\in[T^{-1/2},1]$. This gives the pair $(O(\sqrt T),O(T^{3/4}))$ at $V=1$ and $(O(T^{2/3}),O(T^{2/3}))$ at $V=T^{-1/6}$, without a Slater condition. The budget-focused endpoint $V=T^{-1/2}$ gives $(O(T),O(\sqrt T))$. The same update yields $O((1+E[P_T])\sqrt T/V)$ expected dynamic regret for predictable feasible comparator paths, without common feasibility or path-length input. Its budget bound instead depends on the shortest feasible path, up to a dimension factor.
• Abstract（参考訳）: 本研究では,非バイアス雑音による制約値と勾配の観測時に,逆制約を伴う制約付きオンライン凸最適化について検討する。 標準偏差のガウス値ノイズ$σ$は、既知の勾配であっても、期待される後悔と期待されるハード違反の最大値である$Ω(\min\{σ,1\}T/\log^7T)$の最悪の下限となる。 これにより、固定された$δ>0$と固定された正の雑音レベルに対する任意の$O(T^{1-δ})$保証を除外する。 したがって、予算違反を調査し、固定された地平線内のどの窓にも最も大きな累積オーバースペンドを課す。 非負のバランスで観測されたネット消費を追跡し、現在のフィードバックノイズの前に制約重みを設定するLEDGERを導入する。 一般的な実現可能性と条件付き有限分散フィードバックの下では、固定問題パラメータに対して \LEDGER\ は$O(\sqrt T/V)$期待の後悔と$O(\sqrt V\,T^{3/4}+σ\sqrt T)$期待の予算違反を$V\in[T^{-1/2},1]$とする。 これはペア $(O(\sqrt T),O(T^{3/4}))$ at $V=1$ and $(O(T^{2/3}),O(T^{2/3}))$ at $V=T^{-1/6}$ を与える。 予算中心のエンドポイント$V=T^{-1/2}$は$(O(T),O(\sqrt T))$を与える。 同じアップデートで$O((1+E[P_T])\sqrt T/V)$ expected dynamic regret for predictable feasible comparator paths, without without common feasibility and path-length input。 その予算は、寸法要素まで、最も短い実行可能な経路に依存する。

関連論文リスト

• Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets [0.0]
  ネストした縮小可能な領域を2つの設定でオンライン最適化する。 懸念されている最小限の試験と累積余剰試験は、後悔の保証を保っている。 決定論的リセット可能なネスト付き凸体チェッカーは運動を制限する。
  論文  参考訳（メタデータ） (2026-08-29T06:01:56Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• 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)
• Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
  重畳の非線形観測回数が限られていることから, スパースベクトルの回復を考察する。 本稿では, 一般化畳み込みペナルティとハマー化データ忠実度を組み合わせた正規化に基づくフレームワークを提案する。 仮に局所的な定常点を保った位数$sqrtslog(n)/m$の誤差境界を導出する。
  論文  参考訳（メタデータ） (2026-07-12T07:29:39Z)
• Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization [12.903796669387809]
  オンライン凸最適化 (OCO) における高い確率的後悔境界について, 強い凸損失を伴って検討した。 雑音適応性, フィードバック構造, 制約満足度の交点において, オープンな質問を解決するための3つの結果を確立する。
  論文  参考訳（メタデータ） (2026-06-06T07:40:55Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを考察する。 鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。 我々は、$(sqrtmathbbE[S_T])$としてスケールする情報理論の下限を確立し、最も達成可能な予測適応的後悔の基本的な特徴を提供する。
  論文  参考訳（メタデータ） (2026-05-21T08:57:38Z)
• When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
  良性オーバーフィッティングが線形レートで失敗することを示します。 この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
  論文  参考訳（メタデータ） (2026-05-07T14:14:09Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret with Infinite Variance [0.0]
  任意の値に対する期待された後悔は、有界密度だけで$mathbbE[g(m,V,W)] le L|m-|2$を満たすことを示す。 雑音が$p in (1,2)$に対してp$-第1モーメントしか持たず、市場価値関数が$$-Hlderである場合、エポックアルゴリズムが後悔$widetildeO(T1-2(p-1)/(p + d(p-1)))$を達成することを証明する。
  論文  参考訳（メタデータ） (2026-03-06T20:15:58Z)
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。 バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
  論文  参考訳（メタデータ） (2026-02-02T18:17:34Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。 我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
  論文  参考訳（メタデータ） (2023-01-26T18:04:26Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
  本稿では,長期的制約を伴うオンライン凸最適化について考察する。 新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
  論文  参考訳（メタデータ） (2021-06-09T15:18:06Z)

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

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