Newest papers

Primal-Dual Adaptive Subgradient Methods

Karthik Prakhya, Zimeng Wang, Alp Yurtsever · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.28300 · cited by 0 works (OpenAlex) · open-access PDF

Vietnamese

Chúng tôi đề xuất các phương pháp subgradient primal-dual thích ứng cho tối ưu hóa cong. Phương pháp đầu tiên của chúng tôi áp dụng kích thước bước theo kiểu AdaGrad cho vấn đề kép và phục hồi các giải pháp nguyên thủy bằng cách trung bình hóa các đầu ra oracle kiểu Fenchel có liên quan. Nó đạt được $\widetilde{\mathcal{O}}(T^{-1/2})$ convergence cho phần còn lại của mục tiêu kép, phần còn lại của mục tiêu nguyên thủy và khoảng cách khả thi trong chế độ không trơn tru, trong khi tự động cải thiện đến $\mathcal{O}(T^-1})$ khi mục tiêu kép trơn tru. Chúng tôi tiếp tục phát triển một biến thể tăng tốc, giữ lại $\widetilde\mathath{O}}(T^{-1/2})$ nonsmo

Machine translation (Meta M2M100); the English original follows.

Abstract

We propose adaptive primal-dual subgradient methods for constrained convex optimization. Our first method applies an AdaGrad-style step-sizes to the dual problem and recovers primal solutions by averaging the associated Fenchel-type oracle outputs. It achieves $\widetilde{\mathcal{O}}(T^{-1/2})$ convergence for the dual objective residual, primal objective residual, and feasibility gap in the nonsmooth regime, while automatically improving to $\mathcal{O}(T^{-1})$ when the dual objective is smooth. We further develop an accelerated variant, which retains the $\widetilde{\mathcal{O}}(T^{-1/2})$ nonsmooth rate while achieving $\mathcal{O}(T^{-2})$ convergence in the smooth regime under mild assumptions. These guarantees require no prior knowledge of the underlying regularity. We demonstrate the empirical performance of the proposed methods on optimal transport and semidefinite relaxation of the Max-Cut problem.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Subgradient method, Mathematical optimization, Dual (grammatical number), Convergence (economics), Oracle, Mathematics

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange