論文の概要: Hardness of Maximum Likelihood Learning of DPPs
- arxiv url: http://arxiv.org/abs/2205.12377v1
- Date: Tue, 24 May 2022 21:46:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-29 01:59:46.447401
- Title: Hardness of Maximum Likelihood Learning of DPPs
- Title（参考訳）: DPPの最大習熟度学習の硬さ
- Authors: Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
- Abstract要約: 機械学習におけるDPPの研究において、クレスザは問題はNP完全であると推測した。
クレスザ予想を証明し、その予想を支持するいくつかの予備的な証拠を示す。
また,最適ログ類似度に対する最悪ケース近似を実現するアルゴリズムを初めて取得する。
- 参考スコア（独自算出の注目度）: 25.06251462216571
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Determinantal Point Processes (DPPs) are a widely used probabilistic model
for negatively correlated sets. DPPs have been successfully employed in Machine
Learning applications to select a diverse, yet representative subset of data.
In seminal work on DPPs in Machine Learning, Kulesza conjectured in his PhD
Thesis (2011) that the problem is NP-complete. The lack of a formal proof
prompted Brunel, Moitra, Rigollet and Urschel (COLT 2017) to conjecture that,
in opposition to Kulesza's conjecture, there exists a polynomial-time algorithm
for computing a maximum-likelihood DPP. They also presented some preliminary
evidence supporting their conjecture.
In this work we prove Kulesza's conjecture. In fact, we prove the following
stronger hardness of approximation result: even computing a
$\left(1-O(\frac{1}{\log^9{N}})\right)$-approximation to the maximum
log-likelihood of a DPP on a ground set of $N$ elements is NP-complete. At the
same time, we also obtain the first polynomial-time algorithm that achieves a
nontrivial worst-case approximation to the optimal log-likelihood: the
approximation factor is $\frac{1}{(1+o(1))\log{m}}$ unconditionally (for data
sets that consist of $m$ subsets), and can be improved to $1-\frac{1+o(1)}{\log
N}$ if all $N$ elements appear in a $O(1/N)$-fraction of the subsets.
In terms of techniques, we reduce approximating the maximum log-likelihood of
DPPs on a data set to solving a gap instance of a "vector coloring" problem on
a hypergraph. Such a hypergraph is built on a bounded-degree graph construction
of Bogdanov, Obata and Trevisan (FOCS 2002), and is further enhanced by the
strong expanders of Alon and Capalbo (FOCS 2007) to serve our purposes.
- Abstract（参考訳）: 決定点過程 (Determinantal Point Processs, DPPs) は負相関集合に対する確率論的モデルである。
DPPは、多様だが代表的なデータサブセットを選択するために、機械学習アプリケーションに成功している。
機械学習におけるDPPの研究において、クレスザはPh.D. Thesis (2011)でNP完全であると推測した。
公式な証明の欠如により、Brunel, Moitra, Rigollet and Urschel (COLT 2017) は Klesza の予想に反して、最大形 DPP を計算する多項式時間アルゴリズムが存在すると推測した。
彼らはまた、彼らの予想を支持するいくつかの予備的な証拠を示した。
この研究で、我々はクレスザの予想を証明する。
実際、近似結果のより強い硬さを証明している:$\left(1-O(\frac{1}{\log^9{N}})\right)$-approximation to the maximum log-likelihood of a $N$ elements is NP-complete。
近似係数は$\frac{1}{(1+o(1))\log{m}}$ 条件付き($m$ のサブセットからなるデータセットに対して)であり、すべての$n$要素が$o(1/n)$ のサブセットに現れる場合、1-\frac{1+o(1)}{\log n}$ に改善できる。
手法の面では、データセット上のdppの最大ログ類似度を近似し、ハイパーグラフ上の「ベクトル彩色」問題のギャップインスタンスを解決する。
このようなハイパーグラフはBogdanov, Obata and Trevisan (FOCS 2002) の有界グラフ構造の上に構築され、Alon and Capalbo (FOCS 2007) の強い拡張によってさらに拡張され、我々の目的に役立てられる。
関連論文リスト
- Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。
提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
論文 参考訳（メタデータ） (2024-03-31T02:03:35Z) - 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) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility
Amortizations in Repeated Rankings [9.066817876491053]
我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。
幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。
提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。
我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
論文 参考訳（メタデータ） (2022-02-07T14:43:35Z) - Recurrently Predicting Hypergraphs [30.092688729343678]
問題は、$n$要素の集合に対して$mathcalO(2n)$でスケーリング可能なマルチウェイ関係(ハイパーエッジ)の数から生じる。
そこで本研究では,提案手法の初期推定を反復的に精算することにより,入射行列を予測する再帰型ハイパーグラフニューラルネットワークを提案する。
論文 参考訳（メタデータ） (2021-06-26T01:12:41Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳（メタデータ） (2021-06-03T07:22:48Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。