論文の概要: MAC Advice for Facility Location Mechanism Design

• arxiv url: http://arxiv.org/abs/2403.12181v1
• Date: Mon, 18 Mar 2024 18:52:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-20 18:21:58.042968
• Title: MAC Advice for Facility Location Mechanism Design
• Title（参考訳）: MACを用いた施設配置機構設計
• Authors: Zohar Barak, Anupam Gupta, Inbal Talgam-Cohen,
• Abstract要約: 我々は、$k$-facility位置決め機構設計問題について検討する。 以前のモデルとは異なり、$k$の最適施設位置の予測は各エージェントの位置の予測に対して$n$の予測を受ける。 予測された位置の$delta$-fractionの一部が任意に誤りを許容され、残りの予測は$varepsilon$-errorまで修正される。
• 参考スコア（独自算出の注目度）: 12.136427429093395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithms with predictions have attracted much attention in the last years across various domains, including variants of facility location, as a way to surpass traditional worst-case analyses. We study the $k$-facility location mechanism design problem, where the $n$ agents are strategic and might misreport their location. Unlike previous models, where predictions are for the $k$ optimal facility locations, we receive $n$ predictions for the locations of each of the agents. However, these predictions are only "mostly" and "approximately" correct (or MAC for short) -- i.e., some $\delta$-fraction of the predicted locations are allowed to be arbitrarily incorrect, and the remainder of the predictions are allowed to be correct up to an $\varepsilon$-error. We make no assumption on the independence of the errors. Can such predictions allow us to beat the current best bounds for strategyproof facility location? We show that the $1$-median (geometric median) of a set of points is naturally robust under corruptions, which leads to an algorithm for single-facility location with MAC predictions. We extend the robustness result to a "balanced" variant of the $k$ facilities case. Without balancedness, we show that robustness completely breaks down, even for the setting of $k=2$ facilities on a line. For this "unbalanced" setting, we devise a truthful random mechanism that outperforms the best known result of Lu et al. [2010], which does not use predictions. En route, we introduce the problem of "second" facility location (when the first facility's location is already fixed). Our findings on the robustness of the $1$-median and more generally $k$-medians may be of independent interest, as quantitative versions of classic breakdown-point results in robust statistics.
• Abstract（参考訳）: 予測付きアルゴリズムは、伝統的な最悪のケース分析を超える方法として、施設位置の変種を含む、さまざまな領域で近年注目を集めている。 我々は、$k$-facilityロケーションメカニズムの設計問題を調査し、$n$エージェントは戦略的であり、位置を誤報告する可能性がある。 以前のモデルとは異なり、$k$の最適施設位置の予測は各エージェントの位置の予測に対して$n$の予測を受ける。 しかし、これらの予測は「ほとんど」で「ほぼ」正しい(略してMAC)、すなわち予測された位置の$\delta$-fractionの一部が任意に誤りを許容され、残りの予測は$\varepsilon$-errorまで修正できる。 我々は誤りの独立を前提にしない。 このような予測は、現在の防犯施設の配置で最善を尽くすことができるだろうか? 一組の点の1ドル中央値(幾何学的中央値)は、汚職の下で自然に堅牢であることが示され、MAC予測による単一ファクティリティ位置のアルゴリズムが導かれる。 我々はロバスト性の結果を$k$のファシリティケースの"バランスの取れた"変種に拡張する。 バランスが取れなければ、ライン上の$k=2$の設備であっても、ロバスト性は完全に崩壊する。 この「バランスの取れない」設定のために、予測を使用しないLu et al [2010] の最もよく知られた結果を上回る真にランダムなメカニズムを考案する。 途中に「第2の」施設配置の問題(第1の施設位置が固定されている場合)を導入する。 古典的なブレークポイントの定量的バージョンがロバストな統計結果をもたらすため、中間者1ドル、より一般的な$k$-メディアンのロバスト性に関する我々の発見は、独立した関心を持つ可能性がある。

関連論文リスト

• Fair Secretaries with Unfair Predictions [12.756552522270198]
  予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。 私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
  論文  参考訳（メタデータ） (2024-11-15T00:23:59Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  拒絶による分類は、モデルを予測しないことを許容する学習パラダイムとして現れます。 そこで我々は,事前学習したモデルの性能を最大化する理想的なデータ分布を求める。 私たちのフレームワークは、クリーンでノイズの多いデータセットで実証的にテストされます。
  論文  参考訳（メタデータ） (2024-05-29T01:32:17Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• Zero-Regret Performative Prediction Under Inequality Constraints [5.513958040574729]
  本稿では不等式制約下での性能予測について検討する。 我々は,ある程度の精度しか必要としない頑健な原始双対フレームワークを開発する。 次に、位置ファミリに対する適応的原始双対アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-22T04:54:26Z)
• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。 我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
  論文  参考訳（メタデータ） (2023-05-16T07:52:08Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Probable Domain Generalization via Quantile Risk Minimization [90.15831047587302]
  ドメインの一般化は、目に見えないテスト分布でうまく機能する予測子を求める。 我々はDGのための新しい確率的フレームワークを提案し、高い確率でよく動作する予測器を学習することを目指している。
  論文  参考訳（メタデータ） (2022-07-20T14:41:09Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。 本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
  論文  参考訳（メタデータ） (2022-02-07T21:08:02Z)
• SLOE: A Faster Method for Statistical Inference in High-Dimensional Logistic Regression [68.66245730450915]
  実用データセットに対する予測の偏見を回避し、頻繁な不確実性を推定する改善された手法を開発している。 私たちの主な貢献は、推定と推論の計算時間をマグニチュードの順序で短縮する収束保証付き信号強度の推定器SLOEです。
  論文  参考訳（メタデータ） (2021-03-23T17:48:56Z)
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
  トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。 我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。 例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
  論文  参考訳（メタデータ） (2020-11-15T21:34:44Z)

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

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