Universal regularization methods - varying the power, the smoothness and the accuracy

Introduction

We consider the (possibly) convexly-constrained optimization problem

where $f:\hbox{I\hskip-1.5ptR}^{n}\longrightarrow\hbox{I\hskip-1.5ptR}$ is a smooth, possibly nonconvex, objective and where the feasible set ${\cal F}\subset\hbox{I\hskip-1.5ptR}^{n}$ is closed, convex and non-empty (for example, the set ${\cal F}$ could be described by simple bounds and both polyhedral and more general convex constraints)We are tacitly assuming that the cost of evaluating constraint functions and their derivatives is negligible.. Clearly, the case of unconstrained optimization is covered here by letting ${\cal F}=\hbox{I\hskip-1.5ptR}^{n}$. We are interested in the case when $f\in\mathcal{C}^{p,\beta_{p}}({\cal F})$, namely, $f$ is $p-$times continuously differentiable in ${\cal F}$ with the $p$th derivative being Hölder continuous of (unknown) degree $\beta_{p}\in$Note that if $\beta_{p}>1$, then the resulting class of objectives is restricted to multivariate polynomials of degree $p$. If $p=1$, we only allow $\beta_{1}\in(0,1]$, for reasons to be explained later in the paper.. We consider adaptive regularization methods applied to problem (1.1) that generate feasible iterates $x_{k}$ that are (possibly very) approximate minimizers over ${\cal F}$ of local models of the form

where $T_{p}(x_{k},s)$ is the $p$th order Taylor polynomial of $f$ at $x_{k}$ and $r>p\geq 1$. The parameter $\sigma_{k}>0$ is adjusted to ensure sufficient decrease in $f$ happens when the model value is decreased. In this paper, we derive evaluation complexity bounds for finding first-order critical points of (1.1) using higher-order adaptive regularization methods. Despite the higher order of the models, the model minimization is performed only approximately, generalizing the approach in . The proposed methods also ensure that the steps are ‘sufficiently long’, in a new way, generalizing ideas in . The ensuing complexity analysis shows the robust interplay of the regularization power $r$, the model accuracy $p$ and the degree of smoothness $\beta_{p}$ of the objective, with some surprising results. In particular, we find that the degree of smoothness of the objective—which is often unknown and is even allowed to be absent here—is accurately reflected in the complexity of the methods, independently of the regularization power, provided the latter is sufficiently large. Furthermore, for all possible powers $r$, the methods satisfy increasingly better bounds as the accuracy $p$ of the models and smoothness level $\beta_{p}$ are increased. All bounds vary continuously as a function of the regularization power and smoothness level. Table 4.1 in Section 4 summarizes our complexity bounds.

We now review existing literature in detail and further clarify our approach, motivation and contributions. Cubic regularization for the (unconstrained) minimization of $f(x)$ for $x\in\hbox{I\hskip-1.5ptR}^{n}$ was proposed independently by , with showing it has better global worst-case function evaluation complexity than the method of steepest descent. Extending , we proposed some practical variants – Adaptive Regularization with Cubics (ARC) – that satisfy the same complexity bound as the regularization methods in , namely at most $\mathcal{O}(\epsilon^{-\frac{3}{2}})$ evaluations are needed to find a point $x$ for which

under milder requirements on the algorithm (specifically, inexact model minimization). We further showed in that this complexity bound for ARC is sharp and optimal for a large class of second-order methods when applied to functions with globally Lipschitz-continuous second derivatives. Quadratic regularization, namely, a first order accurate model of the objective regularized by a quadratic term, has also been extensively studied, and shown to satisfy the complexity bound of steepest descent, namely, $\mathcal{O}(\epsilon^{-2})$ evaluations to obtain (1.2) . It was also shown in that one can loosen the requirement that global Lipschitz continuity of the second derivative holds, to just global Hölder continuity of the same derivative with exponent $\beta_{2}\in(0,1]$. Then, if one also regularizes the quadratic objective model by the power $2+\beta_{2}$ of the step, involving the (often unknown) Hölder exponent, the resulting method requires $\mathcal{O}(\epsilon^{-\frac{2+\beta_{2}}{1+\beta_{2}}})$ evaluations, which just as a function of $\epsilon$, belongs to the interval $\left[\epsilon^{-\frac{3}{2}},\epsilon^{-2}\right]$; these bounds are sharp and optimal for objectives with corresponding level of smoothness of the Hessian . Note that this bound also holds if $\beta_{2}=0$.

An important related question and extension was answered in : if higher-order derivatives are available, can one improve the complexity of regularization methods? It was shown in that if one considers approximately minimizing a $(r-1)$th order Taylor model of the objective regularized by the (weighted) $r$th power of the (Euclidean) norm of the step in each iteration (so $r=p+1$), the complexity of the resulting adaptive regularization method is $\mathcal{O}(\epsilon^{-\frac{r}{r-1}})$ evaluations to obtain (1.2), under the assumption that the $(r-1)$th derivative tensor is globally Lipschitz continuous. The method proposed in measures progress of each iteration by comparing the Taylor model decrease (without the regularization term) to that of the true function decrease and only requiring mild approximate (local) minimization of the regularized model. Here, we generalize these higher-order regularization methods from to allow for an arbitrary local Taylor model, an arbitrary regularization power of the step and varying levels of smoothness of the highest-order derivative in the Taylor model.

The interest in considering relaxations of Lipschitz continuity to Hölder continuity of derivatives comes not only from the needs of some engineering applications (such as flows in gas pipelines [16, Section 17] and properties of nonlinear PDE problems ), but also in its own right in optimization theory, as a bridging case between the smooth and non-smooth classes of problems . In particular, a zero Hölder exponent for a Hölder continuous derivative corresponds to a bounded derivative, an exponent in $(0,1)$ corresponds to a continuous but not necessarily differentiable derivative, while an exponent of $1$ corresponds to a Lipschitz continuous derivative that can be differentiated again. For the case of function with Hölder-continuous gradients, methods have already been devised, and their complexity analysed, both as a weaker set of assumptions and as an attempt to have a ‘smooth’ transition between the smooth and nonsmooth (convex) problem classes, without knowing a priori the level of smoothness of the gradient (i.e., the Hölder exponent) ; even lower complexity bounds are known . In we considered regularization methods applied to nonconvex objectives with Hölder continuous gradients (with unknown exponent $\beta_{1}\in(0,1]$), that employ a first-order quadratic model of the objective regularized by the $r$th power of the step. We showed that the worst-case complexity of the resulting regularization methods varies depending on $\min\{r,1+\beta_{1}\}$. In particular, when $1<r\leq 1+\beta_{1}$, the methods take at most $\mathcal{O}\left(\epsilon^{-\frac{r}{r-1}}\right)$ evaluations/iterations until termination, and otherwise, at most $\mathcal{O}\left(\epsilon^{-\frac{1+\beta_{1}}{\beta_{1}}}\right)$ evaluations/iterations to achieve the same condition. The latter complexity bound reflects the smoothness of the objective’s landscape, without prior knowledge or use of it in the algorithm, and is independent of the regularization power. Here we generalize the approach in to $p$th order Taylor models and find that similar bounds can be obtained. Also, we are able to allow $\beta_{p}=0$ provided $p\geq 2$. We note that advances beyond Lipschitz continuity of the derivatives for higher-order regularization methods were also obtained in , where a class of problems with discontinuous and possibly infinite derivatives (such as when cusps are present) is analysed, yielding similar bounds to .

