arXiv:2609.27241v1 stat.ML

멤버십 쿼리를 활용한 능동 학습의 샘플 복잡도에 관하여

On the Sample Complexity of Active Learning with Membership Queries

Ganghua Wang, Shaddin Dughmi

제출 2026-09-24

한국어 초록

본 연구는 능동 학습(active learning)의 근본적인 질문, 즉 임의의 쿼리를 합성할 수 있는 능력이 얼마나 강력한가라는 문제를 다시 살펴본다. 학습자가 주어진 레이블 없는 풀(pool)에서만 쿼리를 선택하는 풀 기반 능동 학습과 비교할 때, 쿼리 능력에서의 이처럼 사소해 보이는 변화가 통계적 학습의 난이도를 극적으로 바꿀 수 있음을 발견하였다. 특히 풀 기반 설정에서는 본질적으로 학습이 느려 샘플 수에 대해 다항식 수준의 오차 감소만을 달성하는 일부 가설 클래스(hypothesis class)가, 합성된 쿼리가 허용되면 지수적으로 학습 가능해진다. 이러한 두드러진 격차는 멤버십 쿼리 합성(membership query synthesis)이 근본적으로 다른 학습 방식을 유도하며, 이는 기존 능동 학습 이론으로는 충분히 설명되지 않아 그 복잡도를 규명하기 위한 새로운 분석 도구가 필요함을 시사한다. 이러한 현상에 착안하여, 본 연구는 몇 가지 충분 조건을 개발하고 흥미로운 예시들을 제시하며, 어떤 가설 클래스가 합성된 쿼리를 통해 효율적인 학습을 허용하는지 이해하기 위한 추측적 관점을 제안한다.

원문 초록

This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, we find that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular, some hypothesis classes that are inherently slow to learn in the pool-based setting, achieving only polynomial error decay in the number of samples, become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its complexity. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.27241v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2604.04535v2cs.LG공통 태그 Active Learning, Learning Theory

동치 쿼리로부터의 학습, 재고찰

Learning from Equivalence Queries, Revisited

생성 모델과 추천 시스템 같은 현대 기계학습 시스템은 배포, 사용자 상호작용, 주기적 모델 업데이트의 순환을 통해 발전하는 경우가 많다. 이는 고정된 예측 과제 시퀀스에 대한 손실 또는 후회 최소화에 초점을 맞추는 표준 지도학습 프레임워크와 다르다. 이러한 설정에 착안하여, 우리는 Angluin(1988)이 도입한 동치 쿼리로부터의 학습이라는 고전적 모델을 재고찰한다. 이 모델에서 학습자는 반복적으로 가설을 제안하고, 배포된 가설이 부적절할 경우 반례를 받는다. 그러나 완전 적대적 반례 생성 하에서는 모델이 지나치게 비관적일 수 있다. 또한 대부분의 선행 연구는 학습자가 반례의 올바른 레이블도 관찰하는 완전 정보(full-information) 설정을 가정하는데, 이는 항상 자연스러운 가정이 아니다. 우리는 환경을 덜 적대적인 반례 생성기의 광범위한 부류로 제한함으로써 이러한 문제를 해결하며, 이를 대칭적(symmetric) 생성기라 부른다. 비형식적으로, 이러한 생성기는 가설과 타깃 사이의 대칭 차집합만을 기반으로 반례를 선택한다. 이 부류는 무작위 반례(Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024)와 같은 자연스러운 메커니즘뿐 아니라, 주어진 복잡도 척도에 따라 가장 단순한 반례를 반환하는 생성기도 포괄한다. 이 프레임워크 내에서 완전 정보 피드백과 밴딧(bandit) 피드백 양쪽 설정 하에 동치 쿼리로부터의 학습을 연구한다. 두 설정 모두에서 학습 라운드 수에 대한 타이트한 경계를 도출하고, 향후 연구 방향을 제시한다. 우리의 분석은 대칭적 적대자에 대한 게임 이론적 관점과 적응적 가중치 기법, 그리고 미니맥스(minimax) 논증을 결합한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.