PR-SDBPG, a penalty-regularized variant that eliminates the rare-visit assumption, and VR-PR-SDBPG, which improves the resulting sample complexities entirely through variance reduction, are developed, believed to be the first explicit stochastic nonconvex-nonconvex simple bilevel optimization guarantees.
Abstract
We study stochastic simple bilevel optimization with smooth, possibly nonconvex upper- and lower-level objectives accessed only through stochastic gradient oracles. A key challenge is that the dual multiplier induced by the lower-level constraint may become unbounded near lower-level stationary points, invalidating bounded-dual analyses and destabilizing stochastic gradient estimates. To address this, we propose \emph{Stochastic Dynamic Barrier Perturbed Gradient} (SDBPG), a single-loop method that adaptively perturbs the dual formulation to regularize this degeneracy. The perturbation stabilizes the multiplier and yields controlled bias and variance even near the lower-level stationarity region. Under a rare-visit assumption governed by a parameter $\delta \in (0, \tfrac{1}{2}]$, SDBPG finds an $(\epsilon, \epsilon)$-stationary point in $\mathcal{O}(\epsilon^{-1/\delta})$ iterations, with sample gradient complexities $\mathcal{O}(\epsilon^{-2/\delta})$ and $\mathcal{O}(\epsilon^{-3/\delta})$ for the upper- and lower-level objectives, where larger $\delta$ corresponds to rarer visits to the bad region describing the negative alignment between the two objectives when the lower-level gradient is small. We further develop PR-SDBPG, a penalty-regularized variant that eliminates the rare-visit assumption, and VR-PR-SDBPG, which improves the resulting sample complexities entirely through variance reduction. To our knowledge, these are the first explicit $(\epsilon_f,\epsilon_g)$-stationarity guarantees for stochastic nonconvex-nonconvex simple bilevel optimization.
We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias $O(\tau_{\mathrm{mix}}/T)$ uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under $\sigma^2\mapsto 2\Lambda G_\sigma^2$ and $L^2\mapsto 2\Lambda L^2$, where $\Lambda=O(\tau_{\mathrm{mix}}\log T)$. For positive centered noise, the tuned method achieves expected sample complexity $\widetilde{O}((\tau_{\mathrm{mix}}^2G_\sigma+\tau_{\mathrm{mix}}^{5/2}G_\sigma^2)\varepsilon^{-3}+\tau_{\mathrm{mix}}^5\varepsilon^{-2})$. The exactly noiseless specialization achieves $\widetilde{O}(\varepsilon^{-2})$ with mixing-time-free constants, while a mixing-time-oblivious variant achieves $\widetilde{O}(\tau_{\mathrm{mix}}^6\varepsilon^{-3}+\tau_{\mathrm{mix}}^3\varepsilon^{-2})$. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.
A sharp lower bound is proved for smooth nonconvex stochastic optimization with uniformly bounded gradient noise with uniformly bounded gradient noise and resolves the question raised by whether almost-surely bounded oracle error permits a better rate than bounded variance.
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.
Felipe Atenas, Alejandro Jofré, Pedro Pérez-Aros et al.· 0 citations
This work proposes a novel single-loop algorithm based on a constrained reformulation in which lower-level stationarity is imposed as a constraint, and constructs a regularized Lagrangian by introducing a quadratic regularizer and restricting the dual variable to a bounded domain.
For smooth nonconvex stochastic multi-objective problems, stochastic multi-gradient descent (SMG) computes an approximate steepest common descent direction of the objectives from stochastic gradients. With unbiased, variance-bounded stochastic gradients, this note establishes a new convergence rate for SMG in terms of the squared Pareto-stationarity (PS) measure. With a constant stepsize and linearly growing mini-batches, this measure at the algorithm's output is $\widetilde O(T^{-1})$ after $T$ iterations. This improves on the $\widetilde O(T^{-1/4})$ bound obtained by Chen et al. (2024) under the same setting, where $\widetilde O(\cdot)$ suppresses logarithmic factors. The key to the rate improvement is to exploit the Lipschitz continuity of the PS measure, defined by the norm of the multi-gradient descent algorithm (MGDA) direction, rather than the $(1/2)$-H\"older continuity of the MGDA direction used by Chen et al. (2024). The proof was discovered while the author was preparing homework for a graduate course: ChatGPT 5.4 Thinking Extended generated the initial proof strategy in response to an author-written homework-solution prompt; the author then verified and reorganized the resulting argument. The appendices document the prompt and summarize the student submissions.
We study whether stochastic nonconvex optimization can be reduced to ordinary static regret minimization in online convex optimization in a black-box manner. For smooth nonconvex objectives, our reduction maintains a predictable gradient tracker, while a black-box online learner selects a preconditioner that determines how this tracker is transformed into the update direction. The learner receives linear convex losses and is evaluated against a single fixed comparator over one undiscounted online game. For a $\beta$-smooth objective with range bounded by $M$ and an unbiased stochastic-gradient oracle with variance bounded by \(\sigma^2\), we establish $$\frac{1}{T}\sum_{t=1}^T \mathbb E\!\left[\|\nabla f(x_t)\|_2^2\right] \lesssim \frac{\sigma\sqrt{M\beta}}{\sqrt T} + \frac{\sqrt{M\beta}\, \mathscr R_T(\mathcal A,I_d)}{T} + \frac{M\beta}{T}.$$ Consequently, any black-box OCO algorithm with $\mathscr R_T(\mathcal A,I_d)=O(\sqrt T)$ recovers the classical $O(\frac{1}{\sqrt{T}})$ convergence rate. We further show that the same black-box framework extends beyond the smooth setting to Lipschitz nonconvex objectives without Lipschitz continuous gradients. Importantly, this extension continues to rely only on an ordinary static-regret guarantee and requires no stronger notion of online regret. When the OCO oracle admits square-root static regret, the resulting conversion achieves the optimal $O(T^{-2/7})$ convergence rate for the corresponding Goldstein stationary point. These results resolve the open problem posed by Chen and Hazan (2024). More broadly, our framework separates optimizer design into gradient prediction and online preconditioner selection, providing a principled perspective on how adaptive optimization methods may be understood through static regret and applied in nonconvex optimization.