Vi beskriver och utforskar ett nytt perspektiv på urvalskomplexiteten i aktivt lärande. I många situationer där det allmänt ansågs att aktivt lärande inte hjälper, visar vi att aktivt lärande hjälper i gränsen, ofta med exponentiella förbättringar i urval komplexitet. Detta står i kontrast till den traditionella analysen av aktiva inlärningsproblem såsom icke-homogena linjära avskiljare eller djupbegränsade beslutsträd, där (1/ ) lägre gränser är vanliga. Sådana nedre gränser bör tolkas noggrant; ja, vi bevisar att det alltid är möjligt att lära sig en god klassificering med ett antal prov asymptotiskt mindre än detta. Dessa nya insikter uppstår från en subtil variation på den traditionella definitionen av prov komplexitet, som inte tidigare erkänts i den aktiva lärande litteraturen.
En ny definition av urvalskomplexitet föreslås i REF för att visa att aktivt lärande är strikt bättre än passivt lärande asymptotiskt.
The true sample complexity of active learning
{'venue': 'Machine Learning', 'journal': 'Machine Learning', 'mag_field_of_study': ['Mathematics', 'Computer Science']}