論文の概要: An Improved Algorithm For Online Reranking
- arxiv url: http://arxiv.org/abs/2209.04870v1
- Date: Sun, 11 Sep 2022 14:03:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-13 14:08:39.844827
- Title: An Improved Algorithm For Online Reranking
- Title（参考訳）: オンラインリランキングのための改良アルゴリズム
- Authors: Marcin Bienkowski, Marcin Mucha
- Abstract要約: 我々は、アルゴリズムが注文された$n$要素のリストを保持するオンライン嗜好集約のモデルについて研究する。
競合比(ALG-to-OPTコスト比)が$O(r2)$である計算効率の良いランダム化アルゴリズムを構築する。
O(r3/2 cdot sqrtn)$-competitive and $Omega(r)$ is a lower bound on the performance of any deterministic online algorithm。
- 参考スコア（独自算出の注目度）: 0.45687771576879593
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a fundamental model of online preference aggregation, where an
algorithm maintains an ordered list of $n$ elements. An input is a stream of
preferred sets $R_1, R_2, \dots, R_t, \dots$. Upon seeing $R_t$ and without
knowledge of any future sets, an algorithm has to rerank elements (change the
list ordering), so that at least one element of $R_t$ is found near the list
front. The incurred cost is a sum of the list update costs (the number of swaps
of neighboring list elements) and access costs (position of the first element
of $R_t$ on the list). This scenario occurs naturally in applications such as
ordering items in an online shop using aggregated preferences of shop
customers. The theoretical underpinning of this problem is known as Min-Sum Set
Cover.
Unlike previous work (Fotakis et al., ICALP 2020, NIPS 2020) that mostly
studied the performance of an online algorithm ALG against the static optimal
solution (a single optimal list ordering), in this paper, we study an arguably
harder variant where the benchmark is the provably stronger optimal dynamic
solution OPT (that may also modify the list ordering). In terms of an online
shop, this means that the aggregated preferences of its user base evolve with
time. We construct a computationally efficient randomized algorithm whose
competitive ratio (ALG-to-OPT cost ratio) is $O(r^2)$ and prove the existence
of a deterministic $O(r^4)$-competitive algorithm. Here, $r$ is the maximum
cardinality of sets $R_t$. This is the first algorithm whose ratio does not
depend on $n$: the previously best algorithm for this problem was $O(r^{3/2}
\cdot \sqrt{n})$-competitive and $\Omega(r)$ is a lower bound on the
performance of any deterministic online algorithm.
- Abstract（参考訳）: 我々は、アルゴリズムが規則付き$n$要素のリストを維持するオンライン嗜好集約の基本的なモデルについて研究する。
入力は望ましい集合 $r_1, r_2, \dots, r_t, \dots$ のストリームである。
R_t$を見た後、将来の集合の知識がなければ、アルゴリズムは要素を再ランクし(リストの順序を変更する)、リストフロントの少なくとも1つの要素を見つける必要がある。
発生したコストは、リスト更新コスト(隣接するリスト要素のスワップ数)とアクセスコスト(リスト上の$R_t$の最初の要素の配置)の合計である。
このシナリオは、オンラインショップにおける商品の注文のような、ショップ顧客の選好を集約したアプリケーションで自然に発生する。
この問題の理論的基盤はMin-Sum Set Coverとして知られている。
オンラインアルゴリズムALGの静的最適解(単一最適リスト順序付け)に対する性能を主に研究した以前の研究 (Fotakis et al., ICALP 2020, NIPS 2020) とは異なり、本論文では、ベンチマークが証明可能なより強力な最適動的解 OPT (リスト順序付けも変更できる) である、明らかに難しい変種について検討する。
オンラインショップの観点では、ユーザーベース全体の嗜好が時間とともに進化することを意味している。
我々は、競争比が$O(r^2)$である計算効率の良いランダム化アルゴリズムを構築し、決定論的な$O(r^4)$-競争性アルゴリズムの存在を証明する。
ここで、$r$は集合の最大濃度$R_t$である。
この問題に対する最善のアルゴリズムは$o(r^{3/2} \cdot \sqrt{n})$-競合であり、$\omega(r)$は任意の決定論的オンラインアルゴリズムのパフォーマンスに対する下限である。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。
その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
論文 参考訳（メタデータ） (2023-12-14T17:31:38Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Quick Streaming Algorithms for Maximization of Monotone Submodular
Functions in Linear Time [16.346069386394703]
単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。
線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。
我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
論文 参考訳（メタデータ） (2020-09-10T16:35:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。