Nonsmooth Convex Optimization

Momentum

3 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 16

Sep 21, 2026math.OC

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.

Dan Garber

Faculty of Data and Decision Sciences Technion - Israel Institute of Technology

Oracle Complexity Optimization Convergence Analysis Nonsmooth Convex Optimization

Ask PDF

Sep 17, 2026math.OC

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

We study efficient algorithms for realizing the first-order oracle complexity of optimization of

G

-Lipschitz convex functions with respect to the

\ell_{q}

-norm over an

\ell_{p}

-ball of radius

R

, where

1\leq p,q\leq \infty

. For

p<q

, we obtain error

\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})

after

T

oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is

\widetilde{O}(GR/T)

for Euclidean Lipschitzness over an

\ell_1

-ball of radius

R

(

p=1,q=2

). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of

R B_{p}^{d}

, we introduce a novel notion of stable center whose movement is bounded by

\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}})

in the

\ell_{q}

-norm after

T

steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.

David Martínez-Rubio, Cristóbal Guzmán

IMDEA Software Institute, Madrid, Spain · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile

Constrained Optimization Nonsmooth Convex Optimization

Ask PDF

Sep 17, 2026math.OC

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

We study first-order black-box convex optimization over an

\ell_p

-ball for objectives Lipschitz in the

\ell_q

-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set (

p < q

) can improve convergence rates in convex optimization, and matching prior lower bounds up to logarithmic factors. Our rates include

\widetilde O(1/T)

for convex Euclidean-Lipschitz optimization over the

\ell_1

-ball, improving on the

O(1/\sqrt{T})

classical rate under general assumptions. The key technical device is a new online learning game, where the comparator is evaluated using the maximum of affine losses observed so far. We bound the value of this game above and below in terms of a combinatorial online learning quantity: the sequential fat-shattering dimension, which we characterize for the

\ell_p / \ell_q

case. Our results generally apply when the feasible set

X

and the set of possible subgradients

H

are convex, centrally symmetric, and admit a type of minmax theorem, advancing on a fundamental question by Sridharan [Sri12, Section 10.1.2, Q3]. As a geometric consequence of our analysis, of independent interest, we obtain estimates for the expected distance of a convex hull of samples to their mean in several Banach geometries, a version of the celebrated Wendel's theorem (Wen62), but quantitative and for bounded general distributions as opposed to centrally symmetric ones.

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1

IMDEA Software Institute, Madrid, Spain · Purdue University, West Lafayette, IN, USA · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile +1

Nonsmooth Convex Optimization

Ask PDF

Aug 13, 2026cs.LG

Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target

π(dx)\propto \exp\{-f(x)-g(x)\}\,dx, \qquad x\in\mathbb R^d,

where

f

m

-strongly convex with

L_f

-Lipschitz gradient and

g

is convex and

G

-Lipschitz. Let

g_λ

be the Moreau envelope of

g

π_λ

the corresponding smoothed target, and

a_λ=\operatorname{tr}H_λ

, where

H_λ

is the a.e./weak Hessian of

g_λ

. We show that the leading MYULA discretization error is controlled by the reference active trace

B_{\mathrm{ref}}

, the average of

a_λ

along the heat substep of one MYULA update started from

π_λ

, rather than by the global curvature bound

d/λ

. If

M_λ

is an a.e. upper bound for

a_λ

, then, up to logarithmic factors,

N \lesssim \frac{1}{m} \left[ L_f + \frac{ τ_f+G^2+B_{\mathrm{ref}} }{ \varepsilon_{\mathrm{alg}}^2 } + \frac{M_λ}{\varepsilon_{\mathrm{alg}}} \right], \qquad τ_f:= \sup_x\operatorname{tr}\nabla^2 f(x),

iterations suffice to ensure

\sqrt m\,W_2(μ_N,π_λ)\leq\varepsilon_{\mathrm{alg}}

, where

μ_N

is the law of the

N

-th iterate and

W_2

is the quadratic Wasserstein distance. We also prove the Moreau-bias bound

\sqrt m\,W_2(π_λ,π) \leq \frac{G^2λ}{4}.

Thus, choosing

λ\asymp\varepsilon/G^2

gives an end-to-end guarantee for

π

. The universal estimate

B_{\mathrm{ref}}\leq d/λ

yields

\widetilde O(\varepsilon^{-3})

accuracy dependence. For the structured piecewise-linear, lasso-type, group, and total-variation penalties considered here, curvature--tube estimates make

