Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

기술적 요약: 비매끄러운 서브모듈러-오목 함수의 오프라인 및 온라인 미니맥스 문제 해결

문제 공식화
본 연구는 다음과 같은 형태의 혼합 정수 미니맥스 및 맥스민 최적화 문제를 다룹니다:
$$\max_{y \in Y} \min_{S \subset Q} f(S, y) \quad \text{및} \quad \min_{S \subset Q} \max_{y \in Y} f(S, y)$$
여기서 $Q = [n]$은 $n$개의 원소로 구성된 기본 집합이며, $2^Q$는 멱집합을 나타내고, $Y \subset \mathbb{R}^m$은 컴팩트한 볼록 집합입니다. 목적 함수 $f: 2^Q \times \mathbb{R}^m \to \mathbb{R}$은 집합 변수 $S$에 대해 서브모듈러이고 연속 변수 $y$에 대해 오목하다고 가정합니다. 특히, 이 함수는 두 변수 모두에 대해 비매끄러운(미분 불가능한) 것이 허용됩니다. 저자들은 쌍대 간격이 $\epsilon$으로 제한되는 $\epsilon$-안장점, 즉 쌍 $(\bar{S}, \bar{y})$를 계산하는 것을 목표로 합니다.

방법론
제안된 접근법은 엑스트라그래디언트 (extragradient) 방법에 기반한 0 차 (Zeroth-Order, ZO) 프레임워크를 활용합니다. 이 방법론은 비매끄러움과 혼합 변수 구조를 처리하기 위해 두 가지 주요 기술에 의존합니다:

1. 서브모듈러성을 위한 로바스 (Lovász) 확장: 이산 서브모듈러 구성 요소를 처리하기 위해 저자들은 서브모듈러 집합 함수를 하이퍼큐브 $[0, 1]^n$ 위의 연속적인 볼록 함수로 매핑하는 로바스 확장 $f^L$을 활용합니다. 집합 변수에 대한 $f^L$의 서브그래디언트는 함수 평가 (부분 집합의 최대 체인을 통해) 만을 사용하여 계산할 수 있으므로 고차 정보의 필요성을 피할 수 있습니다.
2. 오목성을 위한 가우스 평활화: 함수가 비매끄러울 수 있는 연속 오목 변수 $y$에 대해 저자들은 가우스 평활화를 적용합니다. 그들은 2 점 추정기를 사용하여 평활화된 함수의 그래디언트를 근사하는 랜덤 오라클을 정의합니다. 이를 통해 명시적으로 도함수에 접근하지 않고도 그래디언트 기반 업데이트가 가능해집니다.

결과적으로 생성된 알고리즘 (알고리즘 1, ZO-EG) 은 반복 루프에서 작동합니다:

• 전진 단계: 현재 반복점 $z_k = (x_k, y_k)$에서 연산자를 추정하기 위해 가우스 방향을 샘플링하여 $y$에 대한 랜덤 오라클을 계산하고 $x$에 대한 서브그래디언트를 계산합니다.
• 외삽 단계: 미리보기 (lookahead) 점 $\hat{z}_k$로 하강 단계를 수행합니다.
• 업데이트 단계: $\hat{z}_k$에서 연산자를 재추정하고 두 번째 하강 단계를 수행하여 $z_{k+1}$을 업데이트합니다.

이 방법은 함수 값 쿼리 (0 차 정보) 만을 필요로 하며, 그래디언트나 서브그래디언트에 직접 접근할 수 있다고 가정하지 않습니다.

주요 기여 및 이론적 결과
본 논문은 오프라인 및 온라인 설정 모두에 대한 수렴 보장을 제공합니다:

• 오프라인 수렴: 저자들은 알고리즘이 기대값으로 $\epsilon$-안장점으로 수렴함을 증명합니다. 총 샘플 복잡도는 $O(nm^2\epsilon^{-2})$임이 입증되었으며, 여기서 $n$은 기본 집합의 크기이고 $m$은 연속 변수의 차원입니다. $n$에 대한 의존성은 로바스 확장 서브그래디언트 계산의 반복당 비용에서 비롯되며, 반복 횟수는 $m$에 의존합니다.
• 온라인 수렴: 비용 함수 $f_k$가 시간에 따라 변하는 온라인 설정에서 알고리즘은 기대 온라인 쌍대 간격 $O(\sqrt{N \bar{P}_N})$을 달성합니다. 여기서 $N$은 반복 횟수이고 $\bar{P}_N$은 최적 결정 시퀀스의 경로 길이입니다. 이 결과는 온라인 최적화에서 확립된 동적 후회 (dynamic regret) 경계와 일치합니다.
• 해의 존재성: 본 논문은 특히 확장의 최소화자가 하이퍼큐브의 꼭짓점에 있을 때, 확장의 연속 해와 관련하여 원래 이산 문제에 대한 안장점이 존재하는 조건을 논의합니다.

수치적 결과 및 응용
이론적 발견은 적대적 이미지 분할과 반감독 클러스터링에 중점을 둔 수치 예시를 통해 설명됩니다:

• 오프라인 적대적 분할: 이 방법은 시드 픽셀의 신뢰 가중치를 적대자가 교란시키는 미니맥스 문제에 적용됩니다. 알고리즘은 적대적 교란에 대한 견고성을 보여주며, 실제 지면 (ground truth) 과 일치하는 분할을 성공적으로 복원합니다.
• 온라인 적대적 분할: 이 알고리즘은 모양과 클러스터가 이동하고 회전하여 매 프레임마다 비용 함수가 변경되는 비디오 스트림에서 테스트되었습니다. 이 방법은 사전 훈련 없이 실시간 분할 (CPU 에서 약 80 fps) 을 수행합니다.
• 딥러닝과의 비교: 온라인 적대적 설정에서 제안된 ZO 방법은 Intersection over Union (IoU), 정밀도, 재현율 측면에서 감독 및 반감독 훈련된 U-Net 모델 모두를 능가합니다. 특히 ZO 방법은 사전 훈련이 필요 없으며, 메모리 사용량이 U-Net(8 MB) 에 비해 현저히 적습니다 (0.05 MB), 그리고 대규모 데이터 세트에 접근할 수 없는 미지의 환경에서도 효과적으로 작동합니다.

의의 및 주장
저자들은 이것이 비매끄러운 서브모듈러-오목 비용 함수를 가진 미니맥스 최적화 문제를 해결하는 첫 번째 연구라고 주장합니다. 이 연구의 의의는 다음과 같습니다:

1. 격차 해소: 매끄러움의 부재와 혼합 이산 - 연속 특성으로 인해 이전에 해결하기 어려웠던 일종의 조합 미니맥스 문제를 다룹니다.
2. 0 차 효율성: 전통적으로 연속 비매끄러운 문제에 사용되던 0 차 방법이 로바스 확장을 통해 서브모듈러 최적화에 효과적으로 적응될 수 있음을 보여줍니다.
3. 견고성과 효율성: 수치적 결과는 이 접근법이 사전 훈련이 불가능하거나 환경이 비정상적인 실시간, 자원 제약, 그리고 적대적 환경에서 딥러닝에 대한 실현 가능한 대안을 제공함을 시사합니다.

본 논문은 향후 연구가 이러한 해와 혼합 전략 내시 균형 사이의 관계를 탐구하고, 결과를 서브모듈러-서브모듈러 비용 함수로 확장하며, 비제한 제약 집합을 조사할 수 있음을 언급하며 마무리합니다.