Recently, proposed a new cubic regularization scheme that yields a universal algorithm in the sense that its complexity reflects the (possibly unknown or even absent) degree of sufficient smoothness of the objective; the approach in addresses the case $p=2$, $r=3$ and $\beta_{2}\in$ in our framework. Our ARp algorithm includes a modification in a similar (but not identical) vein to that in . In particular, our approach checks a theoretical condition that carefully monitors the length of the step on each iteration on which the objective is sufficiently decreased. The technique in is different in that it requires a specific/new sufficient decrease condition of the objective on each iteration that makes progress. We generalize the approach in and achieve complexity bounds with similar universal properties for varying $r$, $p$ and unknown $\beta_{p}\in$, provided $r\geq p+\beta_{p}$. We are also able to analyze ARp’s complexity in the regime $p<r\leq p+\beta_{p}$ providing continuously varying results with $r$ and $\beta_{p}$.

Our algorithm can be applied to convexly-constrained optimization problems with nonconvex objectives, where the constraint/feasibility evaluations are inexpensive, offering another generalization of proposals in and which are presented for the unconstrained case only; we also extend by allowing inexact subproblem solution.

The structure of the paper is as follows. Section 2 describes our main algorithmic framework, ARp. Section 3 presents our complexity analysis while Section 4 concludes with a summary of our complexity bounds (see Table 4.1) and a discussion of the results.

A universal adaptive regularization framework - ARp

Let $f\in\mathcal{C}^{p}({\cal F})$, with $p$ integer, $p\geq 1$; let $r\in\hbox{I\hskip-1.5ptR}$, $r>p\geq 1$. We measure optimality using a suitable continuous first-order criticality measure for (1.1). We define this measure for a general function $h:\hbox{I\hskip-1.5ptR}^{n}\longrightarrow\hbox{I\hskip-1.5ptR}$ on ${\cal F}$: for an arbitrary $x\in{\cal F}$, the criticality measure is given by

where $P_{\cal F}$ denotes the orthogonal projection onto ${\cal F}$ and $\|\cdot\|$ the Euclidean norm. Letting $h(x):=f(x)$ in (2.1), it is known that $x$ is a first-order critical point of problem (1.1) if and only if $\pi_{f}(x)=0$. Also note that

For more properties of this measure see .

Our ARp algorithm generates feasible iterates $x_{k}$ that (possibly very) approximately minimize the local model

which is a regularization of the $p$th order Taylor model of $f$ around $x_{k}$,

where $\nabla^{j}_{x}f(x^{k})[s]^{j}$ is the $j$th order tensor $\nabla^{j}_{x}f(x^{k})$ of $f$ at $x_{k}$ applied to the vector $s$ repeated $j$ times. Note that $T_{p}(x_{k},0)=f(x_{k})$. We will also use the measure (2.1) with $h(s):=m_{k}(x_{k}+s)$ for terminating the approximate minimization of $m_{k}(x_{k}+s)$, and for which we have again

A summary of the main algorithmic framework is as follows.

Iterations for which $\rho_{k}\geq\eta_{1}$ and (2.9) hold (and so $x_{k+1}=x_{k}+s_{k}$) are called successful, those for which $\rho_{k}\geq\eta_{2}$ and (2.9) hold are referred to as very successful, while the remaining ones are unsuccessful. For a(ny) $j\geq 0$, we denote the set of successful iterations up to $j$ by $\mathcal{S}_{j}=\{0\leq k\leq j:\,\rho_{k}\geq\eta_{1}\;\;\mbox{and}\;\;(\ref{step-long-gn})\,\,{\rm holds}\}$ and the set of unsuccessful ones by $\mathcal{U}_{j}=\{0,\ldots,j\}\setminus\mathcal{S}_{j}$. We have the following simple lemma that relates the number of successful and unsuccessful iterations and that is ensured by the mechanism of the Algorithm 2.

Lemma 2.1 [9, Theorem 2.1] For any fixed $j\geq 0$ until termination, let $\sigma_{\rm up}>0$ be such that $\sigma_{k}\leq\sigma_{\rm up}$ for all $k\leq j$ in Algorithm 2. Then ${|\mathcal{U}_{j}|\leq\frac{|\log\gamma_{3}|}{\log\gamma_{1}}|\mathcal{S}_{j}|+\frac{1}{\log\gamma_{1}}\log\left(\frac{\sigma_{\rm up}}{\sigma_{0}}\right),}$ (2.11) where $|\cdot|$ denotes the cardinality of the respective index set.

Proof. The proof of (2.11) follows identically to the given reference; note that the sets $\mathcal{S}_{j}$ and $\mathcal{U}_{j}$ are not identical to the usual ARC ones in but the mechanism for modifying $\sigma_{k}$ in ARp coincides with the one in ARC on these iterations and that is why the proof of this lemma follows identically to [9, Theorem 2.1]. $\Box$

Now we comment on the construction of the ARp algorithm. Note that the model minimization conditions (Step 2) and the definition of $\rho$ in Step 4 are straightforward generalizations of the approach in to $p$th order Taylor models regularized by different powers $r$ of the norm of the step. Furthermore, recall that conditions (2.5), (2.6) and (2.7) are approximate local optimality conditions for the nonconvex polynomial model $m_{k}(x_{k}+s)$ minimization over a convex set, $x_{k}+s\in\mathcal{F}$; in fact, they are even weaker than that as they require strict decrease (from the base point $s=0$) and approximate first-order criticality for the convexly constrained model. Thus, any descent optimization method—even first-order algorithms such as the projected gradient method—can be applied to ensure these conditions with ease (with no additional derivatives evaluations required than those needed to set up the model $m_{k}$ at $x_{k}$). Designing efficient techniques specifically for the approximate minimization of such regularized, nonconvex, high-order polynomial optimization problems is beyond our scope here, but an essential component of the success of such methods. Existing regularization-related approaches are available for general nonconvex problems up to third order , or dedicated to convex regularized tensor models (see and the references therein) or specialized to nonlinear least-squares problems ; these complement classical references such as , where third and fourth order tensor methods were proposed.

