A variant of the cubic-regularized Newton method for nonconvex optimization that is parameter-free in that it requires no prior knowledge of problem-dependent parameters is analyzed, and an oracle complexity bound is derived for finding an $(varepsilon, \delta)-second-order stationary point.
Abstract
We analyze a variant of the cubic-regularized Newton method for nonconvex optimization. This variant is parameter-free in that it requires no prior knowledge of problem-dependent parameters. Under the generalized smoothness condition $\|\nabla^3 f(x)\| \leq L_0 + L_1 \|\nabla f(x)\|$, we derive an oracle complexity bound for finding an $(\varepsilon, \delta)$-second-order stationary point. This assumption is weaker than the generalized smoothness conditions used in existing analyses of second-order methods, while the complexity bound improves upon existing guarantees for parameter-free second-order methods. In particular, when $L_1 = 0$, the bound matches the optimal dependence on $L_0$ as well as on $\varepsilon$, $\delta$, and the initial function value gap, up to additive logarithmic terms. To establish this bound, we derive Taylor-type inequalities and prove their equivalence to the generalized smoothness condition.
We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on $\mathbb{R}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\eta=\Theta(1/\sqrt n)$, the last iterate achieves an optimization error of order $d/\sqrt n$, showing that the extra $\log n$ factor appearing in high dimensions is unnecessary in every fixed dimension. We complement this result with a matching linear-in-$d$ lower bound and show that the sharp worst-case dimension-horizon dependence is of order $\min\{d,\log n\}/\sqrt n$. This solves, in particular, a COLT open problem posed by Koren and Segal in 2020 and shows that the correct dependence on the dimension is linear rather than logarithmic.
We study the deterministic first-order oracle complexity of finding stationary points of the value function in smooth nonconvex-Polyak-{\L}ojasiewicz (NC-P{\L}) minimax optimization. We assume that the objective is jointly $\ell$-smooth and satisfies the $\mu$-P{\L} condition in the dual variable, and that its value function $\Phi(x):=\max_y f(x;y)$ satisfies $\Phi(0)-\inf_x\Phi(x)\leq\Delta$. When $\kappa:=\ell/\mu\gtrsim 1$ and $0<\epsilon^2\lesssim\ell\Delta$, we prove that every deterministic first-order method requires $\Omega(\ell\Delta\kappa/\epsilon^2)$ oracle queries in the worst case to find $x$ satisfying $\|\nabla\Phi(x)\|\leq\epsilon$. This rate matches the known upper bound in its dependence on $(\ell,\Delta,\kappa,\epsilon)$ [Yang et al., 2022] and shows that the linear dependence on $\kappa$ is unavoidable for deterministic first-order methods.
We develop accelerated algorithms for convex $(H_0,H_1)$-smooth optimization, where $\|\nabla^2 f(x)\|\le H_0+H_1(f(x)-f^*)$. This class generalizes standard smoothness and contains the $(L_0,L_1)$-smooth class. Combining a Nesterov-type accelerated gradient scheme with small-dimensional relaxation and phase restarts, we obtain a full-gradient method with iteration complexity $\widetilde O(\sqrt{H_0\widetilde R^2/\varepsilon}+\sqrt{H_1\widetilde R^2}\log(F_0/\varepsilon))$. We extend the same approach to randomized coordinate optimization, obtaining a coordinate method with uniform sampling whose iteration complexity carries the standard factor $d$, and a coordinate method with non-uniform sampling whose iteration complexity is governed by $S_{1/2}^{(j)}=\sum_i\sqrt{H_{j,i}}$. These results provide, to our knowledge, the first accelerated full-gradient and coordinate guarantees for this convex class. We also provide practical implementation recommendations. Experiments confirm the predicted acceleration, gains from non-uniform sampling, and the viability of inexact relaxation.
We study the first-order oracle complexity of finding a queried point with small gradient in $\ell_p$ geometry, with particular attention to the information needed to adapt the unknown smoothness and distance scales. In the strict counted local value--gradient model, no finite complexity bound can depend only on $LR/\eps$ without a nondegenerate local scale observation: a one-dimensional construction keeps $LR/\eps=4$ while defeating every prescribed finite query budget. We resolve Diakonikolas's general-$\ell_p$ parameter-free extension question for every fixed $1<p<\infty$. Under a nondegenerate secant initialization, the method knows neither the smoothness constant $L$, the initial solution distance $R$, nor $f^*$, and returns a queried point $\widehat x$ with $\|\nabla f(\widehat x)\|_q\le\eps$. For fixed finite $p>2$, we first establish the dimension-free deterministic known-parameter upper exponent $p/(p+2)$ in $K=LR/\eps$, matching the published lower polynomial exponent under its horizon and dimension qualifications. The finite local routine fits the same observable scale--radius procedure, so this exponent is preserved without knowing $L$ or $R$. Writing $\Kbar=\max\{1,LR/\eps\}$, the post-initialization pair-oracle complexity is $O_p(\Kbar^{1/2})$ for $1<p<2$, $O(\Kbar^{1/2})$ for $p=2$, and $O_p(\Kbar^{p/(p+2)})$ for $p>2$, together with the additive calibration cost $O_p(\log(e+L/M_0))$ in every regime.
We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this class. This may be surprising due to the fact that accelerated methods are readily available under the assumption of smoothness in $\ell_1$-norm. While Dragomir et al. (Mathematical Programming, 2022) have already showed that acceleration might be impossible under relative smoothness, their prox-function is pathological and constructed together with the hard instance. In contrast, we show non-acceleration for a specific prox-function with particularly favorable structure. We also extend the result to the quantum setting, proving the same lower bound in the class of functions $L$-smooth relative to negative von Neumann entropy on the spectrahedron of $d \times d$ Hermitian positive-semidefinite matrices with unit trace.
Jacob M. Aguirre, Dmitrii M. Ostrovskii· 0 citations
We study deterministic first-order minimization of a convex function without prior knowledge of the objective's growth, smoothness regime, or associated parameters. We develop anytime, parameter-free bundle-level methods that adapt simultaneously to these unknown properties and attain best-known oracle complexities. For nonsmooth Lipschitz objectives satisfying quadratic growth, the proposed bundle-level W-certificate method (BLW) achieves the optimal complexity without requiring the growth modulus or target accuracy as input. We then introduce an accelerated variant, A-BLW. Without knowing the H\"older smoothness parameters, the quadratic-growth modulus, or the target accuracy, A-BLW attains the optimal rates in the nonsmooth, weakly smooth, and smooth regimes. Central to both methods is an affine W-certificate, a condition based on the descent-slowness of an affine minorant that converts the geometry of a bundle model into an optimality-gap guarantee under quadratic growth. A stopping-time analysis further shows that the same A-BLW algorithm, without modification, achieves the corresponding best-known rates for general convex objectives and for objectives satisfying H\"older growth of order at least two. Numerical experiments illustrate the practical performance of the proposed methods.