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

Optimal quantum sample complexity of learning algorithms

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2018年第1期19卷

作者： Srinivasan Arunachalam Ronald De Wolf QuSoft CWI Amsterdam the Netherlands QuSoft CWI and University of Amsterdam the Netherlands

In learning theory, the VC dimension of a concept class ℒ is the most common way to measure its "richness." A fundamental result says that the number of examples needed to learn an unknown target concept c ∈ ℒ under an unknown distribution D, is tightly determined by the VC dimension d of the concept class ℒ. Specifically, in the PAC model Θ(d/ε + log(1/δ)/ε) examples are necessary and sufficient for a learner to output, with probability 1 - δ, a hypothesis h that is ε-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c ∈ ℒ, we know that Θ(d/ε2 + log(1/δ)/ε2) examples are necessary and sufficient to output an hypothesis h ∈ ℒ whose error is at most ε worse than the error of the best concept in ℒ.Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is Ω(d1-ν/ε =+ d + log(1/δ)/ε) for arbitrarily small constant η ≥ 0. Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/ε) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every con

关键词： PAC learning lower bounds quantum computing sample complexity

Distribution-dependent sample complexity of large margin learning

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2013年第1期14卷

作者： Kevin Murphy Bernhard Schölkopf Sivan Sabato Nathan Srebro Naftali Tishby Google MPI for Intelligent Systems Microsoft Research New England Cambridge MA Toyota Technological Institute at Chicago Chicago IL The Rachel and Selim Benin School of Computer Science and Engineering The Hebrew University Jerusalem Israel

We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on the sample complexity, both governed by the margin-adapted dimension of the data distribution. The upper bounds are universal, and the lower bounds hold for the rich family of sub-Gaussian distributions with independent features. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. To prove the lower bound, we develop several new tools of independent interest. These include new connections between shattering and hardness of learning, new properties of shattering with linear classifiers, and a new lower bound on the smallest eigenvalue of a random Gram matrix generated by sub-Gaussian variables. Our results can be used to quantitatively compare large margin learning to other learning rules, and to improve the effectiveness of methods that use sample complexity bounds, such as active learning.

关键词： distribution-dependence linear classifiers sample complexity supervised learning

The optimal sample complexity OF PAC learning

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2016年第1期17卷

作者： Kevin Murphy Bernhard Schölkopf Steve Hanneke Google MPI for Intelligent Systems

This work establishes a new upper bound on the number of samples sufficient for PAC learning in the realizable case. The bound matches known lower bounds up to numerical constant factors. This solves a long-standing open problem on the sample complexity of PAC learning. The technique and analysis build on a recent breakthrough by Hans Simon.

关键词： PAC learning learning algorithm minimax analysis sample complexity statistical learning theory

A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2016年第1期17卷

作者： Kevin Murphy Bernhard Schölkopf Radosław Adamczak Google MPI for Intelligent Systems Institute of Mathematics University of Warsaw Warszawa Poland

We consider the problem of recovering an invertible n×n matrix A and a sparse n×p random matrix X based on the observation of Y = AX (up to a scaling and permutation of columns of A and rows of X). Using only elementary tools from the theory of empirical processes we show that a version of the Er-SpUD algorithm by Spielman, Wang and Wright with high probability recovers A and X exactly, provided that p ≥ Cn log n, which is optimal up to the constant C.

关键词： Er-SpUD algorithm exact recovery l1 minimization sample complexity sparse dictionaries

Quantum Search-to-Decision Reduction for the LWE Problem∗

学校读者我要写书评

暂无评论

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2025年第2期E108A卷 104-116页

作者： Sudo, Kyohei Hara, Keisuke Tezuka, Masayuki Yoshida, Yusuke Osaka Univ Toyonaka 5600831 Japan Natl Inst Adv Ind Sci & Tech nol AIST Tokyo 1350064 Japan Yokohama Natl Univ Yokohama 2400067 Japan Tokyo Inst Technol Tokyo 152 Japan

The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. The efficiency of the reduction can be regarded as the gap in difficulty between the problems. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only 2 times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction is incomparable to the classical reduction in terms of sample complexity and query complexity. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over Zq where q is a prime. In short, this theorem states that, if a hardcore predicate a s (mod q) can be predicted with probability distinctly greater than 1/q with respect to a uniformly random a is an element of Znq, then it is possible to determine s is an element of

关键词： key learning with errors learning parity with noise search decision reduction Goldreich-Levin theorem quantum reduction complexity sample complexity

Theory and fast learned solver for ℓ¹-TV regularization

学校读者我要写书评

暂无评论

INVERSE PROBLEMS 2025年第1期41卷

作者： Liu, Xinling Wang, Jianjun Jin, Bangti Southwest Univ Sch Math & Stat Chongqing 400715 Peoples R China China West Normal Univ China West Normal Univ Sichuan Prov Sch Math & Informat Key Lab Optimizat Theory & Applicat Nanchong 637009 Peoples R China Chinese Univ Hong Kong Dept Math Shatin Hong Kong Peoples R China

