A new, fast adaptive regularization methods is proposed and analyzed under local Lipschitz smoothness of the $p$-th order tensor, matching the complexity bounds of standard tensor methods under global Lipschitz smoothness yp to logarithmic terms.
Abstract
A new, fast adaptive regularization methods is proposed and analyzed under local Lipschitz smoothness of the $p$-th order tensor. For nonconvex problems, it achieves the optimal $\mathcal{O}\!\left(|\log(\epsilon)|\epsilon^{-(p+1)/p}\right)$ complexity to obtain first-order $\epsilon$-stationary points and in the convex case, it yields $\mathcal{O}\!\left(|\log(\epsilon)|\epsilon^{-1/p}\right)$ iterations to drive the optimality gap below $\epsilon$, thus matching the complexity bounds of standard tensor methods under global Lipschitz smoothness yp to logarithmic terms. The proposed algorithm follows the line of standard tensor methods with an appropriately chosen regularization and suitable modifications. Initial numerical experiments and comparisons for some nonconvex regression problems are made with the standard adaptive cubic regularization where we showcase some potential of the proposed method.
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.
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.
In this paper, we present a novel second-order method called Accelerated Inexact Newton Extragradient (AINE) for convex optimization using $\delta$-inexact Hessians. We show that AINE can find an $\epsilon$-solution in the inexact second-order oracle (ISO) complexity of $\mathcal{O}( (\delta/\epsilon)^{1/2} + (L_2/\epsilon)^{2/7} )$ when the Hessian is $L_2$-Lipschitz continuous, and a better complexity of $\mathcal{O}( (\delta/\epsilon)^{1/2} + (L_3/\epsilon)^{1/5} )$ when the third-order derivative is $L_3$-Lipschitz continuous. Notably, each iteration of our method can be conducted in the same running time as matrix multiplication up to logarithmic factors. In addition, we also establish matching oracle complexity lower bounds for both setups, demonstrating the optimality of our methods.
Lesi Chen, Chengchang Liu, Luo Luo et al.· 1 citation
We study online discrepancy minimization: vectors $v_1,\ldots,v_T\in\mathbb{R}^n$ arrive sequentially, and each must immediately be assigned a sign $x_t\in\{\pm1\}$, with the aim of minimizing $\|\sum_{t=1}^T x_t v_t\|_\infty$. We give a polynomial-time potential-based algorithm combining a regularization of the $\ell_\infty$-norm with restriction to an adaptively chosen coordinate set. For i.i.d. inputs with independent, symmetric, centered, unit-variance sub-Gaussian coordinates of sub-Gaussian norm at most $\sigma$, the algorithm achieves terminal discrepancy $O(\sigma^8\sqrt{n})$ with probability at least $1-\exp(-\Omega(\sigma^3\sqrt{n}))$. If the coordinates are independently masked by Bernoulli variables with mean $k/n$, where $k\gtrsim(\log n)^2$, the bound improves to $O(\sigma^8\sqrt{k})$, with failure probability $\exp(-\Omega(\sigma^3\sqrt{k}))$. Both guarantees hold for every prescribed finite horizon $T$, with no dependence on $T$. The dense result substantially generalizes a theorem of Bansal and Spencer (2020) for Rademacher inputs and gives an efficient $O(\sqrt{n})$ bound for Gaussian inputs, as conjectured by Gamarnik et al. (2022). When $T$ is polynomially larger than $n$, this is conditionally close to optimal: under worst-case hardness assumptions for standard approximate lattice problems, Vafa and Vaikuntanathan (2025) showed that no polynomial-time algorithm, even offline, can improve the $\sqrt{n}$ scale by a fixed polynomial factor in $T/n$.
We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$\Omega\left( \frac{\Delta L}{\epsilon^2} + \frac{\Delta L\sigma^2}{\epsilon^4} \right)$$ queries to find a point with expected gradient norm at most \(\epsilon\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.
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.