Mild Over-Parameterization Benefits Asymmetric Tensor PCA

• URL: http://arxiv.org/abs/2604.10208v1
• Date: Sat, 11 Apr 2026 13:34:48 GMT
• Title: Mild Over-Parameterization Benefits Asymmetric Tensor PCA
• Abstract summary: Asymmetric PCA (ATPCA) is prototypical model for studying the trade-offs between sample complexity, computation, and memory.<n>We focus on the setting where $overlinek geq 4$ is even and consider descent-based algorithms under a limited memory budget.
• Score: 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.

Related papers

• Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model [12.775038922010452]
  Modern machine learning models are optimized by optimizing high-dimensional non-dimensional empirical risk functions.<n>Within a simple supervised learning setting, we develop a precise picture of the empirical risk landscape.<n>We propose an approximate incremental message passing (ImAMP) algorithm and precisely characterize it.
  arXiv  Detail & Related papers  (2026-06-26T19:57:08Z)
• Sequential Minimal Optimization for $\varepsilon$-SVR with MAPE Loss and Sample-Dependent Box Constraints [0.0]
  We derive a Sequential Minimal Optimization (SMO) algorithm for the quadratic dual problem arising from $varepsilon$-SVRciteVapnik1995, Drucker1997, Smola2004 modified to minimize the Mean Absolute Percentage Error (MAPE)citeMakridakis1993, Hyndman2006.<n>An implementation is available in the open-source textttpsvr R packageciteBenavidesHerrera2026Rpsvr.
  arXiv  Detail & Related papers  (2026-05-02T13:51:46Z)
• Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits [0.0]
  We present two new algorithms to simulate an $n$-qubit circuit $C$.<n>The proposed algorithms are simple, only require a linear amount of memory, are trivially parallel, and interact nicely with ZX-diagram simplification routines.
  arXiv  Detail & Related papers  (2026-03-06T15:27:23Z)
• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  Existing approaches for the Extended Adversarial (SEA) model require prior knowledge of problem-specific parameters, such as the diameter of the domain $D$ and the Lipschitz constant of the loss functions $G$.<n>We develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters.
  arXiv  Detail & Related papers  (2025-10-06T10:53:37Z)
• Efficient Network Automatic Relevance Determination [30.611086842690426]
  Network Automatic Relevance Determination (NARD) is an extension of ARD for linearly probabilistic models.<n>NARD simultaneously model sparse relationships between inputs $X in mathbb Rd times N$ and outputs $Y in mathbb Rm times N$.
  arXiv  Detail & Related papers  (2025-06-14T05:20:25Z)
• Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.422662003404586]
  We propose an alternating preconditioned gradient descent (APGD) algorithm for noisy matrix sensing problems.<n>APGD consistently achieves the fastest convergence and the lowest computation time compared to the existing alternatives.
  arXiv  Detail & Related papers  (2025-02-01T15:44:39Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
  We show that the problem suffers from a $frackSNR2$-to-$frack2SNR2$ statistical-to-computational gap. We also analyze a simple thresholding algorithm which, outside of the narrow regime where the problem is hard, solves the associated mixed regression detection problem.
  arXiv  Detail & Related papers  (2023-03-03T18:03:49Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
  We study the shortest path (SSP) problem in reinforcement learning with linear function approximation, where the transition kernel is represented as a linear mixture of unknown models. We propose a novel algorithm for learning the linear mixture SSP, which can attain a $tilde O(d B_star1.5sqrtK/c_min)$ regret.
  arXiv  Detail & Related papers  (2021-10-25T08:34:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.