论文标题
一种针对一类非线性组成凸优化问题的新的原始偶算法
A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
论文作者
论文摘要
我们开发了一种新颖的原始二重性算法来解决一类非平滑和非线性组成凸的最小化问题，该问题涵盖了许多现有和全新的模型作为特殊情况。我们的方法依赖于新的NonConvex潜在功能，Nesterov的加速方案和自适应参数更新策略的组合。我们的算法是单循环的，并且每卷复杂性较低。在只有一般凸度和温和的假设下，我们的算法通过三个不同的标准实现$ \ mathcal {o}（1/k）$收敛速率：原始客观残留物，双重客观残差和原始双差间隙，其中$ k $是iT iTeation Counter。我们的速率既是奇异的（即，在平均序列上）和非共性（即，在最后的题序列上）。如果只有一个目标术语是强凸（或同等地，其共轭为$ l $ -smooth），则这些收敛率最多可加速至$ \ Mathcal {O}（1/k^2）$。据我们所知，这是第一种算法，该算法在非线性组成凸最小化的原始近期序列上达到了最佳速率。作为副产品，我们指定了我们的算法，以解决具有诸控和非共性速率保证的一般凸锥受约束程序。我们测试了我们的算法，并将它们与有关二进制分类和凸连接游戏模型的两种最新方法进行了比较。
We develop a novel primal-dual algorithm to solve a class of nonsmooth and nonlinear compositional convex minimization problems, which covers many existing and brand-new models as special cases. Our approach relies on a combination of a new nonconvex potential function, Nesterov's accelerated scheme, and an adaptive parameter updating strategy. Our algorithm is single-loop and has low per-iteration complexity. Under only general convexity and mild assumptions, our algorithm achieves $\mathcal{O}(1/k)$ convergence rates through three different criteria: primal objective residual, dual objective residual, and primal-dual gap, where $k$ is the iteration counter. Our rates are both ergodic (i.e., on an averaging sequence) and non-ergodic (i.e., on the last-iterate sequence). These convergence rates can be accelerated up to $\mathcal{O}(1/k^2)$ if only one objective term is strongly convex (or equivalently, its conjugate is $L$-smooth). To the best of our knowledge, this is the first algorithm achieving optimal rates on the primal last-iterate sequence for nonlinear compositional convex minimization. As a by-product, we specify our algorithm to solve a general convex cone constrained program with both ergodic and non-ergodic rate guarantees. We test our algorithms and compare them with two recent methods on a binary classification and a convex-concave game model.
