Fast Agnostic Learners in the Plane

Fast Agnostic Learners in the Plane

by Talya Eden

Formal & Physical Sciences AI — Models & Research UYQArtificial intelligence (AI)UYQMMachine learning
🎙 Talya Eden 👥 385 📅 November 1, 2025 ⏱ 70 min 👁 59 📄 original study 🧭 2026-08-16
Available in: English (current) Français

Keywords

agnostic learningproper learningtime complexitysample complexitygeometric concepts

Summary

Talya Eden presents recent results on fast agnostic learners for geometric concept classes in the plane, specifically triangles, convex k-gons (for small k), and convex sets. The talk begins by defining the agnostic learning model, where the goal is to find a function from a concept class that minimizes error with respect to an arbitrary distribution, allowing for a relaxation epsilon. She emphasizes the distinction between sample complexity and time complexity, noting that proper agnostic learning is computationally hard in general, but in 2D, efficient learners exist for certain classes. The main contribution is a framework that decouples the sample used for building candidate concepts from the sample used for evaluation, leading to improved running times while maintaining optimal sample complexity for k-gons. For convex sets under the uniform distribution, they achieve faster computation at a slight cost in sample complexity. The talk also explores connections to property testing and distance approximation, showing how agnostic learning can be used to approximate distances to concept classes. The technical approach involves constructing a small set of reference concepts from a subsample, then using range searching data structures to efficiently evaluate their empirical risk. The results improve known running times for triangles, 4-gons, and 5-gons, and provide a trade-off for convex sets. The talk concludes with open questions about closing the gap between sample and time complexity.

224 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk provides valuable insights into the time complexity of agnostic learning, a less explored aspect compared to sample complexity. The argumentation is solid, building on known results and clearly motivating the focus on 2D geometric classes. The speaker explains the intuition behind the algorithmic framework, which involves constructing a small set of candidate concepts and evaluating them efficiently. The presentation is rigorous, with formal definitions and references to prior work, and the speaker addresses questions from the audience, clarifying technical points. The results are presented as improvements over existing algorithms, with a clear trade-off for convex sets. The connection to property testing adds depth, showing broader implications of the work.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous, with clear definitions and references to prior work, including the foundational paper by Kearns et al. (1992) and specific results for geometric classes. The speaker cites joint work with Ludmila Glinskih and Sofya Raskhodnikova, and mentions related results by other researchers. The title accurately reflects the content, focusing on fast agnostic learners in the plane. The presentation is technical and assumes familiarity with computational learning theory, but the speaker provides sufficient context. No comments were provided, so no analysis of public reception is possible.

215 words

Title / Content Match

The title accurately reflects the content: the talk focuses on fast agnostic learners for geometric concept classes in the plane.

Quality & Reliability

8/10

Presentation of original research by a recognized expert, with clear technical details and references to prior work. The talk is rigorous but assumes advanced knowledge, and the video has no visual aids or transcript verification.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

  • Joint work with Ludmila Glinskih and Sofya Raskhodnikova — The presented results are based on this collaboration.
  • Kearns et al. (1992) — Foundational work on agnostic learning.
  • Sofya Raskhodnikova and others on convex sets under uniform distribution — Prior work on agnostic learning for convex sets.

Concurring Sources

  • Kearns et al. (1992) — Foundational work on agnostic learning, consistent with the talk's framework.

Contribution & Novelties

The talk presents new algorithmic results for agnostic learning of geometric concept classes in the plane, improving time complexity while maintaining optimal sample complexity for k-gons. The framework of decoupling the sample for building candidates from the sample for evaluation is a novel approach that could be applied to other concept classes. The connection to property testing provides a new perspective on the relationship between learning and testing.

Pour aller plus loin :

  • Agnostic learning — Overview of the agnostic learning model.
  • VC dimension — Fundamental concept in learning theory.
  • Property testing — Related field with connections to learning.

99 words

Radar Profile

The radar profile shows high scores in technical level and information quality, indicating a dense, expert-level presentation. The lower scores in fiabilite_globale and quantite_information reflect the lack of visual aids and the reliance on verbal explanation, but the overall profile suggests a solid scientific talk.

Reliability 8/10