論文の概要: Streaming Stochastic Submodular Maximization with On-Demand User Requests
- arxiv url: http://arxiv.org/abs/2601.10901v1
- Date: Thu, 15 Jan 2026 23:00:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-19 20:21:50.304124
- Title: Streaming Stochastic Submodular Maximization with On-Demand User Requests
- Title（参考訳）: オンデマンドユーザ要求による確率的部分モジュラ最大化のストリーミング
- Authors: Honglian Wang, Sijing Tu, Lutz Oettershagen, Aristides Gionis,
- Abstract要約: 我々はニュースレコメンデーションプラットフォームのダイナミクスにインスパイアされたサブモジュラーストリーミングの問題を考える。
利用者の来訪回数を事前に把握している場合には,従来の手法を効果的に適応させることが可能であることを示す。
我々は,1/(8ドル)の競争率を達成する新しいオンラインストリーミングアルゴリズムを導入し,そこでは近似品質を$で制御する。
- 参考スコア（独自算出の注目度）: 18.265540765570844
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We explore a novel problem in streaming submodular maximization, inspired by the dynamics of news-recommendation platforms. We consider a setting where users can visit a news website at any time, and upon each visit, the website must display up to $k$ news items. User interactions are inherently stochastic: each news item presented to the user is consumed with a certain acceptance probability by the user, and each news item covers certain topics. Our goal is to design a streaming algorithm that maximizes the expected total topic coverage. To address this problem, we establish a connection to submodular maximization subject to a matroid constraint. We show that we can effectively adapt previous methods to address our problem when the number of user visits is known in advance or linear-size memory in the stream length is available. However, in more realistic scenarios where only an upper bound on the visits and sublinear memory is available, the algorithms fail to guarantee any bounded performance. To overcome these limitations, we introduce a new online streaming algorithm that achieves a competitive ratio of $1/(8δ)$, where $δ$ controls the approximation quality. Moreover, it requires only a single pass over the stream, and uses memory independent of the stream length. Empirically, our algorithms consistently outperform the baselines.
- Abstract（参考訳）: 本稿では,ニュースレコメンデーションプラットフォームのダイナミクスにインスパイアされた,ストリーミングサブモジュールの最大化における新しい問題について検討する。
我々は、ユーザーがいつでもニュースウェブサイトを訪問できる設定を検討し、訪問毎に最大$k$のニュースアイテムを表示する必要がある。
ユーザのインタラクションは本質的に確率的であり、ユーザに提示された各ニュースアイテムは、ユーザによって一定の受け入れ確率で消費され、各ニュースアイテムは特定のトピックをカバーする。
我々のゴールは、期待されるトピックの総カバレッジを最大化するストリーミングアルゴリズムを設計することである。
この問題に対処するため、マトロイド制約を受ける部分モジュラー最大化への接続を確立する。
我々は,事前のユーザ訪問数や,ストリーム長の線形サイズのメモリが利用可能である場合に,従来の手法を効果的に適用できることを実証した。
しかし、より現実的なシナリオでは、ビジターとサブリニアメモリの上限のみが利用できる場合、アルゴリズムはバウンドパフォーマンスを保証できない。
これらの制限を克服するため、我々は1/(8δ)$という競争率を達成する新しいオンラインストリーミングアルゴリズムを導入し、$δ$は近似品質を制御する。
さらに、ストリームに1回のパスしか必要とせず、ストリーム長に依存しないメモリを使用する。
経験的に、我々のアルゴリズムはベースラインを一貫して上回っている。
関連論文リスト
- User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2023-09-21T21:51:55Z) - Online and Streaming Algorithms for Constrained $k$-Submodular
Maximization [25.15934533974176]
制約付き$k$-submodularは、広告アロケーション、インフルエンス、パーソナライズされたレコメンデーションなど、多くの個別の最適化問題をキャプチャする一般的なフレームワークである。
本研究では,モノトーンと一般(おそらく非モノトーン)の両方の目的に制約された$k$サブモジュールのシングルパスストリーミングとオンラインアルゴリズムを開発する。
論文 参考訳（メタデータ） (2023-05-25T12:53:17Z) - Optimal Data Selection: An Online Distributed View [61.31708750038692]
この問題のオンライン版と分散版のアルゴリズムを開発する。
ランダム選択法は, ランダム選択法よりも5～20%高い性能を示した。
ImageNet と MNIST の学習タスクにおいて、我々の選択方法はランダム選択よりも5-20% 高い性能を示した。
論文 参考訳（メタデータ） (2022-01-25T18:56:16Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Learning Salient Boundary Feature for Anchor-free Temporal Action
Localization [81.55295042558409]
時間的行動のローカライゼーションはビデオ理解において重要な課題である。
純粋にアンカーフリーな時間的定位法を初めて提案する。
このモデルには,(i)エンドツーエンドのトレーニング可能な基本予測器,(ii)サリエンシベースのリファインメントモジュール,(iii)いくつかの一貫性制約が含まれている。
論文 参考訳（メタデータ） (2021-03-24T12:28:32Z) - Cross Layer Optimization and Distributed Reinforcement Learning for Wireless 360° Video Streaming [54.60967639512643]
本稿では,各ユーザに対して利用可能なレートを最大化し,ユーザのQoEを最大化するために効率的に利用するクロスレイヤ最適化手法を提案する。
この問題を2つの相互関連サブプロブレムに分解できることを示す。
複数の独立エージェントの並列学習を活用し,アプリケーション層サブプロブレムを解くために,アクタ・クリティカル・ディープ・強化学習(DRL)を提案する。
論文 参考訳（メタデータ） (2020-11-12T12:59:10Z) - Fair and Representative Subset Selection from Data Streams [4.53279507109072]
ストリーム内のデータ項目が複数の不随意群に属する設定について検討する。
ストリーミングサブモジュラー問題の公平性を考慮した変種に対する効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-09T07:49:13Z) - Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack
Constraint [13.357957711519134]
制約されたサブモジュール問題には、パーソナライズされたレコメンデーション、チーム形成、バイラルマーケティングによる収益化など、さまざまな応用が含まれている。
我々は5.83のランダム化近似を達成し、O(n log n)$禁断時間、すなわち少なくとも$n$を他の最先端アルゴリズムよりも高速に実行する単純なグリーディアルゴリズムを提案する。
そこで我々は,非単調な目的に対する最初の定数近似である9-近似を求め,実データと合成データに改良された性能を示すアルゴリズムの実験評価を行った。
論文 参考訳（メタデータ） (2020-07-09T18:15:01Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z) - Non-Cooperative Game Theory Based Rate Adaptation for Dynamic Video
Streaming over HTTP [89.30855958779425]
Dynamic Adaptive Streaming over HTTP (DASH)は、新興かつ有望なマルチメディアストリーミング技術であることを示した。
本稿では,サーバの限られた輸出帯域幅をマルチユーザに対して最適に割り当てるアルゴリズムを提案し,その品質・オブ・エクスペリエンス(QoE)を公平性で最大化する。
論文 参考訳（メタデータ） (2019-12-27T01:19:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。