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

• arxiv url: http://arxiv.org/abs/2609.06921v2
• Date: Sun, 13 Sep 2026 20:13:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:04.523547
• Title: Constrained Online Learning with Noisy Constraint Values
• Title（参考訳）: ノイズのある制約値による制約付きオンライン学習
• Abstract要約: 一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
• 参考スコア（独自算出の注目度）: 55.29259818039367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study constrained online convex optimization with adversarial constraints and conditionally unbiased, finite-variance observations of constraint values and gradients. Under common feasibility, our \LEDGER\ algorithm attains $O(\sqrt T)$ expected regret and $O(\sqrt{T\log(eT)})$ expected budget violation, the largest cumulative overspend over any window. It uses a reflected exponential potential, clipped signed observations, and predictable adaptive regularization, with one feedback triple and one projection per round. Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed. A Gaussian testing lower bound proves that the budget rate has optimal horizon dependence under square-root regret at fixed positive noise, including the logarithm. The same obstruction holds for terminal violation, so the logarithm is not a cost of maximizing over windows; an $O(\sqrt T)$ budget bound instead forces linear regret. In contrast, fixed positive Gaussian value noise yields a joint regret--hard-violation lower bound of $Ω(\min\{σ,1\}T/\log^2 T)$, even with exact gradients in one dimension. The hard-violation construction matches arbitrarily many moments while preserving a feasible-endpoint gap and constant endpoint probabilities. Together, the bounds separate uncertainty about hard feasibility from learnable signed budgets. Deterministic restarts remove the horizon input without changing either upper rate.
• Abstract（参考訳）: 本研究では,制約値と勾配の条件付き無バイアス有限分散観測による制約付きオンライン凸最適化について検討した。 一般的な実現可能性の下では、我々の \LEDGER\ アルゴリズムは$O(\sqrt T)$期待の後悔と$O(\sqrt{T\log(eT)})$期待の予算違反を達成します。 反射指数ポテンシャル、クリッピングされたサインされた観測、予測可能な適応正則化を使い、1ラウンドあたりのフィードバックは3倍、投射は1つである。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。 ガウステストの下限は、予算レートが対数を含む固定正の雑音において平方根の後悔の下で最適な地平線依存性を持つことを証明している。 同じ障害は終端違反であるので、対数は窓越しに最大化するコストではない;$O(\sqrt T)$ budget bound は代わりに線形後悔を強いる。 対照的に、固定正のガウス値ノイズは、一次元の厳密な勾配であっても、ジョイント・リサート-ハード-違反の下界が$Ω(\min\{σ,1\}T/\log^2T)$となる。 ハード違反構成は、可能なエンドポイントギャップと一定のエンドポイント確率を維持しながら、任意に多くのモーメントに一致する。 この境界は、難易度に関する不確実性と、学習可能な署名された予算とを分けている。 決定論的再起動は、どちらかの上限レートを変更することなく水平線入力を除去する。

関連論文リスト

• 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)

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

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