An optimization problem for continuous submodular functions
DOI:
https://doi.org/10.24193/subbmath.2021.1.17Keywords:
Continuous submodular optimization, entropy method, secret sharing.Abstract
Real continuous submodular functions, as a generalization of the corre- sponding discrete notion to the continuous domain, gained considerable attention recently. The analog notion for entropy functions requires additional properties: a real function defined on the non-negative orthant of Rn is entropy-like (EL) if it is submodular, takes zero at zero, non-decreasing, and has the Diminishing Returns property. Motivated by problems concerning the Shannon complexity of multipartite secret sharing, a special case of the following general optimization problem is considered: find the minimal cost of those EL functions which satisfy certain constraints. In our special case the cost of an EL function is the maximal value of the n partial derivatives at zero. Another possibility could be the supre- mum of the function range. The constraints are specified by a smooth bounded surface S cutting off a downward closed subset. An EL function is feasible if at the internal points of S the left and right partial derivatives of the function differ by at least one. A general lower bound for the minimal cost is given in terms of the normals of the surface S. The bound is tight when S is linear. In the two- dimensional case the same bound is tight for convex or concave S. It is shown that the optimal EL function is not necessarily unique. The paper concludes with several open problems.
Mathematics Subject Classification (2010): 90C26, 46N10, 49Q10.
References
Bach, F., Learning with Submodular Functions: A Convex Optimization Perspective, Foundations and Trends in Machine Learning, 2013.
Bach, F., Submodular functions: from discrete to continuous domains, Math. Program., 175(2019), no. 1-2, 419-459.
Beimel, A., Secret-sharing schemes: A survey, In: Proceedings of the Third International Conference on Coding and Cryptology, IWCC’11, Springer-Verlag, Berlin, Heidelberg, 2011, 11-46.
Bian, Y., Buhmann, J.M., Krause, A., Continuous submodular function maximization, arXiv preprint arXiv:2006.13474, 2020.
Botton, L., Curtis, F.E., Nocedal, J., Optimization methods for large-scale machine learning, Siam Review, 60(2018), no. 2, 223-311.
Chen, L., Hassani, H., Karbasi, A., Online continuous submodular maximization, In: AISTATS, Playa Blanca, Lanzarote, Canary Islands, 2018.
Csirmaz, L., Matus, F., Padro, C., Bipartite secret sharing and staircases, Unpublished manuscript, 2020.
Farras, O., Martı-Farre, J., Padro, C., Ideal multipartite secret sharing schemes, J. Cryptology, 25(2012), no. 3, 434-463.
Farras, O., Metcalf-Burton, J.R., Padro, C., Vazquez, L., On the optimization of bipartite secret sharing schemes, Des. Codes Cryptog., 63(2012), no. 2, 255-271.
Metcalf-Burton, J.R., Information rates of minimal non-matroid-related access structures, CoRR, 2008.
Rudin, W., Principles of Mathematical Analysis, McGraw-Hill Book Co., New York, 3rd edition, 1976.
Staib, M., Jegelka, S., Robust budget allocation via continuous submodular functions, In: Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, vol. 70 of Proceedings of Machine Learning Research, 3230-3240.
Yeung, R.W., A First Course in Information Theory, Information Technology: Transmission, Processing and Storage, Springer US, 2012.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Studia Universitatis Babeș-Bolyai Mathematica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