B_{\mathrm{ref}}

independent of

λ

, yielding

\widetilde O(\varepsilon^{-2})

for the same classical MYULA kernel.

Yuchen Xin, Zhihua Zhang

School of Mathematical Sciences, Peking University

Langevin Dynamics Sample Complexity Convergence Analysis Nonsmooth Convex Optimization

Ask PDF

Jul 8, 2026stat.ML

Finding a stationary point of a stochastic convex problem

We consider the problem of finding stationary points for stochastic convex optimization problems. Rather than surrogates to stationarity, such as a proximity-to-stationarity guarantee or small gradient of the Moreau envelope, we ask for a stronger notion: that the subdifferential of the objective actually contains a small element. This criterion is non-trivial, because subdifferentials of convex functions fail to converge uniformly, even in arbitrarily small neighborhoods of the optimum. Our convergence guarantees rely on dimension theory to decompose the graph of the subdifferential of a convex function, showing how stochastic sampling preserves "pieces" of these graphs, and allowing effective application of proximal-point-like methods.

Felipe Areces, John Duchi, Malo Sommers

Stanford University

Stochastic Optimization Convergence Nonsmooth Convex Optimization

Ask PDF

Jul 2, 2026math.OC

Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization

In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods.

Siyuan Zhang, Nachuan Xiao, Xin Liu

Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Nonsmooth Convex Optimization Decentralized Optimization

Ask PDF

Jun 23, 2026math.OC

New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon

n

, we consider the standard fixed stepsizes

η=Θ(1/\sqrt n)

. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order

1/\sqrt n

, thereby removing the extra

(\log n)

factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order

(\log n)/\sqrt n

. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1

Department of Computer Science, Aarhus University, Aarhus, Denmark · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic Optimization Last-Iterate Convergence Convergence Analysis Stochastic Optimization Convergence Nonsmooth Convex Optimization

Ask PDF

Jun 21, 2026math.OC

Adam Converges in Nonsmooth Nonconvex Optimization

Adam is one of the most widely implemented and influential modern optimizers. Why is it effective across different optimization problems in practice? This question arguably lies at the center of the optimization community over the last decade and has motivated a substantial body of work aimed at understanding its convergence behavior. However, existing studies have mainly focused on the convergence rate of Adam in smooth nonconvex optimization, which unfortunately does not adequately capture practical settings, since many real-world problems are nonsmooth, such as those arising in training neural networks. Thus, these studies cannot fully explain the popularity and empirical success of Adam. Recently, an insightful and powerful framework called Online-to-Nonconvex Conversion has opened a new way to analyze Adam for nonsmooth nonconvex optimization. Unfortunately, prior works along this line share two common limitations. First, all of them ignore the important bias-correction term in the original Adam algorithm. Second and more importantly, many of them require extra operations that are not used in Adam, such as a clipping step. Therefore, the convergence guarantee for the original Adam method still remains unclear. In this work, we present the first finite-time analysis for the classical form of Adam, i.e., with the bias-correction step and without further algorithmic modifications, and prove that a randomly scaled learning rate ensures a convergence rate of

1/T^{\frac{2}{13}}

for nonsmooth nonconvex optimization. Moreover, our result provably applies to the modern heavy-tailed noise regime, which is closer to practice. Interestingly, our theory is established under the parameter choice

β_1=β_2

, aligning with the recent empirical studies.

Zijian Liu

Department of Technology, Operations, and Statistics Leonard N. Stern School of Business New York University New York, NY 10012, USA

Heavy-Tailed Noise Nonconvex Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Nonsmooth Convex Optimization

Ask PDF

May 26, 2026cs.LG

Convergence of Spectral Descent for Non-smooth Optimization

The Muon optimizer has recently demonstrated remarkable empirical success in training large language models. However, the theoretical understanding of its mechanisms remains limited. Current convergence guarantees for Muon rely heavily on smoothness assumptions, leaving its non-smooth convergence behavior largely unexplored. In this work, we take a step toward bridging this gap by investigating Spectral Descent (SD), a simplified variant of Muon, together with its truncated counterpart, Truncated Spectral Descent (TSD). Under convexity, Lipschitz continuity, and sharpness conditions, we establish global linear convergence for both SD and TSD in non-smooth convex formulations. We also study regularized variants equipped with decoupled weight decay and derive sublinear convergence guarantees through their connection with Frank-Wolfe methods. Finally, we apply our theoretical framework to robust low-rank matrix recovery under mixed sparse and dense noise regimes and provide rigorous recovery guarantees. Numerical experiments support the theoretical findings and demonstrate the effectiveness of Muon-type methods for non-smooth optimization.

