Statistical learning theory: a pack-based strategy for uncertain feasibility and optimization problems. (English) Zbl 1201.93135
Blondel, Vincent D. (ed.) et al., Recent advances in learning and control. Festschrift for Mathukumalli Vidyasagar on the occasion of his sixtieth birthday. London: Springer (ISBN 978-1-84800-154-1/pbk). Lecture Notes in Control and Information Sciences 371, 1-14 (2008).
Summary: In this paper, a new powerful technique, denoted as pack-based strategy is introduced in the context of statistical learning theory. This strategy allows us to derive bounds on the number of required samples that are manageable for “reasonable” values of probabilistic confidence and accuracy. Using this technique for feasibility and optimization problems involving Boolean expressions consisting of polynomials, we prove that the number of required samples grows with the accuracy parameter \(\varepsilon \) as \(\frac{1}{\varepsilon} \ln \frac{1}{\varepsilon}\). This is a significant improvement when compared to the existing bounds which depend on \(\frac{1}{\varepsilon ^{2}} \ln \frac{1}{\varepsilon ^{2}}\). We also apply this strategy to convex optimization problems. In this case, we show that the required sample size is inversely proportional to the accuracy for fixed confidence.
For the entire collection see [Zbl 1140.93006].
For the entire collection see [Zbl 1140.93006].
MSC:
| 93E35 | Stochastic learning and adaptive control |
| 93E25 | Computational methods in stochastic control (MSC2010) |
Keywords:
statistical learning theory; randomized algorithms; probabilistic robustness; uncertain systemsReferences:
| [1] | Alamo, T., Tempo, R., Camacho, E.F.: Revisiting statistical learning theory for uncertain feasibility and optimization problems. In: Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, USA (December 2007) |
| [2] | Alamo, T., Tempo, R., Camacho, E.F.: Improved sample size bounds for probabilistic robust control design: a pack-based strategy. In: Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, USA (December 2007) |
| [3] | Alamo, T., Tempo, R., Rodríguez, D., Camacho, E.F.: A sequentially optimal randomized algorithm for robust LMI feasibility problems. In: Proceedings of the European Control Conference, 2007, Kos, Greece (July 2007) |
| [4] | Calafiore, G.; Campi, M. C., Uncertain convex programs: randomized solutions and confidence levels, Math. Program., 102, 25-46 (2005) · Zbl 1177.90317 · doi:10.1007/s10107-003-0499-y |
| [5] | Calafiore, G.; Campi, M. C., The scenario approach to robust control design, IEEE Transactions on Automatic Control, 51, 5, 742-753 (2006) · Zbl 1366.93457 · doi:10.1109/TAC.2006.875041 |
| [6] | Calafiore, G., Dabbene, F.: An iterative localization method for probabilistic feasibility of uncertain LMIs. In: Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, USA (December 2006) · Zbl 1138.93027 |
| [7] | Calafiore, G.; Polyak, B. T., Stochastic algorithms for exact and approximate feasibility of robust LMIs, IEEE Transactions on Automatic Control, 46, 11, 1755-1759 (2001) · Zbl 1007.93080 · doi:10.1109/9.964685 |
| [8] | Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Annals of mathematical statistics, 23, 493-507 (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330 |
| [9] | Fujisaki, Y.; Dabbene, F.; Tempo, R., Probabilistic design of LPV control systems, Automatica, 39, 1323-1337 (2003) · Zbl 1033.93025 · doi:10.1016/S0005-1098(03)00108-0 |
| [10] | Fujisaki, Y., Kozawa, Y.: Probabilistic robust controller design: probable near minimax value and randomized algorithms. In: Calafiore, G., Dabbene, F. (eds.) Probabilistic and Randomized Methods for Design under Uncertainty, Springer, London (2006) · Zbl 1274.93282 |
| [11] | Hoeffding, W., Probability inequalities for sums of bounded random variables, Journal of American Statistics Association, 58, 13-30 (1963) · Zbl 0127.10602 · doi:10.2307/2282952 |
| [12] | Kanev, S.; De Schutter, B.; Verhaegen, M., An ellipsoid algorithm for probabilistic robust controller design, Systems and Control Letters, 49, 365-375 (2003) · Zbl 1157.93389 · doi:10.1016/S0167-6911(03)00115-4 |
| [13] | Koltchinskii, V.; Abdallah, C. T.; Ariola, M.; Dorato, P.; Panchenko, D., Improved sample complexity estimates for statistical learning control of uncertain systems, IEEE Transactions on Automatic Control, 45, 12, 2383-2388 (2000) · Zbl 0991.93130 · doi:10.1109/9.895579 |
| [14] | Polyak, B. T.; Tempo, R., Probabilistic robust design with linear quadratic regulators, Systems & Control Letters, 43, 343-353 (2001) · Zbl 0974.93070 · doi:10.1016/S0167-6911(01)00117-7 |
| [15] | Tempo, R.; Bai, E.-W.; Dabbene, F., Probabilistic robustness analysis: explicit bounds for the minimum number of samples, Systems & Control Letters, 30, 237-242 (1997) · Zbl 0901.93017 · doi:10.1016/S0167-6911(97)00005-4 |
| [16] | Tempo, R.; Calafiore, G.; Dabbene, F., Randomized Algorithms for Analysis and Control of Uncertain Systems, Communications and Control Engineering Series (2005), London: Springer, London · Zbl 1079.93002 |
| [17] | Vapnik, V. N., Statistical Learning Theory (1998), New York: John Wiley & Sons, New York · Zbl 0935.62007 |
| [18] | Vapnik, V. N.; Chervonenkis, A. Ya., On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications, 16, 264-280 (1971) · Zbl 0247.60005 · doi:10.1137/1116025 |
| [19] | Vapnik, V. N.; Chervonenkis, A. Ya., Necessary and sufficient conditions for the uniform convergence of means to their expectations, Theory of Probability and its Applications, 26, 3, 532-553 (1981) · Zbl 0487.60036 · doi:10.1137/1126059 |
| [20] | Vidyasagar, M., A Theory of Learning and Generalization: with Applications to Neural Networks and Control Systems (1997), London: Springer, London · Zbl 0928.68061 |
| [21] | Vidyasagar, M., Statistical learning theory and randomized algorithms for control, Control Systems Magazine, 18, 6, 69-85 (1998) · doi:10.1109/37.736014 |
| [22] | Vidyasagar, M., Randomized algorithms for robust controller synthesis using statistical learning theory, Automatica, 37, 1515-1528 (2001) · Zbl 1055.93512 · doi:10.1016/S0005-1098(01)00122-4 |
| [23] | Vidyasagar, M.; Blondel, V. D., Probabilistic solutions to some NP-hard matrix problems, Automatica, 37, 9, 1397-1405 (2001) · Zbl 1031.93165 · doi:10.1016/S0005-1098(01)00089-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
