Data Selection for Empirical Risk Minimization

Data Selection for Empirical Risk Minimization

by Alexander Shlimovich

Formal & Physical Sciences AI — Models & Research UYQArtificial intelligence (AI)UYQMMachine learning
🎙 Alexander Shlimovich 👥 385 📅 May 29, 2026 ⏱ 48 min 👁 50 📄 original study 🧭 2026-08-16
Available in: English (current) Français

Keywords

data selectionempirical risk minimizationsample complexitycore setsCarathéodory theorem

Summary

The talk presents a theoretical framework for data selection in empirical risk minimization (ERM). The central question is whether a small subset of training data can achieve performance comparable to training on the full dataset. The speaker formalizes this via a ’teacher’ that selects a subset of size k to minimize the loss of a fixed ERM learner. He studies this for mean estimation, linear regression, and linear classification. For mean estimation, he shows that for k=1 the worst-case loss ratio is 2, and for k=2 it is 2 (with a refined Carathéodory theorem for convex functions). For general k, the problem becomes hard, and only asymptotic results are known. For linear regression, he introduces a relaxation to support sets (core sets) and shows that for k≥2d the optimal loss ratio is 1, while for k=d+1 it is bounded by d+1. He also discusses volume sampling to achieve bounds for k=d. For linear classification with max-margin, he shows that k>d suffices for perfect accuracy, and k≤d gives no guarantee. The talk concludes with open questions and connections to sample compression schemes.

181 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk provides valuable insights into the theoretical foundations of data-centric machine learning. It formalizes the problem of data selection and provides tight bounds for specific settings, which is a significant contribution. The argumentation is rigorous, with proofs sketched for key results. The use of Carathéodory’s theorem and volume sampling is well-motivated and demonstrates a deep understanding of the underlying mathematics. The speaker also highlights the limitations and open problems, which adds to the credibility of the work.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous, with clear definitions and formal statements. The speaker cites relevant prior work, including Carathéodory’s theorem and volume sampling, and builds upon them. The title accurately reflects the content. The talk is a seminar presentation, so it lacks peer review, but the results appear to be novel and well-founded. The speaker also acknowledges the difficulty of the general problem, which is honest and appropriate.

161 words

Title / Content Match

The title accurately reflects the content, which focuses on selecting data subsets for empirical risk minimization.

Quality & Reliability

8/10

The talk presents original theoretical results with rigorous proofs, building on established theorems (Carathéodory) and known sampling methods (volume sampling). The speaker is a PhD student at Technion, and the work is joint with researchers from Purdue and Technion, indicating academic credibility. However, the presentation is a seminar talk and not peer-reviewed, and some results are only asymptotic or conjectured.

Key Moments

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

Cited Sources

  • Carathéodory's theorem — Referenced as the classical theorem used to reduce the number of points needed to represent a point in a convex hull.
  • Volume sampling — Referenced as a sampling method used to achieve bounds for linear regression.

Concurring Sources

  • Carathéodory's theorem — The theorem is used to justify the existence of small subsets that preserve the optimal solution.
  • Volume sampling — Referenced as a method to achieve unbiased estimators and optimal bounds.

Contribution & Novelties

The talk presents novel theoretical results on data selection for ERM, providing tight bounds for mean estimation and linear regression in specific regimes. It introduces a refined Carathéodory theorem for convex functions and uses volume sampling to achieve optimal bounds. The work also connects to sample compression schemes and core sets, offering a unified perspective.

Pour aller plus loin :

  • Carathéodory’s theorem — Classical result used to reduce the number of points needed to represent a point in a convex hull.
  • Core sets — Concept of small subsets that approximate the full dataset for a given task.
  • Sample compression schemes — Related framework for learning from small subsets.

108 words

Radar Profile

The radar profile shows high scores in all dimensions, indicating a well-rounded and rigorous presentation. The talk is technically deep, with strong quantitative and qualitative information, and high reliability.

Reliability 8/10