We study whole-sequence convergence of the smoothing-based full-splitting proximal subgradient method (S-FSPS) for structured nonconvex and nonsmooth fractional programs, introduced by Bo\c{t}, Li, and Tao (SIAM J. Optim., 35(4):2623--2653, 2025) as Algorithm~4.1. Existing theory guarantees only the existence of a subsequence converging to a limiting lifted stationary point. We show that this guarantee is sharp by constructing two admissible instances whose corresponding primal sequences both have cluster set $\{1\}\times\mathbb S^1$ and infinite length, although every cluster point is a limiting lifted stationary point. The construction prescribes a slowly rotating spiral and realizes it exactly through a compatible first-order jet and a $C^{1,1}$ Whitney extension. In the first instance, $A$ has rank one and every smoothing-dual iterate is nonzero. In the second, the feasible set is full-dimensional, $A$ has full row rank, and each of $f\circ K$, $g\circ A$, and the numerator $g\circ A+h$ is nonconstant on the feasible set. The first instance also yields a nonconvergent example for the corresponding variable-smoothing, single-loop, full-splitting method for nonconvex and nonsmooth composite optimization, although that method still admits a subsequence converging to an exact stationary point. Thus, a vanishing but nonsummable smoothing schedule does not imply whole-sequence convergence.
We give a counterexample to the convergence conjecture in Remark 12 of [Bolte&Pauwels, 2021] for mini-batch stochastic approximation with definable potentials. The construction uses two convex piecewise-affine, hence semialgebraic, summands on $\mathbb{R}$. We choose a deterministic nonincreasing block stepsize sequence satisfying $\alpha_k = o(1/\log k)$ and an admissible minimum-norm selection from each aggregate batch field. On successive blocks, the iterates form lazy reflected random walks on nested dyadic lattices. An explicit endpoint-cover-time estimate, Markov's inequality, and the first Borel-Cantelli lemma imply that almost surely every sufficiently late block's iterates visit their entire lattice. Consequently, the iterates remain in $[-1,1]$ but do not converge, and their accumulation set is exactly $[-1,1]$, on which the averaged objective is constant. Finally, the construction has $\sum_k \alpha_k^2 =\infty$. Both Chat-GPT 5.6 (Sol) and Gemini Pro 3.1 (DeepThink) were used in the development and drafting of this result.
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.
The classical Strang projector-splitting integrator is widely observed to converge with order two, whereas the error analysis that remains uniform as the smallest singular value retained in the low-rank approximation tends to zero proves only order one. We show that this gap is intrinsic under the standard assumptions. We construct $3\times3$ matrix differential equations that are $C^2$ in time and smooth in the matrix variable, with rank-two initial data that satisfy uniform boundedness, Lipschitz, tangency-defect, and regularity bounds. Nevertheless, the exact-subflow Strang method has a nonzero $h^2$ term in the local error over one periodic forcing cycle consisting of four Strang steps. Repetition of that cycle rules out a global second-order bound whose constant and stepsize threshold are independent of the retained singular values. The mechanism is a rapid rotation of the factor directions associated with the small singular value: first-order consistency is preserved, but the changing projection spaces prevent the cancellation normally expected from a symmetric Strang composition. Hence the robust first-order result cannot, under these assumptions alone, be upgraded to robust second order for the classical projector-splitting method.
It is shown that any first-order method guaranteeing a bound on the primal objective gap f(x_N)-f(x_\star) assuming only a bound on $\|x_0-x_\star\|$ actually has a stronger guarantee on an explicit, computable primal-dual gap at the same rate.
In this paper, we exhibit a randomized first-order algorithm to compute Goldstein approximate second-order stationary points of $L$-smooth functions, using tools from randomized smoothing. The algorithm has oracle complexity $\widetilde{O}({ n^2}/{\varepsilon^9}+{ n^3}/{\varepsilon^7})$, where $n=1,2,\ldots$ is the input dimension and $\varepsilon>0$ is the (common) tolerance. We also present extensions to weakly convex functions and applications to bilevel optimization.
Cubic regularized Newton methods have the optimal $\mathcal{O}(\epsilon^{-3/2})$ global rate, but a dense subproblem solve limits the feasible block size. Scalable Cubic Newton variants replace the true block curvature with a diagonal, low-rank, Kronecker-factored, or sketched surrogate and, most often, give up the exact cubic step. We introduce a blockwise optimizer that minimizes an independent cubic model per parameter tensor over the true block Hessian, under a per-block adaptive cubic constant and a monotone guard on the full loss. Arbitrarily large tensors are handled matrix-free in a Lanczos-built Krylov subspace, where we prove that the step minimizes the cubic model. The theory also supplies the $\mathcal{O}(\epsilon^{-3/2})$ iteration complexity bound, a second-order guarantee, and monotone per-block descent. Four variants of this outer scheme are evaluated against the original adaptive regularization with cubics (ARC) optimizer, some other recent cubic Newton variants, Adam, SOAP, and L-BFGS. On a 91.4M-parameter implicit neural representation (INR), the variants introduced in this work are the only evaluated here cubic Newton methods whose steps stay exact on every block. Run to full convergence on FINER 2D image fitting, one of the ARC variants introduced here, ARC-$\varphi_1$, reaches 133.5 dB peak signal-to-noise ratio, while tuned Adam plateaus at 78.2 dB after about 70 minutes. In that time ARC-$\varphi_1$ reaches 95.6 dB.
R. Podorozhny· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
