論文の概要: Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs
- arxiv url: http://arxiv.org/abs/2102.05347v1
- Date: Wed, 10 Feb 2021 09:34:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-11 14:39:27.642875
- Title: Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs
- Title（参考訳）: 非対称DPPに対する簡便かつ近接最適MAP推論
- Authors: Nima Anari and Thuy-Duong Vuong
- Abstract要約: 非対称なカーネル行列によって定義される決定点過程に対する最大後続推定(MAP)問題について検討する。
局所探索を用いてこの問題に対する最初の乗法近似保証を得る。
近似係数が$kO(k)$ に近いので、理論上、実験的に、この問題に対する最先端の手法と好適に比較できることが示される。
- 参考スコア（独自算出の注目度）: 3.3504365823045044
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Determinantal point processes (DPPs) are widely popular probabilistic models
used in machine learning to capture diversity in random subsets of items. While
traditional DPPs are defined by a symmetric kernel matrix, recent work has
shown a significant increase in the modeling power and applicability of models
defined by nonsymmetric kernels, where the model can capture interactions that
go beyond diversity. We study the problem of maximum a posteriori (MAP)
inference for determinantal point processes defined by a nonsymmetric positive
semidefinite matrix (NDPPs), where the goal is to find the maximum $k\times k$
principal minor of the kernel matrix $L$. We obtain the first multiplicative
approximation guarantee for this problem using local search, a method that has
been previously applied to symmetric DPPs. Our approximation factor of
$k^{O(k)}$ is nearly tight, and we show theoretically and experimentally that
it compares favorably to the state-of-the-art methods for this problem that are
based on greedy maximization. The main new insight enabling our improved
approximation factor is that we allow local search to update up to two elements
of the solution in each iteration, and we show this is necessary to have any
multiplicative approximation guarantee.
- Abstract（参考訳）: 行列点過程(英: determinantal point process、dpps)は、アイテムのランダム部分集合の多様性を捉えるために機械学習で用いられる確率モデルである。
従来のDPPは対称性カーネル行列によって定義されるが、最近の研究では非対称性カーネルによって定義されるモデルのモデリング能力と適用性が大幅に増加している。
非対称な正半有限行列 (NDPPs) によって定義される決定的点過程に対する最大後微分(MAP)推論の問題は、カーネル行列 $L$ の最大 $k\times k$ 主マイナーを見つけることが目的である。
対称DPPに以前に適用された手法である局所探索を用いて、この問題に対する最初の乗算近似保証を得る。
我々の近似値である $k^{o(k)}$ はほぼタイトであり、理論上、実験上、欲欲の最大化に基づくこの問題に対する最先端の手法と比較することが好ましいことを示した。
改良された近似係数を実現できる大きな新しい洞察は、各繰り返しにおいて、局所探索がソリューションの最大2つの要素を更新できるようにすることである。
関連論文リスト
- Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Low-complexity subspace-descent over symmetric positive definite
manifold [9.346050098365648]
対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。
提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
論文 参考訳（メタデータ） (2023-05-03T11:11:46Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳（メタデータ） (2022-09-16T19:15:50Z) - Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。
最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。
低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-07-01T15:22:12Z) - Nonparametric estimation of continuous DPPs with kernel methods [0.0]
パラメトリックおよび非パラメトリック推論法は、有限の場合、すなわち、点パターンが有限の基底集合に存在する場合において提案されている。
我々は、この最大可能性(MLE)問題の制限バージョンが、RKHSにおける非負関数に対する最近の表現定理の範囲内にあることを示す。
この有限次元問題を解くための固定点アルゴリズムを提案し,解析し,実証する。
論文 参考訳（メタデータ） (2021-06-27T11:57:14Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
本稿では,MISDP(MISDP)とMISDP(MISDP)について述べる。
次に、それらの連続緩和値の理論的最適性ギャップを分析し、それらが最先端の値よりも強いことを証明する。
市販の解法は一般にMISDPを解くのが難しいため,MISDPと同等の大きさのMILP(mixed-integer linear program)を用いてSPCAを任意の精度で近似する。
論文 参考訳（メタデータ） (2020-08-28T02:07:08Z) - Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。
最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
論文 参考訳（メタデータ） (2020-05-07T00:39:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。