List-Decodable Learning
A relaxed recovery model in statistical learning that allows an algorithm to output a candidate list rather than a single hypothesis. It is applicable to highly noisy data settings.
Timeline (last 90 days)
The core of the algorithm is a novel boosting procedure that recovers the hidden weight vectors to constant error in a list-decodable manner.
List-decodable learning is a relaxed recovery model in statistical learning: the algorithm is allowed to output a candidate list whose size does not exceed a preset upper bound, as long as the target concept appears in the list with high probability.
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.
All Facts (3)
The core of the algorithm is a novel boosting procedure that recovers the hidden weight vectors to constant error in a list-decodable manner.
50%UnverifiedList-decodable learning is a relaxed recovery model in statistical learning: the algorithm is allowed to output a candidate list whose size does not exceed a preset upper bound, as long as the target concept appears in the list with high probability.
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%