ν-paraconvex functions are nonconvex, nonsmooth functions satisfying a relaxed midpoint inequality that strictly generalizes weakly convex functions. This result characterizes the class (local Lipschitzness giving a nonempty Clarke subdifferential, and a saddle-point-free region around the optimum under a Hölderian error bound) and establishes convergence rates of projected subgradient methods under constant, diminishing, square-summable, geometrically decaying, and a new Scaled Polyak step-size, with linear convergence under the Hölderian error bound. The methods are applied to robust low-rank matrix recovery problems such as matrix completion, image inpainting, and robust nonnegative matrix factorization.
ν-paraconvex functions are nonconvex, nonsmooth functions satisfying a relaxed midpoint inequality h(λx+(1−λ)y) ≤ λh(x)+(1−λ)h(y)+ρ·min{λ,1−λ}·‖x−y‖^(1+ν), which strictly generalizes the class of wea…