Finding a stationary point of a stochastic convex problem

• URL: http://arxiv.org/abs/2607.06883v1
• Date: Wed, 08 Jul 2026 00:54:11 GMT
• Title: Finding a stationary point of a stochastic convex problem
• Abstract summary: Subdifferentials of convex functions fail to converge uniformly, even in arbitrarily small neighborhoods of the optimum.<n>Our convergence guarantees rely on dimension theory to decompose the graph of the subdifferential of a convex function.
• Score: 1.0055428846517076
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition [39.146761527401424]
  This work introduces a proximal subgradient method for minimizing the sum of an expected cost.<n>We use the Kurdyka-Lojasiewicz (KL) property to guarantee convergence of the whole trajectory to a single stationary point.
  arXiv  Detail & Related papers  (2026-08-05T23:07:27Z)
• Mean-square and linear convergence of a stochastic proximal point algorithm in metric spaces of nonpositive curvature [0.0]
  We define a variant of the proximal point algorithm in the general setting of nonlinear (separable) Hadamard spaces for approximating zeros of the mean of a monotone vector field.<n>We prove its convergence under a suitable strong monotonicity assumption, together with a probabilistic independence assumption and a separability assumption on the perturbed spaces.
  arXiv  Detail & Related papers  (2025-10-12T16:54:04Z)
• Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness [50.78508362183774]
  Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance.<n>Most require the Lipschitz condition, which is often not met in common machine learning schemes.
  arXiv  Detail & Related papers  (2025-07-11T15:36:48Z)
• Approximating Fixpoints of Approximated Functions [0.31457219084519]
  We show how to approximate the least fixpoint of functions that are not known precisely, but represented by a sequence of approximating functions that converge to them.<n>Our results can be used to iterate to the least fixpoint almost surely for systems where the function of interest can be approximated with given probabilistic error bounds.
  arXiv  Detail & Related papers  (2025-01-15T16:52:21Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning [1.5229257192293195]
  We investigate the uniform convergence of subdifferential mappings from empirical risk to population risk in nonsmooth, non-valued to deterministic optimization.<n>These guarantees offer new insight into the geometry of problems arising in robust statistics and related applications.
  arXiv  Detail & Related papers  (2024-05-16T17:49:46Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Coordinate Descent Methods for Fractional Minimization [7.716156977428555]
  We consider a class of structured fractional convex problems in which the numerator part objective is the sum of a differentiable convex non-linear function. This problem is difficult since it is non-smooth convergence. We propose two methods for solving this problem.
  arXiv  Detail & Related papers  (2022-01-30T00:47:04Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.