Achieving Directional-Stationarity from a Single Random Direction Step
Abstract
This paper addresses the challenge of obtaining strong optimality guarantees in constrained nonsmooth nonconvex optimization under mild regularity conditions, namely local Lipschitz continuity and existence of directional derivatives. While standard methods typically ensure weak stationarity notions, achieving directional (d-)stationarity remains nontrivial. We show that a random direction exploration step is sufficient to attain d-stationarity. The proposed approach augments any feasible base method with one additional randomized exploration step per iteration, which samples a direction and step size and accepts the candidate based on a function value comparison. The resulting scheme guarantees that all accumulation points are d-stationary almost surely, independently of the behavior of the underlying method. Moreover, under conditions on the base method, it preserves convergence rates of the base method, as established for the difference-of-convex algorithm (DCA), prox-linear-type schemes, and interpolated normalized gradient descent (INGD). The theoretical results are complemented by numerical experiments illustrating the effect and guarantees of the exploration step.
Related
- Statistical Learning of Conditional Single-Index U-Processes Under Local Stationarity and Missing-At-Random Functional Responses
- Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
- Penalizations of Two-Dimensional Simple Random Walk by Direction-Dependent Excursion Counts and Edge-Crossing Counts
- Gaussian and non-Gaussian limits for the total edge-length of random directional nearest-neighbour graphs
BibTeX
@misc{greenstein2026achieving,
title = {{Achieving Directional-Stationarity from a Single Random Direction Step}},
author = {Dan Greenstein and Nadav Hallak},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.22045},
eprint = {2605.22045},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.22045},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Achieving Directional-Stationarity from a Single Random Direction Step
AU - Dan Greenstein
AU - Nadav Hallak
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2605.22045
UR - https://arxiv.org/abs/2605.22045
AB - This paper addresses the challenge of obtaining strong optimality guarantees in constrained nonsmooth nonconvex optimization under mild regularity conditions, namely local Lipschitz continuity and existence of directional derivatives. While standard methods typically ensure weak stationarity notions, achieving directional (d-)stationarity remains nontrivial. We show that a random direction exploration step is sufficient to attain d-stationarity. The proposed approach augments any feasible base method with one additional randomized exploration step per iteration, which samples a direction and step size and accepts the candidate based on a function value comparison. The resulting scheme guarantees that all accumulation points are d-stationary almost surely, independently of the behavior of the underlying method. Moreover, under conditions on the base method, it preserves convergence rates of the base method, as established for the difference-of-convex algorithm (DCA), prox-linear-type schemes, and interpolated normalized gradient descent (INGD). The theoretical results are complemented by numerical experiments illustrating the effect and guarantees of the exploration step.
ER -