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.
Abstract
This paper studies the convergence of stochastic gradient descent (SGD) 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. Our first contribution is to demonstrate that SGD in this setting implicitly optimizes a penalized problem whose minimizer does not coincide with the true minimizer. To mitigate this convergence failure, we reformulate the original task as an equivalent bilevel optimization problem and propose a gradient-based algorithm, termed Residual Learning. Theoretical analysis shows that Residual Learning finds a solution to the original, unbiased optimization problem despite the hardware imperfections. Beyond exact convergence, we quantify how the response functions affect convergence complexity via the hardware condition number and show that a polynomial dependence on it is unavoidable in general, via a construction of a hard instance. The theoretical results are supported by numerical simulations that demonstrate the effectiveness of the proposed algorithm.
Gradient-based learning under non-convex constraints exhibits a notable phenomenon: Despite the existence of many equivalent global minimizers, optimization algorithms consistently converge to a small subset of structured solutions. This behavior, known as implicit bias, remains insufficiently understood in constrained and non-convex settings. In this article, we investigate the mechanism of implicit bias induced by projected gradient-based optimization over general non-convex feasible sets. By modeling projected gradient descent as a continuous-time dynamical system, we derive a projected gradient flow characterized by tangent and normal cone decompositions, which capture the local geometry of the constraint set. Based on this formulation, we show that constraint geometry continuously filters gradient directions along the optimization trajectory, leading to a trajectory-dependent implicit regularization effect without modifying the objective function. We further formalize this effect through a cumulative normal projection energy functional and prove that the optimization dynamics converge to solutions minimizing both empirical risk and geometric incompatibility with the constraint set. Extensive experiments on synthetic and real-world datasets validate the theoretical predictions, demonstrating consistent alignment between solution geometry, optimization trajectories, and generalization performance. These results provide a unified geometric and dynamical explanation of implicit bias in constrained learning systems.
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
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 provides a comprehensive survey of the convergence properties of temporal-difference (TD) learning and Q-learning, which are two fundamental algorithms in reinforcement learning (RL). We systematically categorize the existing literature into the tabular setting and two function approximation regimes: linear and nonlinear (deep neural networks). In the tabular setting, we review the foundational stochastic-approximation theory that ensures asymptotic convergence and discuss recent non-asymptotic results that provide explicit sample-complexity bounds under various coverage and sampling conditions. For linear function approximation, we address the stability challenges inherent in off-policy learning and examine stabilization mechanisms, such as gradient-based methods, regularization, and target networks. Furthermore, we explore the recent theoretical advancements in deep RL, focusing on finite-time analysis within the overparameterized regime. By synthesizing these diverse perspectives, this survey highlights the theoretical evolution from asymptotic stability to non-asymptotic efficiency and identifies the remaining gaps and provides a coherent roadmap for future research toward a unified theoretical understanding of RL dynamics.
Han-Dong Lim, Hyunjun Na, Taeho Lee et al.· International Journal of Con...· 0 citations
We study policy optimization for gain-scheduled linear quadratic regulation, where one schedule of gains, interpolated through fixed weighting functions, is optimized against a family of plants. The resulting cost can develop spurious local minima, and existing convergence certificates are either local or severely conservative. We establish an exact identity: when the gradient of the cost is evaluated with the minimizer's closed-loop covariances, the scheduled cost is star-convex about the minimizer. The identity holds on the entire feasible set, for any parametrization of the schedule. Convergence is governed by a single dimensionless ratio. Wherever the ratio satisfies a threshold condition, gradient descent converges linearly to the optimum on entire sublevel regions at an explicit rate; at every spurious stationary point the condition necessarily fails. Experiments that maximize the ratio directly show the threshold to be an active boundary of the landscape. This extended version contains the complete proofs and additional numerical studies omitted from the letter for space.
Shiva Shakeri, Péter Baranyi, M. Mesbahi· 0 citations
This article applies dynamic integral quadratic constraints (IQCs) to the analysis and synthesis of accelerated stochastic gradient algorithms. We consider composite objective functions whose gradient can be approximated via mini-batch sampling and we model the resulting stochastic gradient oracle as a feedback nonlinearity in the spirit of Lur'e systems from robust control. Our first main contribution is a family of IQCs that characterize the second-order statistics of mini-batch gradients, extending the classical Zames--Falb multipliers. Our second contribution is a semidefinite-program for certifying exponential convergence rates of stochastic gradient algorithms, and a complementary condition for bounding the asymptotic variance caused by non-vanishing gradient noise. Our third contribution is a convex synthesis procedure that identifies mini-batch gradient algorithms with the smallest certifiable convergence rate.
Dennis Gramlich, C. Scherer, Christian Ebenbauer· 0 citations