The purpose of this manuscript is to derive new convergence results for
several subgradient methods applied to minimizing nonsmooth convex functions
with H\"olderian growth. The growth condition is satisfied in many applications
and includes functions with quadratic growth and weakly sharp minima as special
cases. To this end there are three main contributions. First, for a constant
and sufficiently small stepsize, we show that the subgradient method achieves
linear convergence up to a certain region including the optimal set, with error
of the order of the stepsize. Second, if appropriate problem parameters are
known, we derive a decaying stepsize which obtains a much faster convergence
rate than is suggested by the classical $O(1/\sqrt{k})$ result for the
subgradient method. Thirdly we develop a novel "descending stairs" stepsize
which obtains this faster convergence rate and also obtains linear convergence
for the special case of weakly sharp functions. We also develop an adaptive
variant of the "descending stairs" stepsize which achieves the same convergence
rate without requiring an error bound constant which is difficult to estimate
in practice.

本文探讨次梯度法在极值点问题（特别是带有 Hölder 增长 ）中，固定和衰减步长下的收敛性及误差，并介绍了一种名为 “下降楼梯” 的步长方式，最终提出了一种自适应变体方法以实现更快的收敛速度。

具有 Hölder 增长函数的更快次梯度方法

Faster Subgradient Methods for Functions with Hölderian Growth

We analyze the convergence rate of the alternating direction method of
multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex
separable functions subject to linear constraints. Previous analysis of the
ADMM typically assumes that the objective function is the sum of only two
convex functions defined on two separable blocks of variables even though the
algorithm works well in numerical experiments for three or more blocks.
Moreover, there has been no rate of convergence analysis for the ADMM without
strong convexity in the objective function. In this paper we establish the
global linear convergence of the ADMM for minimizing the sum of any number of
convex separable functions. This result settles a key question regarding the
convergence of the ADMM when the number of blocks is more than two or if the
strong convexity is absent. It also implies the linear convergence of the ADMM
for several contemporary applications including LASSO, Group LASSO and Sparse
Group LASSO without any strong convexity assumption. Our proof is based on
estimating the distance from a dual feasible solution to the optimal dual
solution set by the norm of a certain proximal residual, and by requiring the
dual stepsize to be sufficiently small.

本文研究交替方向乘子法 (ADMM) 用于多个非光滑凸可分函数的线性约束约束下极小化问题的收敛速率，通过引入一种新的与其它满足该问题的近似算法有所不同的证明手段，我们在不限制强凸性的情况下，建立了全局线性收敛性的证明方案，表明 ADMM 的线性收敛性可以在三个以上的可分函数的情况下适用，包括 LASSO，Group LASSO 和 Sparse Group LASSO 等当代应用。