軽度な過剰パラメータ化は非対称テンソルPCAに有益である

概要: 非対称テンソルPCA（ATPCA）は、サンプル複雑度、計算、メモリの間のトレードオフを研究するための典型的なモデルである。 この問題に対する既存のアルゴリズムは通常、信号を復元するために少なくとも d^{\left\lceil\overline{k}/2\right\rceil} の状態メモリコストを必要とする。ここで d はベクトル次元、 \overline{k} はテンソル次数である。 本研究では、 \overline{k} \geq 4 が偶数である状況に焦点を当て、限られたメモリ予算のもとで（確率的）勾配降下法ベースのアルゴリズムを考える。これにより、モデルの過パラメータ化はわずかに許されるにとどまる。 我々は、状態メモリコスト d^{2} の行列パラメータ化手法を提案する。これは、この問題に対処するための新しい三相の交互更新アルゴリズムを用いるものであり、わずかな過パラメータ化が学習を促進する様子を、2つの重要な側面で示す：（i）サンプル効率が向上し、我々の限られたメモリ設定において \emph{ほぼ最適な} d^{\overline{k}-2} のサンプル複雑度を達成できること；そして（ii）問題構造への適応性が高まること。これは以前は認識されていなかった現象であり、連続するベクトルがより整合（アライン）していくにつれて必要なサンプルサイズが自然に減少し、対称極限では d^{\overline{k}/2} に到達し、 \emph{最良}として知られる多項式時間計算量と一致する。 我々の知る限り、これは、メモリコストが d^{\overline{k}} に依存しない（独立な）ATPCAに対する \emph{最初の} 実行可能（tractable）なアルゴリズムである。