Yixuan Yang, Yuqing He, Song Li

School of Mathematical Sciences, Zhejiang University, Hangzhou, China

Muon Optimizer Nonsmooth Convex Optimization

Ask PDF

May 23, 2026cs.LG

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a

(δ, ε)

-Goldstein stationary point with zeroth-order oracle complexity of

{\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}})

, where

d

is the problem dimension and

p\in(1,2]

is the order of bounded moments. Note that our dependence on dimension

d

matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters

δ

and

ε

is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.

Zhuanghua Liu, Luo Luo

Stochastic Optimization Gradient Clipping Zeroth-Order Optimization Heavy-Tailed Noise Nonconvex Optimization Nonsmooth Convex Optimization+1

Ask PDF

May 15, 2026math.OC

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients

Much of the existing theory on first-order non-smooth optimization is built on a restrictive assumption that the gradients of the objective function are uniformly bounded. We introduce a much more realistic class of generalized Lipschitz functions, where the gradient norms are bounded by an affine function of the optimality gap. We then ask a natural question: what algorithm achieves the best global convergence rates for solving convex stochastic generalized Lipschitz optimization problems? To address this, we develop a new convergence analysis for several existing algorithms and find that AdamW with clipped updates, provably outperforms other popular stochastic optimization methods, such as SGD and AdaGrad. Moreover, our analysis establishes the critical role of AdamW's exponentially weighted gradient accumulation, as opposed to simple averaging. We further show that clipped AdamW is universal and achieves improved rates under the popular generalized smoothness assumption, analyze the convergence of clipped AdamW with diagonal and matrix preconditioners, and extend our results to the quasar-convex setting.

Dmitry Kovalev

Yandex Research

Stochastic Optimization Gradient Clipping Stochastic Optimization Convergence Adaptive Gradient Methods Nonsmooth Convex Optimization

Ask PDF

May 13, 2026math.OC

Nonsmooth Set-Gradient Ascent to the Pareto Front via Layered Hypervolume and Magnitude Indicators

A nonsmooth set-gradient ascent method is developed for moving finite approximation sets toward the Pareto front in multiobjective optimization. The method optimizes layered set indicators: a base indicator is evaluated on successive nondomination layers, and the layer values are combined with rapidly decreasing weights. This gives ascent directions to nondominated and dominated points while preventing deeper layers from compensating for deterioration of the first front. Two base indicators are treated: the hypervolume indicator and the magnitude indicator of the dominated set, whose expansion over coordinate projections contains extent, projected-area, and volume terms. The scalar objectives are nonsmooth because nondomination layers change combinatorially and the active orthogonal-union geometry changes piecewise. On fixed strata, where layer assignments and active geometry remain unchanged, the indicators are piecewise smooth and chamberwise continuous. For the magnitude indicator, an exact gradient formula is derived as a linear combination of hypervolume gradients of projected shadow sets. Thus, for fixed objective dimension, magnitude gradients have the same asymptotic time complexity as hypervolume gradients. Lexicographic layer aggregation is related to a unary infinitesimal encoding. For finite-

ε

surrogates, the main nonsmoothness mechanisms are isolated and chamberwise Lipschitz continuity on bounded sets is proved; a two-point counterexample shows that hard-layer scalarization is not globally continuous across layer switches. The theory motivates a projected finite-difference implementation with repulsion and recovery from stagnation. Numerical examples and reproducible code cover two- and three-objective settings, including objective-space tests, curved fronts, a supersphere benchmark, and traces comparing layered magnitude and hypervolume ascent.

Michael T. M. Emmerich

Faculty of Information Technology, University of Jyväskylä, Finland

Multi-Objective Optimization Pareto Optimization Nonsmooth Convex Optimization

Ask PDF

May 11, 2026math.OC

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

We study the parameterized complexity of testing approximate first-order stationarity at a prescribed point for continuous piecewise-affine (PA) functions, a basic task in nonsmooth optimization. PA functions form a canonical model for nonsmooth stationarity testing and capture the local polyhedral geometry that appears in ReLU-type training losses. Recent work by Tian and So (SODA 2025) shows that testing approximate stationarity notions for PA functions is computationally intractable in the worst case, and identifies fixed-dimensional tractability as an open direction. We address this direction from the viewpoint of parameterized complexity, with the ambient dimension

