기술 요약: 볼록 함수의 샘플링 및 재구성

1. 문제 정의

본 논문은 단위 큐브 $\Omega = [0, 1]^d$ 위에 정의된 다변량 볼록 함수에 대한 최적 복구(optimal recovery) 문제를 다룬다. $n$개의 점 샘플 $\Lambda = \{x_1, \dots, x_n\}$과 그에 대응하는 데이터 벡터 $w = (f(x_1), \dots, f(x_n))$가 주어졌을 때, 목표는 $L_p$ 노름($1 \le p \le \infty$)에서 최악의 경우의 복구 오차를 최소화하는 근사 함수 $\tilde{f}$를 구축하는 것이다.

연구는 두 가지 특정 모델 클래스인 볼록 함수에 집중한다:

1. 클래스 $B(\Omega)$: 1에 의해 균등하게 유계인 볼록 함수 ($|f(x)| \le 1$).
2. 클래스 $L(\Omega)$: 1에 의해 균등하게 유계이면서 서브그레이디언트(subgradient)가 균등하게 유계인 볼록 함수 ($|v| \le 1$ for all $v \in \partial f(x)$). 이는 1-립시츠(1-Lipschitz)인 것과 동치이다.

주요 목적은 가능한 모든 샘플 사이트의 선택과 모든 복구 알고리즘에 대한 최악의 경우 오차의 하한(infimum)으로 정의되는 샘플링 수(sampling numbers) $\rho_n(K)_{L_p}$를 결정하는 것이다. 또한, 복구 알고리즘이 선형으로 제한되는 선형 샘플링 수 $\rho_n^\ell(K)_{L_p}$에 대해서도 조사한다.

2. 방법론

저자들은 샘플링 수의 상한과 하한을 설정하기 위해 근사 이론, 볼록 기하학, 그리고 확률적 방법을 결합하여 사용한다.

2.1 텐서 곱 격자와 선형 방법

초기에 본 논문은 표준적인 **균등 텐서 곱 격자(uniform tensor product grids)**와 **조각별 다중 선형 보간(piecewise multilinear interpolation)**의 성능을 분석한다.

• 상한(Upper Bounds): 클래스 $L$의 경우, 균등 격자는 $r = 1 + 1/p$일 때 $O(n^{-r/d})$의 오차율을 보인다. 클래스 $B$의 경우, 동일한 비율을 달성하기 위해서는 비균등 텐서 격자(경계 근처에서 등급이 매겨진 격자)가 필요하다.
• 하한(Lower Bounds): 저자들은 텐서 곱 격자나 선형 복구 방식에 제한될 경우 이러한 비율이 최적임을 증명하기 위해 특정 반례("힌지(hinge)" 함수 또는 수정된 볼록 함수 사용)를 구성한다.

2.2 비선형 및 비텐서 샘플링

진정한 최적의 비율을 결정하기 위해, 논문은 텐서 격자를 넘어선다.

• 최적 집합의 존재성: 확률적 논증을 사용하여, 다음 두 가지 핵심적인 기하학적 성질을 만족하는 특정 데이터 사이트 집합 $\Lambda_n^*$ (이는 텐서 곱 격자가 아님)의 존재를 증명한다:
  1. 내부에 샘플 포인트가 없는 임의의 닫힌 볼록 집합은 부피가 $O(\frac{\log n}{n})$으로 유계이다.
  2. 해당 집합은 $\epsilon \approx n^{-1/d}$인 $\epsilon$-넷(net)을 형성한다.
• 오차 분석: 이 특정 사이트들에서 일치하는 두 볼록 함수 사이의 차이를 분석함으로써, 저자들은 샘플링 수에 대한 더 정밀한 상한을 도출한다. 이는 함수들이 서로 다른 영역을 볼록 집합으로 덮고, 서브그레이디언트 및 극 집합(polar sets)의 성질(마흘러의 부등식 참조)을 활용하는 과정을 포함한다.

2.3 구성적 복구 알고리즘

최적 비율의 존재성은 비구성적인 확률적 증명에 의존하지만, 섹션 6에서는 계산적으로 실행 가능하며 최적에 가까운 복구 알고리즘을 제안한다.

• 상한 성질(Supremum Property): 이 알고리즘은 클래스 $L$과 $B$가 점별 상한(pointwise suprema)에 대해 닫혀 있다는 사실을 이용한다.
• 정식화: 복구 맵 $A_\Lambda(w)$는 데이터 제약 조건(및 유계 제약 조건)을 만족하는 모델 클래스의 모든 함수들의 점별 상한으로 정의된다.
• 구현: 이 무한 차원 최적화 문제는 유한 차원 문제로 축소된다. 복구 함수는 데이터 제약(클래스 $B$의 경우 선형, 클래스 $L$의 경우 원뿔 제약)을 만족하는 **아핀 함수(affine functions)**들의 상한임이 밝혀졌다. 이를 통해 복구를 선형 계획법(클래스 $B$의 경우) 또는 원뿔 계획법(클래스 $L$의 경우)을 통해 계산할 수 있다.

