检索结果-内蒙古大学图书馆

Asymptotic Analysis of Sampling Estimators for randomized numerical linear algebra Algorithms

JOURNAL OF MACHINE LEARNING RESEARCH 2022年 23卷

作者： Ma, Ping Chen, Yongkai Zhang, Xinlian Xing, Xin Ma, Jingyi Mahoney, Michael W. Univ Georgia Dept Stat Athens GA 30602 USA Univ Calif San Diego Dept Family Med & Publ Hlth La Jolla CA 92093 USA Virginia Tech Dept Stat Blacksburg VA USA Cent Univ Finance & Econ Dept Stat & Math Beijing Peoples R China Univ Calif Berkeley Int Comp Sci Inst Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

The statistical analysis of randomized numerical linear algebra (RandNLA) algorithms within the past few years has mostly focused on their performance as point estimators. However, this is insufficient for conducting statistical inference, e.g., constructing confidence intervals and hypothesis testing, since the distribution of the estimator is lacking. In this article, we develop an asymptotic analysis to derive the distribution of RandNLA sampling estimators for the least-squares problem. In particular, we derive the asymptotic distribution of a general sampling estimator with arbitrary sampling probabilities in a fixed design setting. The analysis is conducted in two complementary settings, i.e., when the objective of interest is to approximate the full sample estimator, and when it is to infer the underlying ground truth model parameters. For each setting, we show that the sampling estimator is asymptotically normally distributed under mild regularity conditions. Moreover, the sampling estimator is asymptotically unbiased in both settings. Based on our asymptotic analysis, we use two criteria, the Asymptotic Mean Squared Error (AMSE) and the Expected Asymptotic Mean Squared Error (EAMSE), to identify optimal sampling probabilities. Several of these optimal sampling probability distributions are new to the literature, e.g., the root leverage sampling estimator and the predictor length sampling estimator. Our theoretical results clarify the role of leverage in the sampling process, and our empirical results demonstrate improvements over existing methods.

关键词： least squares randomized numerical linear algebra leverage scores asymp-totic distribution mean squared error asymptotic mean squared error

来源：评论

学校读者我要写书评

暂无评论

Asymptotic analysis of sampling estimators for randomized numerical linear algebra algorithms

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2022年第1期23卷 7970-8014页

作者： Ping Ma Yongkai Chen Xinlian Zhang Xin Xing Jingyi Ma Michael W. Mahoney Department of Statistics University of Georgia Department of Family Medicine and Public Health University of California at San Diego Department of Statistics Virginia Tech Department of Statistics and Mathematics Central University of Finance and Economics International Computer Science Institute and Department of Statistics University of California at Berkeley

关键词： least squares randomized numerical linear algebra leverage scores asymptotic distribution mean squared error asymptotic mean squared error

来源：评论

学校读者我要写书评

暂无评论

Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2025年 26卷

作者： Na, Sen Mahoney, Michael W. Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA Univ Calif Berkeley ICSI Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

We consider online statistical inference of constrained stochastic nonlinear optimization problems. We apply the Stochastic Sequential Quadratic Programming (StoSQP) method to solve these problems, which can be regarded as applying second-order Newton's method to the Karush-Kuhn-Tucker (KKT) conditions. In each iteration, the StoSQP method computes the Newton direction by solving a quadratic program, and then selects a proper adaptive stepsize alphat to update the primal-dual iterate. To reduce dominant computational cost of the method, we inexactly solve the quadratic program in each iteration by employing an iterative sketching solver. Notably, the approximation error of the sketching solver need not vanish as iterations proceed, meaning that the per-iteration computational cost does not blow up. For the above StoSQP method, we show that under mild assumptions, the rescaled primal-dual sequence 1/\/alphat (xt x*, lambda t lambda*) converges to a mean-zero Gaussian distribution with a nontrivial covariance matrix depending on the underlying sketching distribution. To perform inference in practice, we also analyze a plug-in covariance matrix estimator. We illustrate the asymptotic normality result of the method both on benchmark nonlinear problems in CUTEst test set and on linearly/nonlinearly constrained regression problems.

关键词： constrained stochastic optimization Newton sketching online inference un- certainty quantification randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

randomized JOINT DIAGONALIZATION OF SYMMETRIC MATRICES

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2024年第1期45卷 661-684页

作者： He, Haoze Kressner, Daniel Ecole Polytech Fed Lausanne EPFL Inst Math CH-1015 Lausanne Switzerland

Given a family of nearly commuting symmetric matrices, we consider the task of computing an orthogonal matrix that nearly diagonalizes every matrix in the family. In this paper, we propose and analyze randomized joint diagonalization (RJD) for performing this task. RJD applies a standard eigenvalue solver to random linear combinations of the matrices. Unlike existing optimization-based methods, RJD is simple to implement and leverages existing high-quality linear algebra software packages. Our main novel contribution is to prove robust recovery: Given a family that is & varepsilon;-near to a commuting family, RJD jointly diagonalizes this family, with high probability, up to an error of norm O(& varepsilon;). We also discuss how the algorithm can be further improved by deflation techniques and demonstrate its state-of-the-art performance by numerical experiments with synthetic and real-world data.

