2025-11-16T06:16:12.477685

Approximation theory for 1-Lipschitz ResNets

Murari, Furuya, SchÃ¶nlieb

1-Lipschitz neural networks are fundamental for generative modelling, inverse problems, and robust classifiers. In this paper, we focus on 1-Lipschitz residual networks (ResNets) based on explicit Euler steps of negative gradient flows and study their approximation capabilities. Leveraging the Restricted Stone-Weierstrass Theorem, we first show that these 1-Lipschitz ResNets are dense in the set of scalar 1-Lipschitz functions on any compact domain when width and depth are allowed to grow. We also show that these networks can exactly represent scalar piecewise affine 1-Lipschitz functions. We then prove a stronger statement: by inserting norm-constrained linear maps between the residual blocks, the same density holds when the hidden width is fixed. Because every layer obeys simple norm constraints, the resulting models can be trained with off-the-shelf optimisers. This paper provides the first universal approximation guarantees for 1-Lipschitz ResNets, laying a rigorous foundation for their practical use.

academic

1-Lipschitz ResNets의 근사 이론

기본 정보

논문 ID: 2505.12003
제목: Approximation theory for 1-Lipschitz ResNets
저자: Davide Murari (University of Cambridge), Takashi Furuya (Doshisha University, RIKEN AIP), Carola-Bibiane Schönlieb (University of Cambridge)
분류: cs.LG cs.NA math.NA
발표 학회: 39th Conference on Neural Information Processing Systems (NeurIPS 2025)
논문 링크: https://arxiv.org/abs/2505.12003v2

초록

본 논문은 음의 기울기 흐름의 명시적 오일러 단계를 기반으로 하는 1-Lipschitz 잔차 신경망(ResNets)의 근사 능력을 연구한다. 제한된 Stone-Weierstrass 정리를 활용하여, 너비와 깊이가 증가할 수 있을 때 이러한 1-Lipschitz ResNets이 임의의 컴팩트 영역에서 스칼라 1-Lipschitz 함수 집합에서 조밀함을 먼저 증명한다. 또한 이러한 네트워크가 스칼라 구간별 아핀 1-Lipschitz 함수를 정확히 표현할 수 있음을 증명한다. 더욱이 잔차 블록 사이에 노름 제약이 있는 선형 매핑을 삽입함으로써 숨겨진 너비가 고정되었을 때도 동일한 조밀성을 유지할 수 있다는 더 강한 결론을 증명한다. 각 계층이 간단한 노름 제약을 따르므로, 결과 모델은 기성 최적화기로 훈련될 수 있다.

연구 배경 및 동기

문제의 중요성

1-Lipschitz 신경망은 여러 중요한 분야에서 기초적인 역할을 한다:

생성 모델링: Wasserstein GAN의 판별기는 Kantorovich-Rubinstein 쌍대성을 통해 1-Wasserstein 거리의 효율적인 추정을 제공하기 위해 1-Lipschitz이어야 한다
역 문제: Plug-and-Play 알고리즘에서 1-Lipschitz 제약은 반복 방식의 수렴성을 보장한다
견고한 분류기: 네트워크의 Lipschitz 상수를 제어하면 적대적 공격에 대한 견고성을 향상시킬 수 있다

기존 방법의 한계

표현 능력 저하: 네트워크의 Lipschitz 상수를 제약하면 일반적으로 표현 능력이 감소하여 성능이 현저히 저하된다
이론 부재: 제약된 네트워크의 근사 특성에 대한 이해가 부족하며, 서로 다른 제약 전략은 현저히 다른 표현 능력을 생성할 수 있다
구현 어려움: 기존의 1-Lipschitz ResNet은 엄격한 이론적 보장이 부족하다

연구 동기

본 논문은 1-Lipschitz ResNets의 이론적 분석 공백을 메우고, 이러한 종류의 네트워크의 근사 능력을 이해하기 위한 엄격한 수학적 기초를 제공하며, 실제 응용을 위한 이론적 지원을 제공하는 것을 목표로 한다.

핵심 기여

첫 번째 통용 근사 정리: 1-Lipschitz ResNets에 대한 첫 번째 통용 근사 보장을 제공하며, 음의 기울기 흐름 기반 ResNets이 스칼라 1-Lipschitz 함수 집합에서 조밀함을 증명한다
고정 너비의 근사 결과: 노름 제약이 있는 선형 매핑을 도입함으로써, 고정된 네트워크 너비의 경우에도 통용 근사 특성을 유지할 수 있음을 증명한다
구성적 증명 방법: 제한된 Stone-Weierstrass 정리 기반 및 구간별 아핀 함수 기반의 두 가지 증명 전략을 제공한다
실용적 아키텍처 설계: 명확한 제약 조건을 가진 제안된 네트워크 아키텍처는 표준 최적화기로 훈련될 수 있다

방법 상세 설명

작업 정의

컴팩트 집합 $X \subset \mathbb{R}^d$ 에서의 1-Lipschitz 함수 공간 연구: $C_1(X,\mathbb{R}) = \{g : X \to \mathbb{R} \mid \|g(y) - g(x)\|_2 \leq \|y - x\|_2, \forall x,y \in X\}$

