A randomized two-point direct-search algorithm for nonconvex time-varying optimization and derive iteration-complexity bounds under both constant and diminishing probing ratios, which recover the complexity of existing zeroth-order methods in the time-invariant setting while extending direct- search methods beyond static settings.
Abstract
Optimization under zeroth-order (i.e., bandit) feedback is central to many engineering problems where the analytic forms of objectives and/or constraints are unavailable. In modern applications, such as online control and online learning, optimization problems often evolve with time, requiring adaptive optimization methodologies. Yet, existing methods in this seting are largely confined to adaptations of methodologies developed for time-invariant or first-order optimization, and thus often rely on gradient surrogates that fail to fully exploit the zeroth-order structure of the available information. In this paper, we propose a randomized two-point direct-search algorithm for nonconvex time-varying optimization and derive iteration-complexity bounds under both constant and diminishing probing ratios. The resulting analysis yields explicit stationarity bounds in terms of the temporal variability of the problem and possible oracle errors. Our complexity bounds recover the complexity of existing zeroth-order methods in the time-invariant setting, while extending direct- search methods beyond static settings. As an illustrative application, we show that the methodology is naturally suited to solve optimal (equilibrium-selection) control problems for dynamical systems. In this setting, the analysis yields explicit stationarity bounds in terms of the temporal variability of the problem, measured through the effects of plant dynamics and exogenous disturbance variations.
This paper proposes a novel decentralized stochastic first-order optimization algorithm, which does not require second-order Hessian or Jacobian matrices, for the setting where the lower-level loss function is nonconvex but satisfies the Polyak–Łojasiewicz (PL) condition.
Yihan Zhang, Xinwen Zhang, My T. Thai et al.· 0 citations
This paper proposes an online generalized-sparsity-constrained regression framework, focusing on online cardinality-constrained linear regression and low-rank matrix sensing, and introduces an efficient online hard-thresholding algorithm that performs closed-form updates and requires storing only summary statistics, making it computationally, memory, and storage efficient.
This paper investigates distributed online optimization for multi-agent dynamical systems with constrained inputs and time-varying cost functions. While online convex optimization offers a principal framework for sequential decision-making, existing online learning and optimization algorithms typically require accurate system models, limiting their applicability in practical settings. To overcome this challenge, we propose a distributed bandit online feedback optimization algorithm that relies solely on real-time input-output data. The algorithm employs a smoothing zeroth-order one-point estimator to construct local gradient approximations directly from cost evaluations. Additionally, to enforce input constraints effectively, we integrate a projection-free conditional gradient update, making the algorithm well-suited for online and large-scale settings. Furthermore, we establish a sublinear dynamic regret bound that depends on a temporal variation measure of system non-stationarity. Finally, numerical simulations demonstrate the effectiveness of the proposed algorithm.
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.
This paper studies the convergence of stochastic gradient descent when the implemented updates are subject to a persistent and state-dependent bias, in which the desired update is scaled by response functions component-wise, and proposes a gradient-based algorithm, termed Residual Learning.
Zhaoxian Wu, Quan Xiao, Tayfun Gokmen et al.· 0 citations
We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions. Our focus is on obtaining non-asymptotic bounds for the expected excess risk rather than sampling guarantees for the full target distribution. The key ingredient of our analysis is a direct passage from relative entropy to objective-value error, based on a weighted Csisz\'ar--Kullback--Pinsker inequality and exponential-moment estimates. This avoids intermediate Wasserstein bounds and yields sharper dependence on the Log-Sobolev constant, a quantity that may scale exponentially with the inverse temperature and the dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds on $\mathbb{E}[F(x_k)]-\min F$ in terms of the inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to an inexact-gradient version of ULA, allowing for biased and stochastic gradient surrogates whose mean-square error grows at most quadratically in the state. This framework covers stochastic gradients and zeroth-order estimators based only on function evaluations. In particular, we show that both Gaussian and spherical finite-difference estimators fit into the inexact-ULA theory and obtain explicit function-evaluation complexity bounds for zeroth-order Langevin optimization. To the best of our knowledge, these are the first non-asymptotic global non-convex optimization complexity bounds for zeroth-order ULA. We also provide numerical experiments illustrating the behavior of the proposed zeroth-order Langevin schemes.
E. Naldi, Marco Rando, Lorenzo Rosasco et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
