Cover Image

Active Learning for Decision Trees with Provable Guarantees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Moakhar, Arshia Soltani, Laoaron, Tanapoom, Ghahremani, Faraz, Banihashem, Kiarash, Hajiaghayi, MohammadTaghi
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Matroid Algorithms Under Size-Sensitive Independence Oracles
by: Banihashem, Kiarash, et al.
Published: (2026)

Bandit Social Learning: Exploration under Myopic Behavior
by: Banihashem, Kiarash, et al.
Published: (2023)

A Dynamic Algorithm for Weighted Submodular Cover Problem
by: Banihashem, Kiarash, et al.
Published: (2024)

Replicable Composition
by: Banihashem, Kiarash, et al.
Published: (2026)

Dynamic Metric Embedding into $\ell_p$ Space
by: Banihashem, Kiarash, et al.
Published: (2024)

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
by: Banihashem, Kiarash, et al.
Published: (2025)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
by: Banihashem, Kiarash, et al.
Published: (2025)

Pandora with Inaccurate Priors
by: Banihashem, Kiarash, et al.
Published: (2025)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Bi-Criteria Metric Distortion
by: Banihashem, Kiarash, et al.
Published: (2024)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
by: Das, Debarati, et al.
Published: (2025)

2-Approximation for Prize-Collecting Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2023)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)

Prize-Collecting Forest with Submodular Penalties: Improved Approximation
by: Ahmadi, Ali, et al.
Published: (2025)

On the Power of Interactive Proofs for Learning
by: Gur, Tom, et al.
Published: (2024)

Replication-proof Bandit Mechanism Design with Bayesian Agents
by: Shin, Suho, et al.
Published: (2023)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

Optimal Contest Beyond Convexity
by: Golrezaei, Negin, et al.
Published: (2026)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Online Sampling and Decision Making with Low Entropy
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2021)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
by: Sato, Atsuki, et al.
Published: (2025)

Dynamic Spectral Clustering with Provable Approximation Guarantee
by: Laenen, Steinar, et al.
Published: (2024)

Differentially Private Verification of Distribution Properties
by: Du, Elbert, et al.
Published: (2026)

Efficient and Private Property Testing via Indistinguishability
by: Dwork, Cynthia, et al.
Published: (2025)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)

Adaptive and oblivious statistical adversaries are equivalent
by: Blanc, Guy, et al.
Published: (2024)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Samplability makes learning easier
by: Blanc, Guy, et al.
Published: (2025)

Efficient Turing Machine Simulation with Transformers
by: Li, Qian, et al.
Published: (2025)

Is nasty noise actually harder than malicious noise?
by: Blanc, Guy, et al.
Published: (2025)