论文标题
取回：制作更有效的催化剂以进行凸优化
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
论文作者
论文摘要
加速的近端算法（APPA），也称为“催化剂”，是从凸优化到近似近端计算（即正则最小化）的良好降低。这种减少在概念上是优雅的，可以保证强大的收敛速度。但是，这些速率具有多余的对数项，因此需要计算每个近端点至高精度。在这项工作中，我们为加速近端点（recapp）提出了一种新颖的放松误差标准，该标准消除了高精度子问题解决方案的需求。我们将recapp应用于两个规范问题：有限的和最大结构化最小化。对于有限的问题，我们匹配了以前通过精心设计的问题特异性算法获得的最著名的复杂性。为了最大程度地减少$ \ max_y f（x，y）$，其中$ f $以$ x $为$ x $，而在$ y $中强烈concave，我们改进了受对数因素限制的最著名的（催化剂）。
The accelerated proximal point algorithm (APPA), also known as "Catalyst", is a well-established reduction from convex optimization to approximate proximal point computation (i.e., regularized minimization). This reduction is conceptually elegant and yields strong convergence rate guarantees. However, these rates feature an extraneous logarithmic term arising from the need to compute each proximal point to high accuracy. In this work, we propose a novel Relaxed Error Criterion for Accelerated Proximal Point (RECAPP) that eliminates the need for high accuracy subproblem solutions. We apply RECAPP to two canonical problems: finite-sum and max-structured minimization. For finite-sum problems, we match the best known complexity, previously obtained by carefully-designed problem-specific algorithms. For minimizing $\max_y f(x,y)$ where $f$ is convex in $x$ and strongly-concave in $y$, we improve on the best known (Catalyst-based) bound by a logarithmic factor.
