arXiv:2610.13787v1 math.OC

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

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

Gon Buzaglo, Guy Kornowski

제출 2026-10-09

한국어 초록

본 논문에서는 볼록 제약 집합 하에서 목적 함수가 평활(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)을 기반으로 합니다.

원문 초록

We present new algorithms for stochastic optimization problems in which the objective is neither smooth nor convex, subject to a convex constraint set. Our algorithms return a $(δ,\varepsilon)$-Goldstein stationary point, as recently defined for constrained problems by Liu et al. (2024), with improved complexities, and are the first to achieve optimal convergence rates for this task in several settings. In particular, we design projection-based and projection-free algorithms that achieve a $\widetilde O(δ^{-1}\varepsilon^{-3})$ rate using stochastic gradients, which we show to be optimal, and a $\widetilde O(dδ^{-1}\varepsilon^{-3})$ rate using zeroth-order queries, which is also optimal in its dependence on the dimension $d$ and improves over prior work. Notably, our lower bound is given in terms of the Frank-Wolfe gap and holds even for smooth problems, which is of independent interest. These results show that in nonconvex stochastic optimization, the convergence rate is degraded neither by the presence of constraints nor by nonsmoothness. Our analysis is based on a reduction to online linear optimization, extending a related technique from unconstrained optimization.

제출 이력

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

  1. arXiv:2610.13787v1

함께 살펴볼 논문

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

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.38561v2math.OC공통 태그 Stochastic Optimization, zeroth-order optimization

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

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

arXiv:2609.30499v2stat.ML공통 태그 Stochastic Optimization, nonconvex optimization

거리 의존적 모멘트 조건에서의 일반적인 비볼록 SGD: 유한 시계 정지성과 나가예프 한계

Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

균일한 노이즈 모멘트 한계 조건은 반복점(iterate)에 따라 변동성이 증가하는 확률적 그래디언트를 배제합니다. 본 논문에서는 거리 의존적인 조건부 모멘트 하에서, 매끄럽고 하한이 있는 비볼록(nonconvex) 목적 함수에 대한 일반적인 단일 샘플 확률적 경사하강법(SGD)을 연구합니다. 2차 모멘트 조건만으로도 직접적인 하강-변위(descent--displacement) 논증을 통해 시계 의존적 스텝사이즈를 갖는 $T^{-1/3}$ 기대 평균 제곱 그래디언트 정지성을 도출합니다. 명시적인 오라클 복잡도 따름정리는 $Δ$가 초기 목적 함수 차이이고 $σ^2+b_2\|x-x_1\|^2$가 분산을 제한할 때 $Lb_2Δ^3\varepsilon^{-6}$ 및 $LΔσ^2\varepsilon^{-4}$ 확률적 항을 포함하여 기존에 알려진 매끄러운 블룸-글라디셰프(Blum--Gladyshev, BG-0) 하한과 일치합니다. 따라서 수정되지 않은 일반 SGD는 이 2차 모멘트 클래스에서 미니맥스 확률적 복잡도를 달성합니다. $p>2$인 경우, 예측 가능한 국소화(localization)와 힐베르트 공간 푹-나가예프(Fuk--Nagaev) 부등식을 통해 로그 분산과 다항식 희귀 충격(rare-shock) 기여를 분리하는 높은 확률 한계를 얻습니다. 국소화 반경은 재귀식으로부터 유도되므로, 유계 반복점 가정, 클리핑, 정규화(normalization), 모멘텀(momentum) 또는 증가하는 배치(batch) 크기가 필요하지 않습니다. 또한 신뢰도 증가율(increasing-confidence rates), $\sqrt{T}$ 정지성을 회복하는 목적 함수 차이 성장 개선, 그리고 확률적 $L^p$-립시츠 예시를 제시합니다. 광범위한 BG-0 최적성 진술은 추가적인 오라클 구조를 통해 더 빠른 알고리즘이 허용되는 더 좁은 평균 제곱 평활 클래스와 구별됩니다.

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:2607.22906v1cs.LG공통 태그 Stochastic Optimization, nonconvex optimization

하강 방향으로부터 학습: 일방 Hölder 정칙성 하의 적응형 경사하강법

Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Hölder Regularity

연속 미분 가능하고 비볼록일 수 있는 목적함수에 대해, 일방 Hölder 정칙성 하에서 적응형 경사하강법을 연구한다. 고전적인 Hölder 또는 Lipschitz 그래디언트 가정과 달리, 후자는 전체 그래디언트 변화를 제어하는 반면, 우리의 조건은 하강 부등식에 나타나는 방향 항만을 제한한다. 이는 그래디언트 변화가 크더라도 업데이트 방향에 직교하거나, 그 방향을 따라 유리한 경우 보다 덜 보수적인 스텝 크기를 허용할 수 있다. 양의 일방 Hölder 곡률 추정에 기반한 적응형 스칼라 스텝 방법을 제안하며, 이를 간단한 충분 감소(sufficient-decrease) 보호 장치와 결합한다. 수용된 업데이트 구간을 포함하는 볼록 영역 위의 비볼록 목적함수에 대해, Hölder 지수에 의해 결정되는 명시적 최적 반복 정류(stationarity) 한계를 증명한다. 미리 정해진 감소 스텝 크기 스킴과 달리, 이 방법은 국소 하강 기하에 적응한다. 방향 곡률과 전체 그래디언트 변화를 분리하도록 설계된 두 개의 풀 배치(full-batch) 벤치마크에서 접근법을 평가한다. 이진 분류 문제에서, 이 방법은 비교된 스칼라 그래디언트 방법들 중 최종 교차 엔트로피, 목적함수 값, 그래디언트 노름이 가장 낮고, 분류 마진이 가장 크다. 비볼록 Hölder 회귀 문제에서, 최종 목적함수 간극과 그래디언트 노름이 가장 낮다. 이 결과는 전체 그래디언트 변화가 하강을 방해하지 않는 방향으로 인해 부풀려질 때, 일방 Hölder 곡률이 효과적인 적응형 스텝 크기 신호임을 시사한다.

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

토론

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