arXiv:2609.38561v2 math.OC

타원체 샘플링을 활용한 무매개변수 영차 최적화

Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

Alexander Sholokhov, Alexander Rogozin

제출 2026-09-29

한국어 초록

영차 최적화(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 데이터셋을 사용한 힌지 손실 이진 분류 태스크에 대한 수치 실험은 제안된 접근법의 실질적인 우수성을 확인해 줍니다.

원문 초록

Zeroth-order optimization methods are essential for solving black-box problems where gradient information is unavailable or expensive to compute. This paper presents POEM-ES, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating subspace preconditioning with ellipsoidal randomized sampling. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-ES performs anisotropic sampling guided by a fixed structural symmetric positive semi-definite (SPSD) preconditioner $\hatΣ$ that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where $λ_{\max}(\hatΣ) = 1$, we introduce the use of the empirical effective dimension $d^* = \operatorname{tr}(\hatΣ)$, which reflects the intrinsic dimensionality of the problem and guides both the sampling and randomized smoothing parameter schedules. In practice, such a preconditioner can be effectively obtained via pilot sampling, historical trajectories, or domain-specific expert knowledge. We prove that POEM-ES achieves a dimension-reduced convergence rate under low-rank structural assumptions, requiring only $\tilde{\mathcal{O}}\left( \frac{\left( r^2 κ(\hatΣ) + d^* \right) L^2 D_{\mathcal{X}}^2}{\varepsilon^2} \right)$ stochastic zeroth-order oracle queries. The method remains fully parameter-free and demonstrates significant improvements over the original POEM in problems with low-rank structure where $d^* \ll d$. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.38561v2

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.13787v1math.OC공통 태그 Stochastic Optimization, zeroth-order optimization

제약 조건이 있는 비평활 비볼록 확률적 최적화를 위한 최적 알고리즘

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)을 기반으로 합니다.

arXiv:2610.13871v1cs.LG공통 태그 Stochastic Optimization, zeroth-order optimization

영차 잔차 추적을 통한 부분 정보 확률적 최적화

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)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.

arXiv:2609.27199v1cs.LG공통 태그 Stochastic Optimization, zeroth-order optimization

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)을 구분한다.

arXiv:2609.25325v1cs.NE공통 태그 Stochastic Optimization, black-box optimization

대규모 언어 모델을 활용한 온라인 자동 알고리즘 설계

Online Automated Algorithm Design with Large Language Models

대규모 언어 모델(LLM)은 추론과 코드 합성을 통해 자동 알고리즘 설계(AAD)를 가능하게 한다. 그러나 기존의 LLM 기반 AAD 방법 대부분은 알고리즘 설계와 대상 최적화를 분리하여, 최적화 상태가 변화하는 동안에도 고정된 설계를 그대로 배포한다. 기존의 적응형 옵티마이저는 이러한 변화에 대응할 수 있지만, 그 조정은 사전에 정의된 파라미터, 연산자 또는 전략의 범위에 국한된다. 이러한 한계를 해결하기 위해, 본 논문은 알고리즘 자체를 상태 의존적 결정 변수로 취급하는 새로운 최적화 패러다임인 온라인 LLM 기반 AAD를 제안한다. 각 단계에서 LLM 에이전트는 현재의 최적화 상태로부터 새로운 동작 로직을 갖춘 알고리즘을 합성한다. 생성된 알고리즘을 실행하면 탐색이 진행되고 이후 설계를 위한 피드백이 제공되므로, 별도의 오프라인 알고리즘 사전학습 단계 없이도 알고리즘 설계와 대상 최적화가 결합된다. 이 패러다임을 구현하기 위해 본 논문은 상충하는 설계 관점을 조율하여 실행 가능한 알고리즘을 합성하고, 실행 피드백을 활용해 이후 설계를 위해 런타임 증거를 해석하는 방식을 개선하는 멀티 에이전트 프레임워크인 OnDesign을 제안한다. 우리는 두 가지 주류 블랙박스 최적화 패러다임에 걸친 세 가지 시나리오, 즉 베이지안 최적화, 진화적 연속 최적화, 진화적 혼합 변수 최적화에서 OnDesign을 평가한다. 여섯 개의 벤치마크 스위트와 하나의 공학 문제에 대해 다양한 문제 차원에서 수행한 광범위한 실험을 통해, 기존 옵티마이저와 오프라인 LLM 기반 AAD 방법보다 우수한 전반적 성능을 보임을 입증한다.

arXiv:2609.22329v1cs.NE공통 태그 Stochastic Optimization, black-box optimization

블랙박스 최적화에서 대리 모델로서의 인공 신경망

Artificial Neural Networks as Surrogate Models in Black Box Optimization

블랙박스 최적화(Black-Box Optimization, BBO)는 여러 공학 분야에서 흔히 적용되며, 수치 측정 및 시뮬레이션 기술의 발전을 활용할 수 있다. 이는 해석적 기술(analytical description)이 존재하지 않는 최적화 함수를 다룬다. 이 방법은 탐색 공간 내의 입력점과, 센서, 실험, 시뮬레이션 등 비해석적 수단을 통해 얻어진 해당 목적 함수 값의 쌍만을 필요로 하는 방법에 의존한다. 일반적인 접근법으로는 진화적 최적화(evolutionary optimization)와 기타 메타휴리스틱(metaheuristics)이 있다. BBO 방법은 목적 함수 값에만 의존하기 때문에 일반적으로 많은 평가(evaluation)를 필요로 하며, 이는 목적 함수를 평가하는 데 시간이 많이 걸리거나 비용이 많이 드는 경우 문제가 된다. 이로 인해 선택된 실제 목적값을 평가하고 탐색 공간 전체에 걸쳐 목적 함수를 근사하는 회귀 모델을 학습시키는 대리 기반 최적화(surrogate-based optimization)를 사용하게 된다. 대리 모델 지원 블랙박스 최적화는 소량 데이터 학습(small-data learning) 문제인데, 이는 옵티마이저가 제한된 평가로부터 비용이 큰 목적 함수를 근사해야 하기 때문이다. 대리 모델은 데이터 효율적인 회귀자(regressor) 역할을 하며, 제한된 평가 예산(evaluation budget) 하에서 유망하거나 정보성이 높은 지점으로 탐색을 유도한다. 본 논문에서는 목적 함수의 선택적 평가를 위해 인공 신경망을 사용하는 새로운 대리 모델인 적응적 충실도 넥서스 공분산 행렬 적응 진화 전략(Adaptive-Fidelity Nexus Covariance Matrix Adaptation Evolution Strategy, AFN-CMA-ES)을 제안한다. 실험 결과는 최신(state-of-the-art) 대리 모델 지원 BBO 방법들과 비교하여 경쟁력 있는 성능을 보여준다.

arXiv:2607.22567v1math.OC공통 태그 Stochastic Optimization, zeroth-order optimization

영차(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 하에서의 최적화 동작을 확인한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.