However, there are two main differences to the by-now standard approaches to (cubic or higher order) regularization methods. Firstly, we check whether the gradient goes below $\epsilon$ at each trial points, and if so, terminate on possibly unsuccessful iterations (Step 3). Secondly, when the step $s_{k}$ provides sufficient decrease according to (2.8), we check whether $s_{k}$ satisfies (2.9), and only allow steps that have such carefully-monitored length to be taken by the algorithm; if (2.9) fails or $\rho_{k}\leq\eta_{1}$, $\sigma_{k}$ is increased. Note that though the length of the step $s_{k}$ decreases as $\sigma_{k}$ is increased, this is not the case for the expression $\sigma_{k}\|s_{k}\|^{r-1}$ in (2.9), which increases with $\sigma_{k}$, as Lemma 3.4 implies. These two additional ingredients—the gradient calculation at each trial point and the step length condition (2.9)—are directly related to trying to achieve universality of ARp, extending ideas from . Further explanations and discussions for the theoretical need, or otherwise, for condition (2.9) are given next, in Remark 2.1, and later in the paper, in Remarks 3.2 (b) and 3.4 (b).

We further comment on condition (2.9), its connections to and existing literature, and possible alternatives.

We can replace condition (2.9) with the weaker requirement that $\sigma_{k}\|s_{k}\|^{r-1}\geq\alpha\epsilon$; then, all subsequent results would remain unchanged. This choice however, would make the algorithm construction dependent on the accuracy $\epsilon$ (elsewhere than in the termination condition), which is not numerically advisable.

Instead of requiring (2.9) on each successful step, we could ask that each model minimization step calculated in Step 2 satisfies (2.9); if (2.9) failed, $\sigma_{k}$ would be increased at the end of Step 2 and the model minimization step would be repeated. This approach may result in an unnecessarily small step in practice, but the ensuing ARp complexity bounds would remain qualitatively similar.

Condition (2.9) does not appear as such in the algorithmic variants proposed in , as those enforce sufficient decrease conditions on $f$ in the algorithm for the case $p=2$ and $r=3$, which is the only case addressed in . But (2.9) (with $r=3$) is a necessary ingredient for achieving the required sufficient decrease conditions in ; see Lemma 2.3 (in particular, equation (2.21)) therein.

Following , instead of (2.9), we could employ a different definition of $\rho_{k}$ in (2.8), namely, replacing the denominator in (2.8) by a rational function in $\epsilon$ and $\sigma_{k}$, or by a function of $\sigma_{k}$ and the gradient at the new point (see for example [19, (6.5)]), to achieve the desired order of model/function decrease for universal complexity and behaviour. According to our calculations, again, qualitatively similar complexity bounds would be obtained for such ARp variants.

We note that using specific $\rho_{k}$ definitions (namely, with a denominator connected to the length of the step) so as to enforce a particular sufficient decrease property for the objective evaluations was also used in for trust-region and quadratic regularization variants, in order to achieve optimal complexity bounds for the ensuing methods.

According to our calculations, without the condition (2.9) on the length of the step, or a similar measure of progress, the complexity of ARp would dramatically (but continuously) worsen in the regime when $r>p+\beta_{p}$, as $r$ increases. But as we clarify at the end of Section 3, for the case $r\leq p+\beta_{p}$, same-order complexity bounds could be obtained for ARp without using (2.9); so in principle, for this parameter regime, (2.9) could be removed from the construction of ARp. However, note that as $\beta_{p}$ is not generally known a priori, the regime of most interest – both in terms of best complexity bounds and practicality – is when $r$ is large; hence the need for condition (2.9) in ARp, for both regimes.

Worst-case complexity analysis of ARp

We have the following simple consequence of (2.6).

Lemma 3.1 On each iteration of Algorithm 2, we have the decrease ${f(x_{k})-T_{p}(x_{k},s_{k})\geq\frac{\sigma_{k}}{r}\|s_{k}\|^{r}.}$ (3.1)

Proof. Note that condition (2.6) and the definition of $m_{k}(s)$ in (2.2) immediately give (3.1). $\Box$

We have the following upper bound on $s_{k}$.

Lemma 3.2 On each iteration of Algorithm 2, we have ${\|s_{k}\|\leq\max_{1\leq j\leq p}\left\{\left(\frac{pr}{j!\sigma_{k}}\|\nabla^{j}_{x}f(x_{k})\|\right)^{\frac{1}{r-j}}\right\}.}$ (3.2)

Proof. It follows from (2.6), (2.2) and (2.3) that

which from Cauchy-Schwarz and norm properties, further implies

The last displayed equation cannot hold unless at least one of the terms on the left-hand side is negative, which is equivalent to (3.2), using also that $r>p\geq 1$. $\Box$

Let us assume that $f\in\mathcal{C}^{p,\beta_{p}}$, namely,

$f\in C^{p}({\cal F})$ and $\nabla^{p}_{x}f$ is Hölder continuous on the path of the iterates and trial points, namely,

holds for all $y\in[x_{k},x_{k}+s_{k}]$, $k\geq 0$ and some constants $L_{p}\geq 0$ and $\beta_{p}\in$, where $\|\cdot\|$ is the Euclidean norm on $\hbox{I\hskip-1.5ptR}^{n}$ and $\|\cdot\|_{T}$ is recursively induced by this norm on the space of the $p$th order tensors.

see for a proof of (3.3) and (3.4), with A.1 replacing Lipschitz continuity of the $p$th derivative.

Note that throughout the paper we assume $r>p\geq 1$, $r\in\hbox{I\hskip-1.5ptR}$ and $p\in\hbox{I\hskip-1.5ptN}$; and that either $p\geq 1$ and $\beta_{p}\in(0,1]$ or $p\geq 2$ and $\beta_{p}\in$. Thus in both cases $p+\beta_{p}-1>0$.

Lemma 3.3 Assume that A.1 holds. Then on each iteration of Algorithm 2, we have ${\pi_{f}(x_{k}+s_{k})\leq L_{p}\|s_{k}\|^{p+\beta_{p}-1}+(\sigma_{k}+\theta)\|s_{k}\|^{r-1}.}$ (3.5)

Proof. Using the triangle inequality and (2.1) with $h\stackrel{{\scriptstyle\rm def}}{{=}}f$ and $h\stackrel{{\scriptstyle\rm def}}{{=}}m_{k}$, we obtain

The last inequality, the contractive property of the projection operator $P_{{\cal F}}$ and the inner termination condition (2.7) give

where we used (3.4) to obtain the second inequality. Now (3.5) follows from replacing (3.7) in (3.6). $\Box$

Lemma 3.4 Assume that A.1 holds. If ${\sigma_{k}\geq\max\left\{\theta,\kappa_{2}\|s_{k}\|^{p+\beta_{p}-r}\right\},}$ (3.8) where ${\kappa_{2}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{rL_{p}}{p(1-\eta_{2})},}$ (3.9) then both $\rho_{k}\geq\eta_{2}$ and (2.9) hold, and so iteration $k$ is very successful.

