論文の概要: Mild Over-Parameterization Benefits Asymmetric Tensor PCA
- arxiv url: http://arxiv.org/abs/2604.10208v1
- Date: Sat, 11 Apr 2026 13:34:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-14 20:13:15.903033
- Title: Mild Over-Parameterization Benefits Asymmetric Tensor PCA
- Title（参考訳）: 非対称テンソルPCAの過度パラメータ化効果
- Authors: Shihong Ding, Weicheng Lin, Cong Fang,
- Abstract要約: 非対称PCA(ATPCA)は、サンプル複雑性、計算、メモリ間のトレードオフを研究するための原型モデルである。
私たちは$overlinek geq 4$が偶数であるような設定にフォーカスし、限られたメモリ予算の下で降下アルゴリズムを検討する。
- 参考スコア（独自算出の注目度）: 12.923414933046574
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Asymmetric Tensor PCA (ATPCA) is a prototypical model for studying the trade-offs between sample complexity, computation, and memory. Existing algorithms for this problem typically require at least $d^{\left\lceil\overline{k}/2\right\rceil}$ state memory cost to recover the signal, where $d$ is the vector dimension and $\overline{k}$ is the tensor order. We focus on the setting where $\overline{k} \geq 4$ is even and consider (stochastic) gradient descent-based algorithms under a limited memory budget, which permits only mild over-parameterization of the model. We propose a matrix-parameterized method (in $d^{2}$ state memory cost) using a novel three-phase alternating-update algorithm to address the problem and demonstrate how mild over-parameterization facilitates learning in two key aspects: (i) it improves sample efficiency, allowing our method to achieve \emph{near-optimal} $d^{\overline{k}-2}$ sample complexity in our limited memory setting; and (ii) it enhances adaptivity to problem structure, a previously unrecognized phenomenon, where the required sample size naturally decreases as consecutive vectors become more aligned, and in the symmetric limit attains $d^{\overline{k}/2}$, matching the \emph{best} known polynomial-time complexity. To our knowledge, this is the \emph{first} tractable algorithm for ATPCA with $d^{\overline{k}}$-independent memory costs.
- Abstract（参考訳）: 非対称テンソルPCA(ATPCA)は、サンプル複雑性、計算、メモリ間のトレードオフを研究するための原型モデルである。
既存のアルゴリズムでは、信号の回復には少なくとも$d^{\left\lceil\overline{k}/2\right\rceil}$状態メモリコストが必要であり、$d$はベクトル次元、$\overline{k}$はテンソルオーダーである。
我々は、$\overline{k} \geq 4$が偶数であるような設定に焦点を合わせ、限られたメモリ予算の下で勾配勾配に基づくアルゴリズムを考える。
本稿では,新しい3相交互更新アルゴリズムを用いて,行列パラメータ化手法($d^{2}$状態メモリコスト)を提案する。
(i)サンプル効率を向上し、限られたメモリ設定におけるサンプルの複雑さを達成できるようにします。
(II)問題構造への適応性、つまり、必要となるサンプルサイズが連続ベクトルがより整列化するにつれて自然に減少し、対称極限で$d^{\overline{k}/2}$に達し、既知の多項式時間複雑性と一致する。
我々の知る限り、これは$d^{\overline{k}}$-independent memory costでATPCAの抽出可能アルゴリズムである。
関連論文リスト
- Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits [0.0]
我々は、$n$-qubit 回路をシミュレートする2つの新しいアルゴリズムを提示する。
提案アルゴリズムは単純で、線形メモリしか必要とせず、自明に並列であり、ZX-ダイアグラムの単純化ルーチンとうまく相互作用する。
論文 参考訳（メタデータ） (2026-03-06T15:27:23Z) - Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。
パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
論文 参考訳（メタデータ） (2025-10-06T10:53:37Z) - Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.422662003404586]
雑音行列検出問題に対する交互事前条件勾配降下法(APGD)を提案する。
APGDは、既存の代替法と比較して、最も早く収束し、最も低い計算時間を達成する。
論文 参考訳（メタデータ） (2025-02-01T15:44:39Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
論文 参考訳（メタデータ） (2023-03-03T18:03:49Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。