An official website of the United States government
Matrix sketching is a powerful tool for reducing the size of large data matrices. Yet there are fundamental limitations to this size reduction when we want to recover an accurate estimator for a task such as least square regression. We show that these limitations can be circumvented in the distributed setting by designing sketching methods that minimize the bias of the estimator, rather than its error. In particular, we give a sparse sketching method running in optimal space and current matrix multiplication time, which recovers a nearly-unbiased least squares estimator using two passes over the data. This leads to new communication-efficient distributed averaging algorithms for least squares and related tasks, which directly improve on several prior approaches. Our key novelty is a new bias analysis for sketched least squares, giving a sharp characterization of its dependence on the sketch sparsity. The techniques include new higher moment restricted Bai-Silverstein inequalities, which are of independent interest to the non-asymptotic analysis of deterministic equivalents for random matrices that arise from sketching.
more »
« less
Concentration and moment inequalities for heavy-tailed random matrices
We prove Fuk-Nagaev and Rosenthal-type inequalities for the sums of indepen- dent random matrices, focusing on the situation when the norms of the matrices possess finite moments of only low orders. Our bounds depend on the “intrinsic” dimensional char- acteristics such as the effective rank, as opposed to the dimension of the ambient space. We illustrate the advantages of such results in several applications, including new moment inequalities for the sample covariance operators of heavy-tailed distributions. Moreover, we demonstrate that our techniques yield sharpened versions of the moment inequalities for empirical processes.
more »
« less
- Award ID(s):
- 2045068
- PAR ID:
- 10518734
- Publisher / Repository:
- arxiv.org
- Date Published:
- Journal Name:
- arXivorg
- ISSN:
- 2331-8422
- Subject(s) / Keyword(s):
- Fuk-Nagaev inequality Rosenthal’s inequality random matrix covariance estimation heavy tails.
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)For probabilistic programs, it is usually not possible to automatically derive exact information about their properties, such as the distribution of states at a given program point. Instead, one can attempt to derive approximations, such as upper bounds on tail probabilities. Such bounds can be obtained via concentration inequalities, which rely on the moments of a distribution, such as the expectation (the first raw moment) or the variance (the second central moment). Tail bounds obtained using central moments are often tighter than the ones obtained using raw moments, but automatically analyzing central moments is more challenging. This paper presents an analysis for probabilistic programs that automatically derives symbolic upper and lower bounds on variances, as well as higher central moments, of cost accumulators. To overcome the challenges of higher-moment analysis, it generalizes analyses for expectations with an algebraic abstraction that simultaneously analyzes different moments, utilizing relations between them. A key innovation is the notion of moment-polymorphic recursion, and a practical derivation system that handles recursive functions. The analysis has been implemented using a template-based technique that reduces the inference of polynomial bounds to linear programming. Experiments with our prototype central-moment analyzer show that, despite the analyzer’s upper/lower bounds on various quantities, it obtains tighter tail bounds than an existing system that uses only raw moments, such as expectations.more » « less
-
null (Ed.)This work provides quantitative tests of the extent of violation of two inequalities applicable to qubits coupled into Bell states, using IBM's publicly accessible quantum computers. Violations of the inequalities are well established. Our purpose is not to test the inequalities, but rather to determine how well quantum mechanical predictions can be reproduced on quantum computers, given their current fault rates. We present results for the spin projections of two entangled qubits, along three axes A , B , and C , with a fixed angle θ between A and B and a range of angles θ ′ between B and C . For any classical object that can be characterized by three observables with two possible values, inequalities govern relationships among the probabilities of outcomes for the observables, taken pairwise. From set theory, these inequalities must be satisfied by all such classical objects; but quantum systems may violate the inequalities. We have detected clear-cut violations of one inequality in runs on IBM's publicly accessible quantum computers. The Clauser–Horne–Shimony–Holt (CHSH) inequality governs a linear combination S of expectation values of products of spin projections, taken pairwise. Finding S > 2 rules out local, hidden variable theories for entangled quantum systems. We obtained values of S greater than 2 in our runs prior to error mitigation. To reduce the quantitative errors, we used a modification of the error-mitigation procedure in the IBM documentation. We prepared a pair of qubits in the state |00〉, found the probabilities to observe the states |00〉, |01〉, |10〉, and |11〉 in multiple runs, and used that information to construct the first column of an error matrix M . We repeated this procedure for states prepared as |01〉, |10〉, and |11〉 to construct the full matrix M , whose inverse is the filtering matrix. After applying filtering matrices to our averaged outcomes, we have found good quantitative agreement between the quantum computer output and the quantum mechanical predictions for the extent of violation of both inequalities as functions of θ ′.more » « less
-
Abstract We prove moment inequalities for exponential sums with respect to singular measures, whose Fourier decay matches those of curved hypersurfaces. Our emphasis will be on proving estimates that are sharp with respect to the scale parameter $$N$$, apart from $$N^\epsilon $$ losses. In a few instances, we manage to remove these losses.more » « less
-
Abstract Plane partitions in the totally symmetric self-complementary symmetry class (TSSCPPs) are known to be equinumerous with$$n\times n$$ alternating sign matrices, but no explicit bijection is known. In this paper, we give a bijection from these plane partitions to$$\{0,1,-1\}$$ -matrices we call magog matrices, some of which are alternating sign matrices. We explore enumerative properties of these matrices related to natural statistics such as inversion number and number of negative ones. We then investigate the polytope defined as their convex hull. We show that all the magog matrices are extreme and give a partial inequality description. Finally, we define another TSSCPP polytope as the convex hull of TSSCPP boolean triangles and determine its dimension, inequalities, vertices, and facets.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
