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

Japanese

私たちの最初の方法は、ダブル問題にAdaGradスタイルのステップサイズを適用し、関連するFenchelタイプのオラクル出力の平均を回復することによって、元のソリューションを回復します。 これは、ダブルオラクルが滑らかであるとき、自動的に$\mathcal{O}(T^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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