The first accelerated full-gradient and coordinate guarantees for this convex class are provided, to the knowledge, and practical implementation recommendations are provided.
Abstract
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.
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.
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.
We study $(2+1)$-dimensional oscillatory integral operators of the form \[ T_\lambda f(x,y)=\int_{\mathbb{R}}e^{i\lambda P(x,y)t^k}\psi(x,y,t)f(t)dt,\qquad k\geq 1, \] where the phase $P$ is a real-analytic function with a critical point at the origin. We establish the sharp $L^2\to L^2$ decay rate of $\frac12\min\{1/h_{P}, 1/k\}$, where $h_{P}$ denotes Varchenko's Newton height of $P$. The two terms in the minimum reflect a natural competition between the spatial degeneracy of $P$ and the temporal degeneracy of $t^k$; their optimality is confirmed by a Knapp-type and a focusing example, respectively. A $TT^{*}$ reduction transforms the $L^2$ estimate into a scalar oscillatory integral, allowing Varchenko's theorem to apply directly. Building on this foundation, complex interpolation yields the sharp $L^2\to L^{2k+2}$ bound. Finally, in the regime $h_{P}\geq k$, we obtain sharp $L^2\to L^p$ decay estimates for all $p$.
We prove that the $L_1$-discrepancy with arbitrary nonnegative weights suffers from the curse of dimensionality. More precisely, for every $\varepsilon \in (0,1)$ and $d \in \mathbb{N}$, the inverse of the $L_1$-discrepancy satisfies \[ N_{1,+}(\varepsilon, d) \ge \frac{(1-\varepsilon)^2}{1 + \varepsilon} \left( \frac{3+2 \sqrt{3}}{6}\right)^d, \] where $(3+2\sqrt{3})/6 = 1.07735\ldots$. The proof combines a change to a volume-biased probability measure with a fractional-moment estimate for the normalized discrepancy function. The lower bound applies, in particular, to equally weighted point sets. The argument uses the nonnegativity of the weights in an essential way and does not cover arbitrary signed weights.
We study convex-concave minimax optimization problems with bilinear coupling of the form $\min_{x\in \mathcal X}\max_{y\in \mathcal Y} \; f(x)+\langle y,\mathbf{B}x\rangle-g(y),$ where the functions $f$ and $g$ have H\"older continuous (sub)gradients. This setting covers a broad range of regimes, from nonsmooth problems with bounded subgradient variation to smooth problems with Lipschitz continuous gradients; for a smooth component used in the coupling-induced regularizer, its Lipschitz-gradient constant is assumed to hold in the ambient space. We propose a sliding method that exploits the composite structure of the problem by querying the oracles associated with $f$, $g$, and the bilinear coupling operator at prescribed frequencies determined by their individual properties. The method is based on a recursive sliding scheme for monotone variational inequalities. We establish convergence guarantees under H\"older continuity and show how the resulting complexity bounds depend explicitly on the H\"older exponents, H\"older constants, strong convexity parameters, and spectral properties of the coupling matrix. Our analysis covers nonstrongly convex and partially strongly convex regimes. For stochastic problems, we prove a uniform expected-gap bound in the degenerate regime and, under ambient smoothness and positive effective curvature, convergence up to an explicit noise floor. Numerical experiments reproduce the predicted H\"older exponents and confirm that the number of gradient evaluations required for each function separates according to its own smoothness level rather than the worse of the two. A tomographic benchmark shows runtime gains when gradient evaluations are more expensive than the additional matrix-vector products.
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