Proof. We assume that (3.8) holds, which implies that

The definition of $\rho_{k}$ in (2.8) gives $\displaystyle|\rho_{k}-1|=\frac{|f(x_{k}+s_{k})-T_{p}(x_{k},s_{k})|}{f(x_{k})-T_{p}(x_{k},s_{k})}$, whose numerator we upper bound by (3.3), and whose denominator we lower bound by (3.1), to deduce

We employ (3.10) and the expression of $\kappa_{2}$ in (3.9), in (3.11), to deduce that $|1-\rho_{k}|\leq 1-\eta_{2}$, which ensures that $\rho_{k}\geq\eta_{2}$.

It remains to show that (3.8) also implies (2.9). From (3.8), we have that $\sigma_{k}\geq\theta$, which together with (3.5), give

The definition (3.9), and requirements $r>p$ and $\eta_{2}\in(0,1)$, imply that $L_{p}\leq\kappa_{2}$. This and (3.12) give

From (3.10), $\kappa_{2}\leq\sigma_{k}\|s_{k}\|^{r-p-\beta_{p}}$. We use this to bound $\kappa_{2}$ in (3.13), which gives the inequality

Thus $\sigma_{k}\|s_{k}\|^{r-1}\geq\frac{1}{3}\pi_{f}(x_{k}+s_{k})$, which implies (2.9) since $\alpha\leq\frac{1}{3}$. $\Box$

Lemma 3.5 Let $r>p+\beta_{p}$ and assume A.1. While Algorithm 2 has not terminated, if ${\sigma_{k}\geq\max\left\{\theta,\kappa_{1}\epsilon^{\frac{p+\beta_{p}-r}{p+\beta_{p}-1}}\right\},}$ (3.14) where ${\kappa_{1}\stackrel{{\scriptstyle\rm def}}{{=}}\left(3^{r-p-\beta_{p}}\kappa_{2}^{r-1}\right)^{\frac{1}{p+\beta_{p}-1}}\;\;\mbox{and}\;\;\kappa_{2}\;\;\mbox{is defined in (\ref{constant-0}),}\;\;}$ (3.15) then (3.8) holds, and so iteration $k$ is very successful.

Proof. We will prove our result by contradiction. We assume that (3.8) does not hold on iteration $k$, and so

Note that while Algorithm 2 does not terminate, we have $\pi_{f}(x_{k}+s_{k})\geq\epsilon$. Also, from (3.14), $\sigma_{k}\geq\theta$. We use these two inequalities into (3.5) to deduce

We now employ (3.16) to upper bound the second term in (3.17) by $2\kappa_{2}$, namely,

We use (3.16) again to provide an upper bound on $\|s_{k}\|$, which is possible since $r>p+\beta_{p}$. Thus

Using this bound in (3.18), which is possible since $p+\beta_{p}>1$, we obtain the first inequality below,

where to obtain the second inequality, we used that $L_{p}<\kappa_{2}$, which in turn follows from (3.9), $r>p$ and $\eta_{2}\in(0,1)$. Finally, (3.20) and the definition of $\kappa_{1}$ in (3.15) imply that $\sigma_{k}<\kappa_{1}\epsilon^{\frac{p+\beta_{p}-r}{p+\beta_{p}-1}}$, which contradicts (3.14). Thus (3.8) must hold and Lemma 3.4 implies that $\rho_{k}\geq\eta_{2}$ and (2.9) hold, and so $k$ is very successful. $\Box$

(Parameter regime) The proof of Lemma 3.5 requires $r>p+\beta_{p}$ and $p+\beta_{p}>1$ (to deduce (3.19) and (3.20), respectively). However, the result of Lemma 3.5 remains true if $r=p+\beta_{p}$ and it is proved together with the case $r<p+\beta_{p}$ in Lemma 3.10. Note that, when $r=p+\beta_{p}$, (3.14) becomes $\sigma_{k}\geq\max\{\theta,\kappa_{2}\}$, which precisely matches the corresponding expression (3.32) in Lemma 3.10 for this same case.

(Condition (2.9)) Without employing (2.9), we showed inequality (3.5) that connects the length of the step to that of the projected gradient. The two terms on the right-hand side of (3.5) have similar forms as powers of $\|s_{k}\|$, with the exponents crucially determined by Hölder continuity properties of the objective and the power of the regularization term in the model, respectively. Lemmas 3.4 and 3.5 proved that if $\sigma_{k}$ is sufficiently large, then the second term in (3.5), namely, $\sigma_{k}\|s_{k}\|^{r-1}$, will be larger than the term that is a multiple of $\|s_{k}\|^{p+\beta_{p}-1}$; hence ensuring that (2.9) holds. To further explain this point, note that in (3.5), when $r>p+\beta_{p}$ and $\|s_{k}\|\leq 1$ (which is the difficult case), the larger term on the right-hand side is a multiple of $\|s_{k}\|^{p+\beta_{p}-1}$ when $\sigma_{k}$ is larger than a constant. Lemma 3.5 showed that if $\sigma_{k}$ is further increased, in an $\epsilon$-dependent way, then the term that is a multiple of $\|s_{k}\|^{r-1}$ in (3.5) becomes the larger of the two terms.

Lemma 3.6 Let $r>p+\beta_{p}$ and assume A.1. Then, while Algorithm 2 has not terminated, we have ${\sigma_{k}\leq\max\left\{\sigma_{0},\gamma_{2}\theta,\gamma_{2}\kappa_{1}\epsilon^{\frac{p+\beta_{p}-r}{p+\beta_{p}-1}}\right\},}$ (3.21) where $\kappa_{1}$ is defined in (3.15).

Proof. Let the right-hand side of (3.14) be denoted by $\overline{\sigma}$. It follows from Lemma 3.5 and the mechanism of the algorithm that

Thus, when $\sigma_{0}\leq\gamma_{2}\overline{\sigma}$, it follows that $\sigma_{k}\leq\gamma_{2}\overline{\sigma}$, where the factor $\gamma_{2}$ is introduced for the case when $\sigma_{k}$ is less than $\overline{\sigma}$ and the iteration $k$ is not very successful. Letting $k=0$ in (3.22) gives (3.21) when $\sigma_{0}\geq\gamma_{2}\overline{\sigma}$ since $\gamma_{2}>1$. $\Box$

We are ready to establish an upper bound on the number of successful iterations until termination.

