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 consider the problem of minimizing the $k$-th order partial derivative $f=\partial_j^k g$ of an unknown function $g$ along a fixed coordinate direction $j$, based on noisy queries of $g$. Assuming that $g$ has H\"older regularity ${\beta+k}$ for some $\beta\ge 2$, that $f$ is strongly convex on a compact convex set $\Theta\subset\mathbb{R}^d$ and that $g$ and $f$ satisfy mild boundedness and Lipschitz regularity conditions on $\Theta$, we propose a kernel-based estimator of $\nabla f$ and analyze the projected stochastic gradient algorithm driven by this estimator. We obtain a non-asymptotic upper bound on the optimization error of the order $d^{(2\beta+k-1)/(\beta+k)}\,N^{-(\beta-1)/(\beta+k)}$, where $N$ is the total number of queries. We also establish a minimax lower bound of the order $N^{-(\beta-1)/(\beta+k)}$ showing that this rate is optimal in $N$ over all sequential algorithms.
A. Akhavan, Sirine Louati, Alexandre B. Tsybakov· 0 citations
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.
It is proved that every deterministic first-order algorithm requires a first-order oracle that returns both the function value and the full subdifferential at every query point, and establishes the optimal deterministic oracle complexity.
A lower bound of $\Omega(\,\frac{d^2}{\log(d+1)})$ on the oracle complexity in this setting is provided, to close this gap dating back to 1996, up to polylogarithmic factors.
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.
Let $Q\geq 1$ be large, and $\delta \in(0,1)$ be small. Denote by $\mathcal C \subset \mathbb R^3$ a sufficiently smooth curve with non-vanishing curvature and torsion. How many rational points $\mathbf{a}/q$ of height $q\in[Q,2Q]$ are $\delta/q$-near $\mathcal C$? This manuscript provides an essentially optimal answer. We show that the folklore conjectures are incorrect for certain manifolds with codimension $\ge 2$, including the moment curve $(t,t^2,t^3)$. The reason is a hitherto hidden `major arc'type obstruction. We also establish matching upper bounds (up to endpoints). Our argument combines purely Fourier analytical techniques with the planar counting results by Vaughan--Velani.
Mingfeng Chen, A. Seeger, Rajula Srivastava et al.· 2 citations· ⚡1