기술 요약: 온라인 알고리즘은 고립된 퍼셉트론 해를 찾을 수 없다

1. 문제 정의

본 논문은 **이진 퍼셉트론 문제(binary perceptron problem)**를 조사한다. 이는 무작위 제약 충족 문제(random CSP)로서, 목표는 $m \times n$ 행렬 $G$의 성분이 i.i.d. 표준 가우시안 분포를 따를 때, 모든 성분에 대해 $G\sigma \ge \kappa\sqrt{n}$을 만족하는 부호 벡터 $\sigma \in \{\pm 1\}^n$를 찾는 것이다. 이 문제는 고정된 제약 밀도 $\alpha > 0$에 대해 $m = \lfloor \alpha n \rfloor$인 비례 영역(proportional regime)에서 연구된다.

이 모델의 결정적인 특징은 **강한 동결(strong freezing)**이다. 즉, 임의의 $\alpha > 0$에 대해, 거의 모든 해는 **고립(isolated)**되어 있다. 구체적으로, 높은 확률로 모든 해는 다른 어떤 해와도 $\Omega(n)$의 해밍 거리(Hamming distance)를 가진다. 이러한 기하학적 특성은 효율적인 알고리즘이 해를 찾는 데 어려움을 겪을 것임을 시사한다. 왜냐하면 근처에 해가 존재하지 않아 국소 탐색(local search)을 통해 해로 유도될 수 없기 때문이다.

그러나 역설이 존재한다. 효율적인 알고리즘, 특히 온라인 알고리즘(열(column)을 하나씩 처리하며 부호를 돌이킬 수 없이 할당하는 방식)은 특정 제약 밀도(예: $\kappa=0$일 때 $\alpha < 0.327$)에서 해를 찾는 것으로 알려져 있다. 핵심 질문은 다음과 같다: 이러의 성공적인 온라인 알고리즘들이 전형적인 고립된 해들을 찾는 것인가, 아니면 드물게 존재하는 잘 연결된(well-connected) 해의 클러스터들을 찾아내는 것인가?

2. 방법론 및 증명 전략

저자들은 온라인 알고리즘이 상수 확률로 고립된 해를 찾을 수 없음을 증명한다. 즉, 성공 확률은 $n \to \infty$일 때 0으로 수렴한다. 증명은 세 가지 주요 기술적 단계로 진행된다.

A. 결정론적 알고리즘으로의 환원

저자들은 임의의 무작위 온라인 알고리즘이 평균화 논증(averaging argument)을 통해 분석될 수 있음을 먼저 관찰한다. 따라서 현재의 열 $g_t$, 열들의 이력, 그리고 이전에 할당된 부호들의 함수로서 $t$ 단계에서의 부호 $\sigma_t$가 결정되는 결정론적 온라인 알고리즘을 고려하는 것으로 충분하다.

B. "학습 중단(Stop-Learning)" 렘마 (접미사 병렬 베이스라인)

핵심 통찰은 만약 온라인 알고리즘이 $h$-고립된 해(여기서 $h = \omega(\log^4 n)$)를 성공적으로 출력한다면, 알고리즘은 프로세스 종반부에 효과적으로 "학습을 멈춰야" 한다는 것이다.

• 논리: 만약 알고리즘이 고립된 해를 출력한다면, 마지막 $r$개의 부호(여기서 $r < h$)는 반드시 해의 접두사(prefix)에 의해 유일하게 결정되어야 한다. 만약 알고리즘이 여전히 "학습 중"(즉, 남은 열들의 특정 순서에 따라 결정 규칙을 변경함)이라면, 이는 비유일한 완성을 출력할 위험이 있으며, 이는 고립 특성을 위반하게 된다.
• 구성: 저자들은 접미사 병렬 베이스라인(suffix-parallel baseline) 알고리즘 $\text{Alg}^{(r)}$을 정의한다. 이 알고리즘은 처음 $n-r$개의 열에 대해서는 원래의 알고리즘 $\text{Alg}$와 동일하게 동작한다. 그러나 마지막 $r$개의 열에 대해서는, 이 열들이 단계 $n-r+1$에서 동시에 도착한 것처럼 취급한다. 구체적으로, 모든 접미사 열 $Y_i$에 대해 동일한 결정 함수 $\phi = \text{SubAlg}_{n-r+1}$를 적용하며, 접미사 내에서의 도착 순서는 무시한다.
• 결과: 가우시안 열들의 교환 가능성(exchangeability)과 평균화 논증을 사용하여, 저자들은 모든 성공적인 알고리즘에 대해, 해당 알고리즘의 출력이 높은 확률로 이 접미사 병렬 베이스라인과 일치하는 $r$이 존재함을 보여준다.

C. 베이스라인의 반집중(Anti-Concentration)

증명의 두 번째 부분은 어떤 접미사 병렬 베이스라인도 유일한 완성을 만들어낼 수 없음을 입증한다.