3. 주요 기여 및 결과

3.1 표준 방법의 하위 최적성(Suboptimality)

볼록 함수의 경우, 고전적인 매끄러움 클래스(Sobolev 또는 Hölder 공간 등)에 대해 최적인 표준 절차들이 **하위 최적(suboptimal)**이라는 점은 핵심적인 발견이다.

• 텐서 격자: $1 < p < \infty$이고 $d \ge 2$인 경우, 균등 텐서 곱 격자에서 샘플링하면 $n^{-(1+1/p)/d}$의 비율을 얻는다. 그러나 최적의 비율은 이보다 빠르다.
• 선형 방법: 선형 복구 방법은 비선형 방법보다 현저히 떨어진다. 구체적으로 $p=2$일 때, 선형 샘플링 수는 $n^{-3/2d}$로 감소하는 반면, 최적의 비선형 비율은 (로그 인자를 제외하면) $n^{-2/d}$이다.

3.2 최적 샘플링 비율

본 논문은 (로그 인자를 제외한) 샘플링 수 $\rho_n(K)_{L_p}$의 최적 감소율을 확립한다:

• $1 \le p \le d$의 경우: 비율은 $n^{-2/d}$이다.
• $p \ge d$의 경우: 비율은 $n^{-(1+d/p)/d}$이다.
• 종합: 최적의 비율은 $\tilde{r} = \min\{2, 1 + d/p\}$인 $n^{-\tilde{r}/d}$로 특징지어진다.

이러한 비율은 특정 비텐서 곱 샘플링 집합과 비선형 재구성 방법을 사용하여 달성된다.

3.3 특정 사례

• $p=1$ 및 $p=\infty$: 텐서 곱 격자와 선형 방법을 사용하여 최적의 비율을 달성할 수 있다.
• $p=2$: 선형 샘플링 수 $\rho_n^\ell(L)_{L_2}$는 $n^{-3/2d}$로 감소하는 반면, 최적의 비선형 비율은 $n^{-2/d}$이다. 이는 볼록 함수에 대해 선형과 비선형 복구 사이에 상당한 격차가 있음을 강조한다.
• 클래스 $B$ 대 $L$: $L \subset B$이지만, $p < \infty$인 경우 두 클래스의 최적 샘플링 비율은 본질적으로 같다. 그러나 $p=\infty$인 경우, $B$의 샘플링 수는 0으로 감소하지 않는 반면($\rho_n(B)_{L_\infty} \asymp 1$), $L$의 경우 $n^{-1/d}$로 감소한다.

4. 의의 및 주장

본 논문은 볼록 함수의 샘플링 수에 대한 최적 감소율을 규명함으로써, 표준 격자 기반 방법과 이론적 최적치 사이의 불일치를 해결했다고 주장한다.

• 비선형성의 필수성: 본 연구는 볼록 함수의 경우, 비선형 재구성 방법이 대부분의 $p$ 값에 대해 선형 방법 및 표준 텐서 격자 샘플링보다 훨씬 더 우수함을 보여준다. 이는 고전적인 매끄러움 클래스에서 선형 방법과 균등 격자가 종종 최적인 것과는 대조적이다.
• 엔트로피와의 연결: 유도된 최적 샘플링 비율($p \le d$일 때 $n^{-2/d}$)은 이 클래스들의 엔트로피 수(entropy numbers) 감소율과 일치한다. 이는 볼록 함수의 샘플링 수가 엔트로피보다 더 빠르게 감소할 수 있는 일부 고전적 매끄러움 클래스와 달리, 엔트로피와 동일한 복잡도 척스에 의해 지배됨을 시사한다.
• 구성적 알고리즘: 논문은 (아핀 함수의 상한을 이용한) 볼록 최적화에 기반한 실용적이고 안정적이며 최적에 가까운 복구 알고리즘을 제공하며, 이는 노이즈가 있는 데이터에도 적용 가능하다.

저자들은 최적의 샘플 집합의 존재가 확률적 방법을 통해 증명되었지만, 그러한 집합의 명시적 구성은 여전히 열린 문제임을 언급한다. 다만, 제안된 복구 알고리즘은 어떤 사이트 세트에 대해서도 작동하며, 사이트가 이론적 요구 사항에 따라 선택될 경우 최적에 가까운 성능을 발휘한다.