关键词： approximate joint diagonalization randomized numerical linear algebra matrix analysis independent component analysis

来源：评论

学校读者我要写书评

暂无评论

Data-driven model selections of second-order particle dynamics via integrating Gaussian processes with low-dimensional interacting structures

引用

PHYSICA D-NONlinear PHENOMENA 2024年 461卷

作者： Feng, Jinchao Kulick, Charles Tang, Sui Great Bay Univ Sch Sci Dongguan Guangdong Peoples R China Univ Calif Santa Barbara Dept Math Isla Vista CA 93106 USA

In this paper, we focus on the data -driven discovery of a general second -order particle -based model that contains many state-of-the-art models for modeling the aggregation and collective behavior of interacting agents of similar size and body type. This model takes the form of a high -dimensional system of ordinary differential equations parameterized by two interaction kernels that appraise the alignment of positions and velocities. We propose a Gaussian Process -based approach to this problem, where the unknown model parameters are marginalized by using two independent Gaussian Process (GP) priors on latent interaction kernels constrained to dynamics and observational data. This results in a nonparametric model for interacting dynamical systems that accounts for uncertainty quantification. We also show that our estimators can be efficiently derived through the use of preconditioned techniques, ensuring scalability. Moreover, we perform a theoretical analysis to interpret the methodology and investigate the conditions under which the kernels can be recovered. We demonstrate the effectiveness of the proposed approach on various prototype systems, including the selection of the order of the systems and the types of interactions. In particular, we present applications to modeling two real -world fish motion datasets that display flocking and milling patterns up to 248 dimensions. Despite the use of small datasets, the GP -based approach learns an effective representation of the nonlinear dynamics in these spaces and outperforms competitor methods.

关键词： Particle-based system Data-driven methods Gaussian process Kernel ridge regression Inverse problems randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

On the Noise Sensitivity of the randomized SVD

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第5期71卷 3802-3834页

作者： Romanov, Elad Stanford Univ Dept Stat Stanford CA 94305 USA

The randomized singular value decomposition (R-SVD) is a popular sketching-based algorithm for efficiently computing the partial SVD of a large matrix. When the matrix is low-rank, the R-SVD produces its partial SVD exactly;but when the rank is large, it only yields an approximation. Motivated by applications in data science and principal component analysis (PCA), we analyze the R-SVD under a low-rank signal plus noise measurement model;specifically, when its input is a spiked random matrix. The singular values produced by the R-SVD are shown to exhibit a BBP-like phase transition: when the SNR exceeds a certain detectability threshold, that depends on the dimension reduction factor, the largest singular value is an outlier;below the threshold, no outlier emerges from the bulk of singular values. We further compute asymptotic formulas for the overlap between the ground truth signal singular vectors and the approximations produced by the R-SVD. Dimensionality reduction has the adverse affect of amplifying the noise in a highly nonlinear manner. Our results demonstrate the statistical advantage of the R-SVD-in both signal detection and estimation-over more naive sketched PCA variants;the advantage is especially dramatic when the sketching dimension is small. Our analysis is asymptotically exact, and substantially more fine-grained than existing operator-norm error bounds for the R-SVD, which largely fail to give meaningful error estimates in the moderate SNR regime. It applies for a broad family of sketching matrices previously considered in the literature, including Gaussian i.i.d. sketches, random projections, and the sub-sampled Hadamard transform, among others. Lastly, we derive optimal singular value shrinkers for singular values and vectors obtained through the R-SVD, designed optimally for both matrix denoising and covariance estimation. For the second task, the performance gains offered by the new shrinker may be particularly significant, especially so when th

关键词： Vectors Principal component analysis Signal to noise ratio Matrix decomposition Noise measurement Noise reduction Dimensionality reduction Dimension reduction sketching principal component analysis randomized numerical linear algebra random matrix theory

来源：评论

学校读者我要写书评

暂无评论

SURROGATE-BASED AUTOTUNING FOR randomized SKETCHING ALGORITHMS IN REGRESSION PROBLEMS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2025年第2期46卷 1247-1279页

作者： Cho, Younghyun Demmel, James Derezin, Michal Li, Haoyun Luo, Hengrui Mahoney, Michael Murray, Riley Univ Calif Berkeley Berkeley CA 94720 USA Santa Clara Univ Santa Clara CA 95053 USA Univ Michigan Ann Arbor MI 48109 USA Georgia Inst Technol Atlanta GA 30332 USA Lawrence Berkeley Natl Lab Berkeley CA 94720 USA Rice Univ Houston TX 77005 USA Univ Calif Berkeley Lawrence Berkeley Natl Lab Berkeley CA 94720 USA Int Comp Sci Inst Berkeley CA USA Sandia Natl Labs Livermore CA 94550 USA

