arXiv:2608.05460math.OCcs.LG2026-08

提出一种新方法,能在非凸随机优化中高效收敛,无需严格假设。

A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition

论文配图:A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition
图 1 · 摘自论文原文
  • 用渐进采样和自适应步长,处理非光滑非凸的期望目标函数
  • 仅需样本量非减且无界,即可保证函数值几乎必然收敛
  • 结合KL条件可得整体轨迹收敛,并给出多项式速率(带对数因子)

本文提出一种近端随机次梯度方法,用于最小化期望成本与一个下半连续、近端有界的正则项之和。目标函数的被积函数可能非光滑、非凸,但满足关于决策变量的非光滑局部下降引理结构假设,涵盖具有Lipschitz梯度的光滑损失及其与凸函数差的形式。每轮迭代中,期望成本由逐步精化的样本平均替代,步长通过类似Armijo的线搜索选择,确保在采样误差下仍满足充分下降性。该框架比现有方法更通用,不要求正则项(弱)凸或随机预言机方差有界,分析首次在光滑情形也给出新收敛保证。我们证明了函数值序列几乎必然收敛,且所有轨迹聚点为驻点,仅需样本量序列非减且无界,无需指定增长速率。借助Kurdyka-Łojasiewicz(KL)性质,进一步将子列收敛升级为整个轨迹收敛至单一驻点。对于指数型KL消影函数与多项式增长的样本量,推导出函数值与迭代点的显式多项式收敛速率(含对数因子)。

原文摘要 · Abstract (English)

This work introduces a proximal stochastic subgradient method for minimizing the sum of an expected cost, whose integrand is potentially nonsmooth and nonconvex, and a lower semicontinuous, prox-bounded function. We target a broad class of integrands obeying a nonsmooth, localized variant of the descent lemma in the decision variable, a structural assumption that simultaneously covers smooth losses with Lipschitz gradient and differences of such losses with convex functions. At each iteration the expected cost is replaced by a sample average that is progressively refined, and the proximal-subgradient stepsize is selected by an Armijo-type line search enforcing a sufficient-decrease property up to stochastic errors induced by the sample-based approximation. This framework accommodates substantially more general problem formulations than existing methods, in particular, it requires neither (weak) convexity of the regularizer nor a uniform bound on the variance of the stochastic oracle, and our analysis yields convergence guarantees that are new even in the smooth setting. Specifically, we establish almost sure convergence of the sequence of function values and stationarity of every accumulation point of the trajectories under the relaxed requirement that the sample-size sequence be merely nondecreasing and unbounded, with no prescribed growth rate. Leveraging the Kurdyka-Lojasiewicz (KL) property, we further upgrade this subsequential guarantee to convergence of the whole trajectory to a single stationary point. Finally, for exponential-type KL desingularizing functions and polynomially growing sample sizes, we derive explicit polynomial convergence rates, up to a logarithmic factor, for both the function values and the iterates.

非凸优化随机算法收敛性分析KL条件

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。