論文の概要: Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

• arxiv url: http://arxiv.org/abs/2602.20578v1
• Date: Tue, 24 Feb 2026 05:59:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.625087
• Title: Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets
• Title（参考訳）: ダウンクローズド凸集合上のオンライン非モノトンDR-サブモジュラー最大化の上線化可能性
• Authors: Yiyang Lu, Haresh Jadav, Mohammad Pedramfar, Ranveer Singh, Vaneet Aggarwal,
• Abstract要約: ダウンクロース凸関数上の非モノトンダイミッシング・リターン関数のオンライン投影について検討した。 我々の主な貢献は、慎重に設計された指数的再パラメータ化の下で、このクラスが1/e$linear-izableであることを示す新しい構造結果である。 その結果、ラウンド毎に1つのクエリで$O(T1/2)$static regretを取得し、適応性と動的後悔の保証をアンロックする。
• 参考スコア（独自算出の注目度）: 40.61353645255313
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study online maximization of non-monotone Diminishing-Return(DR)-submodular functions over down-closed convex sets, a regime where existing projection-free online methods suffer from suboptimal regret and limited feedback guarantees. Our main contribution is a new structural result showing that this class is $1/e$-linearizable under carefully designed exponential reparametrization, scaling parameter, and surrogate potential, enabling a reduction to online linear optimization. As a result, we obtain $O(T^{1/2})$ static regret with a single gradient query per round and unlock adaptive and dynamic regret guarantees, together with improved rates under semi-bandit, bandit, and zeroth-order feedback. Across all feedback models, our bounds strictly improve the state of the art.
• Abstract（参考訳）: 我々は,既存のプロジェクションフリーオンライン手法が最適以下後悔と限定的なフィードバック保証に悩まされる状況において,非モノトンダイミッシング・リターン(DR)-サブモジュラー関数のダウンクロース凸集合上でのオンライン最大化について検討した。 我々の主な貢献は、指数的再パラメータ化、スケーリングパラメータ、サロゲートポテンシャルの下で、このクラスが1/e$-linearizableであることを示す新しい構造的結果であり、オンライン線形最適化の削減を可能にする。 その結果、ラウンド毎の1つの勾配クエリで$O(T^{1/2})$static regretを取得し、適応性と動的後悔の保証をアンロックし、半帯域幅、帯域幅、ゼロ階フィードバックで改善した。 すべてのフィードバックモデルにおいて、私たちの限界は、最先端の状態を厳格に改善します。

関連論文リスト

• $γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions [52.031993908548294]
  このような関数の広範な近似を特徴付ける新しい一階述語条件である$-weakly $-up-concavityを導入する。 本フレームワークは,DR-サブモジュラークラスに対する最適係数を復元し,既存の近似係数を大幅に改善する。
  論文  参考訳（メタデータ） (2026-02-13T22:34:44Z)
• Online Submodular Maximization via Online Convex Optimization [11.989282746688064]
  我々は、ポテンシャル関数、すなわちポテンシャル関数の大規模なクラスがしきい値凸最適化(OCO)に還元されることを証明した。 我々は,オンライン学習問題において,動的後悔,盗賊,楽観的な学習設定など,多くの異なるバージョンに縮小が及んでいることを示す。
  論文  参考訳（メタデータ） (2023-09-08T14:08:19Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2022-05-02T08:48:22Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)

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

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