• 설정: 베이스라인이 접미사 열 $Y_1, \dots, Y_r$에 부호를 할당하기 위해 고정된 함수 $\phi$를 사용한다고 하자. 출력이 해가 되기 위한 조건은 합 $\frac{1}{\sqrt{r}}\sum z_i Y_i$가 특정 영역(접두사 제약에 의해 이동된 상측 직교 영역) 내에 있어야 한다는 것이다.
• 유일성 제약: 해가 고립되려면, 문자열 $z$는 이 선형 제약을 만족하는 $\{\pm 1\}^r$ 내의 유일한 문자열이어야 한다.
• 기하학적 논증: 이 유일성은 무작위 벡터 $S_\phi = \frac{1}{\sqrt{r}}\sum \phi(Y_i)Y_i$가 $\mathbb{R}^m$ 내의 매우 좁은 "껍질(shell)"(두 상측 직교 영역 사이의 차이)에 놓여 있어야 함을 의미한다.
• 확률적 경계: 저자들은 $S_\phi$의 분포를 가우시안 무작위 변수 $Z$로 근사하기 위해 베리-에센(Berry-Esseen) 정리를 적용한다. 그 후, 가우시안 벡터에 대한 반집중 경계를 제공하는 나자로프(Nazarov)의 부등식을 호출한다. 이 부등식은 가우시안 벡터가 그러한 좁은 껍질 안에 떨어질 확률이 극도로 작음($o(1)$)을 보여준다.
• 결론: 베이스라인이 $o(1)$의 확률로 유일한 해를 생성하므로, 그리고 모든 성공적인 온라인 알고리즘이 본질적으로 그러한 베이스라인과 일치해야 하므로, 온라인 알고리즘 자체의 성공 확률 또한 $o(1)$이다.

3. 주요 기여 및 결과

주요 정리

정리 1.1 (비형식적): 모든 제약 밀도 $\alpha > 0$와 마진 $\kappa$에 대하여, 모든 온라인 알고리즘은 이진 퍼셉트론의 고립된 해를 $o(1)$의 확률로 찾는다.

• 이 결과는 표준 이진 퍼셉트론에 적용되며, 대칭 이진 퍼셉트론(symmetric binary perceptron) 및 제약 집합이 분리된 기타 일반적인 퍼셉트론 모델로 확장된다.
• 고립 임계치는 $h = \omega(\log^4 n)$으로 완화되었는데, 이는 문헌에서 일반적으로 논의되는 선형 고립($\Omega(n)$)보다 훨씬 약한 조건임에도 불구하고, 이 결과가 견고함을 보여준다.

선행 연구와의 비교

• Gong, Huang, Li, and Sellke [GHLS26]: 이전에 안정적인(stable) 알고리즘(입력 재표집 시 출력이 약간만 변하는 알고리즘)이 고립된 해를 최대 약 0.84의 확률로 찾는다는 것을 보여주었다.
  • [GHLS26]의 한계: 이 바운드는 상수 값이며, 0으로 수렴하지 않는다. 즉, 0.8의 확률로 성공하는 알고리즘을 배제하지 못한다. 또한, 최신 알려진 온라인 알고리즘(예: Jo and Lee [JL26a])이 그들이 정의한 의미에서 안정적인지 여부도 불분명하다.
• 본 연구: 온라인 알고리즘을 위해 **사라지는 바운드(vanishing bound, $o(1)$)**를 제공한다. 이는 온라인 알고리즘이 고립된 해를 상수 확률로 찾을 가능성을 결정적으로 부정한다.

4. 의의 및 주장

본 논문은 이진 퍼셉트론 문제의 "통계적-계산적 간극(statistical-to-computational gap)"의 핵심적인 측면을 해결한다.

• 역설의 해결: 고립된 점들로 구성된 해 공간에도 불구하고 효율적인 온라인 알고리즘이 해를 찾는다는 외견상의 모순은, [BIL+15, BDVLZ20]에서 제기된 가설을 확인 함으로써 해결된다. 저자들은 온라인 알고리즘이 전형적인 고립된 해들을 찾을 수 없다는 것을 입증한다. 따라서 만약 이들이 성공한다면, 그것은 해 공간에 존재하는 지수적으로 드물지만 잘 연결된(well-connected) 해의 클러스터를 찾아내고 있는 것이 분명하다.
• 알고리즘적 난해함: 이 연구는 중첩 갭 속성(Overlap Gap Property, OGP) 프레임워크와 구별되는 온라인 알고리즘에 대한 새로운 난해성 결과를 확립한다. OGP가 안정적인 알고리즘에 대한 난해성을 증명하는 표준 도구인 반면, 저자들의 증명은 해들 사이의 중첩 기하학보다는 온라인 설정의 구조적 제약(돌이킬 수 없는 결정)과 반집중 특성에 의존한다.
• 범위: 이 결과는 불일치 최소화(discrepancy minimization) 및 퍼셉트론 학습에 사용되는 광범위한 알고리즘 클래스에 적용되며, 여기에는 최첨단 온라인 알고리즘인 Jo and Lee [JL26a]가 포함된다. 이는 해당 알고리즘들이 "동결된" 고립된 해의 지형을 탐색하는 데 본질적으로 능력이 없음을 확인해 준다.

요약하자면, 본 논문은 온라인 알고리즘의 성공이 지배적인 고립된 해를 찾는 능력보다는, 드물고 비고립된 해 클러스터의 존재와 접근성에 달려 있다는 것을 엄밀하게 증명한다.