선형 연상 기억의 날카로운 용량 임계값: 승리자 취하기에서 리스트 회색까지

한 $d\times d$ 선형 기억은 몇 개의 키-값 연상을 저장할 수 있는가? 우리는 이 대답이 기억 행렬의 $d^2$ 도freedom뿐만 아니라 회색 기준 (retrieval criterion) 에도 의존한다고 보여준다. 등방성 가우시안 모델 (isotropic Gaussian model) 에서 저장된 쌍에 대해, 모든 신호가 가장 큰 방해자 (distractor) 를 이겨야 하는 톱-1 회색 (top-1 retrieval) 은 로그 스케일 $d^2\asymp n\log n$ 을 요구한다. 우리는 키-대상 외적 (key-target outer products) 의 중첩을 통해 연상을 저장하는 상관 행렬 기억 구성 (correlation matrix memory construction) 이 날카로운 상전이를 통해 이 스케일을 달성함을 증명하며, 이것이 어떤 선형 기억에도 필수적임을 보여준다. 따라서 로그는 승리자 취하기 (winner-take-all) 해독의 내재적 극값 가격이다. 우리는 다음으로 올바른 대상이 유일한 최고 점수 항목이 아니어야 하지만 가장 강력한 후보들 중 하나여야 하는 리스트 회색 (listwise retrieval) 을 고려한다. 이 제도를 공식화하기 위해, 우리는 올바른 대상을 제어된 후보 목록에 포함함을 증명하는 볼록 상단 꼬리 기준 (convex upper-tail criterion) 인 꼬리 평균 마진 (Tail-Average Margin, TAM) 을 제안한다. 이 리스트 회색 기준 하에서 용량은 $d^2\asymp n$ 스케일을 따른다. 부하 $n/d^2\toα$ 에서 우리는 두 매개변수 스칼라 변분 원리를 통해 TAM 경험적 리스크 최소화자 (empirical-risk minimizer) 에 대한 정확한 점근 이론을 개발한다. 이 이론은 풍부한 현상론을 가진다: 린드리스 한계 (ridgeless limit) 에서 만족 가능 및 불만족 가능 상의 구분 임계 부하를 제공하는 닫힌 형태, 그리고 참 점수의 극한 법칙, 경쟁자 점수, 마진, 백분위 프로필의 예측 법칙을 제공한다. 마지막으로, 작은 꼬리 외삽은 추측적 날카로운 톱-1 임계값 $d^2\sim 2n\log n$ 을 유도한다.