비평활 서브모듈러-오목 함수의 오프라인 및 온라인 최소-최대 문제 해결: 영차(Zeroth-Order) 접근법
Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
한국어 초록
우리는 최소화 변수에 대해 서브모듈러(submodular)이고 최대화 변수에 대해 오목(concave)이며, 비평활(non-smooth)할 수 있는 목적 함수를 갖는 최대-최소(max-min) 및 최소-최대(min-max) 문제를 고려한다. 우리는 이 문제에 적용된 영차(zeroth-order) 방법의 성능을 조사한다. 이 방법은 최소화 변수에 대한 목적 함수의 로바스 확장(Lovász extension)의 서브그래디언트(subgradient)와, 최대화 변수에 대한 평활화된 함수의 그래디언트(gradient)를 추정하기 위한 가우시안 스무딩(Gaussian smoothing)에 기반한다. 기댓값의 의미에서, 우리는 오프라인의 경우 알고리즘이 ε-안장점(saddle point)으로 수렴(convergence)함을 증명한다. 더 나아가, 우리는 온라인 설정에서 기댓값의 의미로 알고리즘이 $O(\sqrt{N(1+\bar{P}_N)})$의 온라인 듀얼리티 갭(duality gap)을 달성함을 보인다. 여기서 $N$은 반복 횟수이고 $\bar{P}_N$은 최적 결정 시퀀스의 경로 길이(path length)이다. 모든 경우에 대한 복잡도 분석과 하이퍼파라미터(hyperparameter) 선택이 제시된다. 이론적 결과는 수치 예제를 통해 설명된다.
원문 초록
We consider max-min and min-max problems with objective functions that are possibly non-smooth, submodular with respect to the minimiser and concave with respect to the maximiser. We investigate the performance of a zeroth-order method applied to this problem. The method is based on the subgradient of the Lovász extension of the objective function with respect to the minimiser and based on Gaussian smoothing to estimate the smoothed function gradient with respect to the maximiser. In expectation sense, we prove the convergence of the algorithm to an $ε$-saddle point in the offline case. Moreover, we show that, in the expectation sense, in the online setting, the algorithm achieves $O(\sqrt{N(1+\bar{P}_N)})$ online duality gap, where $N$ is the number of iterations and $\bar{P}_N$ is the path length of the sequence of optimal decisions. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
신경망 집합 함수의 완화 학습을 통한 최적 부분집합 오라클 발전
Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions
신경망 집합 함수 학습은 AI 기반 신약 개발에서의 화합물 선택 및 제품 추천을 포함한 광범위한 중요 응용 분야에서 핵심적인 역할을 한다. 최근 연구에서는 실용적인 약지도(weakly supervised) 설정하에서 집합 함수를 암묵적으로 학습하기 위한 최적 부분집합 오라클(optimal subset oracle)을 도입하였으며, 모델 파라미터는 평균장 변분 추론(mean-field variational inference)을 통해 최적화된다. 그러나 이러한 프레임워크는 변분 분포를 업데이트할 때 증거 하한(evidence lower bound, ELBO)의 그래디언트를 추정하기 위해 몬테카를로 샘플링에 의존한다. 반복적인 샘플링은 상당한 계산 오버헤드를 초래하며, 이로 인한 확률적 특성은 최적화 궤적을 불안정하게 만들 수 있다. 본 연구에서는 증거 하한을 집합 함수의 연속 완화(continuous relaxation)로 재해석하고, 변분 최적화 과정에서 샘플링 기반 ELBO 그래디언트 추정을 대체하는 대리 목적 함수(surrogate objective)를 학습한다. 학습된 대리 함수는 연속 도메인 전반에 걸쳐 안정적이고 효율적인 그래디언트를 제공함으로써 계산 오버헤드를 줄이고 추론을 가속화한다. 아울러, 부분모듈러 최대화(submodular maximization) 하에서 제안된 프레임워크에 대한 근사 보장을 확립하고, 변분 자유 에너지(variational free energy)와의 연관성을 규명한다. 다양한 실제 태스크에 대한 실험 결과, 기존 베이스라인 대비 일관된 성능 향상이 확인되었다.
공정 예산 연속 및 이산 벤치마크에서 MMAO의 대규모 실증 평가
A Large-Scale Empirical Evaluation of MMAO Under Fair-Budget Continuous and Discrete Benchmarks
MMAO: Mechanism and Stability Analysis of Metabolic Closed-Loop Metaheuristics
제약 조건이 있는 비평활 비볼록 확률적 최적화를 위한 최적 알고리즘
Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
본 논문에서는 볼록 제약 집합 하에서 목적 함수가 평활(smooth)하지도 볼록(convex)하지도 않은 확률적 최적화(stochastic optimization) 문제를 위한 새로운 알고리즘을 제시합니다. 제안하는 알고리즘은 제약이 있는 문제에 대해 Liu et al. (2024)이 최근 정의한 $(δ,\varepsilon)$-골드스타인 정상점($(δ,\varepsilon)$-Goldstein stationary point)을 향상된 복잡도로 반환하며, 여러 설정에서 이 작업에 대해 최초로 최적의 수렴(convergence) 속도를 달성합니다. 구체적으로, 확률적 기울기(stochastic gradient)를 사용하여 최적임을 증명한 $\widetilde O(δ^{-1}\varepsilon^{-3})$ 속도를 달성하는 투영 기반(projection-based) 및 무투영(projection-free) 알고리즘을 설계하고, 0차 쿼리(zeroth-order queries)를 사용하여 차원 $d$에 대한 의존성 측면에서 최적이자 기존 연구를 개선한 $\widetilde O(dδ^{-1}\varepsilon^{-3})$ 속도를 달성합니다. 특히, 우리의 하한(lower bound)은 프랭크-울프 갭(Frank-Wolfe gap) 관점에서 제시되며 평활한 문제에서도 성립하므로 독립적인 관심 대상이 됩니다. 이러한 결과는 비볼록 확률적 최적화에서 제약 조건의 존재나 비평활성 모두에 의해 수렴 속도가 저하되지 않음을 보여줍니다. 본 분석은 제약 없는 최적화의 관련 기법을 확장하여 온라인 선형 최적화(online linear optimization)로의 귀약(reduction)을 기반으로 합니다.
영차 잔차 추적을 통한 부분 정보 확률적 최적화
Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
많은 최적화(optimization) 문제에서는 그래디언트(gradient)의 일부에만 직접 접근할 수 있으며, 나머지 성분은 함수 평가를 통해 추론해야 합니다. 이러한 구조는 수행적 예측(performative prediction), 수행적 강화학습(performative reinforcement learning), 그리고 블랙박스 하위 레벨을 갖는 이단계 최적화(bilevel optimization)에서 발생합니다. 본 논문에서는 사용 가능한 그래디언트 성분과 잔차의 이동 추정치를 결합하는 부분 정보 확률적 최적화(Partially Informed Stochastic Optimization, PISO)를 제안합니다. PISO는 각 영차(zeroth-order) 관측을 이 추정치 중심으로 정렬함으로써, 무작위 탐침으로 인한 분산이 잔차의 크기가 아닌 추적 오차에 의존하도록 만듭니다. 이를 통해 명시적인 수축 메커니즘과 모멘텀(momentum)에 대한 원리적 해석을 갖춘 무작위 스케치 반복(iteration)을 도출합니다. 매끄러운 비볼록 목적 함수에 대해, 접근 불가능한 그래디언트 성분에 대한 균일한 경계를 요구하지 않으면서 잔차의 변동과 초기 크기에 의존하는 수렴(convergence) 보장을 확립합니다. 독립적으로 샘플링된 함수 평가와 가우시안 또는 구면 탐침을 사용할 때, PISO는 립시츠 그래디언트 조건에서 \(O(d^{2}\varepsilon^{-6})\), 추가적인 립시츠 헤시안(Hessian) 가정 하에서는 \(O(d^{2}\varepsilon^{-5})\)의 우수한 함수 평가 복잡도를 달성합니다. 이러한 수렴 속도는 업데이트당 단 하나의 탐침 방향, 두 개의 함수 샘플, 그리고 하나의 기지 성분 샘플만을 필요로 합니다. 또한 본 분석은 배치 처리를 통해 배포 횟수를 줄이는 대신 관측치를 교환하는 방식을 정량화합니다. 다섯 가지 설정 전반에서, PISO 변형들은 세 가지 설정에서 유사한 오라클 접근을 갖는 테스트된 베이스라인 대비 성능을 향상시키고, 이단계 라우팅에서는 유사한 해에 더 빠르게 도달하며, 수행적 강화학습에서는 반응 모델(response-model)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.
타원체 샘플링을 활용한 무매개변수 영차 최적화
Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling
영차 최적화(zeroth-order optimization) 방법은 그래디언트 정보를 사용할 수 없거나 계산 비용이 많이 드는 블랙박스 문제를 해결하는 데 필수적입니다. 본 논문에서는 부분공간 사전조건화(subspace preconditioning)와 타원체 무작위 샘플링(ellipsoidal randomized sampling)을 통합하여 최근의 POEM 방법을 확장한 새로운 무매개변수(parameter-free) 확률적 영차 알고리즘인 POEM-ES를 제시합니다. 등방성(isotropic) 무작위 방향에 의존하는 전통적인 영차 접근 방식과 달리, POEM-ES는 기저의 저차원 기하학적 구조를 인코딩하는 고정된 구조적 대칭 양의 준부호(SPSD) 사전조건자 $\hatΣ$에 의해 유도되는 비등방성(anisotropic) 샘플링을 수행합니다. $λ_{\max}(\hatΣ) = 1$인 표준 구조적 스펙트럼 정규화 조건 하에서, 본 연구는 문제의 내재적 차원을 반영하고 샘플링 및 무작위 스무딩 매개변수 스케줄 모두를 유도하는 경험적 유효 차원 $d^* = \operatorname{tr}(\hatΣ)$의 활용을 도입합니다. 실제 적용에서 이러한 사전조건자는 파일럿 샘플링, 과거 궤적 또는 도메인 특화 전문가 지식을 통해 효과적으로 얻을 수 있습니다. 본 연구에서는 POEM-ES가 저계수 구조적 가정을 만족할 때 차원이 축소된 수렴 속도를 달성하며, 단지 $\tilde{\mathcal{O}}\left( \frac{\left( r^2 κ(\hatΣ) + d^* \right) L^2 D_{\mathcal{X}}^2}{\varepsilon^2} \right)$회의 확률적 영차 오라클 쿼리만을 요구함을 증명합니다. 제안된 방법은 완전히 매개변수 없이(parameter-free) 유지되며, $d^* \ll d$인 저계수 구조를 가진 문제에서 기존 POEM 대비 현저한 개선을 입증합니다. LibSVM 데이터셋을 사용한 힌지 손실 이진 분류 태스크에 대한 수치 실험은 제안된 접근법의 실질적인 우수성을 확인해 줍니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.