쌍대 추적에서 클리핑까지: 이론적으로 입증 가능한 더 빠른 분포 강건 다중 목표 최적화
From Dual Tracking to Clipping: Provably Faster Distributionally Robust Multi-Objective Optimization
한국어 초록
다중 목표 최적화(MOO)는 여러 기준 하에서 학습이 요구되는 응용 분야에서 점점 더 많은 주목을 받고 있습니다. 그러나 기존의 대부분의 MOO 정식화는 데이터의 분포 변화(distributional shift)를 명시적으로 고려하지 않습니다. 본 논문에서는 각 목표의 최악의 경우 분포 하에서 여러 목표를 최소화하는 분포 강건 다중 목표 최적화(DR-MOO)를 도입합니다. 우리는 DR-MOO를 위한 파레토(Pareto) 형태의 해 개념을 제안하고, 이론적 보장이 동반된 다중 경사하강법(MGDA) 알고리즘을 개발합니다. 라그랑주 쌍대 재정식화(Lagrangian dual reformulation)를 활용하여, 먼저 내부 루프를 통해 쌍대 변수를 추정하고 $ε$-파레토-정상점($ε$-Pareto-stationary point)에 도달하기 위해 총 표본 복잡도(sample complexity) $\mathcal{O}(ε^{-8})$을 달성하는 이중 루프 MGDA를 설계합니다. 수렴 속도를 더욱 개선하기 위해, 대규모 배치(large-batch) 샘플링과 그래디언트 클리핑(gradient clipping)을 결합하여 일반화된 매끄러움(generalized smoothness)을 수용하고 확률적 선호도 업데이트의 바이어스를 제어함으로써 이중 샘플링의 필요성을 제거합니다. 이를 통해 표본 복잡도가 $\mathcal{O}(ε^{-4})$로 대폭 개선된 단일 루프 이중 클립 MGDA를 도출합니다. 우리의 이론은 쌍대 목표의 균일하게 유계된 그래디언트를 요구하지 않으면서 비볼록(nonconvex) 문제에 적용됩니다. 실험을 통해 본 제안 방법들이 최신 MGDA 베이스라인들과 견줄 만한 경쟁력을 갖추고 있음을 입증합니다.
원문 초록
Multi-objective optimization (MOO) has received growing attention in applications that require learning under multiple criteria. However, most existing MOO formulations do not explicitly account for distributional shifts in the data. We introduce distributionally robust multi-objective optimization (DR-MOO), which minimizes multiple objectives under their respective worst-case distributions. We propose Pareto-type solution concepts for DR-MOO and develop multi-gradient descent algorithms (MGDA) with provable guarantees. Leveraging a Lagrangian dual reformulation, we first design a double-loop MGDA that uses an inner loop to estimate dual variables and achieves a total sample complexity $\mathcal{O}(ε^{-8})$ for reaching an $ε$-Pareto-stationary point. To further improve convergence, we combine large-batch sampling with gradient clipping to accommodate generalized smoothness and control bias in stochastic preference updates, eliminating the need for double sampling. This yields a single-loop double-clip MGDA with substantially improved sample complexity $\mathcal{O}(ε^{-4})$. Our theory applies to nonconvex problems without requiring uniformly bounded gradients of the dual objectives. Experiments demonstrate that our methods are competitive with state-of-the-art MGDA baselines.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
편향된 샘플에서의 학습
Learning from a Biased Sample
데이터 기반 의사결정을 위한 경험적 위험 최소화 접근법은 결정 규칙이 배포될 때 직면하게 될 조건과 동일한 조건에서 추출된 학습 데이터에 대한 접근을 필요로 합니다. 그러나 일부 상황에서는, (관측 가능하거나 관측 불가능한 속성으로 특징지어지는) 일부 집단이 일반 모집단에 비해 과소 또는 과대 표현된다는 의미에서 학습 샘플에 바이어스가 있을 수 있으며, 이 경우 학습 세트에 대한 경험적 위험 최소화는 배포 시 잘 작동하는 규칙을 도출하지 못할 수 있습니다. 우리는 조건부 Γ-편향 샘플링이라는 샘플링 바이어스 모델을 제안하는데, 여기서 관측된 공변량은 샘플 선택 확률에 임의로 크게 영향을 미칠 수 있지만 샘플 선택 확률의 설명되지 않는 변동량은 상수 인자로 제한됩니다. 분포적 강건 최적화(distributionally robust optimization) 프레임워크를 적용하여, Γ-편향 샘플링 하에서 학습 분포를 생성할 수 있는 테스트 분포 집합에서 발생하는 최악의 위험을 최소화하는 결정 규칙을 학습하는 방법을 제안합니다. Rockafellar와 Uryasev의 결과를 적용하여 이 문제가 증강된 볼록 위험 최소화 문제와 동치임을 보입니다. 체 방법(method of sieves)을 통해 샘플링 바이어스에 강건한 모델 학습에 대한 통계적 보장을 제공하고, 손실 함수가 강건 학습 목표를 포착하는 심층 학습 알고리즘을 제안합니다. 건강 설문 데이터로부터 정신 건강 점수 예측에 관한 사례 연구와 ICU 재원 기간 예측에 관한 사례 연구를 통해 제안된 방법을 실증적으로 검증합니다.
지지 비지배점에 의한 다목적 네트워크 문제의 비지배 집합 표현
Representing the Non-dominated Set of Multi-objective Network Problems by Supported Non-dominated Points
다목적 조합 최적화에서 비지지 비지배점(unsupported non-dominated point)은 통상 지지점(supported point)보다 수가 많으며, 계산하기도 훨씬 어려운 경우가 많다. 최근 연구에 따르면 극단 지지 비지배점(extreme supported non-dominated point)은 특정 이진 문제의 비지배 집합에 대해 고품질 표현을 제공한다. 본 논문에서는 이 관찰이 용량 제한 네트워크 최적화 문제로 일반화되지 않음을 보인다. 즉, 호(arc) 용량이 증가할수록 표현 품질이 저하되는 반면, 지지 비지배점은 여러 품질 지표에서 지속적으로 고품질 표현을 제공한다. 그러나 지지점 집합도 실용적인 응용에서는 지나치게 클 수 있으며, 일반적으로 소수의 고정된 대안만이 요구된다. 비지배 집합에서 고정 크기 표현을 선택하려면 계산 비용이 높은 전체 집합 생성이 필요하므로, 표현이 제공하려는 계산 상의 이점이 감소한다. 따라서 본 논문은 부분집합 선택 문제에서 (극단) 지지점을 대안적 후보 집합으로 제안한다. 수치 실험 결과, 후보 집합을 지지 비지배점으로 제한하더라도 완전한 비지배 집합에서 선택한 것과 거의 동일한 품질의 고정 크기 표현을 얻을 수 있음을 보인다. 종합하면, 지지 비지배점은 고품질 표현이자 부분집합 선택을 위한 합리적인 후보 집합으로 모두 활용될 수 있다.
미관측 교란 변수에 강건한 위험 점수 학습
Learning Risk Scores Robust to Unobserved Confounders
미관측 교란의 영향을 받는 역사적 관찰 데이터로부터, 희소 자원이나 개입 대상 개인의 우선순위를 정하기 위한 위험 점수를 학습하는 문제를 다룬다. 누가 희소 자원을 받을지에 대한 결정은 설문 응답과 같이 기록된 특성에 기반한 위험 점수에 의해 종종 안내된다. 이러한 위험 점수는 개인의 특성, 배분 결정, 결과에 대한 역사적 기록인 관찰 데이터로부터 직접 학습되는 경우가 점점 늘고 있다. 역사적 배분 정책이 도입한 바이어스를 보정하는 역 성향 가중치(inverse propensity weighting, IPW)와 같은 표준 방법은, 역사적 결정 과정이 기록된 특성으로 완전히 설명될 수 있다면 정확한 위험 점수를 학습하는 데 사용될 수 있다. 그러나 실무에서는 역사적 결정이 종종 기록되지 않은 정보에 의존하여, 학습된 위험 점수가 과거 우선순위를 이끌었던 기록되지 않은 상황을 가진 개인들을 정확히 체계적으로 과소 우선순위화하게 만든다. IPW를 기반으로, 이러한 종류의 미관측 교란에 강건한 위험 점수를 학습하는 방법을 제안한다. 미관측 교란 하에서는 성향 가중치를 신뢰할 수 있게 추정할 수 없으므로, 대신 관측 가능한 데이터와 교란 정도에 대한 도메인 정보 기반 추정치로 결정되는 불확실성 집합에 속하는 것으로 취급하며, 인과 추론(causal inference)의 민감도 분석(sensitivity analysis)과 Wasserstein 분포적 강건 최적화(Wasserstein distributionally robust optimization)를 결합한다. 그 결과 강건 위험 점수 학습 문제는 표본 기반 근사를 허용하며, 이를 기성 솔버와 호환되는 지수 원뿔 프로그램(exponential cone program)으로 재공식화한다. UCI Machine Learning Repository의 데이터셋에서 파생된 반합성(semi-synthetic) 데이터에서 접근법의 효과를 입증한다. 제안 방법은 다른 지표를 손상하지 않으면서, 전통적 벤치마크 대비 보정(calibration)을 최대 29.2%까지, 최신(state of the art) 대비 최대 11.1%까지 개선한다.
FedPCD: 우선순위 제약 기반 연합 집계
FedPCD: Priority-Constrained Federated Aggregation
연합학습(FL)은 분산된 클라이언트 데이터로부터 공유 글로벌 모델을 최적화하는 것을 목표로 합니다. 이러한 방식은 평균 성능에는 효과적이지만, 특히 통계적으로 이질적인(heterogeneous) 데이터 분포 하에서는 클라이언트 간에 불공정한 성능을 초래할 수 있습니다. 기존의 공정성 인식 및 다중 목적 연합학습 방법들은 클라이언트 재가중치 부여(re-weighting), 그래디언트(gradient) 보정, 또는 공통 하강(common-descent) 정식화를 통해 이를 다루지만, 종종 글로벌 최적화 방향을 변경하거나 클라이언트의 목적을 대칭적으로 취급합니다. 본 논문에서는 글로벌 최적화 목적과 클라이언트 보호를 분리하는 우선순위 제약 연합 최적화 프레임워크인 FedPCD를 제안합니다. FedPCD는 기존의 연합 집계를 기본(primary) 목적으로 보존하면서, 클라이언트 성능 제약을 충족하는 데 필요한 최소한의 보정만을 허용합니다. 이질적인 연합학습 벤치마크 전반에서 FedPCD는 최신(SOTA) 베이스라인들을 일관되게 능가하여 모든 구성에서 가장 높은 글로벌 정확도를 달성하고 거의 모든 구성에서 하위 10% 클라이언트 정확도를 선도했습니다. 나아가 FedPCD는 글로벌 정확도와 클라이언트 성능 변동성 사이에서 경쟁력 있는 트레이드오프를 유지합니다. 이러한 트레이드오프를 넘어, FedPCD는 훨씬 적은 통신 라운드로 동등하거나 우수한 성능에 도달하며 더 빠른 실증적 수렴을 입증합니다.
프라이버시가 보호되고 분포에 강건한 연합 다중 클래스 분류
Private and Distributionally Robust Federated Multiclass Classification
자산 집약적 산업에서의 고장 진단은 지리적으로 분산된 클라이언트 현장에서 수집된 노이즈가 많고 민감한 데이터로 학습(training)된 다중 클래스 모델(model)을 필요로 합니다. 연합학습(Federated Learning)은 데이터를 중앙 집중화하지 않고도 협업 학습을 가능하게 하지만, 대부분의 접근 방식은 클라이언트 현장에 저장된 개별 레코드에 대한 정형화된 프라이버시 보장을 제공하지 않으며 레이블 노이즈 하에서 성능이 저하될 수 있습니다. 이러한 한계를 해결하기 위해, 본 연구에서는 각 클라이언트에 저장된 레코드에 대해 샘플 수준의 프라이버시를 제공하는 차분 프라이버시 기반의 분포 강건 연합 다중 클래스 분류(classification) 프레임워크를 개발합니다. 본 연구는 교대 방향 승수법(ADMM) 기반 알고리즘으로 해결되는 Crammer-Singer 손실(loss)을 적용한 연합 바서슈타인 분포 강건(Wasserstein distributionally robust) 다중 클래스 목적 함수를 기반으로 구축됩니다. 공개되는 클라이언트 업데이트를 보호하기 위해, 제안하는 기법은 중앙 서버에서 집계되기 전에 로컬 모델과 로컬 분포 강건 변수 모두의 근접 선형화된 클라이언트 업데이트에 보정된 가우시안 노이즈를 주입하며, 모멘트 어카운턴트(moments accountant)를 사용하여 누적 프라이버시 손실을 정량화합니다. 본 연구는 수렴(convergence) 결과 및 명시적인 프라이버시-유용성 트레이드오프와 함께 라운드당 샘플 수준의 $(ε,δ)$-차분 프라이버시 보장과 전체 학습 라운드에 걸친 종합적인 합성 프라이버시 보장을 제공합니다. 시뮬레이션된 산업 고장 데이터 및 UCI 벤치마크 데이터셋에 대한 실험을 통해, 제안하는 기법이 대부분의 테스트 설정에서 차분 프라이버시 연합 경험적 위험 최소화 및 확률적 경사하강법(gradient descent) 베이스라인보다 우수한 성능을 보이며, 강력한 프라이버시 유도 노이즈 하에서 가장 큰 향상을 나타냄을 보입니다.
기하학적 구조를 고려한 다중 목적 최적화: 엔트로피 기반 가중치 업데이트를 적용한 노름 제약 오라클
Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates
다중 경사하강법(Multiple-gradient descent)은 일반적으로 유클리드 기하학에서 공식화되는 반면, 행렬 인식 옵티마이저는 다른 노름(norm)에 의해 유도된 방향을 사용합니다. 본 논문에서는 노름 제약이 있는 선형 최소화 오라클과 태스크 가중치의 엔트로피 업데이트를 결합한 단일 루프 다중 목적 최적화 기법을 분석합니다. 유한 차원 노름 쌍에 대해 결정론적 환경에서 $O(T^{-1/2})$의 에르고딕 정지성(ergodic stationarity) 수렴 속도를 확립하며, 비정규화된 경우 평활성(smoothness) 및 하한 유계성으로부터 필요한 궤적 그래디언트 경계를 유도합니다. 확률적 그래디언트와 유계 그래디언트 가정 하에서는 단일 지속 혼합 그래디언트 모멘텀 버퍼를 통해 선행 항이 태스크 수에 명시적으로 의존하지 않는 $O(T^{-1/4})$ 수렴 속도를 산출합니다. 또한 임의의 유계 그래디언트 시퀀스에 대해 내부 가중치 목적식의 정적 리그릿(static regret)을 확립하고, 엔트로피 정규화와 가중치 하한(weight floor)을 적용하여 궤적 그래디언트 경계를 조건으로 에르고딕 정지성을 유지하면서 웜업(burn-in) 이후 반복별 내부 갭 제어를 달성합니다. 최적의 혼합 그래디언트는 스펙트럼 및 부호 기하학에서 유일하지 않을 수 있으므로, 선택에 독립적인 내부 갭의 필요성을 부여합니다. 본 분석은 동시 연구인 MOON에서 연구된 스펙트럼 구성을 일반적인 노름으로 확장합니다. 실험을 통해 기존 멀티태스크 옵티마이저와 제안 방법을 비교하고 오라클, 가중치 부여 및 모멘텀 선택을 검토합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
47 pages