PAC Learning
A theoretical framework for machine learning proposed by Leslie Valiant in 1984. Its central idea holds that a concept class is learnable if and only if there exists an algorithm capable of outputting an approximately correct hypothesis with high probability using a polynomial number of samples and computation steps.
Timeline (last 90 days)
This work proposes the first algorithm that learns k arbitrary positive linear combinations of ReLUs in fully polynomial time without strong assumptions (with respect to the Gaussian distribution and L2 loss, both sample and time complexity are poly(d, k, 1/ε)).
Under the standard PAC framework, if the noise ratio exceeds a certain threshold, no algorithm can uniquely recover the target; list-decodable learning, however, allows outputting a short list containing the true parameters in polynomial time under high-noise conditions.
This work is fundamental research in statistical learning theory; it does not involve specific engineering implementations or model architectures, but instead makes improvements to the theoretical precision of generalization bounds.
The independent and identically distributed (i.i.d.) assumption is the cornerstone of classical statistical learning theory and is a prerequisite for the PAC learning framework and VC dimension theory
All Facts (4)
This work proposes the first algorithm that learns k arbitrary positive linear combinations of ReLUs in fully polynomial time without strong assumptions (with respect to the Gaussian distribution and L2 loss, both sample and time complexity are poly(d, k, 1/ε)).
50%UnverifiedUnder the standard PAC framework, if the noise ratio exceeds a certain threshold, no algorithm can uniquely recover the target; list-decodable learning, however, allows outputting a short list containing the true parameters in polynomial time under high-noise conditions.
50%UnverifiedThis work is fundamental research in statistical learning theory; it does not involve specific engineering implementations or model architectures, but instead makes improvements to the theoretical precision of generalization bounds.
50%UnverifiedThe independent and identically distributed (i.i.d.) assumption is the cornerstone of classical statistical learning theory and is a prerequisite for the PAC learning framework and VC dimension theory
50%