Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth

Some recent works [53, 16, 11, 10, 38] developed restarted SGM schemes, for minimizing convex functions under $\gamma$-HG or WSM, and analyzed their theoretical convergence and their natural dependence on the growth moduli $\gamma$ and $\sigma_{F}$. Restarted SubGradient (RSG) of [53] and Decaying Stepsize - SubGradient (DS-SG) of [16] present iteration complexity estimates of $\mathcal{O}\left(\log(1/\epsilon)\right)$ under WSM and $\mathcal{O}\left(\frac{1}{\epsilon^{2(\gamma-1)}}\right)$ bound under $\gamma-$(HG) in order to attain $\text{dist}_{X^{*}}(x)\leq\epsilon$. These bounds are optimal for bounded gradients functions, as observed by [29]. Most SGM schemes are dependent up to various degrees on the knowledge of problem information. For instance, RSG and DS-SG rely on lower bounds of optimal value $F^{*}$ and knowledge of parameters $\sigma_{F},\gamma$ or other Lipschitz constants. The restartation is introduced in order to avoid the exact estimation of modulus $\sigma_{F}$. Also, our schemes allows estimations of problem moduli such as $\gamma,\sigma_{F}$, covering cases when these are not known. In the best case, when estimations are close to the true parameters, similar complexity estimates $\mathcal{O}\left(\frac{1}{\epsilon^{2(\gamma-1)}}\right)$ are provided in terms of subgradient evaluations. Moreover, by exploiting additional smooth structure we further obtain lower estimates.

Several decades ago the Proximal Point Algorithm (PPA) started to gain much attraction for both abstract operator theory and the numerical optimization communities. Even in modern applications, where large-scale nonsmooth optimization arises recurrently, practitioners still inspire from proximal minimization theory to design scalable algorithmic techniques that overcomes nonsmoothness. The powerful PPA iteration consists mainly in the recursive evaluation of the proximal operator associated to the objective function. The proximal mapping is based on the infimal convolution with a metric function, often chosen to be the squared Euclidean norm: $\text{prox}_{\mu}^{F}(x):=\arg\min_{z}F(z)+\frac{1}{2\mu}\lVert z-x\rVert^{2}.$ The Proximal Point recursion:

became famous in optimization community when [40, 39] and [4, 5] revealed its connection to various multipliers methods for constrained minimization, see also [31, 32, 28, 12, 13]. There are remarkable works that shown how the growth regularity is a key factor in the iteration complexity of PPA.

Contributions. We list further our main contributions:

Inexact PPA under $\gamma-$(HG). We provide nonasymptotic iteration complexity bounds for IPPA to solve (1) under $\gamma-$HG, when $\gamma\geq 1$. In particular, we obtain $\mathcal{O}\left(\log(1/\epsilon)\right)$ for $\gamma\in[1,2]$ and, in the case of best parameter choice, $\mathcal{O}\left(1/\epsilon^{\gamma-2}\right)$ for $\gamma>2$, to attain $\epsilon$ distance to the optimal set. All these bounds require only convexity of the objective function $F$ and they are independent on any bounded gradients or smoothness. We could not find these nonasymptotic estimates in the literature for general $\gamma\geq 1$.

Restartation. We further analyze the complexity bounds of restarting IPPA, that facilitates the derivation of better computational complexity estimates than the non-restarted IPPA. The complexity estimates have similar orders in both restarted and non-restarted algorithms for all $\gamma\geq 1$.

Total computational complexity. We derive total complexity, including the inner computational effort spent at each IPPA iteration, in terms of number of inner (proximal) gradient evaluations. If $f$ has $\nu-$Holder continuous gradients we obtain that, in the case of best parameter choice, there are necessary:

proximal (sub)gradient evaluations to approach to $\epsilon$ distance to the optimal set. As we discuss in the section 6, the total complexity is dependent on various restartation variables.

Experiments. Our numerical experiments confirm a better behaviour of the restarted IPPA, that uses an inner subgradient method routine, in comparison with other two restarting strategies of classical Subgradient Method. We performed our tests on several polyhedral learning models that includes Graph SVM and Matrix Completion, using synthetic and real data.

As discussed in the introduction, $\gamma$-HG relates tightly with widely known regularity properties such as WSM [53, 36, 37, 7, 9, 1, 8], Quadratic Growth (QG) [53, 22, 26], Error Bound [23] and Kurdika-Lojasiewicz inequality [6, 53].

