- About
- Events
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Spring 2025 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University / Cornell Tech - High School Programming Workshop and Contest 2025
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Advising Guide for Research Students
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- A & B Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Provable Guarantees for Decision Tree Induction (via Zoom)
Abstract: Top-down decision tree learning algorithms, such as CART, ID3, and C4.5, have been machine learning workhorses for decades. However, there hasn't been much theoretical work proving that those algorithms can effectively learn decision trees. In part 1 of this talk, we prove that a large class of top-down algorithms learn a decision tree with accuracy close to that of the best small decision tree as long as the dataset is monotone. In part 2, we develop a new splitting criterion with similar guarantees even if the dataset is not monotone.
Bio: I'm a first year PhD student at Stanford broadly interested in CS theory. As an undergrad, also at Stanford, I worked with Li-Yang Tan and Greg Valiant, and am currently rotating with Moses Charikar. I'm still figuring out which areas of theory most interest me, but so far have dabbled in learning theory, complexity theory, and online algorithms.