The $L_1$-Discrepancy with Nonnegative Weights Suffers from the Curse of Dimensionality

당신이 복잡한 시스템의 모든 가능한 선택 조합을 나타내는 거대한 다차원 캔버스에 그림을 그리려 한다고 상상해 보세요. 컴퓨터 과학과 수학의 세계에서 이 '캔버스'는 종종 하이퍼큐브(hypercube), 즉 온도, 속도, 가격과 같은 서로 다른 변수를 나타내는 각 면을 가진 상자로 표현됩니다. 이 시스템이 어떻게 작동하는지 이해하기 위해, 수학자들은 **준 몬테카를로 적분(Quasi-Monte Carlo integration)**이라는 기법을 사용합니다. 이것은 캔버스 전체의 그림을 샘플링하기 위해 유한한 수의 '점(dots)'을 뿌리는 것과 같습니다. 목표는 이 점들을 완벽하게 선택하여 공간을 고르게 덮음으로써, 모든 구석구석을 일일이 확인하지 않고도 정확한 평균값을 얻는 것입니다.

문제는 변수가 늘어남에 따라(상자의 차원이 높아짐에 따라) 공간이 폭발적으로 커진다는 점입니다. 이는 **차원의 저주(curse of dimensionality)**라고 알려져 있습니다. 이는 마치 새로운 차원이 추가될 때마다 크기가 두 배로 커지는 해변에서 특정 모래알 하나를 찾는 것과 같습니다. 갑자기 해변이 우주보다 더 커져 버리는 것이죠. 점들이 이 공간을 얼마나 잘 덮고 있는지를 측정하기 위해, 수학자들은 **불일치도(discrepancy)**라는 지표를 사용합니다. 불일치도가 낮으면 점들이 완벽한 격자처럼 고르게 퍼져 있다는 뜻입니다. 반대로 높다면, 마치 쏟아진 구슬 주머니처럼 뭉쳐 있다는 뜻입니다. 때때로 단순히 점을 배치하는 대신, 우리는 점들에 '가중치(weights)'를 부여하여(어떤 점에 더 많은 중요성을 부여하는 것처럼) 불균형을 해결하려고 시도하기도 합니다. 여기서 핵심적인 질문은 이것입니다. 우리가 이 영리한 가중치들을 사용하여 차원의 저주를 극복하고 고차원 공간을 효율적으로 덮을 수 있을까요?

Josef Dick이 작성한 이 논문은 이러한 종류의 가중치에 대해 이 질문에 대한 확정적인 "아니오"를 전달합니다. 저자는 비음수 가중치(nonnegative weights)(즉, 어떤 점의 중요성은 높일 수 있지만, 다른 점을 상쇄하기 위해 음수를 사용할 수는 없는 경우)를 사용하는 경우에도 차원의 저주를 피할 수 없음을 증명합니다. 이 논문은 차원이 증가함에 따라 요구되는 점의 개수가 기하급수적으로 늘어난다는 수학적 증명을 제시합니다. 이것은 단순한 제안이나 시뮬레이션이 아닙니다. 그것은 엄밀한 수학적 정리입니다. 이 결과는 이러한 특정 규칙 하에서는 문제가 너무 빠르게 복잡해지기 때문에, 아무리 영리하게 가중치를 할당하더라도 고차원 공간을 해결하는 것이 실질적으로 불가능함을 의미합니다.

정복할 수 없는 상자의 이야기

이것이 왜 그렇게 중요한 일인지 이해하기 위해, 수학자가 사용한 도구들을 살펴봅시다. 당신이 점들이 얼마나 '뭉쳐 있는지'를 측정하는 마법의 저울을 가지고 있다고 상상해 보세요. 이 논문의 세계에서 이 저울은 **$L_1$-불일치도($L_1$-discrepancy)**라고 불립니다. 점들이 완벽하게 퍼져 있다면 저울은 0을 가리킵니다. 점들이 엉망이라면 저울은 더 높은 숫자를 나타냅니다. 목표는 이 숫자를 아주 작게 유지하는 것입니다.