Next we show how the Moreau envelope of a given convex function inherits its growth properties over its entire domain excepting a certain neighborhood of the optimal set. Recall that $\min_{x}F(x)=\min_{x}F_{\mu}(x)$.

It is interesting to remark that the Moreau envelope $F_{\mu}$ inherits a similar growth landscape as $F$ outside a given neighborhood of the optimal set. For instance, under WSM, outside the tube $\mathcal{N}(\sigma_{F}\mu)=\{x\in\mathbf{R}^{n}:\;\text{dist}_{X^{*}}(x)\leq\sigma_{F}\mu\}\}$, the Moreau envelope $F_{\mu}$ grows sharply. Inside of $\mathcal{N}(\sigma_{F}\mu)$ it grows quadratically which, unlike the objective function $F$, allows the gradient to get small near to the optimal set. This separation of growth regimes suggests that first-order algorithms that minimize $F_{\mu}$ would reach very fast the region $\mathcal{N}(\sigma_{F}\mu)$, allowing large steps in a first phase and subsequently, they would slow down in the vicinity of the optimal set.

In the following section we start with the analysis of exact and inexact PPA. Aligning to old results on the subgradient algorithms back to [36], we illustrate the robustness induced by the weak sharp minima regularity.

The basic exact PPA iteration is shortly described as

Recall that by (3) one can express $\nabla F_{\mu}(x^{k})=\frac{1}{\mu}(x^{k}-\text{prox}_{\mu}^{F}(x^{k}))$, which makes PPA equivalent with the constant stepsize Gradient Method (GM) iteration:

Since our reasoning from below borrow simple arguments from classical GM analysis, we will use further (8) to express PPA. It is realistic not to rely on explicit $\text{prox}_{\mu}^{F}(x^{k})$, but an approximated one to a fixed accuracy. By using such an approximation, one can form an approximate gradient $\nabla_{\delta}F_{\mu}(x^{k})$ and interpret IPPA as an inexact Gradient Method. Let $x\in\text{dom}{F}$, then a basic $\delta-$ approximation of $\nabla F_{\mu}(x)$ is

Other works as [40, 42, 48, 49] promotes similar approximation measures for inexact first order methods. Now we present the basic IPPA scheme with constant stepsize.

There already exist a variety of relative or absolute stopping rules in the literature for the class of first-order methods [51, 42, 37, 15]. However, since bounding the norms of gradients is commonly regarded as one of the simplest optimality measures, we use the following:

which is computable by the nature of the iteration. The next result shows the relation between (10) and the distance to optimal set.

If $X^{*}$ are weakly sharp minimizers, the above lemma states that, for sufficiently small $\delta$ and $\lVert\nabla_{\delta}F_{\mu}(x^{k})\rVert$ one can directly guarantee that $x^{k}$ is close to $X^{*}$. From another viewpoint, Lemma 3.1 also suggests for WSM that a sufficiently large $\mu>\frac{\text{dist}_{X^{*}}(x^{0})}{\sigma_{F}}$ provides $\text{prox}_{X^{*}}(x^{0})=\pi_{X^{*}}(x^{0})$ and a $\delta-$optimal solution is obtained as the output of the first IPPA iteration. A similar result stated in [9], guarantees the existence of a sufficiently large smoothing value $\mu$ which makes PPA to converge in a single (exact) iteration.

Note that in general, all the abstract convergence rates of Theorem 4.1 depend on two terms: the first one illustrates the reduction of the initial distance to optimum and the second term reflects the accuracy of the approximated gradient. Therefore, after a finite number (for $\gamma=1$) or at most $\mathcal{O}(\log(1/\epsilon))$ (for $\gamma>1$) IPPA iterations, the evolution of inner accuracy $\delta_{k}$ becomes the main bottleneck of the convergence process. The above theorem provides an abstract insight about how fast should the accuracy $\{\delta_{k}\}_{k\geq 0}$ decay in order that $\{x^{k}\}_{k\geq 0}$ attains the best rate towards the optimal set in terms of $\text{dist}_{X^{*}}(x^{k})$. In short, $(i)$ shows that for WSM a recurrent constant decrease on $\text{dist}_{X^{*}}(x^{k})$ is established only if $\delta_{k}<\mu\sigma_{F}$, while the noise $\delta_{k}$ is not necessary to vanish. This aspect will be discussed in more details below. The last parts $(ii)$ and $(iii)$ suggest that a linear decay of $\delta_{k}$ (for $\gamma=2$) and, respectively, $\delta_{k+1}=h(\delta_{k})$ for general $\gamma>1$, ensure the fastest convergence of the residual.

