Adaptive-batch stochastic gradient descent for constrained optimization based on relaxed barrier functions

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.96402.1775

Abstract

Stochastic Gradient Descent (SGD) is the cornerstone of large-scale optimization; however, its application to problems with a vast number of constraints remains a significant challenge. Methods based on relaxed logarithmic barrier functions have enabled the use of SGD by sampling constraints, yet the reliance on single samples in these methods often leads to high variance and oscillations that hinder progress near the optimal solution.
In this paper, we propose a novel hybrid algorithm, AdaBS-RBSGD, which integrates the relaxed barrier framework with an adaptive batch size strategy. Our algorithm dynamically adjusts the batch size Bk to be inversely proportional to the estimated optimization loss, systematically reducing gradient variance as the iterations approach the solution.
We provide a rigorous mathematical proof establishing the almost-sure convergence of this hybrid algorithm. Furthermore, our theoretical analysis of error bounds demonstrates that active variance management allows the error term associated with stochastic noise to vanish more rapidly compared to the baseline method. Empirically, results on a benchmark problem show that the proposed algorithm significantly outperforms its single-sample counterpart, successfully breaking the “noise floor,” achieving higher stability, and reaching a more accurate final solution. This work presents a practical and theoretically sound methodology for accelerating and improving the precision of stochastic constrained optimization.

Keywords

Constrained Optimization

Stochastic Gradient Descent (SGD)

Relaxed Logarithmic Barrier Functions

Adaptive Batch Sizes

Variance Reduction

Large-Scale Optimization

Subjects

• Control and Optimization

---

References

[1] Balles, L., Romero, J. and Hennig, P. Coupling adaptive batch sizes with learning rates, In
33rd Conf. Uncertainty in Artif. Intell. (UAI), 675–684, 2017.
[2] Beiser, F., Keith, B., Urbainczyk, S. and Wohlmuth, B. Adaptive sampling strategies for
risk-averse stochastic optimization with constraints, IMA J. Numer. Anal. 43(6), (2023)
3729–3765.
[3] Bollapragada, R., Byrd, R. and Nocedal, J. Adaptive sampling strategies for stochastic
optimization, SIAM J. Optim. 28(4), (2018) 3312–3343.
[4] Bottou, L., Curtis, F.E. and Nocedal, J. Optimization methods for large-scale machine
learning, SIAM Rev. 60(2) (2018), 223–311.
[5] Boyd, S. and Vandenberghe, L. Convex optimization, Cambridge University Press, 2004.
[6] Bubeck, S. Convex optimization: Algorithms and complexity, Found. Trends Mach. Learn.
8(3-4) (2015), 231–358.
[7] Dimitrieski, N., Cao, J. and Ebenbauer, C. Stochastic gradient descent for constrained
optimization based on adaptive relaxed barrier functions, IEEE Control Syst. Lett. 9 (2025)
829–834.
[8] Feller, C. and Ebenbauer, C. A stabilizing iteration scheme for model predictive control
based on relaxed barrier functions, Automatica 80 (2017), 328–339.
[9] Fiacco, A.V. and McCormick, G.P. Nonlinear programming: Sequential unconstrained min-
imization techniques, John Wiley & Sons, 1968

[10] Garrigos, G. and Gower, R.M. Handbook of convergence theorems for (stochastic) gradient
methods, arXiv preprint arXiv:2301.11235 (2023).
[11] Karandikar, R.L. and Vidyasagar, M. Convergence rates for stochastic approximation: bi-
ased noise with unbounded variance, and applications, J. Optim. Theory Appl. 203(3) (2024)
2412–2450.
[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, In
Proc. 35th Annu. Conf. Learn. Theory (COLT), PMLR, 178, 1–21, 2022.
[14] Nocedal, J. and Wright, S.J. Numerical optimization, 2nd ed., Springer, 2006.
[15] Polyak, B.T. and Juditsky, A.B. Acceleration of stochastic approximation by averaging,
SIAM J. Control Optim. 30(4) (1992), 838–855.
[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 nonnegative almost supermartin-
gales and some applications, In Optimizing Methods in Statistics, Academic Press, 233–257,
1971.
[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, 1–8, 2017.
[20] Sievert, S. and Shah, S. Improving the convergence of SGD through adaptive batch sizes,
arXiv preprint arXiv:1910.08222 (2019).
[21] Smith, S.L., Kindermans, P.J. and Le, Q.V. Don’t decay the learning rate, increase the batch
size, In Int. Conf. Learn. Represent. (ICLR), 2018.
[22] Wang, M. and Bertsekas, D.P. Incremental constraint projection methods for variational
inequalities, Math. Program. 150 (2015), 321–363.
[23] Wang, X., Ma, S. and Yuan, Y. Penalty methods with stochastic approximation for stochastic
nonlinear programming, Math. Comput. 86(306) (2017) 1793–1820

[24] 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.
[25] Zhang, T. Solving large scale linear prediction problems using stochastic gradient descent
algorithms, In Proc. 21st Int. Conf. Mach. Learn. (ICML), 116, 2004