Multiplicative Weights for Online Binary Prediction under Stable and Changing Expert Reliability: A Simulation Study

Authors

  • Hengzhi Shao

DOI:

https://doi.org/10.54097/1s43tr17

Keywords:

Online learning; Multiplicative weights; Expert advice; Nonstationarity; Regret

Abstract

Combining advisers with unknown and changing reliability is a central problem in online prediction. This paper studies a deterministic exponential weighted-majority predictor in two synthetic environments. Nine experts forecast 1,000 balanced binary outcomes, and 200 Monte Carlo repetitions compared six learning rates from 0.01 to 1.00, equal majority voting, the best fixed expert, and a two-phase oracle. With stable reliabilities, mean errors declined from 241.62 at learning rate 0.01 to 203.10 at learning rate 1.00, close to the best fixed expert's 200.04 and well below equal majority's 407.34. When the initially strongest and weakest experts exchanged accuracies at round 501, mean errors declined from 315.56 to 282.57 as the learning rate increased, but the latter result still incurred 82.34 more errors than the phase-specific oracle. Short-run adaptation showed the opposite learning-rate pattern: during rounds 501-600, learning rate 0.01 averaged 45.11 errors, whereas rates from 0.05 to 1.00 averaged about 63. Faster updating therefore improved full-horizon performance but created greater vulnerability immediately after an abrupt reversal. Static regret alone understated the cost of changing reliability.

References

[1] Littlestone, N., & Warmuth, M. K. (1994). The weighted majority algorithm. Information and Computation, 108(2), 212–261. https://doi.org/10.1006/inco.1994.1009

[2] Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139. https://doi.org/10.1006/jcss.1997.1504

[3] Arora, S., Hazan, E., & Kale, S. (2012). The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1), 121–164. https://doi.org/10.4086/toc.2012.v008a006

[4] Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D. P., Schapire, R. E., & Warmuth, M. K. (1997). How to use expert advice. Journal of the ACM, 44(3), 427–485. https://doi.org/10.1145/258128.258179

[5] Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge University Press. https://doi.org/10.1017/CBO9780511546921

[6] Herbster, M., & Warmuth, M. K. (1998). Tracking the best expert. Machine Learning, 32(2), 151–178. https://doi.org/10.1023/A:1007424614876

[7] de Rooij, S., van Erven, T., Grünwald, P. D., & Koolen, W. M. (2014). Follow the leader if you can, Hedge if you must. Journal of Machine Learning Research, 15, 1281–1316. https://jmlr.org/papers/v15/rooij14a.html

[8] Koolen, W. M., & Van Erven, T. (2015). Second-order quantile methods for experts and combinatorial games. Proceedings of the 28th Conference on Learning Theory, 40, 1155–1175. https://proceedings.mlr.press/v40/Koolen15a.html

[9] Luo, H., & Schapire, R. E. (2015). Achieving all with no parameters: AdaNormalHedge. Proceedings of the 28th Conference on Learning Theory, 40, 1286–1304. https://proceedings.mlr.press/v40/Luo15.html

[10] Mourtada, J., & Gaïffas, S. (2019). On the optimality of the Hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20, 1–28. https://jmlr.org/papers/v20/18-869.html

[11] Cesa-Bianchi, N., Gaillard, P., Lugosi, G., & Stoltz, G. (2012). Mirror descent meets fixed share (and feels no regret). Advances in Neural Information Processing Systems, 25, 989–997. https://proceedings.neurips.cc/paper/2012/hash/8e6b42f1644ecb1327dc03ab345e618b-Abstract.html

[12] Monteleoni, C., & Jaakkola, T. S. (2003). Online learning of non-stationary sequences. Advances in Neural Information Processing Systems, 16, 1093–1100. https://proceedings.neurips.cc/paper/2003/hash/feecee9f1643651799ede2740927317a-Abstract.html

[13] Daniely, A., Gonen, A., & Shalev-Shwartz, S. (2015). Strongly adaptive online learning. Proceedings of the 32nd International Conference on Machine Learning, 37, 1405–1411. https://proceedings.mlr.press/v37/daniely15.html

[14] Jun, K.-S., Orabona, F., Wright, S., & Willett, R. (2017). Improved strongly adaptive online learning using coin betting. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 54, 943–951. https://proceedings.mlr.press/v54/jun17a.html

[15] Blum, A. (1997). Empirical support for Winnow and Weighted-Majority algorithms: results on a calendar scheduling domain. Machine Learning, 26(1), 5–23. https://doi.org/10.1023/A:1007335615132

[16] Dani, V., Madani, O., Pennock, D. M., Sanghai, S., & Galebach, B. (2006). An empirical comparison of algorithms for aggregating expert predictions. Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, 106–113. https://dl.acm.org/doi/10.5555/3020419.3020433

[17] Devaine, M., Gaillard, P., Goude, Y., & Stoltz, G. (2013). Forecasting electricity consumption by aggregating specialized experts. Machine Learning, 90(2), 231–260. https://doi.org/10.1007/s10994-012-5314-7

[18] Gaillard, P., Goude, Y., & Nedellec, R. (2016). Additive models and robust aggregation for GEFCom2014 probabilistic electric load and electricity price forecasting. International Journal of Forecasting, 32(3), 1038–1050. https://doi.org/10.1016/j.ijforecast.2015.12.001

[19] Morris, T. P., White, I. R., & Crowther, M. J. (2019). Using simulation studies to evaluate statistical methods. Statistics in Medicine, 38(11), 2074–2102. https://doi.org/10.1002/sim.8086

Downloads

Published

07-11-2026

Issue

Section

Articles

How to Cite

Shao, H. (2026). Multiplicative Weights for Online Binary Prediction under Stable and Changing Expert Reliability: A Simulation Study. Mathematical Modeling and Algorithm Application, 10(1), 45-49. https://doi.org/10.54097/1s43tr17