Theorem 3.7 Let $r>p+\beta_{p}$, assume A.1 and that $\{f(x_{k})\}$ is bounded below by $f_{\rm low}$ and $\epsilon\in(0,1]$. Then for all successful iterations $k$ until the termination of Algorithm 2, we have ${f(x_{k})-f(x_{k+1})\geq\kappa_{s,p}\epsilon^{\frac{p+\beta_{p}}{p+\beta_{p}-1}},}$ (3.23) where ${\kappa_{s,p}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\eta_{1}}{r}\left(\frac{\alpha^{r}}{\sigma_{\max}}\right)^{\frac{1}{r-1}},\quad\sigma_{\max}\stackrel{{\scriptstyle\rm def}}{{=}}\max\left\{\sigma_{0},\gamma_{2}\theta,\gamma_{2}\kappa_{1}\right\},}$ (3.24) and $\kappa_{1}$ is defined in (3.15). Thus Algorithm 2 takes at most ${\left\lfloor\frac{f(x_{0})-f_{\rm low}}{\kappa_{s,p}}\epsilon^{-\frac{p+\beta_{p}}{p+\beta_{p}-1}}\right\rfloor}$ (3.25) successful iterations/evaluations of derivatives of degree $2$ and above of $f$ until termination.

Proof. On every successful iteration $k$, we have $\rho_{k}\geq\eta_{1}$; this and Lemma 3.1 imply

On every successful iteration $k$ we also have that (2.9) holds. Thus, while the algorithm has not terminated, we have

Applying the first and then the second inequality in (3.27) into (3.26), we deduce

We use that $\epsilon\in(0,1]$ in (3.21) to deduce that

where $\sigma_{\max}$ is defined in (3.24). We combine this upper bound with (3.28) to see that

which gives (3.23). Using that $f(x_{k})=f(x_{k+1})$ on unsuccessful iterations, and that $f(x_{k})\geq f_{\rm low}$ for all $k$, we can sum up over all successful iterations to deduce (3.25). $\Box$

We are left with counting the number of unsuccessful iterations until termination, and the total iteration and evaluation upper bound.

Lemma 3.8 Let $r>p+\beta_{p}$ and $\epsilon\in(0,1]$. Then, for any fixed $j\geq 0$ until termination, Algorithm 2 satisfies ${|\mathcal{U}_{j}|\leq\frac{|\log\gamma_{3}|}{\log\gamma_{1}}|\mathcal{S}_{j}|+\frac{1}{\log\gamma_{1}}\log\frac{\sigma_{\rm max}}{\sigma_{0}}+\frac{r-p-\beta_{p}}{(p+\beta_{p}-1)\log\gamma_{1}}|\log\epsilon|,}$ (3.30) where $\sigma_{\max}$ is defined in (3.24).

Proof. We apply Lemma 2.1. To prove (3.30), we use $\epsilon\in(0,1]$ and the upper bound (3.29) in place of $\sigma_{\rm up}$ in (2.11). $\Box$

Corollary 3.9 Let $r>p+\beta_{p}$ and assume A.1, that $\{f(x_{k})\}$ is bounded below by $f_{\rm low}$ and $\epsilon\in(0,1]$. Then Algorithm 2 takes at most ${\left\lfloor\frac{f(x_{0})-f_{\rm low}}{\kappa_{s,p}}\left(1+\frac{|\log\gamma_{3}|}{\log\gamma_{1}}\right)\epsilon^{-\frac{p+\beta_{p}}{p+\beta_{p}-1}}+\frac{r-p-\beta_{p}}{(p+\beta_{p}-1)\log\gamma_{1}}|\log\epsilon|+\frac{1}{\log\gamma_{1}}\log\frac{\sigma_{\rm max}}{\sigma_{0}}\right\rfloor}$ (3.31) iterations/evaluations of $f$ and its derivatives until termination, where $\kappa_{s,p}$ and $\sigma_{\max}$ are defined in (3.24).

Proof. The proof follows from Theorem 3.7 and (3.30), where we let $j$ denote the first iteration with $\pi_{f}(x_{j}+s_{j})<\epsilon$ (so the iteration where ARp terminates) and we use $j=|\mathcal{S}_{j}|+|\mathcal{U}_{j}|$. $\Box$

(Comment on $\sigma_{\min}$) We note that the lower bound on $\sigma_{k}$, $\sigma_{k}\geq\sigma_{\min}\geq 0$ for all $k$, imposed in (2.10), has not been employed in the above proofs and it is also not needed when $r=p+\beta_{p}$. It seems that in the case $r\geq p+\beta_{p}$, such a lower bound on $\sigma_{k}$ may follow implicitly from (2.9). However, the requirement involving $\sigma_{\min}>0$ is needed for the case $r<p+\beta_{p}$.

(Comment on $\epsilon$) In our main complexity results (such as Corollary 3.9), we have a restriction on the required accuracy tolerance $\epsilon\in(0,1]$; this restriction is for simplicity and simplification of expressions, so as to capture dominating terms in the complexity bounds. It is also intuitive, as we think of $\epsilon$ as (arbitrarily) ‘small’ compared to problem constants. Indeed, instead of an upper bound of $1$ on $\epsilon$, we could have used a bound depending on problem constants such as $L_{p}$, which would preserve the same dominating terms in the complexity bounds. However, as most such problem constants are generally unknown, we prefer our approach as it gives the users/readers a concrete value they can use.

The constants in the bound (3.31) and their behaviour with respect to increasing values of $p$ are discussed in Section 3.4.

For $j\in\{1,\ldots,p\}$, the derivative $\{\nabla^{j}f(x_{k})\}$ is uniformly bounded above with respect to $k$, namely,

We let $M\stackrel{{\scriptstyle\rm def}}{{=}}\displaystyle\max_{1\leq j\leq p}\left\{\left(\frac{rp}{j!\sigma_{\min}}M_{j}\right)^{\frac{1}{r-j}}\right\}$ where $\sigma_{\min}$ is defined in (2.10).

Lemma 3.10 Let $r\leq p+\beta_{p}$ and assume A.1. If $r<p+\beta_{p}$ assume also A.2 and $\sigma_{\min}>0$. If ${\sigma_{k}\geq\max\left\{\theta,\kappa_{2}M^{p+\beta_{p}-r}\right\},}$ (3.32) where $\kappa_{2}$ and $M$ are defined in (3.9) and A.2, respectively, then (3.8) holds, and so iteration $k$ is very successful.

Proof. If $r=p+\beta_{p}$, then (3.32) clearly implies (3.8) and so Lemma 3.4 applies.

If $r<p+\beta_{p}$, then we upper bound $\|s_{k}\|$ by using A.2 in (3.2), as well as $\sigma_{k}\geq\sigma_{\min}$, to deduce that $\|s_{k}\|\leq M$ where $M$ is defined in A.2. Now (3.32) implies (3.8) and so Lemma 3.4 again applies, yielding that iteration $k$ is very successful. $\Box$

We are ready to bound $\sigma_{k}$ from above for all iterations.

