論文の概要: Improving Randomized Metric Distortion to 2.3282
- arxiv url: http://arxiv.org/abs/2608.29308v1
- Date: Sat, 29 Aug 2026 14:49:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:30.920885
- Title: Improving Randomized Metric Distortion to 2.3282
- Title（参考訳）: 2.3282へのランダム化メトリック歪みの改善
- Abstract要約: メートル法社会選択では、各投票者は、未知のメートル法空間において、距離によって$m$の候補者をランク付けする。
ランダム化された投票規則は、候補者よりも宝くじを選ぶためにランキングのみを使用しなければならない。
我々の主な貢献は、ランダムな$D$に対して、ゆがみの安定にどのように使用できるかを示すことである。
- 参考スコア（独自算出の注目度）: 14.532743694321324
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In metric social choice, each voter ranks a set of $m$ candidates by her distance to them in an unknown metric space. The cost of a candidate is its average distance to the voters. A randomized voting rule must use only the rankings to choose a lottery over candidates. Its distortion is the worst-case ratio between the expected cost under the lottery it returns and the cost of the best candidate. Charikar, Ramakrishnan, Wang, and Wu [JACM 2024] prove an upper bound of $2.753$, establishing a constant separation from deterministic rules, for which the best achievable distortion is $3$. Independently, Frank [arXiv:2608.17863] and Ye [arXiv:2608.21202] improve the bound to $2.5$, using an equal mixture of maximal lottery and Integrated Veto. The existing arguments do not yield a better bound with any mixture of these rules. We break this barrier with a new ingredient, a random-size stable lottery. Let $D$ be a random variable over the domain of positive integers. A random-size stable lottery $\mathrm{RSL}_D$ guarantees that the probability of a random voter preferring any fixed candidate $c$ to her favorite of $D$ i.i.d. draws from $\mathrm{RSL}_D$ is at most $\mathbb{E}[1/(D+1)]$, where the probability also averages over $D$. When $D=k$ deterministically, this reduces to the stable $k$-lottery of Charikar, Ramakrishnan, Tan, and Wang [EC 2025]; the case $k=1$ is precisely a maximal lottery. Their minimax argument for a fixed $k$ easily generalizes to a random $D$. Our main contribution is to show how stability with respect to a random $D$ can be used to bound distortion. By mixing a suitably chosen random-size stable lottery with Integrated Veto, we get distortion at most $11641/5000=2.3282$. The proof combines infinite-dimensional conic linear-programming duality, heuristic nonlinear optimization, and exact rational verification via the Bernstein basis.
- Abstract（参考訳）: メートル法社会選択では、各投票者は、未知のメートル法空間において、距離によって$m$の候補者をランク付けする。
候補者の費用は有権者の平均距離である。
ランダム化された投票規則は、候補者よりも宝くじを選ぶためにランキングのみを使用しなければならない。
その歪みは、返却される宝くじの下で予想されるコストと最良の候補者のコストとの最悪のケース比である。
Charikar, Ramakrishnan, Wang, Wu [JACM 2024] は2.753$の上限を証明し、決定論的規則から常に分離する。
フランク [arXiv:2608.17863] とイ [arXiv:2608.21202] は、最大宝くじと積分ベトーの等しい混合を用いて、2.5ドルの上限を改良した。
既存の議論はこれらの規則のいかなる混合ともより良く結びついていない。
我々はこの障壁を、新しい材料、ランダムサイズの安定した宝くじで破る。
D$ を正の整数の領域上のランダム変数とする。
ランダムサイズ安定な宝くじ$\mathrm{RSL}_D$は、任意の固定候補$c$を好きな$D$に優先するランダム投票者の確率が$\mathrm{RSL}_D$から引き出される確率は、最も高い$\mathbb{E}[1/(D+1)]$である。
決定論的に$D=k$とすると、これはCharikar, Ramakrishnan, Tan, Wang [EC 2025] の安定な$k$-lotteryに還元される。
固定の$k$に対するミニマックスの引数は、容易にランダムな$D$に一般化する。
我々の主な貢献は、ランダムな$D$に対する安定性が歪みの束縛にどのように使用できるかを示すことである。
適度に選択されたランダムサイズ安定な宝くじと統合ベトを混合することにより、少なくとも11641/5000=2.3282$の歪みが得られる。
この証明は無限次元の円錐線型計画双対性、ヒューリスティック非線形最適化、バーンスタイン基底による正確な有理性検証を組み合わせたものである。
関連論文リスト
- The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳（メタデータ） (2026-08-03T17:57:01Z) - Randomly Pivoted Partial Cholesky: Random How? [0.0]
A_ii$ に比例する確率の $i-$th 列を選択するランダムにピボットされた部分チョレスキーアルゴリズムは、トレースノルムの普遍的収縮をもたらすことを示す。
A_ii2$ 1 に比例して $i-$th 行を選択すると、フロベニウスノルムにおいて同じ結果が得られる(シャッテン 2-ノルム)。
論文 参考訳（メタデータ） (2024-04-17T15:45:31Z) - $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳（メタデータ） (2023-09-17T01:45:13Z) - A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity [28.068960555415014]
非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。
アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
論文 参考訳（メタデータ） (2023-07-27T19:03:36Z) - Breaking the Metric Voting Distortion Barrier [10.143374372425757]
社会選択における計量歪みの問題を考察する。
歪み3-epsilon$を保証するランダム化ルールを見つけることは、計算社会選択において大きな課題である。
歪みを2.753ドル未満で保証する規則を与えます。
論文 参考訳（メタデータ） (2023-06-30T17:56:33Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Variance-Dependent Best Arm Identification [12.058652922228918]
マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。
武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。
このアルゴリズムは2つの対数項に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-19T04:13:54Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Randomized Smoothing of All Shapes and Sizes [29.40896576138737]
最適」ノルムの適切な概念に対して、任意の「ニッチ」ノルムに対する最適な滑らか化はノルムの *Wulff Crystal* によって与えられるレベル集合を持つことを示す。
ここでは、*バナッハ空間コタイプ*の理論を通して、現在のランダム化平滑化技術に基本的な限界を示す。
論文 参考訳（メタデータ） (2020-02-19T11:41:09Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。