The & ell;(1) and total variation (TV) penalties have been used successfully in many areas, and the combination of the & ell;(1) and TV penalties can lead to further improved performance. In this work, we investigate the mathematical theory and numerical algorithms for the & ell;(1)-TV model in the context of signal recovery: we derive the sample complexity of the & ell;(1)-TV model for recovering signals with sparsity and gradient sparsity. Also we propose a novel algorithm (PGM-ISTA) for the regularized & ell;(1)-TV problem, and establish its global convergence and parameter selection criteria. Furthermore, we construct a fast learned solver (LPGM-ISTA) by unrolling PGM-ISTA. The results for the experiment on ECG signals show the superior performance of LPGM-ISTA in terms of recovery accuracy and computational efficiency.

关键词： & ell (1)-TV regularization sample complexity learned solver algorithm unrolling

Truncated amplitude flow with coded diffraction patterns

学校读者我要写书评

暂无评论

INVERSE PROBLEMS 2025年第1期41卷

作者： Li, Huiping Li, Jiayi Hangzhou Normal Univ Sch Math Hangzhou Peoples R China Hong Kong Univ Sci & Technol Dept Math Hong Kong Peoples R China

The phase retrieval problem, which involves Fourier transforms with random masks, has a wide range of applications in signal and image processing, such as diffraction imaging. In recent years, various first-order methods have been explored, including truncated amplitude flow (TAF). These methods are considered to be simple and effective for solving the phase retrieval problem. However, existing convergence results for TAF mainly focus on random Gaussian measurements, which is very far from practical scenarios. In this paper, we analyze the convergence of a revised TAF (RTAF) for the phase retrieval problem. We focus on coded diffraction patterns composed of Fourier transforms and random masks. Then we justify the linear convergence behavior of such algorithm when near the true solution. By utilizing the local initializer found by a non-truncated spectral method, we establish the exact convergence rates in both the noiseless case and the bounded noise case. Further, we have shown that a general signal x is an element of C-n can be estimated on an optimal sampling order (specifically, O(n log n)). Moreover, our demonstrations indicate that sharp stability can be maintained even when the observations are contaminated by bounded noise. Our experiments have revealed that the RTAF algorithm can reliably estimate the original signal using fewer measurements, aligning with our theoretical analysis. Additionally, numerical experiments have highlighted that the RTAF algorithm outperforms the truncated Wirtinger flow and truncated Riemannian gradient descent algorithms in terms of efficiency and stability, showcasing its superior performance over state-of-the-art algorithms.

关键词： phase retrieval coded diffraction pattern truncated amplitude flow non-convex optimization sample complexity

Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第2期71卷 1153-1170页

作者： Chakraborty, Sourav Fischer, Eldar Ghosh, Arijit Mishra, Gopinath Sen, Sayantan Indian Stat Inst ISI Comp & Commun Sci Div CCSD Adv Comp & Microelect Unit ACMU Kolkata 700108 India Technion Israel Inst Technol Henry & Marilyn Taub Fac Comp Sci IL-3200003 Hefa Israel Natl Univ Singapore Sch Comp Singapore 119077 Singapore Natl Univ Singapore Ctr Quantum Technol Singapore 119077 Singapore

The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently drawn samples from an oracle. The testing task is to distinguish a distribution that satisfies some property from a distribution that is far in some distance measure from satisfying it. The task of tolerant testing imposes a further restriction, that distributions close to satisfying the property are also accepted. This work focuses on the connection between the sample complexities of non-tolerant testing of distributions and their tolerant testing counterparts. When limiting our scope to label-invariant (symmetric) properties of distributions, we prove that the gap is at most quadratic, ignoring poly-logarithmic factors. Conversely, the property of being the uniform distribution is indeed known to have an almost-quadratic gap. When moving to general, not necessarily label-invariant properties, the situation is more complicated, and we show some partial results. We show that if a property requires the distributions to be non-concentrated, that is, the probability mass of the distribution is sufficiently spread out, then it cannot be non-tolerantly tested with o(root n) many samples, where n denotes the universe size. Clearly, this implies at most a quadratic gap, because a distribution can be learned (and hence tolerantly tested against any property) using O(n) many samples. Being non-concentrated is a strong requirement on properties, as we also prove a close to linear lower bound against their tolerant tests. Apart from the case where the distribution is non-concentrated, we also show if an input distribution is very concentrated, in the sense that it is mostly supported on a subset of size s of the universe, then it can be learned using only O(s) many samples. The learning procedure adapts to the input, and works without knowing s in advance.

关键词： Testing complexity theory Probability distribution Computer science Upper bound Surveys Polynomials Machine learning algorithms Machine learning Limiting Distribution testing tolerant testing non-tolerant testing sample complexity

Lower Bounds for Learning Quantum States with Single-Copy Measurements

学校读者我要写书评

暂无评论

ACM TRANSACTIONS ON COMPUTATION THEORY 2025年第1期17卷 1-42页

作者： Nayak, Ashwin Lowe, Angus Univ Waterloo Combinator & Optimizat Waterloo ON Canada MIT Phys Cambridge MA USA

We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d-dimensional state. We first revisit known lower bounds [23] on quantum tomography with accuracy & varepsilon;in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the chi 2-divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore "Pauli tomography" algorithm in terms of its sample complexity. We also derive novel bounds of Omega(r2d/& varepsilon;2) and Omega(r2d2/& varepsilon;2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of chi 2-divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp(O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circu

关键词： Quantum state tomography sample complexity lower bounds single- copy measurements adaptive measurements circuit complexity classical shadows shadow tomography