A kernel-based estimator of $\nabla f$ is proposed and the projected stochastic gradient algorithm driven by this estimator is analyzed, establishing a minimax lower bound and a non-asymptotic upper bound on the optimization error.
Abstract
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.
Let $2\le k\le n$, let $\Omega\subset\mathbb{R}^n$ be open and convex, and let $u$ be a convex viscosity solution of $\sigma_k(D^2u)=1$ in $\Omega$. We prove that the set on which $u$ fails to be locally $C^2$ has vanishing $(n-1)$-dimensional Hausdorff measure. In the intermediate range $3\le k<n$, this gives a codimension-one refinement of the known almost-everywhere partial regularity, and the exponent is sharp. More generally, for a convex viscosity subsolution of $\sigma_k(D^2u)\ge\lambda>0$, we obtain Hausdorff bounds for strata defined by the affine dimension of all supporting contact sets. The proof combines a support-dependent Chou--Wang barrier argument, an estimate for the product of the smallest $k$ semiaxes of a John ellipsoid, and Mooney's convex section-covering theorem. As a direct analytical consequence, the full distributional Hessian is absolutely continuous and $u\in W^{2,1}_{\mathrm{loc}}(\Omega)$, yielding a $k$-Hessian counterpart of the $W^{2,1}$ regularity known for singular Monge--Amp\`ere solutions. In a logically separate structural part, we characterize the distinguished number of flat directions, $n-k+1$, by an asymptotic infimum mean-value formula over affine sections, and explain how this mean-value heuristic leads to the supporting-contact geometry used in the proof.
Let $n\ge2$ and let $u$ be a smooth 2-convex and semi-convex solution of \[ \frac{\sigma _2(D^2u)}{\sigma _1(D^2u)}=f(x). \] We prove an interior Hessian estimate depending on the Lipschitz norm of $f$. The proof combines the integral approach of Chen--Jian--Zhou with the algebraic reduction of the quotient equation to a $\sigma _2$ structure. The main new point is a shifted algebraic inequality that yields a shifted trace Jacobi inequality in divergence form for $\log(\Delta u+a)$. We work with the linearized operator $G=(\Delta u-f)I-D^2u$ of the equivalent equation $\sigma_2(D^2u)=f \Delta u$. The almost divergence-free identity \(\partial_iG_{ij}=-f_j\) enables us to control the \(\Delta f\) term by integration by parts solely in terms of the Lipschitz norm of \(f\). A Legendre--Lewy transformation converts the resulting degenerate divergence-form equation into a uniformly elliptic one. The estimate then follows from a mean-value inequality together with a weighted energy argument. As an application, in dimension two we obtain interior $C^2$ regularity for convex viscosity solutions with positive Lipschitz right-hand side. Moreover, our counterexamples show that the Lipschitz regularity required of the right-hand side is optimal.
For a smooth, complete and normal metric $g = e^{2u}|dx|^2$ with finite total $n$-th order $Q$-curvature on $\mathbb{R}^n$ with dimension $n \geq 2$, we first show that everywhere non-negativity (resp. non-positivity) $n$-th order $Q$-curvature $Q_g^{(n)}$ implies everywhere non-negativity (resp. non-positivity) of the sectional curvature. Based on this fact, we secondly show that, once $Q_g^{(n)}$ is non-negative, then for any compact domain $\Omega \subset \mathbb{R}^n$ with smooth boundary $\partial\Omega$, the following sharp isoperimetric inequality holds: $$|\partial\Omega|_g^{\frac{n}{n-1}} \geq n^{\frac{n}{n-1}} |\mathbb{B}^n|^{\frac{1}{n-1}} \left(1 - \frac{2}{(n-1)!\,|\mathbb{S}^n|} \int_{\mathbb{R}^n} Q_g^{(n)} \, d\mu_g\right) |\Omega|_g.$$ The third claim in this article is that, if the $n$-th order $Q$-curvature, $Q_g^{(n)}$, is non-positive and under the main assumption that Cartan-Hadamard conjecture holds true, then we have the sharp inequality $$|\partial\Omega|_g^{\frac{n}{n-1}} \geq n^{\frac{n}{n-1}} |\mathbb{B}^n|^{\frac{1}{n-1}}|\Omega|_g.$$
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.
It is proved that every deterministic first-order method requires $\Omega(\ell\Delta\kappa/\epsilon^2)$ oracle queries in the worst case to find $x$ satisfying $\Phi(0)-\inf_x\Phi(x)$ and that the linear dependence on $\kappa$ is unavoidable for deterministic first-order methods.
We consider convex admissible viscosity solutions of $\sigma_2(D^2u)=f>0$ in an open subset of $\mathbb R^n$, where $n\ge2$, $0<\alpha<1$, and $f\in C_{\mathrm{loc}}^{0,\alpha}$. We prove that every such solution belongs to $C_{\mathrm{loc}}^{2,\alpha}$. For solutions in $B_2$, we also prove a uniform $C^{2,\alpha}(B_{1/4})$ estimate under an $L^\infty$ bound for $u$, a positive lower bound for $f$, and a $C^{0,\alpha}$ bound for $f$.
Xingchen Zhou, Ruixuan Zhu· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
