論文の概要: Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
- arxiv url: http://arxiv.org/abs/2609.02145v1
- Date: Wed, 02 Sep 2026 06:00:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-03 17:53:18.100103
- Title: Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
- Title（参考訳）: 0.401$因子のオンライン非モノトンDRサブモジュラー最大化
- Abstract要約: 我々は、$d$-oracle単位のコンパクト凸部分集合上の非対称非負、非単調DR-部分モジュラ函数について研究する。
オンラインアルゴリズムは、フィードバックが条件付きで偏りがなく、有界であるときに、およその後悔で0.401$に達する。
- 参考スコア（独自算出の注目度）: 47.30196146041476
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at $1/e$. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has $O(T^{3/4})$ regret and uses $O(dT^{1/4})$ oracle calls per round. More generally, for every $δ\in[0,1/4]$, batching gives $O(T^δ)$ calls per round and $O(T^{4/5-δ/5})$ regret, including a one-call $O(T^{4/5})$ endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with $O(T^{5/6})$ one-point bandit regret.
- Abstract（参考訳）: 我々は、$d$次元単位立方体のコンパクト凸下閉部分集合上での非負の非単調DR-部分モジュラ函数のオンライン最大化について検討した。
最もよく知られた構成上のオフライン近似係数は、対応するメタ可解性仮定の下で0.401ドルである。
我々は、この要因がオンラインでも達成可能であることも示している。
決定後の全情報値オーラクルモデルでは, オーラクルフィードバックが条件付きで偏りがなく有界である場合に, サブ線形近似後悔を伴う係数が0.401$となる。
オンラインアルゴリズムは、変化する目的に対してオフラインの構成を実行しない。
代わりに、オフラインの客観依存のボックスステップを、必要な残余項を累積的に制御する重み付けされたオンライン学習者によって置き換える。
正則な非対称均衡定理は、逆の変動に拘わらず、オフライン係数を保存する。
直接実装は、$O(T^{3/4})$ regretを持ち、ラウンド毎に$O(dT^{1/4})$ Oracleコールを使用する。
より一般的に、すべての$δ\in[0,1/4]$に対して、バッチ処理はラウンド当たり$O(T^δ)$コールと$O(T^{4/5-δ/5})$後悔を与える。
正のアンカー条件下では、ランダム化されたブロッキングは、0.401$と$O(T^{5/6})$ 1-point bandit regretを保っている。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。
本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。
結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
論文 参考訳（メタデータ） (2026-08-12T14:54:15Z) - Block-Wise Differentiable Sinkhorn Attention: Tail-Refinement Gradients with a Gap-Aware Dustbin Bridge [0.0]
本稿では,TPUハードウェア上での長期的コンテキストバランスによる最適輸送注意度を,停止ベース,固定深部テールリファインメントサロゲートを用いて検討する。
本稿では, 局所的代理バイアスバウンド, 後部バイアス証明書, および, 厳密な正の能動ブロックに対する射影収縮証明書を提供する。
合成マスク問題では、最適化された置換基の正確なオートディフは10〜5ドル-10〜10ドルである。
論文 参考訳（メタデータ） (2026-04-28T19:01:11Z) - Improved and Oracle-Efficient Online $\ell_1$-Multicalibration [14.147331133778916]
本研究では,複数のグループにまたがるキャリブレーション予測を行うフレームワークであるエンフォリン・マルチキャリブレーションについて検討する。
そこで本研究では,$widetildemathcalO(T-1/4)$を改良し,オラクル効率を向上する手法を提案する。
我々のフレームワークは、(ell_H)-multicalibration誤差の1ドルLipschitz特性を利用して、ある無限群の族にも拡張する。
論文 参考訳（メタデータ） (2025-05-23T00:37:49Z) - Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - Conservative Contextual Bandits: Beyond Linear Representations [29.5947486908322]
保守的コンバンディット(CCB)は、エージェントのポリシーと後悔を最小限に抑えるとともに、安全上の制約を満たすことを要求することで、シーケンシャルな意思決定における安全性に対処する。
Inverse Gap Weighting (IGW) ベースの探索とオンライン回帰オラクルを用いて, $mathttC-SquareCB$ と $mathttC-FastCB$ の2つのアルゴリズムを開発した。
安全性制約は高い確率で満たされており、$mathttC- SquareCB$の後悔は水平線で$T$のサブ線形であることを示す。
論文 参考訳（メタデータ） (2024-12-09T02:57:27Z) - On the Interplay Between Misspecification and Sub-optimality Gap in
Linear Contextual Bandits [76.2262680277608]
本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。
このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
論文 参考訳（メタデータ） (2023-03-16T15:24:29Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。