기술 요약: 양자화 및 연속적 강한 로또 티켓을 위한 통합 프레임워크

문제 정의

강한 로또 티켓 가설(Strong Lottery Ticket Hypothesis, SLTH)은 충분히 과매개변수화된 무작위 초기화 신경망이, 가중치 업데이트 없이도 더 작은 학습된 네트워크의 성능을 일치시킬 수 있는 희소 서브네트워크를 포함하고 있다는 가설이다. SLTH의 이론적 토대는 무작위 부분 집합 합 문제(Random Subset Sum Problem, RSSP)에 크게 의존하지만, 기존 문헌은 주로 연속적인 설정(임의 정밀도의 가중치)에 국한되어 왔다.

가중치가 이산 집합에서 샘플링되는 양자화 설정으로의 최근 확장 연구들은 상당한 한계에 직면해 왔다. 이 영역의 이전 연구들(예: Diffenderfer와 Kailkhura [2021], Sreenivasan 등 [2022], Kumar와 Natale [2025])은 타겟 네트워크를 연속 가중치로 제한하면서 이진 네트워크로 근사하거나, 양자화 설정에서의 정확한 표현에 대해 실패 확률이 역다항식(inverse-polynomial) 수준으로만 감소하는 보장만을 제공했다. 또한, 이러한 접근 방식들은 근사적 표현(연속)과 정확한 표현(양자화)을 별개의 연구 분야로 취급하여, 반올림 오차와 근사 오차를 동시에 고려하는 통합된 이론적 프레임워크가 부족했다.

방법론

저자들은 이 격차를 해소하기 위해 이산 설정에서의 RSSP에 대한 엄격한 분석을 개발하고 이를 양자화된 SLTH에 적용한다.

1. 이산 무작위 부분 집합 합 문제 (Discrete RSSP)

핵심적인 수학적 기여는 이산 RSSP에 대한 새로운 분석이다. 저자들은 무작위 변수 $X_1, \dots, X_n$이 이산 집합 $\{-M, \dots, M\}$에서 균등하게 샘플링될 때, 공차 $\Delta$ 내에서 타겟 $z$에 합산되는 부분 집합을 찾는 문제를 정의한다.

• 재귀 관계: 분석은 지표 함수 $f_t(z)$를 활용하는데, 이는 시간 $t$에서 타겟 $z$가 $\Delta$-근사되는지 여부를 나타낸다.
• 부피 성장 분석 (Volume Growth Analysis): 저자들은 $\{-M, \dots, M\}$ 범위 내에서 $\Delta$-근사될 수 있는 서로 다른 값들의 수인 "부피" $v_t$의 성장을 추적한다. 저자들은 $v_t$가 두 가지 뚜렷한 단계로 성장함을 증명한다:
  1. 급격한 성장 (Rapid Growth): $v_t$가 빠르게 $M+1$에 도달한다.
  2. 느린 성장 (Slow Growth): $v_t$가 전체 범위를 덮기 위해 천천히 $2M+1$까지 상승한다.
• 확률적 경계: 마팅게일 유사 논법과 집중 부등식(특히 역 마르코프 부등식과 호프딩 부등식을 활용)을 사용하여 이 단계들을 분석함으로써, 전체 집합이 $\Delta$-근사되는 데 필요한 시간 $\tau$에 대한 타이트한 경계값을 도출한다.

2. 양자화된 SLTH에 대한 적용

저자들은 연속 RSSP에서 이산 설정으로 Cunha 등 [2023]의 결과를 확장하여 양자화된 네트워크에 대한 SLTH 보장을 확립한다.

• 네트워크 구성: $2\ell$개의 층을 가진 무작위 초기화된 과매개변수화된 네트워크 $g$를 고려하며, 여기서 가중치는 이산 집합 $S_\delta$(정밀도 $\delta$)에서 균등하게 추출된다.
• 가지치기 전략: 목표는 가중치가 $S_\delta$에 있는 타겟 $\ell$-층 네트워크 $f$를 근사하도록 $g$를 가지치기하는 것이다. 가지치기 과정은 개별 가중치와 뉴런에 대한 독립적인 RSSP 인스턴스를 해결하는 것으로 분해된다.
• 오차 전파: 증명은 Pensia 등 [2020]의 전략을 따르며, 단일 가중치에서 뉴런으로, 뉴런에서 층으로, 그리고 최종적으로 전체 네트워크로 근사 보장을 격상시킨다. 결정적으로, 분석은 비선형성(ReLU)을 통한 오차 전파를 추적하고 층 전반에 걸친 오차 누적을 고려한다.

