Robust stochastic gradient descent for linearly constrained problems via adaptive barrier amplification

Document Type : Research Article

Authors

Abdelouakil Fillali

Smail Addoune

Rebiha Zeghdane

Laboratoire d’Analyse Mathématiques et ses Applications (LAMA), Department of Mathematics, University Mohamed El Bachir El Ibrahimi, Bordj Bou Arreridj, 34030, Algeria.

10.22067/ijnao.2026.95961.1753

Abstract

Methods based on Stochastic Gradient Descent using relaxed barrier functions provide a powerful framework for linearly constrained optimization but often suffer from sensitivity to hyperparameter settings and slow recovery from infeasible regions. Our investigation reveals that the optimal performance of standard relaxed barrier methods is confined to a narrow and unstable, ‘special-case’ optimization path, limiting their practical robustness. This paper introduces a novel algorithm designed to overcome these limitations through a Dynamic Barrier Amplification mechanism. This approach adaptively intensifies the corrective force of the barrier gradient in proportion to the magnitude of constraint violations, ensuring a strong push towards the feasible set specifically when iterates become highly infeasible. We provide a rigorous theoretical analysis, preserving the almost sure convergence guarantees of the baseline algorithm and deriving an explicit linear convergence rate to a neighborhood of the solution. Numerical results on challenging linearly constrained quadratic programming problems demonstrate that our algorithm exhibits superior robustness: it significantly reduces constraint violations in ill-conditioned scenarios compared to the standard method, acting as a reliability safety net, while maintaining competitive efficiency in nominal conditions.

Keywords

Linearly Constrained Optimization

Stochastic Gradient Descent

Relaxed Barrier Functions

Dynamic Barrier Amplification

Robust Optimization

Subjects

• Optimization

---

References

[1] Bach, F. and Moulines, E. Non-asymptotic analysis of stochastic approximation algorithms
for machine learning, In Adv. Neural Inf. Process. Syst. 24 (2011) 451–459.
[2] Bertsekas, D.P. and Tsitsiklis, J.N. Neuro-dynamic programming, Athena Scientific, 1996.
[3] Bottou, L., Curtis, F.E. and Nocedal, J. Optimization methods for large-scale machine
learning, SIAM Rev. 60(2) (2018), 223–311.
[4] Boyd, S. and Vandenberghe, L. Convex optimization, Cambridge University Press, 2004.
[5] Bubeck, S. Convex optimization: Algorithms and complexity, Found. Trends Mach. Learn.
8(3-4) (2015), 231–358.
[6] Dimitrieski, N., Cao, J. and Ebenbauer, C. Stochastic gradient descent for constrained
optimization based on adaptive relaxed barrier functions, arXiv preprint arXiv:2503.10384
(2025).
[7] Feller, C. and Ebenbauer, C. A stabilizing iteration scheme for model predictive control
based on relaxed barrier functions, Automatica, 80 (2017), 328–339.
[8] Fiacco, A.V. and McCormick, G.P. Nonlinear programming: Sequential unconstrained min-
imization techniques, John Wiley & Sons, 1968.
[9] Garrigos, G. and Gower, R.M. Handbook of convergence theorems for (stochastic) gradient
methods, arXiv preprint arXiv:2301.11235 (2023).
[10] Gower, R.M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E. and Richtárik, P. SGD:
General analysis and improved rates, In International conference on machine learning,
PMLR, 2019, 5200–5209.
[11] Kushner, H.J. and Yin, G.G. Stochastic approximation and recursive algorithms and appli-
cations, 2nd ed., Springer, 2003

[12] Li, M., Grigas, P. and Atamtürk, A. New penalized stochastic gradient methods for linearly
constrained strongly convex optimization, J. Optim. Theory Appl. 205(2) (2025) 29.
[13] Liu, J. and Yuan, Y. On almost sure convergence rates of stochastic gradient methods, Proc.
35th Annual Conference on Learning Theory, PMLR, 178 (2022), 1–21.
[14] Nemirovski, A., Juditsky, A., Lan, G. and Shapiro, A. Robust stochastic approximation
approach to stochastic programming, SIAM J. Optim. 19(4) (2009), 1574–1609.
[15] Nocedal, J. and Wright, S.J. Numerical optimization, 2nd ed., Springer, 2006.
[16] Robbins, H. and Monro, S. A stochastic approximation method, Ann. Math. Stat. 22(3)
(1951), 400–407.
[17] Robbins, H. and Siegmund, D. A convergence theorem for non negative almost supermartin-
gales and some applications, Rustagi, J.S. (ed.), Optimizing Methods in Statistics, Academic
Press, 1971, 233–257.
[18] Rockafellar, R.T. Convex analysis, Princeton University Press, 1970.
[19] Roy, S.K. and Harandi, M. Constrained stochastic gradient descent: The good practice, In
Int. Conf. Digit. Image Comput. Tech. Appl. (DICTA), IEEE, 2017, 1–8.
[20] Wang, M. and Bertsekas, D.P. Incremental constraint projection methods for variational
inequalities, Math. Program. 150 (2015), 321–363.
[21] Wang, X., Ma, S. and Yuan, Y.X. Penalty methods with stochastic approximation for stochas-
tic nonlinear programming, Math. comput. 86(306) (2017) 1793–1820.
[22] Yan, Y. and Xu, Y. Adaptive primal-dual stochastic gradient method for expectation-
constrained convex stochastic programs, Math. Program. Comput. 14(2) (2022), 319–363.
[23] Zhang, L., Zhang, Y., Wu, J. and Xiao, X. Solving stochastic optimization with expectation
constraints efficiently by a stochastic augmented Lagrangian-type algorithm, INFORMS J.
Comput. 34(6) (2022) 2989–3006.
[24] Zhang, T. Solving large scale linear prediction problems using stochastic gradient descent
algorithms, In Proc. 21st Int. Conf. Machine Learning (ICML), 2004, 116