GEM-KMeans: GPU 최적화를 통한 대규모 데이터의 메모리 효율적이고 정확한 클러스터링

클러스터링 문제에서 통계적 정확도를 희생하지 않으면서 메모리 효율적으로 확장하는 것은 대규모 데이터 분석 및 머신러닝 문제에 있어 핵심적인 관심사입니다. $K$-means를 위한 음이 아닌 저랭크(Nonnegative Low-Rank, NLR) 행렬 분해는 확장 가능한 클러스터링 방법이며, 이는 최적의 평균 사례 정확한 복구 보장과 연결되는 반정부식 완화(semidefinite relaxations)와 관련됩니다. 하지만 NLR에 대한 직접적인 GPU 구현은 여러 개의 큰 인자 크기 버퍼와 실질적으로 메모리 바운드인 상당한 데이터 이동을 요구합니다. 본 논문에서는 그래디언트 업데이트, 음이 아닌 투영(nonnegative projection), 그리고 정규화를 위한 충분 통계량 및 반복 이동을 행렬 곱셈 에필로그로 융합한 스펙트럴하게 정규화되었지만 수학적으로 동등한 NLR 공식인 GEM-KMeans를 소개합니다. 세 개의 거대한 인자 크기 배열을 유지하는 대신, 저희의 I/O 인식 GPU 구현은 HBM(High Bandwidth Memory)에 추가 저장소로 작은 타일 축소 배열만을 사용하여 단 하나의 인자만 물질화합니다. 우리는 클러스터링 목적 함수를 최적화하기 위한 명시적인 메모리 비용과 스펙트럴하게 정규화된 평활도 경계(smoothness bounds)를 도출했습니다. 합성 및 실제 데이터셋에서 대규모 규모로 정확한 클러스터링이 입증되었으며, GEM-KMeans의 성능 향상은 기존 GPU 가속 로이드 알고리즘 대비 데이터 의존적 런타임 트레이드오프를 포함합니다.