Sharp analysis of power iteration for tensor PCA, improving convergence and stopping criteria.
problem Analyzing the power iteration algorithm for tensor PCA to improve convergence and stopping criteria.
method Sharp bounds on the number of iterations, revealing a smaller algorithmic threshold, proposing a stopping criterion.
result Sharp bounds on the number of iterations required for power method to converge, revealing a smaller algorithmic threshold than previously conjectured.
Paper refutes conjecture on tensor power iteration convergence in overcomplete models.
problem Understanding convergence of tensor power iteration in overcomplete random tensors.
method Analysis of tensor power iteration dynamics from random initialization.
result Polynomially many steps are necessary for convergence, refutes logarithmic conjecture.
New method explains GNNs using power iteration clustering.
problem Mysterious mechanism of message passing in GNNs.
method Subspace power iteration clustering (SPIC) models.
result Message passing in GNNs can be understood through power iteration.
Power iteration has been generalized to solve many interesting problems in machine learning and statistics. Despite its striking success, theoretical understanding of when and how such an algorithm enjoys good convergence property is limited. In this work, we introduce a new class of optimization problems called scale …
Fast algorithm recovers principal eigenvector from noisy matrices.
problem Recovering the first principal eigenvector from noisy positive semidefinite matrices.
method Cone projected power iteration algorithm.
result Achieves polynomial time complexity and small error for certain convex cones.
We present a novel analysis of the dynamics of tensor power iterations in the overcomplete regime where the tensor CP rank is larger than the input dimension. Finding the CP decomposition of an overcomplete tensor is NP-hard in general. We consider the case where the tensor components are randomly drawn, and show that …
ParPIC clusters directed graphs using random walks and diffusion operators.
problem Challenges in vertex-level clustering for directed graphs due to edge directionality.
method Parametrized Power-Iteration Clustering (ParPIC) based on reversible random walks and diffusion operators.
result ParPIC achieves competitive clustering accuracy with improved scalability compared to spectral and teleportation-based methods.
Principal component analysis (PCA) is one of the most powerful tools in machine learning. The simplest method for PCA, the power iteration, requires O(1/Δ) full-data passes to recover the principal component of a matrix with eigen-gap Δ. Lanczos, a significantly more complex method, achieves an accelerated…
Study efficient power iteration for tensor models, proving convergence under specific conditions.
problem Simultaneous alternating power iteration for fixed-order asymmetric rank-one spiked tensor models.
method Finite-iteration local theory, geometrically decaying transient, fixed-order multilinear noise event, warm-start mechanism.
result Convergence to the unique informative local fixed point under specific conditions.
Critical volatility triggers log-normal to power-law transitions in interconnected systems.
problem Understanding the transition from log-normal to power-law distributions in interconnected systems.
method Analyzing an infinite option-on-option chain model, deriving a critical volatility threshold.
result A critical volatility threshold of approximately 250.66% for unconditional cases, dropping to 125.3% with selective survival.
Study spectral learning for odeco tensors, addressing initialization bottlenecks.
problem Recovering orthogonally decomposable tensors under noise.
method Investigates perturbation bounds, non-convex optimization, and initialization strategies.
result Initialization is the main bottleneck for efficient algorithms.
Implicit models can match or exceed explicit models with more test-time compute.
problem Understanding the expressive power and scaling of implicit models.
method Nonparametric analysis of expressive power, mathematical characterization of implicit operators, and test-time scaling experiments.
result Implicit models can progressively express more complex mappings through iteration, matching a richer function class with test-time compute.
This dissertation advances scalable Gaussian processes using iterative methods and pathwise conditioning.
problem The classical Gaussian process formulation is not scalable for large datasets and modern hardware.
method Combining iterative methods and pathwise conditioning to improve scalability.
result Significantly reduced memory requirements and facilitated application to larger datasets.
QAOA matches classical tensor power iteration in spiked tensor model recovery.
problem Statistical estimation in spiked tensor model with computational gap.
method Analysis of QAOA performance on spiked tensor model.
result QAOA weak recovery threshold matches tensor power iteration.
Principal component analysis (PCA) is recognised as a quintessential data analysis technique when it comes to describing linear relationships between the features of a dataset. However, the well-known sensitivity of PCA to non-Gaussian samples and/or outliers often makes it unreliable in practice. To this end, a robust…
SMPI recovers tensor spikes from noisy data with improved performance.
problem Recovering tensor spikes corrupted by Gaussian noise.
method Selective Multiple Power Iterations (SMPI) with polynomial random initializations and symmetrized tensor power iterations.
result SMPI outperforms existing algorithms and approaches theoretical optimal recovery.
Novel algorithm for Markov decision processes using rank-one approximation.
problem Solving planning and learning problems of Markov decision processes.
method Policy iteration with rank-one approximation of transition probability matrix.
result The proposed algorithm consistently outperforms first-order algorithms and their accelerated versions.
Due to the surprisingly good representation power of complex distributions, neural network (NN) classifiers are widely used in many tasks which include natural language processing, computer vision and cyber security. In recent works, people noticed the existence of adversarial examples. These adversarial examples break…
Innovative neural networks reduce memory usage for efficient, accurate segmentation.
problem Efficiently segmenting large graphs with limited memory.
method Iterative neural networks with loops and multiple outputs.
result State-of-the-art semantic segmentation results on demanding datasets.
A new method improves convergence in low-rank approximation.
problem Efficiently solving large-scale numerical linear algebra problems.
method Error-Powered Sketched Inverse Iteration (EPSI) Method.
result Convergence rate improves at least linearly with sketch size.
In this paper a relation between iterated cyclings and iterated powers of elements in a Garside group is shown. This yields a characterization of elements in a Garside group having a rigid power, where 'rigid' means that the left normal form changes only in the obvious way under cycling and decycling. It is also shown …
This work connects diffusion models to power iteration, revealing how low frequencies emerge earlier.
problem Understanding the generation process of diffusion models and their relation to power iteration.
method Examined the linear case of diffusion models, connecting them to the spiked covariance model and power iteration.
result Linear diffusion models converge to the leading eigenvector, similar to power iteration.
Paper analyzes iterative learning for concept classes and learns half-spaces.
problem Learning concept classes efficiently with iterative learners.
method Analyzes various settings of iterative learning and provides a constructive algorithm for half-spaces.
result Constructive iterative algorithm for learning half-spaces from informant.
This paper analyzes how errors accumulate in PCA's deflation method.
problem Error accumulation in PCA's deflation method.
method Mathematical analysis of inexact Hotelling's deflation method in two scenarios.
result Characterization of error propagation in PCA's deflation method.
The paper proposes a method to identify power system oscillation modes using blind source separation.
problem Accurately identifying oscillation modes in power systems with renewable energy sources.
method A high-order blind source identification (HOBI) algorithm based on copula statistic combined with Hilbert transform and iteration procedure.
result The method can identify all oscillation modes and model order from a single channel of observation signals, outperforming state-of-the-art methods.
Looped transformers with LN converge to power method for principal component prediction.
problem Understanding how transformers learn algorithmic procedures.
method Study of principal component prediction with looped linear transformers and layer normalization.
result Gradient descent trains looped transformers with LN to implement the power method for principal component prediction.
New method improves DAG learning by using large coefficients for higher-order terms.
problem Recovering DAG structures from observational data is challenging due to combinatorial optimization.
method Proposes truncated matrix power iteration to approximate DAG constraints efficiently.
result Empirically outperforms previous methods by a factor of 3 or more in structural Hamming distance.
FedPower improves eigenspace estimation privacy in federated learning.
problem Privacy breaches and communication challenges in federated eigenspace estimation.
method FedPower uses a power method with local power iterations and global aggregation, weighted by OPT, and adds Gaussian noise for privacy.
result FedPower provides convergence bounds and demonstrates effectiveness in experiments.
We study distributed computing of the truncated singular value decomposition problem. We develop an algorithm that we call \texttt{LocalPower} for improving communication efficiency. Specifically, we uniformly partition the dataset among m nodes and alternate between multiple (precisely p) local power iterations an…
Researchers discover all affinely homogeneous models for surfaces in 4D space.
problem Identifying all affinely homogeneous models for surfaces in 4D space.
method Improved power series method of equivalence, capturing invariants at the origin, creating branches, and infinitesimalizing calculations.
result Find several inequivalent terminal branches yielding each to some nonempty moduli space of homogeneous models.
Algorithm recovers causal graphs in presence of latent confounders and selection bias.
problem Recovering causal graphs in the presence of latent confounders and selection bias.
method Iterative causal discovery (ICD) algorithm that relies on causal Markov and faithfulness assumptions.
result Sound and complete algorithm that recovers the equivalence class of the underlying causal graph.
We introduce a new spatial data structure for high dimensional data called the \emph{approximate principal direction tree} (APD tree) that adapts to the intrinsic dimension of the data. Our algorithm ensures vector-quantization accuracy similar to that of computationally-expensive PCA trees with similar time-complexity…
A novel method relaxes binary constraints to non-negative spheres for multi-matching and clustering.
problem Optimization problems over binary matrices with injectivity constraints.
method Non-negative spherical relaxation followed by conditional power iteration.
result Automatic adjustment of the continuous parameter related to universe size.
We propose a new method for robust PCA -- the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of low-rank matrices, and the set of sparse matrices; each projection is {\em non-convex…
The increasing importance of renewable energy, especially solar and wind power, has led to new forces in the formation of electricity prices. Hence, this paper introduces an econometric model for the hourly time series of electricity prices of the European Power Exchange (EPEX) which incorporates specific features like…
The paper develops AMP theory for sparse and robust regression with polynomial iterations.
problem Challenges in high-dimensional statistical estimation due to asymptotic theory breakdown.
method Non-asymptotic distributional theory of AMP for sparse and robust regression.
result First finite-sample non-asymptotic distributional theory of AMP for polynomial iterations.
Unified analysis for deterministic samplers in diffusion models.
problem Challenges in analyzing deterministic samplers for diffusion models.
method Unified convergence analysis framework.
result Achieved polynomial iteration complexity for DDIM-type samplers.
Paper examines the structure of stochastic gradients in deep learning.
problem Exploring the structure and heavy tails of stochastic gradients in deep learning.
method Conducted formal statistical tests on stochastic gradients and gradient noise.
result Stochastic gradients and gradient noise do not exhibit power-law heavy tails, but their covariance spectra do.
Algorithm recovers causal graphs from data with fewer tests.
problem Recovering causal graphs from observational data with latent confounders and selection bias.
method Iterative CI tests with increasing condition set sizes.
result Significantly fewer CI tests and condition sets compared to FCI.
Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in statistical learning of latent variable models and in data mining. In this paper, we propose fast and randomized tensor CP decomposition algorithms based on sketching. We build on the idea of count sketches, but introduce many novel ideas which are un…
Optimal trading strategy derived for nonlinear price impact models.
problem Optimal trading with nonlinear price impact induced by alpha signals.
method Variational approach, nonlinear Fredholm equation, iterative scheme.
result Existence and uniqueness of optimal trading strategy under monotonicity condition.
In this paper, wireless video transmission to multiple users under total transmission power and minimum required video quality constraints is studied. In order to provide the desired performance levels to the end-users in real-time video transmissions while using the energy resources efficiently, we assume that power c…
We consider the Principal Component Analysis problem for large tensors of arbitrary order k under a single-spike (or rank-one plus noise) model. On the one hand, we use information theory, and recent results in probability theory, to establish necessary and sufficient conditions under which the principal component ca…
New method minimizes robust density power-based divergences for general parametric densities.
problem Computational complexity of minimizing DPD for general parametric densities.
method Stochastic approach to minimize DPD for general parametric density models.
result Proposed method can be applied to minimize other density power-based γ-divergences.
SDP achieves optimal error in noisy phase synchronization.
problem Phase synchronization with noisy measurements.
method SDP relaxation of Maximum Likelihood Estimation (MLE).
result Achieves error bound of (1+o(1))2npσ2 under normalized squared ℓ2 loss, matching minimax lower bound. Graph neural networks (GNNs) are a powerful tool to learn representations on graphs by iteratively aggregating features from node neighbourhoods. Many variant models have been proposed, but there is limited understanding on both how to compare different architectures and how to construct GNNs systematically. Here, we p…
In this article we present an approach that enables joint wind speed and wind power forecasts for a wind park. We combine a multivariate seasonal time varying threshold autoregressive moving average (TVARMA) model with a power threshold generalized autoregressive conditional heteroscedastic (power-TGARCH) model. The mo…
While deep neural networks have proven to be a powerful tool for many recognition and classification tasks, their stability properties are still not well understood. In the past, image classifiers have been shown to be vulnerable to so-called adversarial attacks, which are created by additively perturbing the correctly…