This work develops comparison-oracle variants of Normalized Gradient Descent and Gradient Descent with Polyak stepsizes and establishes explicit upper bounds on the approximation error that guarantee convergence and derive convergence rates for all proposed methods.
Abstract
Generalized smoothness, such as (L0, L1)-smoothness, have recently attracted considerable attention due to their ability to model optimization problems arising in modern machine and deep learning, where the classical Lipschitz assumptions of the gradient is often violated. At the same time, computing exact gradients may be impractical or computationally expensive in many applications. In this work, we study convex (L0, L1)-smooth optimization (for normalized gradient method we consider quasi-convex problems too) under access only to a normalized approximation recently proposed Comparison Oracle, which returns an inexact normalized gradient in linear time with a bounded absolute error. Within this framework, we develop comparison-oracle variants of Normalized Gradient Descent and Gradient Descent with Polyak stepsizes. We establish explicit upper bounds on the approximation error that guarantee convergence and derive convergence rates for all proposed methods. Unlike existing analyses, our results require neither classical smoothness assumptions nor access to exact gradients or their exact normalized counterparts. Finally, numerical experiments corroborate the theoretical findings.
We study stochastic convex optimization under asymmetric \((L_0,L_1)\)-generalized smoothness, a model motivated by machine-learning objectives whose local curvature may grow with the gradient norm. We assume an unbiased first-order oracle with additive norm-sub-Gaussian noise. Acceleration is difficult in this setting because momentum may enter regions of much larger curvature, while stochastic gradients cannot reliably certify an unrestricted trajectory. We propose \textsf{ARC-SG}, a two-phase accelerated method: Phase~I reduces excessively large gradients using a generalized-smoothness-aware stochastic step, then Phase~II solves strongly convex proximal subproblems by a restarted accelerated solver confined to certified smoothness balls. Exact proximal points do not increase the gradient norm, allowing these certificates to propagate through the outer loop. The contribution is a query-by-query certified-localization construction with explicit generalized-smoothness factors and a strongly convex restart extension. \textsf{ARC-SG} achieves, with high probability, an accelerated optimization contribution and smooth-subclass-optimal statistical dependence on accuracy, up to logarithmic and generalized-smoothness factors. Its convex accuracy exponents agree with a contemporaneous public stochastic-acceleration result under a broader smoothness and affine-variance model; our distinction is the certified geometry, explicit parameter accounting, and strongly convex guarantee. The results recover classical accelerated stochastic rates when \(L_1=0\). Experiments on objectives with unbounded gradients illustrate the two-phase mechanism and its finite-budget advantage.
D. Dvinskikh, A. Gasnikov, A. Lobanov et al.· 0 citations
This work can specifically ensure, without any smoothness assumptions, convergence to Mordukhovich stationarity as long as the base directions asymptotically revert to the negative gradient for small stepsizes.
In smooth convex optimization, the gradient norm is a directly observable measure of stationarity. Accelerating a first-order method that minimizes the gradient norm is known to be more delicate than accelerating the minimization of function values. Optimal accelerated methods such as OGM-G (Kim&Fessler, 2021) are known to exist for any prescribed finite horizon, but their coefficients depend explicitly on the length of that horizon, i.e. the number of iterations. We ask what kind of acceleration is feasible when the stopping horizon is unknown to the method, i.e. for horizon-independent methods. Diakonikolas&Wang (2022) conjectured that an $\Omega(N^{-1})$ lower bound on the squared gradient norm holds at every horizon $N$ for any nonadaptive, horizon-independent linear-span first-order method. We disprove this pointwise conjecture by exhibiting a method that achieves near-$N^{-2}$ last-iterate guarantees on a density-one set of horizons. We show instead that an $\Omega(N^{-1})$ lower bound must hold for infinitely many horizons. More precisely, if $\mathcal G_N(\mathcal A)$ denotes the bound on the squared gradient norm after $N$ iterations for a method $\mathcal A$, we prove that $\limsup_{N\to\infty}N \mathcal G_N(\mathcal A) \ge 1/2$ for any method $\mathcal A$. This bound is sharp: the constant $1/2$ is exactly attained by the horizon-independent gradient-descent schedule of Rotaru et al. (2026). In addition, we show that the above two extreme behaviors cannot be achieved by the same method: any method $\mathcal A$ with an $o(N^{-1})$ guarantee on a subsequence of iterates must satisfy $\limsup_N N \mathcal G_N(\mathcal A)=\infty$. In contrast, best-so-far output admits a uniform $O(N^{-2})$ guarantee.
Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study gradient-norm minimization for convex functions that are $(L,\kappa)$-H\"older smooth with respect to the $\ell_p$-norms, $p \geq 1$. We develop algorithms that achieve near-optimal gradient-oracle complexity for this problem. In the smooth case, our results resolve the previously open setting $p>2$. For H\"older-smooth objectives, we close the complexity gap throughout the full $p$-range, including to the best of our knowledge, a gap in the Euclidean case. We provide two families of algorithms: the first one comes with a simple iteration and generalizes a phenomenon known as mirror duality, exploiting dual behaviours of algorithms with errors and inexact computations. The second makes use of accumulating regularizers centered at different approximate solutions, which we sequentially minimize in order to provide our near-optimal rates.
Nico Pelleriti, Maryam Shiran, David Martínez-Rubio et al.· 0 citations
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.
This study presents a novel Deep Proximal Gradient Descent framework for ill-posed problems by employing a tailored second-order differentiable Input-Convex Neural Networks (ICNNs) as a learned regularizer. A key contribution is the design of convex residual mapping, which preserves the convexity of the regularized objective, thereby enhancing the interpretability of the deep network without sacrificing its expressive power. Based on this framework, we develop two types of algorithms. For linear problems, the ICNN-based regularizer is embedded into the standard proximal gradient structure. For nonlinear problems, we introduce an innovative formulation that employs the learned residual to guide gradient descent, while using the traditional data misfit as a proximal regularizer to avoid network-dominated spurious solutions. Building on this iterative scheme, we establish groundbreaking convergence results for both algorithms, complete with rigorous proofs. Extensive numerical experiments, particularly on real low-dose Computed Tomography data, validate the superior imaging quality and high computational efficiency of our algorithms.
T. Ye, Guangyu Gao, Yang Li et al.· Inverse Problems· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
