Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models
원문 초록
In this work, we consider solving optimization problems with a stochastic objective and deterministic equality constraints. We propose a Trust-Region Sequential Quadratic Programming method to find both first- and second-order stationary points. Our method utilizes a random model to represent the objective function, which is constructed from stochastic observations of the objective and is designed to satisfy proper adaptive accuracy conditions with a high but fixed probability. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a quadratic approximation of the objective subject to a (relaxed) linear approximation of the problem constraints and a trust-region constraint. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature of the reduced Hessian matrix, as well as a second-order correction step to address the potential Maratos effect, which arises due to the nonlinearity of the problem constraints. Such an effect may impede the method from moving away from saddle points. Both gradient and eigen step computations leverage a novel parameter-free decomposition of the step and the trust-region radius, accounting for the proportions among the feasibility residual, optimality residual, and negative curvature. We establish global almost sure first- and second-order convergence guarantees for our method, and present computational results on CUTEst problems, regression problems, and saddle-point problems to demonstrate its superiority over existing line-search-based stochastic methods.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference
강볼록 집합 상의 무작위화 선형 오라클 최적화에 대한 하한
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
AMUSE: 안정적 그래디언트 평가를 갖춘 Anytime Muon
AMUSE: Anytime Muon with Stable Gradient Evaluation
현대 심층 학습은 일반적으로 지정된 학습률 스케줄과 함께 AdamW에 의존하지만, 최근 연구들은 두 요소 모두에 이의를 제기한다. Schedule-Free 최적화는 반복 평균화를 통해 명시적 스케줄을 제거하고, Muon은 행렬 파라미터에 대해 모멘텀을 직교화함으로써 업데이트 기하학을 개선한다. Muon의 강력한 실증적 성능에도 불구하고, 그 근본 메커니즘은 부분적으로만 이해되고 있다. 우리는 river-valley 손실 지형을 통해 Muon을 연구한다. 여기서 유용한 학습 진행은 평탄하고 낮은 곡률의 bulk 부분공간(river)을 따라 이루어지며, 높은 곡률의 지배적 방향은 가파른 계곡 벽(valley walls)을 형성하여 진동을 유발한다. 우리는 실증적으로 Muon의 직교화가 bulk 성분을 증가시켜 river 진행을 가속하지만, 동시에 지배적 방향 노이즈를 증폭하여 진동하는 궤적을 유발함을 보인다. 이를 바탕으로, 우리는 Muon의 빠른 bulk 진행과 Schedule-Free 평균화의 안정화 효과를 통합하는 Anytime Muon with Stable Gradient Evaluation(AMUSE)를 제안한다. AMUSE는 시간에 따라 변하는 보간 계수를 사용하여, 초기에는 빠른 Muon 시퀀스 근처에서 그래디언트를 평가하여 신속한 적응을 이루고, 이후 점진적으로 안정적인 평균화된 시퀀스 쪽으로 이동하여 계곡 벽 진동을 억제한다. 그 결과 AMUSE는 학습률 스케줄이 필요 없으며 anytime 학습을 지원한다. 비전 태스크와 대규모 언어 모델 사전학습 전반에 걸쳐, AMUSE는 (Schedule-Free) AdamW 및 Muon 대비 성능-반복 파레토 프론티어를 일관되게 개선한다.
MMAO: 연속 및 이산 최적화를 위한 내인성 자원 할당 기반 대사적 다중 에이전트 옵티마이저
MMAO: A Metabolic Multi-Agent Optimizer with Endogenous Resource Allocation for Continuous and Discrete Optimization
공정 예산 연속 및 이산 벤치마크에서 MMAO의 대규모 실증 평가
A Large-Scale Empirical Evaluation of MMAO Under Fair-Budget Continuous and Discrete Benchmarks
MMAO-Dyn: A Metabolic Multi-Agent Optimizer for Dynamic Optimization
토론
이 논문과 연결된 포럼 글이 아직 없습니다.