論文の概要: Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment
- arxiv url: http://arxiv.org/abs/2006.08816v6
- Date: Fri, 11 Jun 2021 03:32:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 03:33:49.801666
- Title: Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment
- Title(参考訳): gershgorin disc perfect alignmentによるサイン付きグラフメトリック学習
- Authors: Cheng Yang, Gene Cheung, Wei Hu
- Abstract要約: プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。
距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。
実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
- 参考スコア(独自算出の注目度): 46.145969174332485
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a convex and differentiable objective $Q(\M)$ for a real symmetric
matrix $\M$ in the positive definite (PD) cone -- used to compute Mahalanobis
distances -- we propose a fast general metric learning framework that is
entirely projection-free. We first assume that $\M$ resides in a space $\cS$ of
generalized graph Laplacian matrices corresponding to balanced signed graphs.
$\M \in \cS$ that is also PD is called a graph metric matrix. Unlike low-rank
metric matrices common in the literature, $\cS$ includes the important
diagonal-only matrices as a special case. The key theorem to circumvent full
eigen-decomposition and enable fast metric matrix optimization is Gershgorin
disc perfect alignment (GDPA): given $\M \in \cS$ and diagonal matrix $\S$,
where $S_{ii} = 1/v_i$ and $\v$ is $\M$'s first eigenvector, we prove that
Gershgorin disc left-ends of similarity transform $\B = \S \M \S^{-1}$ are
perfectly aligned at the smallest eigenvalue $\lambda_{\min}$. Using this
theorem, we replace the PD cone constraint in the metric learning problem with
tightest possible linear constraints per iteration, so that the alternating
optimization of the diagonal / off-diagonal terms in $\M$ can be solved
efficiently as linear programs via the Frank-Wolfe method. We update $\v$ using
Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm
start as entries in $\M$ are optimized successively. Experiments show that our
graph metric optimization is significantly faster than cone-projection schemes,
and produces competitive binary classification performance.
- Abstract(参考訳): 実対称行列に対して凸で微分可能な$Q(\M)$が与えられたとき、マハラノビス距離を計算するために使われる正定値(PD)錐において$\M$は射影のない高速な一般計量学習フレームワークを提案する。
まず、$\m$ は平衡符号付きグラフに対応する一般化グラフラプラシアン行列の空間 $\cs$ に存在すると仮定する。
PD である$\M \in \cS$ もグラフ計量行列と呼ばれる。
文献で一般的な低ランク計量行列とは異なり、$\cS$ は特別な場合として重要な対角行列を含む。
完全固有分解を回避し、高速な計量行列最適化を可能にするための重要な定理は gershgorin disc perfect alignment (gdpa) である: $\m \in \cs$ と対角行列 $\s$, ここで $s_{ii} = 1/v_i$ と $\v$ は $\m$'s first eigenvector であるので、gershgorin disc left-ends of similarity transform $\b = \s \m \s^{-1}$ は最小の固有値 $\lambda_{\min}$ で完全に整列する。
この定理を用いることで、計量学習問題におけるPDコーン制約を反復毎の最も厳密な線形制約に置き換え、Frank-Wolfe法による対角線/対角線/対角線の項の交互最適化を効率的に線形プログラムとして解ける。
我々は,$\m$のエントリが順次最適化されるので,局所最適ブロック前条件共役勾配 (lobpcg) を用いて$\v$を更新する。
実験により, グラフ距離の最適化はコーン投影方式よりもはるかに高速であり, 競合する二値分類性能が得られた。
関連論文リスト
- Solving Dense Linear Systems Faster than via Preconditioning [15.781447266000159]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳(メタデータ) (2023-12-14T12:53:34Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳(メタデータ) (2023-10-27T16:54:29Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳(メタデータ) (2023-06-16T17:00:51Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳(メタデータ) (2021-02-15T08:16:51Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-10-25T18:12:50Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳(メタデータ) (2020-05-22T16:55:01Z) - Graph Metric Learning via Gershgorin Disc Alignment [46.145969174332485]
そこで,MathcalS$ の目的 $min_textbfM は計量行列 $textbfM$ の凸微分可能な関数である。
Gershgorinディスクは、最初のeigenvector $textbfv$ of $textbfM$を使って完全に整列可能であることを証明します。
実験により, グラフ距離行列の計算効率は, 競合手法を用いて学習した指標よりも優れていた。
論文 参考訳(メタデータ) (2020-01-28T17:44:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。