Algorithms from randomized numerical linear algebra (RandNLA) are known to be effective in handling high-dimensional computational problems, providing high-quality empirical performance as well as strong probabilistic guarantees. However, their practical application is complicated by the fact that the user needs to set various algorithm-specific tuning parameters which are different from those used in traditional NLA. This paper demonstrates how a surrogate-based auto-tuning approach can be used to address fundamental problems of parameter selection in RandNLA algorithms. In particular, we provide a detailed investigation of surrogate-based autotuning for sketch-and-precondition (SAP)--based randomized least squares methods, which have been one of the great success stories in modern RandNLA. Empirical results show that our surrogate-based autotuning approach can achieve near-optimal performance with much less tuning cost than a random search (up to about 7.6x fewer trials of different parameter configurations). Moreover, while our experiments focus on least squares, our results demonstrate a general-purpose autotuning pipeline applicable to any kind of RandNLA algorithm.

关键词： randomized numerical linear algebra sketching algorithm autotuning least squares problem Bayesian optimization

来源：评论

学校读者我要写书评

暂无评论

Gradient Coding With Iterative Block Leverage Score Sampling

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第9期70卷 6639-6664页

作者： Charalambides, Neophytos Pilanci, Mert Hero, Alfred O. Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Univ Calif San Diego Dept Comp Sci & Engn San Diego CA 92093 USA Univ Calif San Diego Halicioglu Data Sci Inst San Diego CA 92093 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this paper, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized $\ell _randomized$ -subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid $\ell _randomized$ -subspace embedding, and that our resulting approximation converges to the optimal solution.

关键词： Servers Approximation algorithms Task analysis Encoding linear algebra Accuracy Monte Carlo methods Low-rank approximations least-squares regression randomized algorithms randomized numerical linear algebra coded computing stragglers erasure-coding replication-coding

来源：评论

学校读者我要写书评

暂无评论

randomized methods for computing joint eigenvalues, with applications to multiparameter eigenvalue problems and root finding

引用

numerical ALGORITHMS 2024年 1-32页

作者： He, Haoze Kressner, Daniel Plestenjak, Bor Ecole Polytech Fed Lausanne EPFL Inst Math CH-1015 Lausanne Switzerland Univ Ljubljana Fac Math & Phys Jadranska 19 Ljubljana 1000 Slovenia Inst Math Phys & Mech Jadranska 19 Ljubljana 1000 Slovenia

It is well known that a family of nxn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n}\times {n}$$\end{document} commuting matrices can be simultaneously triangularized by a unitary similarity transformation. The diagonal entries of the triangular matrices define the n joint eigenvalues of the family. In this work, we consider the task of numerically computing approximations to such joint eigenvalues for a family of (nearly) commuting matrices. This task arises, for example, in solvers for multiparameter eigenvalue problems and systems of multivariate polynomials, which are our main motivations. We propose and analyze a simple approach that computes eigenvalues as one-sided or two-sided Rayleigh quotients from eigenvectors of a random linear combination of the matrices in the family. We provide some analysis and numerous numerical examples, showing that such randomized approaches can compute semisimple joint eigenvalues accurately and lead to improved performance of existing solvers.

关键词： Commuting matrices Joint eigenvalue Rayleigh quotient randomized numerical linear algebra Multiparameter eigenvalue problem Polynomial system

来源：评论

学校读者我要写书评

暂无评论

randomized LOW-RANK APPROXIMATION OF MONOTONE MATRIX FUNCTIONS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2023年第2期44卷 894-918页

作者： Persson, David Kressner, Daniel EPF Lausanne Inst Math CH-1015 Lausanne Switzerland

This work is concerned with computing low-rank approximations of a matrix function f(A) for a large symmetric positive semidefinite matrix A, a task that arises in, e.g., statistical learning and inverse problems. The application of popular randomized methods, such as the randomized singular value decomposition or the Nystrom approximation, to f(A) requires multiplying f(A) with a few random vectors. A significant disadvantage of such an approach, matrix-vector products with f(A) are considerably more expensive than matrix-vector products with A, even when carried out only approximately via, e.g., the Lanczos method. In this work, we present and analyze funNystrom, a simple and inexpensive method that constructs a low-rank approximation of f(A) directly from a Nystrom approximation of A, completely bypassing the need for matrix-vector products with f(A). It is sensible to use funNystrom whenever f is monotone and satisfies f(0) = 0. Under the stronger assumption that f is operator monotone, which includes the matrix square root A(1/2) and the matrix logarithm log(I + A), we derive probabilistic bounds for the error in the Frobenius, nuclear, and operator norms. These bounds confirm the numerical observation that funNystrom tends to return an approximation that compares well with the best low-rank approximation of f(A). Furthermore, compared to existing methods, funNystrom requires significantly fewer matrix-vector products with A to obtain a low-rank approximation of f(A), without sacrificing accuracy or reliability. Our method is also of interest when estimating quantities associated with f(A), such as the trace or the diagonal entries of f(A). In particular, we propose and analyze funNystrom++, a combination of funNystrom with the recently developed Hutch++ method for trace estimation.

关键词： low-rank approximation randomized numerical linear algebra matrix functions

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：