d

as the parameter. In this paper, we give XP algorithms in fixed dimension for the tractable sides, and prove W[1]-hardness for the complementary sides. Moreover, lower bounds under the Exponential Time Hypothesis rule out algorithms running in time

ρ(d)\size^{o(d)}

for any computable function

ρ

, where

\size

denotes the total binary encoding length of the stationarity-testing instance. As a further consequence, our results yield the corresponding parameterized complexity picture for testing local minimality of continuous PA functions. We further extend our hardness results to a family of shallow ReLU CNN training losses, with stationarity tested in the trainable weight space. Thus, the same parameterized-complexity picture also appears for simple CNN training losses.

Yuhan Ye

MIT

Shallow Neural Networks Nonconvex Optimization Parameterized Complexity Nonsmooth Convex Optimization

Ask PDF

Jan 28, 2026cs.LG

Fast and Efficient Asynchronous Gossip Algorithm for Robust and Non-Smooth Convex Decentralized Learning

Asynchronous primal-dual methods for decentralized non-smooth convex optimization often require each node to maintain

\mathcal{O}(d)

auxiliary variables, where

d

is its degree. This dependence on degree increases memory requirements and can amplify the effects of stale information, especially in dense networks. Motivated by the challenge of frugal memory management in decentralized learning, we introduce Goal-PD, an asynchronous gossip-based primal-dual algorithm that maintains only two variables per node, regardless of the node's degree. We establish almost-sure convergence of Goal-PD to a minimizer of the underlying optimization problem, and prove linear convergence when the objective functions are piecewise linear-quadratic. For decentralized mean estimation, we show that pairwise averaging is a special case of Goal-PD, which establishes a direct link between the proposed primal-dual framework and classical gossip. Experiments on synthetic and real datasets over various network topologies, with non-smooth objectives including median estimation, show that Goal-PD converges faster than existing asynchronous baselines while requiring significantly less memory by design.

Anna van Elst, Olivier Fercoq, Igor Colin +1

LTCI, Télécom Paris, Institut Polytechnique de Paris

Decentralized Learning Nonsmooth Convex Optimization Decentralized Optimization

Ask PDF

Nov 17, 2025cs.LG

On the Gradient Complexity of Private Optimization with Private Oracles

We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time

Ω(\min\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\})

is necessary to achieve

α

excess risk on problems of dimension

d

when

d \geq 1/α^2

. Upper bounds via DP-SGD show these results are tight when

d>\tildeΩ(1/α^4)

. We further show our lower bound can be strengthened to

Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \})

for algorithms which use minibatches of size at most

\bar{m} < \sqrt{d}

. We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by

\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big)

, where

n

is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. Specifically, if the proxy oracle transmits at most

Γ

-bits of information about the gradients in the minibatch, then

Ω\big(\min\{\frac{d}{α^2Γ}, \frac{d}{\log(1/α)}\}\big)

oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.

Michael Menart, Aleksandar Nikolov

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto

Query Complexity Oracle Complexity Differentially Private Stochastic Gradient Descent Differential Privacy Nonsmooth Convex Optimization Empirical Risk Minimization

Ask PDF

Apr 14, 2025math.OC

Towards Weaker Variance Assumptions for Stochastic Optimization

We revisit a classical assumption for analyzing stochastic gradient algorithms where the squared norm of the stochastic subgradient (or the variance for smooth problems) is allowed to grow as fast as the squared norm of the optimization variable. We contextualize this assumption in view of its inception in the 1960s, its seemingly independent appearance in the recent literature, its relationship to weakest-known variance assumptions for analyzing stochastic gradient algorithms, and its relevance in deterministic problems for non-Lipschitz nonsmooth convex optimization. We build on and extend a connection recently made between this assumption and the Halpern iteration. For convex nonsmooth, and potentially stochastic, optimization, we analyze horizon-free, anytime algorithms with last-iterate rates. For problems beyond simple constrained optimization, such as convex problems with functional constraints or regularized convex-concave min-max problems, we obtain rates for optimality measures that do not require boundedness of the feasible set.

Ahmet Alacaoglu, Yura Malitsky, Stephen J. Wright

Department of Mathematics, University of British Columbia · Faculty of Mathematics, University of Vienna · Department of Computer Sciences, University of Wisconsin–Madison

Stochastic Optimization Last-Iterate Convergence Stochastic Approximation Convergence Analysis Nonsmooth Convex Optimization

Ask PDF

Momentum

Related topics

Latest papers 16