論文の概要: Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization

• arxiv url: http://arxiv.org/abs/2610.04049v1
• Date: Fri, 02 Oct 2026 20:52:38 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-06 21:04:57.097351
• Title: Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization
• Title（参考訳）: 非モノトン$k$-部分モジュラー最大化のための幾何依存性近似
• Abstract要約: 支持領域がより均一な選択を許すにつれて、認証された近似係数がどのように改善されるかを示す。 明示的なパラメータの選択は、非遅延認証プロファイルに$underline_k()$を与える。 値保持丸めは、これらの保証をマトロイドとクナプサックの制約に転送する。
• 参考スコア（独自算出の注目度）: 55.29259818039367
• License:
• Abstract: We study nonnegative, non-monotone $k$-submodular maximization with $k\ge2$ labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region $P\subseteq[0,1]^n$, the diagonal level $ζ(P)=\max\{t\in[0,1]:t {\bf 1} \in P\}$ ranges from $ζ=0$, which carries no geometric promise, to $ζ=1$, which is unrestricted support. Our main structural result is a comparator-uniform linearization of the multilinear extension, built from an objective-independent action and a comparator-independent update field. For $k\ge3$, its validity reduces, independently of the number of elements, to four polynomial inequalities of degree at most three in one or two variables, only one of which depends on $k$. Explicit parameter choices give a nondecreasing certified profile $\underlineα_k(ζ)$, in closed form on all of $[0,1]$ when $k=2$. At $ζ=0$ we certify $0.4456\ldots$ for $k=2$ and $0.4541\ldots$ for every $k\ge3$, improving the recent $\sqrt2-1$ guarantee for one matroid or one knapsack, as well as the $1/3$-type guarantees for a fixed number of budgets; at $ζ=1$ we certify $1/2$ for $k=2$, $(\sqrt{17}-3)/2$ for $k=3,4$, and $k/(2k-1)$ for $k\ge5$, whose excess over $1/2$ is of order $1/k$ rather than the previous $1/k^2$. Value-retaining rounding transfers these guarantees to matroid and knapsack constraints, and the same field yields $O(\sqrt T)$ approximate regret online under gradient or post-decision value feedback.
• Abstract（参考訳）: 非負の非単調な$k$-submodular maximization with $k\ge2$ labels under support constraints, and showed the confirmed approximation coefficient improves as the support region allows more uniform selection。 コンパクト凸閉サポート領域 $P\subseteq[0,1]^n$ に対して、対角線レベル $\(P)=\max\{t\in[0,1]:t {\bf 1} \in P\}$ は、幾何的な約束を持たない$ =0$ から $ = 1$ までの範囲であり、これは非制限のサポートである。 主構造的結果は、目的非依存のアクションとコンパレータ非依存の更新フィールドから構築された多線形拡張のコンパレータ-一様線形化である。 k\ge3$ の場合、その妥当性は要素の数とは独立に 1 または 2 変数で最大 3 の次数 4 の多項式不等式に還元され、そのうち 1 つは$k$ に依存する。 明示的なパラメータ選択は、$k=2$のとき、$[0,1]$のすべてのクローズドフォームで、非減少的な認証プロファイル $\underlineα_k(a)$を与える。 例えば、$0.4456\ldots$ for $k=2$と$0.4541\ldots$ for every $k\ge3$, improve the recent $\sqrt2-1$ guarantee for one matroid or one knapsack, and the $1/3$-type guarantees for a fixed number of budgets; at $w=1$ we certify $1/2$ for $k=2$, $(\sqrt{17}-3)/2 $k=3,4$と$k/(2k-1)$ for $k\ge5$。 値保持丸めは、これらの保証をマトロイドとクナプサックの制約に転送し、同じフィールドは、勾配や後決定値のフィードバックの下で、ほぼ後悔する$O(\sqrt T)をオンラインで得る。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids [46.81212204219748]
  本稿では,不均一なポアソン時計を注意深く制御することで,最大利得の局所交換を繰り返すMGPEと呼ばれる新しいアルゴリズムを提案する。 また,マトロイド制約が濃度に減少するか,あるいは目標が$$$-weak DR-submodularityというより強い概念を満たす場合,MGPEはそれぞれ1-e-$と1-e-$の厳密な近似比を自動的に回復できることを示した。
  論文  参考訳（メタデータ） (2026-09-21T13:35:10Z)
• Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting [20.06940271479014]
  クラスごとの分解$I(X;Y)=sum_i_i D_mathrmKL(P_Y|i|P_Y)$を介して、Side-Channel Existence Theoremを$k$クラスに拡張します。 以下の3つの結果が従う: (1) 活性クラス全体の和形式 MI の下限、(2) カスケード臨界コスト定理と、一様予算境界が消滅する非ゼロ、(3) 精度 $mathrmAcc*
  論文  参考訳（メタデータ） (2026-09-06T00:48:40Z)
• One Inverse Step is a Convex Program: Bayes-Limit Calibration of Diffusion Inversion [0.0]
  1つの暗黙のDDIM反転ステップは、事前訓練された拡散モデルが局所多様体幾何学を符号化するかどうかの最も安価なプローブである。 フェルミ窓はモデルのトレーニングサポートと3.6$-$5.6times$で対立し、ヘッセン=リプシッツ定数は法が読み取る曲率の2-$12%である。 最後の条件付き天井 $_t_max(mathrmsym,J)le1$, from $mathrmCov(x_0mid x_t)succeq0$
  論文  参考訳（メタデータ） (2026-08-24T11:01:54Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
  論文  参考訳（メタデータ） (2026-03-09T22:27:00Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)

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

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