Lemma 3.11 Let $r\leq p+\beta_{p}$ and assume A.1. If $r<p+\beta_{p}$ assume also A.2 and $\sigma_{\min}>0$. While Algorithm 2 has not terminated, we have ${\sigma_{k}\leq\max\left\{\sigma_{0},\gamma_{2}\theta,\gamma_{2}\kappa_{2}M^{p+\beta_{p}-r}\right\}\stackrel{{\scriptstyle\rm def}}{{=}}\sigma_{\rm up},}$ (3.33) where $\kappa_{2}$ and $M$ are defined in (3.9) and A.2, respectively.

Proof. The proof follows a similar argument to that of Lemma 3.6, with (3.14) replaced by (3.32). Note also that as $\epsilon$ does not appear in the bound (3.32), (3.33) yields a constant upper bound on $\sigma_{k}$ that is valid for all $k$, irrespective of the required accuracy level $\epsilon$. $\Box$

We are now ready to upper bound the number of successful iterations of Algorithm 2 until termination.

Theorem 3.12 Let $r\leq p+\beta_{p}$, assume A.1 and that $\{f(x_{k})\}$ is bounded below by $f_{\rm low}$. If $r<p+\beta_{p}$ assume also A.2 and $\sigma_{\min}>0$. Then for all successful iterations $k$ until the termination of Algorithm 2, we have ${f(x_{k})-f(x_{k+1})\geq\kappa_{s,r}\epsilon^{\frac{r}{r-1}},}$ (3.34) where ${\kappa_{s,r}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\eta_{1}}{r}\left(\frac{\alpha^{r}}{\sigma_{\rm up}}\right)^{\frac{1}{r-1}},}$ (3.35) and $\sigma_{\rm up}$ is defined in (3.33). Thus Algorithm 2 takes at most ${\left\lfloor\frac{f(x_{0})-f_{\rm low}}{\kappa_{s,r}}\epsilon^{-\frac{r}{r-1}}\right\rfloor}$ (3.36) successful iterations/evaluations of derivatives of degree $2$ and higher of $f$ until termination.

Proof. Note that (3.26), (3.27) and (3.28) continue to hold in this case (they only use general ARp properties and the mechanism of the algorithm). Applying (3.33) in (3.28), we deduce

Using that $f(x_{k})=f(x_{k+1})$ on unsuccessful iterations, and that $f(x_{k})\geq f_{\rm low}$ for all $k$, we can sum up over all successful iterations to deduce (3.36). $\Box$

We are left with counting the number of total iterations and evaluations.

Corollary 3.13 Let $r\leq p+\beta_{p}$, assume A.1 and that $\{f(x_{k})\}$ is bounded below by $f_{\rm low}$. If $r<p+\beta_{p}$ assume also A.2 and $\sigma_{\min}>0$. Then Algorithm 2 takes at most ${\left\lfloor\frac{f(x_{0})-f_{\rm low}}{\kappa_{s,r}}\left(1+\frac{|\log\gamma_{3}|}{\log\gamma_{1}}\right)\epsilon^{-\frac{r}{r-1}}+\frac{1}{\log\gamma_{1}}\log\frac{\sigma_{\rm up}}{\sigma_{0}}\right\rfloor}$ (3.38) iterations/evaluations of $f$ and its derivatives until termination, where $\kappa_{s,r}$ and $\sigma_{\rm up}$ are defined in (3.36) and (3.33), respectively.

Proof. We first upper bound the total number of unsuccessful iterations; for this, we apply Lemma 2.1 to upper bound $|\mathcal{U}_{j}|$ with $\sigma_{\rm up}$ defined in (3.33). To prove (3.38), use (3.36) and (2.11), where we let $j$ denote the first iteration with $\pi_{f}(x_{j}+s_{j})<\epsilon$ (so the iteration where ARp terminates), and we use $j=|\mathcal{S}_{j}|+|\mathcal{U}_{j}|$. $\Box$

(Comment on $\sigma_{\min}$) Note that $\sigma_{\min}>0$ only appears/is used in the complexity bounds for the regime $r<p+\beta_{p}$ (namely in the definition of the constant $M$ in A.2) and not for the case $r=p+\beta_{p}$ (see also our Remark 3.3 (a)).

(Condition (2.9)) We have used (2.9) in the proof of Theorem 3.12 (namely, in the use of (3.28) to deduce (3.37)) and hence for obtaining the main complexity result in the regime $p<r\leq p+\beta_{p}$. This was however, not strictly necessary for obtaining same order complexity bounds (albeit with different constants) in this parameter regime, and was done for simplicity and coherence of the algorithm and results with the regime $r>p+\beta_{p}$ (for which (2.9) is needed), and for practicality as $\beta_{p}$ is not known a priori. Let us briefly outline how one could bypass the use of (2.9) in the proof of Theorem 3.12. Note first that (2.9) implies in this regime, given the constant upper bound (3.33), that $\|s_{k}\|\geq{\rm constant}\times\epsilon^{\frac{1}{r-1}}$. A similar lower bound on $s_{k}$ can be obtained directly (rather than from (2.9)) from (3.5) as follows: when $\|s_{k}\|\leq 1$, (3.5) implies $(\sigma_{k}+\theta+\kappa_{2})\|s_{k}\|^{r-1}\geq\epsilon$; thus, using the constant upper bound (3.33) on $\sigma_{k}$, $\|s_{k}\|\geq\min\{1,{\rm constant}_{\rm new}\times\epsilon^{\frac{1}{r-1}}\}$. Using the latter bound in (3.26), and that $\sigma_{k}\geq\sigma_{\min}$ and $\epsilon\in(0,1]$, we can deduce a same-order bound (in $\epsilon$) as in (3.34). This line of proof is remindful of techniques used in (for the case $\beta_{p}=1$ and $r=p+1$).

(The Lipschitz continuous case) Letting $\beta_{p}=1$ (namely, the $p$th order derivative is Lipschitz continuous) and $r=p+1$ recovers the complexity bounds in , namely, $\mathcal{O}\left(\epsilon^{-\frac{p+1}{p}}\right)$ (albeit with different constants), and shows these bounds continue to hold for any $r\geq p+1$. Note however, that condition (2.9) is not needed in the ARp algorithm in . Our previous remark (b) explains that (2.9) is not strictly needed for the complexity bounds in the regime $r\leq p+\beta_{p}$ (which includes the case $\beta_{p}=1$ and $r=p+1$) for our ARp variant, which clarifies the connection with the algorithm in .

(The case $r=p+\beta_{p}$) Despite their different proofs, when $r=p+\beta_{p}$, the complexity bound (3.38) is identical to the (limit of the) bound (3.31). Comparing the expressions of these two bounds, we find that $r=p+\beta_{p}$ implies that the $|\log\epsilon|$ term in (3.31) vanishes, and that the two complexity bounds clearly agree provided $\kappa_{s,p}=\kappa_{s,r}$ and $\sigma_{\max}=\sigma_{{\rm up}}$. Furthermore, the definitions (3.24) and (3.35) trivially imply $\kappa_{s,p}=\kappa_{s,r}$ if $\sigma_{\max}=\sigma_{{\rm up}}$. Finally, to see the latter identity, use the corresponding definitions in (3.24) and (3.33) and note that $r=p+\beta_{p}$ provides that $\kappa_{1}=\kappa_{2}$, where $\kappa_{1}$ is defined in (3.15).