목표는 $C_1(X,\mathbb{R})$ 에서 조밀한 신경망 집합을 구성하는 것이다.

핵심 구성 블록

1-Lipschitz 잔차 계층

음의 기울기 흐름의 명시적 오일러 단계 기반: $\Phi_{\theta_\ell}(x) = x - \tau_\ell W_\ell^T \sigma(W_\ell x + b_\ell)$

여기서 $\sigma = \text{ReLU}$ 이고, 제약 조건: $0 \leq \tau_\ell \leq 2/\|W_\ell\|_2^2$ , $\|W_\ell\|_2 \leq 1$

네트워크 아키텍처 정의

무제한 너비 및 깊이의 네트워크 집합: $\mathcal{G}_{d,\sigma}(X,\mathbb{R}) = C_1(X,\mathbb{R}) \cap \{v^T \circ \Phi_{\theta_L} \circ \cdots \circ \Phi_{\theta_1} \circ Q : X \to \mathbb{R}\}$

고정 너비의 네트워크 집합: $\tilde{\mathcal{G}}_{d,\sigma,h}(X,\mathbb{R}) = \{v^T \circ \Phi_{\theta_L} \circ A_{L-1} \circ \cdots \circ A_1 \circ \Phi_{\theta_1} \circ Q : X \to \mathbb{R}\}$

여기서 $A_i$ 는 노름 제약이 있는 아핀 매핑이다.

기술적 혁신점

1. 이중 증명 전략

Stone-Weierstrass 방법: 네트워크 집합이 점을 분리하는 격자이며 제한된 Stone-Weierstrass 정리의 조건을 만족함을 검증한다
구성적 방법: 네트워크가 모든 구간별 아핀 1-Lipschitz 함수를 정확히 표현할 수 있음을 증명한다

2. 고정 너비의 혁신적 설계

특수한 잔차 계층 구조를 도입함으로써: $\tilde{\mathcal{E}}_{h,\sigma} = \left\{\Phi_\theta : \mathbb{R}^{h+3} \to \mathbb{R}^{h+3} \mid \Phi_\theta(x) = \begin{bmatrix} \max\{x_1, x_2\} \\ \min\{x_1, x_2\} \\ x_3 \\ \tilde{\Phi}_\theta(x_{4:}) \end{bmatrix}\right\}$

3. ReLU의 핵심 특성 활용

ReLU의 양의 동차성과 다음 항등식을 활용한다:

$x = \sigma(x) - \sigma(-x)$
$\max\{x,y\} = x + \sigma(y-x)$
$\min\{x,y\} = x - \sigma(x-y)$

실험 설정

데이터셋

Two-moon 데이터셋: 4000개 포인트, 표준편차 0.1의 가우시안 노이즈 추가, 20%를 훈련용으로 사용
MNIST 데이터셋: 표준 훈련/테스트 분할, 입력 정규화 처리

평가 지표

분류 정확도
제약 실행 시간 (에포크당 평균 시간)

구현 세부사항

최적화기: 코사인 어닐링 학습률 스케줄을 사용한 Adam 최적화기
배치 크기: 256
가중치 제약: 멱 방법을 사용한 스펙트럼 노름 추정으로 투영 기울기 하강을 통해 실행
초기화: 동적 등거리성 초기화 전략 채택

실험 결과

주요 결과

Two-moon 데이터셋 결과

계층 수	정리 3.1 아키텍처	정리 4.1 아키텍처
L=2	99.75%	88.25%
L=4	99.88%	99.88%
L=8	100.00%	99.88%
L=16	100.00%	100.00%
L=32	99.88%	100.00%
L=64	100.00%	100.00%

MNIST 데이터셋 결과 (정리 4.1 아키텍처)

너비\깊이	L=5	L=10	L=20
h=50	97.85%	97.67%	97.82%
h=100	97.94%	97.70%	97.58%
h=200	97.68%	97.77%	97.89%

실험 발견

훈련 안정성: 두 아키텍처 모두 안정적으로 훈련되며 네트워크 너비와 깊이의 영향을 받지 않는다
제약 비용: 아핀 계층이 있는 아키텍처는 더 높은 제약 비용을 가지며 깊이에 따라 더 빠르게 증가한다
성능 표현: 간단한 작업에서 완벽한 분류에 도달할 수 있으며 복잡한 작업에서도 좋은 성능을 보인다

이론적 분석

주요 정리

정리 3.1 (무제한 너비 깊이)

$d \in \mathbb{N}$ , $\sigma = \text{ReLU}$ , $X \subset \mathbb{R}^d$ 컴팩트라 하자. 그러면 $\mathcal{G}_{d,\sigma}(X,\mathbb{R})$ 는 $C_1(X,\mathbb{R})$ 의 통용 근사 특성을 만족한다.

정리 4.1 (고정 너비)

$d \in \mathbb{N}$ , $\sigma = \text{ReLU}$ , $X \subset \mathbb{R}^d$ 컴팩트라 하자. 그러면 $\tilde{\mathcal{G}}_{d,\sigma,d+3}(X,\mathbb{R})$ 는 $C_1(X,\mathbb{R})$ 의 통용 근사 특성을 만족한다.