Several previous works as [27, 36, 37] analyzed perturbed and incremental SGM algorithms, under WSM, that use noisy estimates $G_{k}$ of subgradient $F^{\prime}(x^{k})$. A surprising common conclusion of these works is that under a sufficiently low persistent noise: $0<\lVert F^{\prime}(x^{k})-G_{k}\rVert<\sigma_{F},$ for all $k\geq 0$, SGM still converges linearly to the optimal set. Although IPPA is based on a similar approximate first order information, notice that the smoothed objective $F_{\mu}$ do not satisfy the pure WSM property. However, our next result states, in a similar context of small but persistent noise of magnitude at most $\frac{\delta}{\mu}$, that IPPA attains $\delta-$accuracy after a finite number of iterations.

To conclude, if the noise magnitude $\frac{\delta}{\mu}$ is below the threshold $\sigma_{F}$, or equivalently $0<\delta^{\nabla}:=\lVert\nabla F_{\mu}(x^{k})-\nabla_{\delta}F_{\mu}(x^{k})\rVert<\sigma_{F}$ then after a finite number of iterations IPPA reaches $\delta$ distance to $X^{*}$. We see that under sufficiently low persistent noise, IPPA still guarantees convergence to the optimal set assuming the existence of an inner routine that computes each iteration. In other words, ”noisy” Proximal Point algorithms share similar stability properties as the noisy Subgradient schemes from [27, 36, 37]. This discussion can be extended to general decreasing $\{\delta_{k}\}_{k\geq 0}$.

We show next that Theorem 4.1 covers well-known results on exact PPA.

The finite convergence of the exact PPA, under WSM, dates back to [9, 7, 1, 4]. Since PPA is simply a gradient descent iteration, its iteration complexity under QG $\gamma=2$ shares the typical dependence on the conditioning number $\frac{1}{\mu\sigma_{F}}$. The Holder growth $\gamma\in(1,2)$ behaves similarly with the sharp minima case: fast convergence outside the neighborhood around the optimum which expands with $\mu$.

A simple argument on the tightness of the bounds for the case $\gamma>2$ can be found in [2]. Indeed, Douglas-Rachford, PPA and Alternating Projections algorithms were analyzed in [2] for particular univariate functions. The authors proved that PPA requires $\mathcal{O}\left(1/\epsilon^{\gamma-2}\right)$ iterations to minimize the particular objective $F(x)=\frac{1}{\gamma}|x|^{\gamma}$ (when $\gamma>2$) up to $\epsilon$ tolerance.

Overall, if the noise vanishes sufficiently fast (e.g. a linear decay with factor $\frac{1}{2}$ in the case $\gamma\leq 2$) then the complexity of IPPA has the same order as the one of PPA. However, a fast vanishing noise $\delta_{k}$ requires an efficient inner routine that computes the iterate $x^{k}$. Particularly, when $F$ is nonsmooth and convex, a simple choice of the inner routine is the Subgradient Method (SM). However, the efficiency of the SM for minimizing a given $\sigma_{f}-$strongly convex function $f$ up to $\delta$ accuracy, i.e. $f(x)-f^{*}\leq\delta$, has the order $\mathcal{O}\left(\frac{1}{\delta}\right)$ subgradient calls [17]. By using the quadratic growth guaranteed by strong convexity, i.e. $\frac{\sigma_{f}}{2}\lVert x-x^{*}\rVert^{2}\leq f(x)-f^{*}\leq\delta$, in order to approach a minimizer at distance $\delta$, SM requires $\mathcal{O}\left(\frac{1}{\delta^{2}}\right)$ iterations. According to this bound, the cost of computing a single iteration of IPPA results into $\mathcal{O}\left(\frac{1}{\delta_{k}^{2}}\right)$ subgradient calls and, therefore, a direct naive counting of the total number of subgradient evaluations over $T$ outer iterations is of order $\mathcal{O}\left(\sum\limits_{k=0}^{T}\frac{1}{\delta_{k}^{2}}\right)$. By using the previous estimates of $T$ necessary for $\text{dist}_{X^{*}}(x^{T})\leq\epsilon$, yields a total estimate of subgradient calls which is significantly larger than the known optimal bound of $\mathcal{O}\left(\frac{1}{\epsilon^{2(\gamma-1)}}\right)$ for SM algorithm. However, we further give a restarted variant of IPPA that overcomes this issue.

The Restarted IPPA (RIPPA) illustrates a simple recursive call of the IPPA combined with a multiplicative decrease of the parameters. Observe that RIPPA is completely independent of the problem constants.