Fugu-MT 論文翻訳(概要): Efficient One Sided Kolmogorov Approximation

論文の概要: Efficient One Sided Kolmogorov Approximation

arxiv url: http://arxiv.org/abs/2207.07916v1
Date: Thu, 14 Jul 2022 10:03:02 GMT
ステータス: 処理完了
システム内更新日: 2022-07-20 07:14:58.156242
Title: Efficient One Sided Kolmogorov Approximation
Title（参考訳）: 効率的な片側コルモゴロフ近似
Authors: Liat Cohen, Tal Grinshpoun, Gera Weiss
Abstract要約: 本研究の主な応用は, 時系列並列スケジュールにおいて, 欠落する確率を推定することである。これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。
参考スコア（独自算出の注目度）: 7.657378889055477
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present an efficient algorithm that, given a discrete random variable $X$ and a number $m$, computes a random variable whose support is of size at most $m$ and whose Kolmogorov distance from $X$ is minimal, also for the one-sided Kolmogorov approximation. We present some variants of the algorithm, analyse their correctness and computational complexity, and present a detailed empirical evaluation that shows how they performs in practice. The main application that we examine, which is our motivation for this work, is estimation of the probability missing deadlines in series-parallel schedules. Since exact computation of these probabilities is NP-hard, we propose to use the algorithms described in this paper to obtain an approximation.
Abstract（参考訳）: 離散確率変数 $X$ と数 $m$ が与えられたとき、最大で$m$ の確率変数を計算し、そのコルモゴロフ距離が 1 辺のコルモゴロフ近似に対しても最小となる効率的なアルゴリズムを提案する。アルゴリズムのいくつかの変種を提示し,その正しさと計算複雑性を分析し,実際にどのように動作するかを示す詳細な経験的評価を行う。この研究のモチベーションである我々が調査する主な応用は、直列並列スケジュールにおける確率的欠落期限の推定である。これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。

関連論文リスト

Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
論文参考訳（メタデータ） (2024-03-15T15:51:27Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
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)
Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文参考訳（メタデータ） (2022-12-15T18:27:39Z)
On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文参考訳（メタデータ） (2022-11-28T08:40:12Z)
Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文参考訳（メタデータ） (2022-10-04T17:13:45Z)
Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文参考訳（メタデータ） (2022-06-17T09:24:41Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文参考訳（メタデータ） (2022-06-07T16:49:54Z)
Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文参考訳（メタデータ） (2021-04-14T19:21:59Z)
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)
Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文参考訳（メタデータ） (2020-01-17T18:47:02Z)

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