어떤 방향이 중요한가? 아핀 강건 최적화 (Affine Robust Optimization)를 위한 희소 설계 (Sparse Design)

강건한 머신러닝 (Robust machine learning) 및 최적화 (optimization)는 불확실성 모델 (uncertainty model)의 선택에 의존합니다. 본 연구에서는 유한한 사전 (finite dictionary)과 예산 제약 (budget constraint)으로 정의될 때, 모델이 반드시 커버해야 하는 불확실성 방향 (uncertainty directions)이 무엇인지 조사합니다. 부분 집합을 선택함으로써 폐쇄형 지지 함수 (closed form support function)를 갖는 원자적 불확실성 집합 (atomic uncertainty set)을 형성하며, 이는 아핀 목적 함수 (affine objectives)에 대해 다루기 쉬운 강건 프로그램 (robust programs)을 생성합니다. 우리는 그래디언트 (gradients), 적대적 섭동 (adversarial perturbations), 또는 홀드아웃 데이터 (held out data)에서 관찰된 변화 (shifts)를 포함하여, 평가 방향 (evaluation directions)에 대한 커버리지 목적 함수 (coverage objective)를 기반으로 한 데이터 주도형 선택 규칙 (data driven selection rule)을 제안합니다. 우리는 이 목적 함수가 단조성 (monotone)과 부가성 (submodular)을 가짐을 증명하며, 이를 통해 $(1-1/e)$ 근사 보장 (approximation guarantee)과 일치하는 하드니스 장벽 (hardness barrier)을 갖는 탐욕법 (greedy method)을 지원합니다. 또한, 선택된 부분 집합으로부터의 손실 (loss)을 제한하는 인증서 (certificate)와 표본 외 제어 (out of sample control)가 가능한 반경 교정 규칙 (radius calibration rule)을 제공합니다.