영차 잔차 추적을 통한 부분 정보 확률적 최적화
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)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.
원문 초록
Many optimization problems provide direct access to only part of the gradient, while the remaining component must be inferred from function evaluations. This structure arises in performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. We introduce Partially Informed Stochastic Optimization (PISO), which combines the available gradient component with a running estimate of the residual. By centring each zeroth-order observation on this estimate, PISO makes the variance due to random probing depend on the tracking error rather than the residual's magnitude. This yields a randomized sketch iteration with an explicit contraction mechanism and a principled interpretation of momentum. For smooth nonconvex objectives, we establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. With independently sampled function evaluations and Gaussian or spherical probes, PISO attains leading function-evaluation complexities of \(O(d^{2}\varepsilon^{-6})\) under Lipschitz gradients and \(O(d^{2}\varepsilon^{-5})\) under an additional Lipschitz-Hessian assumption. These rates require only one probe direction, two function samples, and one known-component sample per update. The analysis also quantifies how batching trades observations for fewer deployments. Across five settings, PISO variants improve on the tested baselines with comparable oracle access in three, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
분산 감소 정책 그래디언트는 거의 미니맥스-최적이다
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
표준 정책 그래디언트(Policy Gradient, PG) 알고리즘은 몬테카를로 업데이트에 의존하기 때문에 추정 분산이 높다는 문제를 가진다. 오프-정책 분산 감소(off-policy variance reduction)가 이 문제를 완화하지만, 현재로서는 최적의 샘플 복잡도(sample complexity)를 확립하려면 균일하게 유계인(uniformly bounded) 중요도 가중치(importance weights)와 같은 제한적인 가정이나 비현실적인 2차(second-order) 연산이 필요하다. 본 연구에서는 Loopless Variance-Reduced PG(LVR-PG)를 소개한다. 이는 재귀적 업데이트(recursive update)와 방어적 중요도 샘플링(defensive importance sampling)을 결합한 1차(first-order) 추정량들의 한 클래스를 추상화하는 통합 이론적 프레임워크로, PAGE-PG와 STORM-PG와 같은 기존 추정량들을 포함한다. 우리는 일반적인 파라메트릭 정책(parametric policy)에 대해 약한 그래디언트 지배(weak gradient domination) 조건 하에서 이 알고리즘 클래스가 $\tilde{\mathcal{O}}(ε^{-2})$의 라스트 이터레이트(last-iterate) 전역 수렴(global convergence)을 달성함을 증명한다. 우리는 순수하게 1차 업데이트만을 사용하여, 최소한의 가정 하에 그래디언트 전처리기(gradient preconditioner) 없이 이 보장을 확립한다. 최신 하한(lower bound)을 연속적인 파라메트릭 정책(continuous parametric policy)으로 확장함으로써, 우리는 $Ω(ε^{-2})$의 샘플 복잡도 한계를 확립하며, 이는 로그 인자(logarithmic factor)와 호라이즌(horizon) 항을 제외하면 우리의 프레임워크가 미니맥스 최적(minimax-optimal)임을 확인해 준다.
제약 조건이 있는 비평활 비볼록 확률적 최적화를 위한 최적 알고리즘
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)을 기반으로 합니다.
타원체 샘플링을 활용한 무매개변수 영차 최적화
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 데이터셋을 사용한 힌지 손실 이진 분류 태스크에 대한 수치 실험은 제안된 접근법의 실질적인 우수성을 확인해 줍니다.
ZO-COSMO: 분산 제로차 최적화를 위한 인덱스 없는 원홉(one-hop) 혼합
ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization
분산 제로차 학습에서 희소 통신은 호환 가능한 피어 상태 좌표(peer-state coordinates)를 요구한다. 우리는 이 원홉(one-hop) 조건을 특성화하고, 활성 링크당 $q$개 값을 사용하는 평균 보존 마스크 합의(average-preserving masked consensus)와 이중 쿼리 추정(two-query estimation)을 결합한 \textsf{ZO-COSMO}를 제안한다. 전역 지원(global supports)은 전 이웃 혼합(all-neighbor mixing)에 사용되며, 매칭 업데이트(matching updates)는 각 쌍 내에서만 합의를 요구한다. 매칭 클래스 내에서 날카로운 스칼라당 수축(contraction-per-scalar) 상계를 유도하고, 핵심 및 희소-모멘텀(sparse-momentum) 업데이트에 대한 수렴 보장을 제공한다. 고정된 매칭에서 정확한 모멘트 항등식(moment identities)은 공유 방향이 그래디언트 이질성(gradient-heterogeneity) 상쇄를 어떻게 보존하고 추정 오차와 불일치(disagreement)를 재분배하는지를 특성화한다. 메커니즘 실험은 불균등 곡률, 노이즈, 희소 모멘텀을 다룬다. 추가 실험은 $64$개의 합성 에이전트와 8개의 논리적 Qwen LoRA 워커를 포함한다. 동일한 페이로드 예산에서 Qwen2-7B QNLI는 explicit-index Rand-$k$ 대비 $3.65$ 정확도 포인트를 얻으며, 8-워커 완전 그래프와 링 그래프에서 edge-local 업데이트는 전 이웃 혼합 대비 각각 $3.42$ 및 $2.53$ 포인트를 얻는다. 매칭-first-step 소거(ablation)는 $3.92$ 포인트의 모멘텀 이득을 보여준다. 시드 인식(seed-aware) 및 동일-매칭(same-matching) 대조는 인코딩, 스케줄링, 쿼리 상관(query correlation)을 구분한다.
Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
자연 정책 그래디언트(NPG)는 신뢰 영역 정책 최적화(Trust Region Policy Optimization) 및 근위 정책 최적화(Proximal Policy Optimization)와 같이 널리 사용되는 방법의 기반이 되는, 잘 정립된 강화학습 알고리즘이며, 이들 방법 모두 강력한 실증적 성공을 보여주었다. 본 논문에서는 동역학이 알려져 있고 수평선 의존적 전이 커널(horizon-dependent transition kernels)을 갖는 유한 수평선 마르코프 결정 과정(Markov Decision Processes)에서 정확한 NPG를 연구한다. 이 설정에서 해당 알고리즘에 대한 최초의 유한 시간 수렴 보장을 제공하며, 상수 및 증가하는 학습률(step size) 체제를 모두 고려한다. 상수 학습률 $η_t=η$에 대해, NPG가 $t$회 반복 후 $\mathcal{O}(H^{2}/t)$의 속도로 아선형(sublinear) 수렴함을 증명한다. 여기서 $H$는 수평선 길이이다. 또한 이 상수 학습률 분석을 전체 지지(full support) 투영 분포 하의 정확한 모집단 투영 오라클(population-projection oracle)에서의 선형 MDP로 확장하여, 테이블(tabular) 설정과 동일한 아선형 속도를 재현한다. 더 나아가 증가하는 학습률에 대해서는, 이 알고리즘이 문제 의존 상수 $\vartheta_ρ> 1$에 대해 $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)$의 선형 수렴 속도를 달성함을 증명하며, $η_0>0$ 및 $H \geq 2$인 형태 $η_t=η_0(H/(H-1))^t$의 수평선만 의존하는(horizon-only) 강건 스케줄(robust schedule)이 동일한 기하(geometric) 속도를 달성한다.
영차(Newton) 동역학을 위한 형식적 운동론: Stein 보정 헤시안 추정과 곡률-분산 트레이드오프
A Formal Kinetic Theory for Zeroth-Order Newton Dynamics:Stein-Corrected Hessian Estimation and Curvature--Variance Trade-offs
영차(Newton)형 방법은 그래디언트와 헤시안을 사용할 수 없을 때 유용하지만, 1차 그래디언트 없는(gradient-free) 방법과는 상당히 다르게 동작한다. 우리는 블랙박스 함수값으로부터 그래디언트와 헤시안을 모두 추정하는 알고리즘을 위한 운동론적 프레임워크를 개발한다. 순진한 무작위 방향 헤시안 추정기는 2차 함수에서조차 편향된 것으로 드러난다; 가우시안 평활화된 목적함수의 헤시안을 추정하려면 가우시안-Stein 보정이 필요하다. 역헤시안의 선형화는 두 가지 노이즈 채널을 드러낸다: 역헤시안으로 전처리(preconditioned)된 그래디언트 노이즈, 그리고 역-헤시안 샌드위치를 통해 전달되는 헤시안 노이즈. 노이즈가 있는 오라클 하에서 두 번째 채널은 2차 차분 인수 $μ_H^{-4}$를 담는다. 작은 질량의 운동론적 리프트(lift)는 유한 단계 Newton 업데이트를 과소감쇠(underdamped) 위상 공간 모델과 연결한다; 과감쇠(overdamped) 공간적 한계는 스텝 크기, 배치 크기, 평활화 반경, 정규화 사이의 곡률-분산 트레이드오프를 드러내는 Lyapunov 경계를 산출한다. 수치 실험은 추정기 항등식, 그래디언트 및 헤시안 분산 법칙, 차원 스케일링, 역 섭동 정확도, 그리고 쿼리 예산 및 정규화 ablation 하에서의 최적화 동작을 확인한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.