arXiv:2407.00966v3 cs.LG

낮은 내재 차원 개념 학습을 위한 스무딩 분석

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos

제출 2024-07-01

한국어 초록

전통적인 지도 학습 모델에서 학습자의 목표는—$\mathbb{R}^d \times \{\pm 1\}$ 위의 임의의 결합 분포로부터 주어진 예시에 대해—어떤 클래스에 속한 가장 잘 맞는 개념(concept)에 $ε$ 이내로 경쟁력 있는 가설을 출력하는 것이다. 단순한 개념 클래스조차 학습하기 어렵다는 강한 난이도 결과를 피하기 위해, 우리는 학습자가 작은 무작위 가우시안 perturbation에 견고한 최적 분류기와만 경쟁하도록 요구하는 스무딩 분석(smoothed-analysis) 프레임워크를 도입한다. 이 미묘한 변화를 통해 (1) 저차원 부분공간에 의존하는(일명 multi-index model) (2) 유계 가우시안 표면적(bounded Gaussian surface area)을 갖는 모든 개념에 대해 폭넓은 학습 결과를 제시할 수 있다. 이 클래스는 반공간(halfspace)의 함수와 (저차원) 볼록 집합을 포함하며, 후자는 비스무딩 설정에서는 가우시안과 같이 highly structured distribution에 대해서만 학습 가능한 것으로 알려져 있었다. 우리가 정의한 스무딩 비지도적 학습(smoothed agnostic learning)은 인스턴스 분포 $D$와 최적 분류기가 임의로 결합(coupled)될 수 있는 경우(비지도적 학습 및 $σ= 0$에 해당)와 완전히 분리(decoupled)된 경우($σ= \infty$) 사이를 보간한다. 이러한 분리를 통해 복잡도 이론적 원시 연산(complexity-theoretic primitives)을 인코딩할 수 있는 최악의 개념을 피할 수 있다. 놀랍게도 우리 분석은 마진(margin)을 이용한 학습과 같은 전통적인 비스무딩 프레임워크에도 새로운 결과를 제공한다. 특히 마진 매개변수 $γ$에 대해 $k^{\mathrm{poly}(\frac{\log k}{εγ}) }$ 시간에 $k$개 반공간의 교집합을 비지도적으로 학습하는 최초의 알고리즘을 얻는다. 우리 연구 이전에는 알려진 최선의 실행 시간이 $k$에 대해 지수적이었다(Arriaga and Vempala, FOCS' 99).

원문 초록

In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on $\mathbb{R}^d \times \{\pm 1\}$-- is to output a hypothesis that is competitive (to within $ε$) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes, we introduce a smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Our definition of smoothed agnostic learning is an interpolation between the case where the instance distribution $D$ and the optimal classifier can be arbitrarily coupled (which corresponds to agnostic learning and $σ= 0$) and completely decoupled (when $σ= \infty$). This decoupling allows us to avoid worst-case concepts that can encode complexity-theoretic primitives. Surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of $k$-halfspaces in time $k^{\mathrm{poly}(\frac{\log k}{εγ}) }$ where $γ$ is the margin parameter. Before our work, the best-known runtime was exponential in $k$ (Arriaga and Vempala, FOCS' 99).

제출 이력

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

  1. arXiv:2407.00966v3제출 시각 미확인

함께 살펴볼 논문

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

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

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