오랫동안 수학자들은 만약 동일한 가중치를 사용해야 한다면(모든 점이 정확히 1의 가치를 갖는 경우), 차원의 저주는 피할 수 없다는 것을 알고 있었습니다. 100차원의 상자를 덮으려면 천문학적인 수의 점이 필요할 것입니다. 하지만 한 가지 미련 섞인 희망이 있었습니다. 만약 우리가 비음수 가중치를 허용한다면—즉, 어떤 점은 2나 3의 '슈퍼 파워'를 주고 다른 점은 0.5의 가치를 주는 식으로—시스템을 속일 수 있지 않을까 하는 희망 말입니다. 적절한 점들이 더 큰 가치를 갖게 함으로써 더 적은 수의 점으로 문제를 해결할 수 있지 않을까요?

Josef Dick의 논문은 이 문을 단호하게 닫아버립니다. 이 증명은 관점의 변화를 이용한 일종의 탐정 이야기와 비슷합니다. 저자는 점들을 일반적인 방식으로 보는 대신, '확률 측도(probability measure)'를 바꿉니다. 이는 문제를 바라보는 렌즈를 바꾸어 문제의 규칙을 변경하는 세련된 방식입니다. 그는 '부피 편향적(volume-biased)' 관점을 도입하는데, 이는 본질적으로 점들이 목표를 놓칠 가능성이 가장 높은 상자의 모서리 부분으로 줌인(zoom-in)하는 것입니다.

이 논증의 핵심을 단순화하면 다음과 같습니다:

1. 설정: 저자는 논의를 위해, 누군가가 고차원에서 완벽하게 작동하는 마법 같은 점과 가중치를 찾아냈다고 가정합니다.
2. 함정: 그런 다음 그는 '분수 모멘트(fractional moments)'(작은 값에 민다는 평균 방식)를 이용한 수학적 트릭을 사용하여, 만약 그러한 완벽한 집합이 존재한다면 그것이 수학의 근본적인 규칙을 위반하게 될 것임을 보여줍니다.
3. 결과: 수학적 계산은 좋은 결과를 얻기 위해 필요한 점의 개수 $N$이 적어도 특정 숫자의 $d$제곱 이상이어야 함을 보여줍니다. 구체적으로, 이 논문은 임의의 작은 오차 허용 범위 $\varepsilon$에 대해, 필요한 점의 개수 $N$이 적어도 다음 식을 만족해야 함을 증명합니다:
   $$N \ge (1 - \varepsilon)^{\frac{2}{1 + \varepsilon}} \left( \frac{3 + 2\sqrt{3}}{6} \right)^d$$
   여기서 $\frac{3 + 2\sqrt{3}}{6}$은 약 1.077입니다.

이것이 평범한 언어로 무엇을 의미할까요? 이는 차원이 하나 추가될 때마다, 이전보다 대략 1.077배 더 많은 점이 필요하다는 것을 의미합니다. 1.077이라는 숫자가 별로 커 보이지 않을 수도 있지만, 지수적 성장(exponential growth)의 세계에서는 재앙입니다. 만약 10차원에서 100차원으로 넘어간다면, 이 작은 승수는 우주의 원자 수를 초과하는 엄청난 숫자로 변합니다.

이 논문은 자신이 다루지 않는 범위에 대해서도 매우 신중합니다. 이 논문은 음수 가중치의 사용을 명시적으로 제외합니다. 만약 음수를 사용할 수 있다면(어떤 점에 '반물질' 같은 무게를 주어 뭉친 부분을 상쇄하는 방식), 이야기는 달라질 수도 있습니다. 하지만 많은 물리적, 금융적 모델이 존재하는 실제 세상에서는 음수 가중치를 사용할 수 없으며, 반드시 0 또는 양수여야 합니다. 이 논문이 모든 비음수 가중치에 대해 차원의 저주가 적용됨을 증명함으로써, 이러한 실제 시나리오에서 지수적인 난이도의 폭발은 피할 수 없음을 확정 짓습니다.

따라서 호기심 많은 십 대를 위한 교훈은 이것입니다: 고차원의 세계에서는 단순히 '가중치'를 조절한다고 해서 문제를 해결할 수 없습니다. 점들을 어떻게 배치하든, 혹은 그 중요성을 얼마나 높이든(양수를 유지하는 한), 공간의 압도적인 크기가 항상 승리할 것입니다. '차원의 저주'는 단순한 소문이 아니라, 이러한 유형의 문제에 대한 수학적 법칙입니다. 이 논문은 단순히 암시하는 것이 아니라, 어떤 여지도 남기지 않는 철저한 논리로 이를 증명합니다. 단순한 가중치 점들을 사용하여 이 거대하고 다차원적인 퍼즐을 풀 수 있는 지름길을 찾겠다는 꿈은 공식적으로 끝났습니다.