論文の概要: Resolving the Optimal Metric Distortion Conjecture

• arxiv url: http://arxiv.org/abs/2004.07447v2
• Date: Mon, 7 Sep 2020 16:52:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-12 22:14:24.995991
• Title: Resolving the Optimal Metric Distortion Conjecture
• Title（参考訳）: 最適計量歪予想の解法
• Authors: Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah
• Abstract要約: 以下の計量歪み問題を考察する。 点の有限集合である$V$と$C$は、同じ距離空間にある。 我々はこれらのランキングのみを入力として、$C$のポイントを選択するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 27.344649091365067
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the following metric distortion problem: there are two finite sets of points, $V$ and $C$, that lie in the same metric space, and our goal is to choose a point in $C$ whose total distance from the points in $V$ is as small as possible. However, rather than having access to the underlying distance metric, we only know, for each point in $V$, a ranking of its distances to the points in $C$. We propose algorithms that choose a point in $C$ using only these rankings as input and we provide bounds on their \emph{distortion} (worst-case approximation ratio). A prominent motivation for this problem comes from voting theory, where $V$ represents a set of voters, $C$ represents a set of candidates, and the rankings correspond to ordinal preferences of the voters. A major conjecture in this framework is that the optimal deterministic algorithm has distortion $3$. We resolve this conjecture by providing a polynomial-time algorithm that achieves distortion $3$, matching a known lower bound. We do so by proving a novel lemma about matching voters to candidates, which we refer to as the \emph{ranking-matching lemma}. This lemma induces a family of novel algorithms, which may be of independent interest, and we show that a special algorithm in this family achieves distortion $3$. We also provide more refined, parameterized, bounds using the notion of $\alpha$-decisiveness, which quantifies the extent to which a voter may prefer her top choice relative to all others. Finally, we introduce a new randomized algorithm with improved distortion compared to known results, and also provide improved lower bounds on the distortion of all deterministic and randomized algorithms.
• Abstract（参考訳）: v$ と $c$ という2つの有限個の点の集合が同じ計量空間に存在し、我々の目標は、v$ の点からの距離が可能な限り小さい $c$ の点を選択することである。 しかし、基礎となる距離メートル法にアクセスするのではなく、各点に対して$V$で、その点との距離を$C$でランク付けすることしか分かっていない。 我々は,これらのランキングのみを入力として,$C$の点を選択するアルゴリズムを提案し,それらの値に有意な値を与える(Worst-case approximation ratio)。 この問題の顕著な動機は投票理論によるもので、$V$は有権者の集合を表し、$C$は候補者の集合を表し、ランキングは有権者の序列的な選好に対応する。 このフレームワークにおける主要な予想は、最適決定論的アルゴリズムが3ドル歪んでいることである。 この予想は、既知の下界と一致する歪みを3ドルに抑える多項式時間アルゴリズムを提供することで解決する。 我々は、有権者と候補者のマッチングに関する新しい補題を証明し、それを \emph{ ranking-matching lemma} と呼ぶ。 この補題は、独立した興味を持つ可能性のある新しいアルゴリズムのファミリーを誘導し、このファミリーの特別なアルゴリズムが歪みを3ドルを達成することを示す。 さらに、$\alpha$-decisivenessという概念を用いて、より洗練され、パラメータ化された境界も提供します。 最後に、既知の結果と比較して歪みが改善された新しいランダム化アルゴリズムを導入し、決定論的およびランダム化アルゴリズム全体の歪みに対する下界を改善した。

関連論文リスト

• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。 この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
  論文  参考訳（メタデータ） (2024-06-26T18:19:10Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• 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)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• No quantum speedup over gradient descent for non-smooth convex optimization [22.16973542453584]
  ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。 私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。 下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
  論文  参考訳（メタデータ） (2020-10-05T06:32:47Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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