비볼록 및 비립�chitz 최적화에서 Bregman ADMM의 2차 KKT 보장
Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization
한국어 초록
우리는 양측 상대 매끄러움(two-sided relative smoothness) 하에서 비볼록 선형 제약 문제에 대한 Bregman ADMM을 분석한다. 이 조건은 표준 Lipschitz 그래디언트 가정을 Bregman 커널에 대한 헤시안 비교로 대체한다. 이 설정은 전역 Lipschitz-그래디언트 상수가 존재하지 않을 수 있는 행렬 및 텐서 모델에서 발생하는 다항식 목적함수를 포괄한다. 우리는 불변 개방 상태공간 영역에서 Bregman ADMM의 한 번의 반복이 매끄러운 원-듀얼 고정점 사상을 정의하며, 그 strict-saddle KKT 점들이 불안정 고정점임을 보인다. 따라서 무작위 초기화로부터 반복값은 확률 0으로 strict saddle에 수렴한다. 기존 1차 수렴 결과와 결합하면, 이는 극한 KKT 점의 거의 확실한(almost-sure) 2차 정상성을 제공한다. 우리는 분산 최적화를 위한 다중 블록 star consensus 공식화로 분석을 확장한다. 기술적 새로움은 2블록 스펙트럴 논증에서 Bregman 특유의 대칭화 및 스케일링 단계를 포함한 행렬식 축소와, consensus 경우 star 그래프 구조를 이용한 영공간(null space) 상쇄에 있다. 분산 행렬 분해에 대한 수치 실험이 이론을 뒷받침하며, 대칭 텐서 분해 예시는 분리 가능한 consensus 설정을 넘어선 더 넓은 Bregman proximal splitting 아이디어를 보여준다.
원문 초록
We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor models for which a global Lipschitz-gradient constant need not exist. We show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal--dual fixed-point map whose strict-saddle KKT points are unstable fixed points; consequently, from random initialization the iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points. We extend the analysis to a multi-block star consensus formulation for distributed optimization. The technical novelty lies in a determinant reduction with a Bregman-specific symmetrization and scaling step in the two block spectral argument, together with a null space cancellation exploiting the star graph structure in the consensus case. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting idea beyond the separable consensus setting.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.28307v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
DPLib: A Standard Benchmark Library for Distributed Power System Analysis and Optimization
Opportunistic Routing in Wireless Communications via Learnable State-Augmented Policies
Optimization Algorithm Design via Electric Circuits
GNN-Empowered Effective Partial Observation MARL Method for AoI Management in Multi-UAV Network
Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks
ACCO: Accumulate While You Communicate for Communication-Overlapped Sharded LLM Training
토론
이 논문과 연결된 포럼 글이 아직 없습니다.