論文の概要: Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

• arxiv url: http://arxiv.org/abs/2610.00545v1
• Date: Wed, 30 Sep 2026 18:26:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:23.696262
• Title: Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization
• Title（参考訳）: オンライン非モノトンDR-サブモジュラー最大化のための幾何学依存境界
• Abstract要約: 凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
• 参考スコア（独自算出の注目度）: 55.29259818039367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. A learner commits each action before observing its objective and competes with the best fixed action in hindsight. We prove a comparator-uniform first-order inequality that gives coefficient $4/9$, improving the online $0.401$ benchmark, with one gradient query and one projection per round and $O(\sqrt T)$ expected approximate regret. If $ζ{\bf 1} \in K\subseteq[0,1]^d$, the coefficient improves to $\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^2]$. The proof is a direct ordered-coordinate argument with an objective-independent rational action. Conversely, a three-group symmetry-gap construction yields an offline oracle upper bound $β_*=0.470438681380894\ldots$ at $ζ=0$, even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every $ζ$. The lower and upper bounds match at $1/2$ for $ζ\ge1/2$, and show that the optimal deficit from $1/2$ is $Θ((1/2-ζ)^2)$ as $ζ\uparrow1/2$. For coefficient-revealed polynomials we obtain $1/2$ for quadratics and a geometry-dependent cubic coefficient starting at $8/17$, including $0.49$ at $ζ=1/5$. A constant objective sequence yields an offline $(4/9-\varepsilon)$ approximation with polynomially many first-order queries on the cube and projections, without requiring a supplied positive lower bound on the optimum. We also give nonanticipating adaptive-adversary and value-feedback guarantees, including $O(T^{3/4})$ regret with one noisy value per round.
• Abstract（参考訳）: コンパクト凸下閉集合上の非負非単調DR-部分モジュラ関数の逆オンライン最大化について検討する。 学習者は、目的を観察する前に各アクションをコミットし、後ろ向きの最高の固定アクションと競合する。 我々は、係数4/9$を与え、オンラインの$0.401$ベンチマークを改善し、1ラウンドごとに1つの勾配クエリと1つのプロジェクションを持ち、$O(\sqrt T)$予想される近似後悔を伴うコンパレータの1次不等式を証明した。 1} \in K\subseteq[0,1]^d$ とすると、係数は $\underlineα( )=\tfrac12-(1-2 )_+^2/[2(3-2 )^2]$ に改善される。 この証明は、客観的非独立な有理作用を持つ直順序座標論である。 逆に、3つの群対称ギャップの構成は、正確な値と完全階調応答であっても、オフラインのオラクル上界$β_*=0.470438681380894\ldots$を$ ==0$とする。 パラメタライズされた拡張と正確な有限インスタンス境界は、各$=$の上限関数を定義する。 下限と上限は1/2$$$\\ge1/2$と一致し、1/2$の最適欠点が$(((1/2-)^2)$ であることを示す。 係数Revealed polynomials に対して、二次数に対して $1/2$ と、幾何依存の立方係数が 8/17$ から始まり、0.49$ が$=1/5$ となる。 定数対物列は、多項式的に多くの立方体および射影上の一階のクエリでオフラインの$(4/9-\varepsilon)$近似を生成する。 O(T^{3/4})$ regret with one noisy value per round。

関連論文リスト

• 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)
• Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor [47.30196146041476]
  我々は、$d$-oracle単位のコンパクト凸部分集合上の非対称非負、非単調DR-部分モジュラ函数について研究する。 オンラインアルゴリズムは、フィードバックが条件付きで偏りがなく、有界であるときに、およその後悔で0.401$に達する。
  論文  参考訳（メタデータ） (2026-09-02T06:00:10Z)
• 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)
• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。 私たちの指導原則は、最大値が丸みを帯びた候補であることです。
  論文  参考訳（メタデータ） (2026-08-03T17:58:00Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$を符号、空間性、正方性制限なしで証明する。 純粋な$varepsilon$-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差の両方が$(varepsilon-2log3(n+1))$である。
  論文  参考訳（メタデータ） (2026-07-30T14:41:34Z)
• Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
  ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。 逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。 設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
  論文  参考訳（メタデータ） (2024-06-10T17:44:11Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)

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

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