Stochastic Functions Learning from Distribution-Driven Data: Generalization Bound and Algorithms

doi:10.1007/s40305-024-00563-y

Journal of the Operations Research Society of China ›› 2026, Vol. 14 ›› Issue (3): 964-994.doi: 10.1007/s40305-024-00563-y

Previous Articles Next Articles

Stochastic Functions Learning from Distribution-Driven Data: Generalization Bound and Algorithms

Jia Wu, Xian-Tao Xiao, Li-Wei Zhang

School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, Liaoning, China

Received:2024-04-01 Revised:2024-08-27 Accepted:2024-09-01 Online:2026-09-30 Published:2026-10-15
Supported by:
This work was supported by National Key R&D Program of China (No. 2022YFA1004000) and the National Natural Science Foundation of China (Nos. 11971089 and 12271076).

Abstract

Abstract: This paper delves into the learning of stochastic functions from distribution-driven data. Utilizing the empirical risk minimization (ERM) approach, we construct a stochastic minimax optimization problem from the distribution-driven data to recover the target random function. The generalization bound of the ERM approach is established based on annealed VC entropy. When the hypothesis set of functions is parameterized by a vector over a compact set, the optimization problem is simplified to a finite-dimensional stochastic composite minimax problem. This problem can be solved through a stochastic compositional gradient descent ascent method. Under mild conditions, the method is proved to converge almost surely to an optimal solution and achieve a sublinear convergence rate.

Key words: Stochastic function learning, Empirical risk minimization, Generalization bound, Stochastic approximation

CLC Number:

62L20·65K05·90C15

Jia Wu, Xian-Tao Xiao, Li-Wei Zhang. Stochastic Functions Learning from Distribution-Driven Data: Generalization Bound and Algorithms[J]. Journal of the Operations Research Society of China, 2026, 14(3): 964-994.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00563-y

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I3/964

[1] Bartle, R.G.: On compactness in functional analysis. Trans. Am. Math. Soc. 79, 35-57(1955)
[2] Bertsekas, D.P.: Convex Optimization Theory. Athena Scientific, Nashua (2009)
[3] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2011)
[4] Bousquet, O., Boucheron, S., Lugosi, G.: Introduction to Statistical Learning Theory, pp. 169-207. Springer, Berlin (2004)
[5] Cucker, F., Zhou, D.-X.: Learning Theory: an Approximation Theory Viewpoint. Cambridge Monographs on Applied and Computational Mathematics, vol. 24. Cambridge University Press, Cambridge (2007)
[6] Holá, V., Holý, D.: Compactness in function spaces. Topol. Appl. 262, 20-29(2019)
[7] Lan, G.: First-order and Stochastic Optimization Methods for Machine Learning. Springer Series in the Data Sciences. Springer, Cham (2020)
[8] Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of Machine Learning. Adaptive Computation and Machine Learning. MIT Press, Cambridge (2018)
[9] Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574-1609(2008)
[10] Rudin, W.: Principles of Mathematical Analysis, 3rd edn. International Series in Pure and Applied Mathematics. McGraw-Hill Book Co., New York-Auckland-Düsseldorf (1976)
[11] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. Society for Industrial and Applied Mathematics (SIAM); Mathematical Programming Society (MPS), Philadelphia, PA (2009)
[12] Vapnik, V.N.: The Nature of Statistical Learning Theory. Springer, New York (1995)
[13] Vapnik, V.N.: Statistical Learning Theory. Adaptive and Learning Systems for Signal Processing Communications, and Control. Wiley, New York (1998)
[14] Wang, M., Bertsekas, D.P.: Incremental constraint projection methods for variational inequalities. Math. Program. 150(2, Ser. A), 321-363(2015)
[15] Wang, M., Fang, E.X., Liu, H.: Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Math. Program. 161(1-2, Ser. A), 419-449(2017)
[16] Zhang, L., Zhang, Y., Wu, J., Xiao, X.: Solving stochastic optimization with expectation constraints efficiently by a stochastic augmented Lagrangian-type algorithm. INFORMS J. Comput. 34(6), 2989- 3006(2022)
[17] Zhang, L., Zhang, Y., Xiao, X., Wu, J.: Stochastic approximation proximal method of multipliers for convex stochastic programming. Math. Oper. Res. 48(1), 177-193(2023)
[18] Zhang, Y., Liu, J., Zhao, X.: Data-driven piecewise affine decision rules for stochastic programming with covariate information (2023). arXiv:2304.13646

Stochastic Functions Learning from Distribution-Driven Data: Generalization Bound and Algorithms

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Hao Cao, Jian-Qiang Hu, Teng Lian. Blackbox Simulation Optimization [J]. Journal of the Operations Research Society of China, 2025, 13(3): 723-749.
[2]	Jian-Chao Bai, Feng-Miao Bian, Xiao-Kai Chang, Lin Du. Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization [J]. Journal of the Operations Research Society of China, 2023, 11(4): 783-807.
[3]	Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates [J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.