The constants in the bound (3.38) and their behaviour with respect to increasing values of $p$ are discussed in Section 3.4.

4 The constants in the complexity bounds

In this section we extract the key constants and expressions in the complexity bounds (3.31) and (3.38) with respect to $p$ and $r$ and show that in important cases, they stay finite as $p$ grows, for some suitable choices of algorithm parameters.

The case $r=p+1$, $\beta_{p}\in$, $p\geq 2$. In this case, the complexity bound (3.31) applies for $\beta_{p}\in[0,1)$. When $\beta_{p}=1$ (the Lipschitz continuous case), the bound (3.38) holds; however, in Remark 3.4 (d), we showed that (3.38) and (the limit of) (3.31) coincide when $r=p+\beta_{p}=p+1$. Hence, without loss of generality, we focus on estimating (3.31) for any $\beta_{p}\in$. Again without prejudice, we ignore algorithm parameters (namely, $\gamma_{1}$, $\gamma_{2}$ and $\gamma_{3}$) that are independent of $p$ as they can easily be fixed. Then, (3.31) is a constant multiple of

where we note that the term $(p+1)$ arises from the denominator of (2.2) and $r=p+1$. Note that for simplicity of calculations, the Hölder constant $L_{p}$ in A.1 was scaled by $(p-1)!$. Thus letting $L$ denote the usual/unscaled Hölder constant, we have

where we assume that $L$ is independent, or stays bounded with $p$. (Of course, $L$ and $L_{p}$ can have further implicit dependencies on $p$ which are difficult to make precise.)

Taking (3.42) explicitly into account, and using Stirling’s formula $\left[(p-1)!\sim[(p-1)/e]^{p-1}\sqrt{2\pi(p-1)}\right]$, we deduce

where we used the standard limits $\lim_{u\rightarrow\infty}u^{\frac{1}{u}}=1$ and $\lim_{u\rightarrow\infty}c^{\frac{1}{u}}=1$, where $c>0$ is an arbitrary constant. This and (3.41) imply that

The limits in (3.44) can be achieved without difficulty by suitable choices/scalings of $\sigma_{0}$ and $\theta$, which are user-chosen algorithm parameters. In particular, let

for any constants $\overline{\sigma}_{0}$ and $\overline{\theta}$ independent of $p$; Stirling’s formula applied to $(p-1)!$ and similar calculations to (3.43) can be used to show that (3.45) satisfy (3.44).

The second term in the sum (3.39) either vanishes when $\beta_{p}=1$ or converges to zero as $p\rightarrow 0$. Proceeding to the third term in the sum (3.39), we have: from (3.40) and (3.42), we deduce $\kappa_{1}\rightarrow 0$ as $p\rightarrow\infty$ and so, irrespective of the scaling of $\sigma_{0}$ and $\theta$, $1\leq\sigma_{\max}/\sigma_{0}<\infty$. Thus the last term in (3.39) is finite.

We can safely conclude now that as $p\rightarrow\infty$, all constants in (3.39) stay bounded or converge to zero for appropriate choices of $\sigma_{0}$ and $\theta$, and so, using also that $\epsilon\in(0,1]$, the bound (3.31) approaches $\mathcal{O}(\epsilon^{-1})$.

The above discussion of limiting constants can be easily extended, with similar results, to any $r=ap+b$ with $a,b>0$ independent of $p$, provided $r>p+\beta_{p}$.

Note also that the more practical case is when $p$ is fixed and $\epsilon$ can be made arbitrarily small; then, the bound (3.31) is well-defined for all algorithm and problem parameter choices, allowing the use of simplified constants and unscaled parameters in the analysis.

The case $r=p+\beta_{p}$, $\beta_{p}\in$, $p\geq 2$. In this case, the bound (3.38) applies (note that the case $\beta_{p}=1$ was already addressed in the first case of this section). The constants in (3.38) stay bounded as $p$ grows, provided $\sigma_{0}$ and $\theta$ are scaled according to (3.45). Indeed, one can show this very similarly to the case $r=p+1$ above, using (3.9), (3.35) and (3.42) to obtain the following estimates

Letting $r=p+\beta_{p}$ in (3.35), we have

where the limit follows similarly to (3.43), using also (3.45). As $p$ grows and as a function of $\epsilon$, (3.38) approaches the same well-defined limit as (3.31), namely, $\mathcal{O}(\epsilon^{-1})$.

The case $p<r<p+\beta_{p}$, $\beta_{p}\in$, $p\geq 2$. In this case, the bound (3.38) applies. However, the limiting constants in (3.38) depend crucially on $M$ in A.2, which grows unbounded with $p$.

Discussion of complexity bounds

We now particularize our algorithm and results to the case when $p=2$ and $r=p+1$, which yields a cubic regularization model (2.2) and algorithm, with condition (2.9), namely,

imposed on any successful step $s_{k}$, and which allows $\sigma_{\min}=0$ in (2.10).

Corollary 4.1 Let $p=2$, $r=3$ and $\epsilon\in(0,1]$. Assume that $f\in C^{2}(\mathcal{F})$, and $\nabla^{2}_{x}f$ is Hölder continuous on the path of the iterates and trial points with exponent $\beta_{2}\in$. Let $\{f(x_{k})\}$ be bounded below by $f_{\rm low}$. Then for all successful iterations $k$ until the termination of Algorithm 2, we have ${f(x_{k})-f(x_{k+1})\geq\kappa_{s,2}\epsilon^{\frac{2+\beta_{2}}{1+\beta_{2}}},}$ (4.2) where ${\kappa_{s,2}\stackrel{{\scriptstyle\rm def}}{{=}}\frac{\eta_{1}}{3}\left(\frac{\alpha^{3}}{\sigma_{\max}}\right)^{\frac{1}{2}},\quad\sigma_{\max}\stackrel{{\scriptstyle\rm def}}{{=}}\max\left\{\sigma_{0},\gamma_{2}\theta,\gamma_{2}\kappa_{1}\right\},}$ (4.3) and $\kappa_{1}\stackrel{{\scriptstyle\rm def}}{{=}}3^{\frac{3-\beta_{2}}{1+\beta_{2}}}\left[\frac{L_{2}}{2(1-\eta_{2})}\right]^{\frac{2}{1+\beta_{2}}}$. Thus Algorithm 2 takes at most ${\left\lfloor\frac{f(x_{0})-f_{\rm low}}{\kappa_{s,2}}\epsilon^{-\frac{2+\beta_{2}}{1+\beta_{2}}}\right\rfloor}$ (4.4) successful iterations/evaluations of derivatives of degree $2$ of $f$ until termination, and at most ${\left\lfloor\frac{f(x_{0})-f_{\rm low}}{\kappa_{s,2}}\left(1+\frac{|\log\gamma_{3}|}{\log\gamma_{1}}\right)\epsilon^{-\frac{2+\beta_{2}}{1+\beta_{2}}}+\frac{1-\beta_{2}}{(1+\beta_{2})\log\gamma_{1}}|\log\epsilon|+\frac{1}{\log\gamma_{1}}\log\frac{\sigma_{\rm max}}{\sigma_{0}}\right\rfloor}$ (4.5) iterations/evaluations of $f$ and its first and second derivatives until termination, where $\kappa_{s,2}$ and $\sigma_{\max}$ are defined in (4.3).

