Generalization Error Bounds for Learning under Censored Feedback
원문 초록
Generalization error bounds from learning theory provide statistical guarantees on how well an algorithm will perform on previously unseen data. In this paper, we characterize the impacts of data non-IIDness due to censored feedback (a.k.a. selective labeling bias) on such bounds. Censored feedback is ubiquitous in many real-world online selection and classification tasks (e.g., hiring, lending, recommendation systems) where the true label of a data point is only revealed if a favorable decision is made (e.g., accepting a candidate, approving a loan, displaying an ad), and remains unknown otherwise. We first derive an extension of the well-known Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, which characterizes the gap between empirical and theoretical data distribution CDFs learned from IID data, to problems with non-IID data due to censored feedback. We then use this CDF error bound to provide a bound on the generalization error guarantees of a classifier trained on such non-IID data. We show that existing generalization error bounds (which do not account for censored feedback) fail to correctly capture the model's generalization guarantees, verifying the need for our bounds. We further analyze the effectiveness of (pure and bounded) exploration techniques, proposed by recent literature as a way to alleviate censored feedback, on improving our error bounds. Together, our findings illustrate how a decision maker should account for the trade-off between strengthening the generalization guarantees of an algorithm and the costs incurred in data collection when future data availability is limited by censored feedback.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
동치 쿼리로부터의 학습, 재고찰
Learning from Equivalence Queries, Revisited
생성 모델과 추천 시스템 같은 현대 기계학습 시스템은 배포, 사용자 상호작용, 주기적 모델 업데이트의 순환을 통해 발전하는 경우가 많다. 이는 고정된 예측 과제 시퀀스에 대한 손실 또는 후회 최소화에 초점을 맞추는 표준 지도학습 프레임워크와 다르다. 이러한 설정에 착안하여, 우리는 Angluin(1988)이 도입한 동치 쿼리로부터의 학습이라는 고전적 모델을 재고찰한다. 이 모델에서 학습자는 반복적으로 가설을 제안하고, 배포된 가설이 부적절할 경우 반례를 받는다. 그러나 완전 적대적 반례 생성 하에서는 모델이 지나치게 비관적일 수 있다. 또한 대부분의 선행 연구는 학습자가 반례의 올바른 레이블도 관찰하는 완전 정보(full-information) 설정을 가정하는데, 이는 항상 자연스러운 가정이 아니다. 우리는 환경을 덜 적대적인 반례 생성기의 광범위한 부류로 제한함으로써 이러한 문제를 해결하며, 이를 대칭적(symmetric) 생성기라 부른다. 비형식적으로, 이러한 생성기는 가설과 타깃 사이의 대칭 차집합만을 기반으로 반례를 선택한다. 이 부류는 무작위 반례(Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024)와 같은 자연스러운 메커니즘뿐 아니라, 주어진 복잡도 척도에 따라 가장 단순한 반례를 반환하는 생성기도 포괄한다. 이 프레임워크 내에서 완전 정보 피드백과 밴딧(bandit) 피드백 양쪽 설정 하에 동치 쿼리로부터의 학습을 연구한다. 두 설정 모두에서 학습 라운드 수에 대한 타이트한 경계를 도출하고, 향후 연구 방향을 제시한다. 우리의 분석은 대칭적 적대자에 대한 게임 이론적 관점과 적응적 가중치 기법, 그리고 미니맥스(minimax) 논증을 결합한다.
A Reproducibility Study of Product-side Fairness in Bundle Recommendation
NLGCL: Naturally Existing Neighbor Layers Graph Contrastive Learning for Recommendation
Boosting Parameter Efficiency in LLM-Based Recommendation through Sophisticated Pruning
Kamae: Bridging Spark and Keras for Seamless ML Preprocessing
FindRec: Stein-Guided Entropic Flow for Multi-Modal Sequential Recommendation
토론
이 논문과 연결된 포럼 글이 아직 없습니다.