Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
원문 초록
This paper is concerned with computationally efficient learning of homogeneous sparse halfspaces in $\mathbb{R}^d$ under noise. Though recent works have established attribute-efficient learning algorithms under various types of label noise (e.g. bounded noise), it remains an open question when and how $s$-sparse halfspaces can be efficiently learned under the challenging malicious noise model, where an adversary may corrupt both the unlabeled examples and the labels. We answer this question in the affirmative by designing a computationally efficient active learning algorithm with near-optimal label complexity of $\tilde{O}\big({s \log^4 \frac d \epsilon} \big)$ and noise tolerance $\eta = \Omega(\epsilon)$, where $\epsilon \in (0, 1)$ is the target error rate, under the assumption that the distribution over (uncorrupted) unlabeled examples is isotropic log-concave. Our algorithm can be straightforwardly tailored to the passive learning setting, and we show that the sample complexity is $\tilde{O}\big({\frac 1 \epsilon s^2 \log^5 d} \big)$ which also enjoys the attribute efficiency. Our main techniques include attribute-efficient paradigms for instance reweighting and for empirical risk minimization, and a new analysis of uniform concentration for unbounded data -- all of them crucially take the structure of the underlying halfspace into account.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Cost-Sensitive Active Learning for Incomplete Data
대규모 언어 모델에서 진실의 트릴레마
The Trilemma of Truth in Large Language Models
일반 대중은 대규모 언어 모델(LLM)에 인간과 유사한 특성을 부여하며, LLM이 특정 정보를 '알고' 있다고 가정하는 경우가 많다. 실제로 LLM은 학습 중 보존된 정보를 내부적 확률적 지식으로 인코딩한다. 본 연구는 해당 지식의 진위를 탐칭(probing)하는 기존 방법들을 검토하고, 세 가지 결함 있는 근본 가정을 밝힌다. 이러한 결함을 해결하기 위해, 다중 인스턴스 학습(MIL)과 conformal prediction을 결합한 다중 클래스 탐칭 프레임워크인 sAwMIL(Sparse-Aware Multiple-Instance Learning)을 제안한다. sAwMIL은 LLM의 내부 표현(representation)을 활용하여 진술을 참, 거짓, 또는 둘 다 아님으로 분류한다. 우리는 새롭게 구축한 세 개의 데이터셋을 사용하여, 기본형 및 채팅 기반 변형을 포함한 16개의 오픈소스 LLM에 대해 sAwMIL을 평가한다. 결과는 (1) 일반적인 탐칭 방법은 신뢰할 수 있고 전이 가능한(transferable) 진위 방향을 제공하지 못하며, 일부 설정에서는 제로샷(zero-shot) 프롬프팅(prompting)보다 성능이 낮음을, (2) 진실과 거짓은 대칭적으로 인코딩되지 않음을, (3) LLM이 참과 거짓 모두와 구별되는 제3의 유형의 신호를 인코딩함을 보여준다.
Attributes Shape the Embedding Space of Face Recognition Models
Ref-Long: Benchmarking the Long-context Referencing Capability of Long-context Language Models
CriticLean: Critic-Guided Reinforcement Learning for Mathematical Formalization
Emergent Semantics Beyond Token Embeddings: Transformer LMs with Frozen Visual Unicode Representations
토론
이 논문과 연결된 포럼 글이 아직 없습니다.