We study least-squares trace regression when the parameter is the sum of a $r$-low-rank and a $s$-sparse matrices and a fraction $\epsilon$ of the labels is corrupted. For subgaussian distributions, we highlight three design properties. The first, termed $\PP$, handles additive decomposition and follows from a product process inequality. The second, termed $\IP$, handles both label contamination and additive decomposition. It follows from Chevet's inequality. The third, termed $\MP$, handles the interaction between the design and featured-dependent noise. It follows from a multiplier process inequality. Jointly, these properties entail the near-optimality of a tractable estimator with respect to the effective dimensions $d_{\eff,r}$ and $d_{\eff,s}$ for the low-rank and sparse components, $\epsilon$ and the failure probability $\delta$. This rate has the form $$ \mathsf{r}(n,d_{\eff,r}) + \mathsf{r}(n,d_{\eff,s}) + \sqrt{(1+\log(1/\delta))/n} + \epsilon\log(1/\epsilon). $$ Here, $\mathsf{r}(n,d_{\eff,r})+\mathsf{r}(n,d_{\eff,s})$ is the optimal uncontaminated rate, independent of $\delta$. Our estimator is adaptive to $(s,r,\epsilon,\delta)$ and, for fixed absolute constant $c>0$, it attains the mentioned rate with probability $1-\delta$ uniformly over all $\delta\ge\exp(-cn)$. Disconsidering matrix decomposition, our analysis also entails optimal bounds for a robust estimator adapted to the noise variance. Finally, we consider robust matrix completion. We highlight a new property for this problem: one can robustly and optimally estimate the incomplete matrix regardless of the \emph{magnitude of the corruption}. Our estimators are based on ``sorted'' versions of Huber's loss. We present simulations matching the theory. In particular, it reveals the superiority of ``sorted'' Huber loss over the classical Huber's loss.
相關內容
We study the Weyl formula for the asymptotic number of eigenvalues of the Laplace-Beltrami operator with Dirichlet boundary condition on a Riemannian manifold in the context of geometric flows. Assuming the eigenvalues to be the energies of some associated statistical system, we show that geometric flows are directly related with the direction of increasing entropy chosen. For a closed Riemannian manifold we obtain a volume preserving flow of geometry being equivalent to the increment of Gibbs entropy function derived from the spectrum of Laplace-Beltrami operator. Resemblance with Arnowitt, Deser, and Misner (ADM) formalism of gravity is also noted by considering open Riemannian manifolds, directly equating the geometric flow parameter and the direction of increasing entropy as time direction.
This paper develops some theory of the matrix Dyson equation (MDE) for correlated linearizations and uses it to solve a problem on asymptotic deterministic equivalent for the test error in random features regression. The theory developed for the correlated MDE includes existence-uniqueness, spectral support bounds, and stability properties of the MDE. This theory is new for constructing deterministic equivalents for pseudoresolvents of a class of correlated linear pencils. In the application, this theory is used to give a deterministic equivalent of the test error in random features ridge regression, in a proportional scaling regime, wherein we have conditioned on both training and test datasets.
In the study of the brain, there is a hypothesis that sparse coding is realized in information representation of external stimuli, which is experimentally confirmed for visual stimulus recently. However, unlike the specific functional region in the brain, sparse coding in information processing in the whole brain has not been clarified sufficiently. In this study, we investigate the validity of sparse coding in the whole human brain by applying various matrix factorization methods to functional magnetic resonance imaging data of neural activities in the whole human brain. The result suggests sparse coding hypothesis in information representation in the whole human brain, because extracted features from sparse MF method, SparsePCA or MOD under high sparsity setting, or approximate sparse MF method, FastICA, can classify external visual stimuli more accurately than non-sparse MF method or sparse MF method under low sparsity setting.
Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor's quantum factorization algorithm requires significant resources scaling linearly with the number size; taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr's lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.
This manuscript is devoted to investigating the conservation laws of incompressible Navier-Stokes equations(NSEs), written in the energy-momentum-angular momentum conserving(EMAC) formulation, after being linearized by the two-level methods. With appropriate correction steps(e.g., Stoke/Newton corrections), we show that the two-level methods, discretized from EMAC NSEs, could preserve momentum, angular momentum, and asymptotically preserve energy. Error estimates and (asymptotic) conservative properties are analyzed and obtained, and numerical experiments are conducted to validate the theoretical results, mainly confirming that the two-level linearized methods indeed possess the property of (almost) retainability on conservation laws. Moreover, experimental error estimates and optimal convergence rates of two newly defined types of pressure approximation in EMAC NSEs are also obtained.
Sequences of parametrized Lyapunov equations can be encountered in many application settings. Moreover, solutions of such equations are often intermediate steps of an overall procedure whose main goal is the computation of quantities of the form $f(X)$ where $X$ denotes the solution of a Lyapunov equation. We are interested in addressing problems where the parameter dependency of the coefficient matrix is encoded as a low-rank modification to a \emph{seed}, fixed matrix. We propose two novel numerical procedures that fully exploit such a common structure. The first one builds upon recycling Krylov techniques, and it is well-suited for small dimensional problems as it makes use of dense numerical linear algebra tools. The second algorithm can instead address large-scale problems by relying on state-of-the-art projection techniques based on the extended Krylov subspace. We test the new algorithms on several problems arising in the study of damped vibrational systems and the analyses of output synchronization problems for multi-agent systems. Our results show that the algorithms we propose are superior to state-of-the-art techniques as they are able to remarkably speed up the computation of accurate solutions.
We propose a general optimization-based framework for computing differentially private M-estimators and a new method for constructing differentially private confidence regions. Firstly, we show that robust statistics can be used in conjunction with noisy gradient descent or noisy Newton methods in order to obtain optimal private estimators with global linear or quadratic convergence, respectively. We establish local and global convergence guarantees, under both local strong convexity and self-concordance, showing that our private estimators converge with high probability to a small neighborhood of the non-private M-estimators. Secondly, we tackle the problem of parametric inference by constructing differentially private estimators of the asymptotic variance of our private M-estimators. This naturally leads to approximate pivotal statistics for constructing confidence regions and conducting hypothesis testing. We demonstrate the effectiveness of a bias correction that leads to enhanced small-sample empirical performance in simulations. We illustrate the benefits of our methods in several numerical examples.
Stochastic differential equation (SDE in short) solvers find numerous applications across various fields. However, in practical simulations, we usually resort to using Ito-Taylor series-based methods like the Euler-Maruyama method. These methods often suffer from the limitation of fixed time scales and recalculations for different Brownian motions, which lead to computational inefficiency, especially in generative and sampling models. To address these issues, we propose a novel approach: learning a mapping between the solution of SDE and corresponding Brownian motion. This mapping exhibits versatility across different scales and requires minimal paths for training. Specifically, we employ the DeepONet method to learn a nonlinear mapping. And we also assess the efficiency of this method through simulations conducted at varying time scales. Additionally, we evaluate its generalization performance to verify its good versatility in different scenarios.
We propose a new method to construct a stationary process and random field with a given convex, decreasing covariance function and any one-dimensional marginal distribution. The result is a new class of stationary processes and random fields. The construction method provides a simple, unified approach for a wide range of covariance functions and any one-dimensional marginal distributions, and it allows a new way to model dependence structures in a stationary process/random field as its dependence structure is induced by the correlation structure of a few disjoint sets in the support set of the marginal distribution.
We describe an efficient method for the approximation of functions using radial basis functions (RBFs), and extend this to a solver for boundary value problems on irregular domains. The method is based on RBFs with centers on a regular grid defined on a bounding box, with some of the centers outside the computational domain. The equation is discretized using collocation with oversampling, with collocation points inside the domain only, resulting in a rectangular linear system to be solved in a least squares sense. The goal of this paper is the efficient solution of that rectangular system. We show that the least squares problem splits into a regular part, which can be expedited with the FFT, and a low rank perturbation, which is treated separately with a direct solver. The rank of the perturbation is influenced by the irregular shape of the domain and by the weak enforcement of boundary conditions at points along the boundary. The solver extends the AZ algorithm which was previously proposed for function approximation involving frames and other overcomplete sets. The solver has near optimal log-linear complexity for univariate problems, and loses optimality for higher-dimensional problems but remains faster than a direct solver.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191