Proof. Clearly, the results follow from Corollary 3.9 for $p=2$, $r=3$ and $\beta_{2}\in[0,1)$, and from Corollary 3.13 for $p=2$, $r=3$ and $\beta_{2}=1$. We note the key ingredients that are needed to obtain (4.2), with the remaining results following from standard telescopic sum arguments and from Lemma 2.1, respectively. Lemmas 3.6 and 3.11 provide the following upper bound on $\sigma_{k}$,

This bound and condition (4.1) (which is (2.9)) are then substituted into the objective decrease condition (3.26) on successful steps which here takes the form

The impact of the value of $\beta_{2}\in$ can be seen in the bound (4.5); for example, when $\beta_{2}=1$, the $|\log\epsilon|$ term disappears, in agreement with known bounds for ARC . Note that as a function of $\epsilon$, Corollary 4.1 matches corresponding bounds in (for different cubic regularization variants) and extends them to convex constraints, allowing inexact subproblem solves. Our purpose here is also to allow $p\geq 2$, and a discussion of the bounds we obtained follows.

2 General discussion of the complexity bounds

Table 4.1 gives a summary of our complexity bounds as a function of $r$ and $q$.

Several remarks and comparisons are in order concerning these bounds.

The first-order case. Note that the case $p=1$ is also covered, with a more general quadratic model and using a Cauchy analysis, in ; the same complexity bounds ensue (as a function of the accuracy) as in Table 4.1 for $p=1$; the case $\beta_{1}=0$ is also not covered in .

Sharpness. For unconstrained problems ($\mathcal{F}=\hbox{I\hskip-1.5ptR}^{n}$), the bound for the case $p=1$ and $r\geq 1+\beta_{1}$, $\beta_{1}\in(0,1]$, was shown to be sharp in . Also, the bounds for ARp with $p=2$ and $2<r\leq 2+\beta_{2}$ and $\beta_{2}\in(0,1]$ are sharp and optimal for the corresponding smoothness classes . We also note that for general $p$, $r=p+1$ and $\beta_{p}=1$ (the Lipschitz continuous case), shows the bounds for (possibly randomized) ARp variants (in ) to be sharp and optimal. The difficult example functions in increase in dimension with $p$, in contrast to uni- or bi-variate examples in .

Continuity. All bounds vary continuously with $r$ and $\beta_{p}\in$. In particular, when $r=p+\beta_{p}$, the complexity bounds in the second and third column match (for a given $p$ and $\beta_{p}$) (see also Remark 3.4 (d)).

Universality . For fixed $p$ and $\beta_{p}$, the best complexity bounds are obtained when $r\geq p+\beta_{p}$. These bounds do not depend on the regularization power $r$, and even though the smoothness parameter $\beta_{p}$ is (usually) unknown, its value is captured accurately in the complexity, even for the case when $\beta_{p}=0$ and $p\geq 2$. Note that the values of the complexity bounds as a function of the accuracy indicate that one should choose $r\geq p+1$ to achieve the best complexity when $\beta_{p}$ is unknown; and there seems to be little reason, from an evaluation complexity point of view, to pick anything other than $r=p+1$. (But, note that, as a benefit of using (2.9), one can simplify ARp’s construction by not imposing a lower bound $\sigma_{\min}$ in the $\sigma_{k}$ update (2.10).)

Complexity values in the order of the accuracy. Table 4.1 shows the increasingly good complexity obtained as $p$ grows and $\beta_{p}\in$, namely, the more derivatives are available and the smoother these derivatives are. In particular, purely as a function of $\epsilon$ and as $r$ varies, we obtain the following ranges of complexity powers : $[\epsilon^{-2},\infty)$ ($p=1$); $[\epsilon^{-\frac{3}{2}},\epsilon^{-2}]$ ($p=2$); $[\epsilon^{-\frac{4}{3}},\epsilon^{-\frac{3}{2}}]$ ($p=3$); $[\epsilon^{-\frac{5}{4}},\epsilon^{-\frac{4}{3}}]$ ($p=4$); and so on.

The Lipschitz continuous case. Letting $\beta_{p}=1$ (namely, the $p$th order derivative is Lipschitz continuous) and $r=p+1$ in Table 4.1 recovers the complexity bounds in , namely, $\mathcal{O}\left(\epsilon^{-\frac{p+1}{p}}\right)$; see also Remark 3.4 (c). Furthermore, the results here show that for our ARp variant, this complexity bound continues to hold for any regularization power $r\geq p+1$.

Loss of smoothness Note that for fixed $p\geq 2$, $\beta_{p}=0$ corresponds to the case when the objective has the highest level of non-smoothness compared to $\beta_{p}\in(0,1]$. Then ARp can still be applied, and the good complexity bounds for the case $r\geq p+\beta_{p}\geq 2$ hold.

Constants in the complexity bounds The constants in the complexity bounds for $r\geq p+\beta_{p}$ stay bounded (above) as $p$ grows, provided some user-chosen algorithm parameters are suitably scaled and that $r=O(p)$ (see Section 3.4). Thus these complexity bounds remain valid with growing $p$ and approach $\mathcal{O}(\epsilon^{-1})$.

Conclusions

We have generalized and modified the regularization methods in to allow for varying regularization power, accuracy of Taylor polynomials and different (Hölder) smoothness levels of derivatives. Our results show the robustness of the evaluation complexity bounds with respect to such perturbations. We found that complexity bounds of regularization methods improve with growing accuracy of the Taylor models and increasing smoothness levels of the objective. Furthermore, when the regularization power $r$ is sufficiently large (say $r\geq p+1$) our modification to ARp in the spirit of allows ARp’s worst-case behaviour to be independent of the regularization power and to accurately reflect the (often unknown) smoothness level of the objective. We have also generalized and to problems with convex constraints and inexact subproblem solutions. The question as to whether the complexity bounds we obtained are sharp remains open when $r\neq p+\beta_{p}$ and $p\geq 3$. This question is particularly poignant in the case when $p<r<p+\beta_{p}$: could a suitable modification of ARp achieve an (improved) evaluation complexity bound that is independent of the regularization power in this case as well?

References