論文の概要: Instance-Optimal Uniformity Testing and Tracking

• arxiv url: http://arxiv.org/abs/2508.02637v1
• Date: Mon, 04 Aug 2025 17:23:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:22.456524
• Title: Instance-Optimal Uniformity Testing and Tracking
• Title（参考訳）: インスタンス-最適一様性テストと追跡
• Authors: Guy Blanc, Clément L. Canonne, Erik Waingarten,
• Abstract要約: 本稿では,一様性追跡の問題を導入し,一様性から偏差を検出するアルゴリズムを提案する。 我々の主な貢献は$operatornamepolylog(operatornameopt)$-competitive uniformity tracking algorithmである。
• 参考スコア（独自算出の注目度）: 20.711670932098176
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the uniform distribution, or, alternatively, if its total variation distance from uniform exceeds some input distance parameter. This question has received a significant amount of interest and its complexity is, by now, fully settled. Yet, we argue that it fails to capture many scenarios of interest, and that its very definition as a gap problem in terms of a prespecified distance may lead to suboptimal performance. To address these shortcomings, we introduce the problem of uniformity tracking, whereby an algorithm is required to detect deviations from uniformity (however they may manifest themselves) using as few samples as possible, and be competitive against an optimal algorithm knowing the distribution profile in hindsight. Our main contribution is a $\operatorname{polylog}(\operatorname{opt})$-competitive uniformity tracking algorithm. We obtain this result by leveraging new structural results on Poisson mixtures, which we believe to be of independent interest.
• Abstract（参考訳）: 均一性テストタスクにおいて、アルゴリズムは、(既知の)有限領域上の未知の確率分布からのサンプルを備え、それが一様分布であるか、あるいは、その一様からの全変動距離が入力距離パラメータを超えるかどうかを判断しなければならない。 この問題はかなりの関心を集めており、その複雑さは今のところ完全に解決されている。 しかし、多くの関心のシナリオを捉えることに失敗し、その定義が予め特定された距離のギャップ問題として定義されることは、準最適性能をもたらす可能性があると論じる。 これらの欠点に対処するために,一様性追跡という問題を導入し,一様性から逸脱を検出するアルゴリズムを可能な限り少ないサンプルを用いて求めるとともに,後から分布分布を知る最適なアルゴリズムと競合するアルゴリズムを提案する。 我々の主な貢献は$\operatorname{polylog}(\operatorname{opt})$-competitive uniformity tracking algorithmである。 この結果は、ポアソン混合物の新たな構造的結果を活用することで得られる。

関連論文リスト

• Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing [7.81603404636933]
  Weibull の確率および累積分布関数 (PDF と CDF) を学習するための汎用フレームワークを提案する。 我々は,サブ線形空間のみを必要としながら,サンプルストリームからの分布のマージ可能な要約を計算する。 提案アルゴリズムは,超線形時間と線形空間の複素量による距離推定手法を改良した。
  論文  参考訳（メタデータ） (2025-03-10T18:57:48Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Adversarially Robust Distributed Count Tracking via Partial Differential Privacy [17.43748116766233]
  分散機能監視(distributed functional monitoring)とも呼ばれる分散追跡モデルについて検討する。 このモデルは、各アイテムのストリームを受け取り、中央サーバと通信する、$k$のサイトを含む。 カウントトラッキングでは、決定論的アルゴリズムとランダム化アルゴリズムの通信に$sqrtk$ギャップがあることが知られている。
  論文  参考訳（メタデータ） (2023-11-01T07:42:13Z)
• Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization [26.4468964378511]
  複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。 データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。 我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
  論文  参考訳（メタデータ） (2023-03-22T21:35:50Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution [8.465228064780748]
  2つの点でサポートされる離散確率測度の間のWasserstein距離の計算が既に#P-hardであることを証明します。 目的関数が最も悪質な外乱分布で滑らかになる分布的に頑健な双対最適輸送問題を導入する。 双対目的関数の平滑化は主目的関数の正則化と等価であることを示す。
  論文  参考訳（メタデータ） (2021-03-10T18:53:59Z)
• Efficient Discretizations of Optimal Transport [16.996068297291057]
  境界分布に対して与えられた点数で離散化を計算するアルゴリズムを提案する。 我々は近似の限界を証明し、幅広い問題について性能を実証する。
  論文  参考訳（メタデータ） (2021-02-16T04:31:52Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

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

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