주요 기여

1. 이산 RSSP를 위한 타이트한 경계: 본 논문은 이산 RSSP에 대한 새롭고 날카로운 확률적 경계를 확립한다. 역다항식 감소의 실패 확률을 보였던 이전의 이산 분석(예: Kumar와 Natale [2025])과 달리, 본 연구는 정밀도 비트 수에 따른 지수적으로 작은 실패 확률을 증명한다.
2. 통합 프레임워크: 제안된 프레임워크는 다음을 입증함으로써 기존 문헌을 통합한다:
   • 연속 설정에서의 근사적 표현(Malach 등 [2020], Pensia 등 [2020]에서 다룸)은 $\delta \to 0$일 때 극한 사례로 나타난다.
   • 양자화 설정에서의 정확한 표현(Kumar와 Natale [2025]에서 다룸)은 $\Delta = 0$일 때 극한 사례로 나타난다.
   • 이 프레임워크는 양자화로 인한 반올림 오차와 가지치기로 인한 근사 오차를 동시에 처리한다.
3. 개선된 과매개변수화 보장: 저자들은 폭이 $O(d \log(1/\delta))$인 깊이-$2\ell$ 무작위 네트워크가 폭 $d$와 정밀도 $\delta$를 가진 임의의 타겟 $\ell$-층 네트워크를 $\epsilon$-근사하도록 가지치기할 수 있음을 도결한다.

결과

• 이론적 보장: 주요 정리(정리 3)는 높은 확률($1 - 4d^{2\ell} \exp(-C'n)$)로, $2\ell$층의 무작위 초기화된 양자화 네트워크가 임의의 타겟 $\ell$-층 양자화 네트워크를 오차 $\epsilon$ 내에서 근사하도록 가지치기될 수 있음을 명시한다. 실패 확률은 과매개변수화 계수에 따라 지수적으로 감소한다.
• 실험적 검증:
  • 부분 집합 합 실험: 저자들은 이산 RSSP 이론을 경험적으로 검증하였으며, 샘플 수 $n \gtrsim C \log(M)$ (여기서 $C \approx 1.5$)일 때 정확한 부분 집합 합 문제($\Delta=0$)를 해결할 확률이 1에 수렴함을 관찰했다.
  • 가지치기 효율성: 실제 테스트에서 저자들은 필요한 RSSP 인스턴스를 해결함으로써 ResNet-50(2,500만 파라미터, FP8 정밀도)을 근사하는 서브네트워크를 성공적으로 식별했다. 이 과정은 병렬화 없이 단일 CPU에서 약 33분이 소요되었으며, 이는 계산적 실현 가능성을 입증한다.

의의 및 주장

본 논문은 연속 및 양자화 설정을 잇는 강한 로또 티켓의 응집된 이론을 향한 근본적인 발걸음을 제공한다고 주장한다. 이 연구는 기존의 연구 라인을 다음과 같이 통합함으로써:

• 기존 경계의 정교화: 양자화 영역에서 실패 확률 보장을 역다항식에서 지수적 감소로 개선한다.
• 실질적 관련성 확대: 근사 보장의 이론적 엄격함을 유지하면서 유한 정밀도 계산(양자화)의 현실을 다룬다.
• 분야의 통합: 근사적 연속 표현과 정확한 양자화 표현 모두가 하나의 더 일반적인 프레임워크의 특수 사례임을 보여준다.

저자들은 자신들의 결과가 양자화된 네트워크에서 로또 티켓이 존재한다는 기존의 경험적 관찰을 뒷받침하며, 자원이 제한된 유한 정밀도 환경에서 가지치기 사용에 대한 더 강력한 이론적 토대를 제공한다고 강조한다.