Efficient convex optimization with oracles. (English) Zbl 1452.68272
Bárány, Imre (ed.) et al., Building bridges II. Mathematics of László Lovász. Conference in celebration of László Lovász’ 70th birthday, Budapest, Hungary, July 2–6, 2018. Berlin: Springer. Bolyai Soc. Math. Stud. 28, 317-335 (2019).
Summary: Minimizing a convex function over a convex set is a basic algorithmic problem. We give a simple algorithm for the general setting in which the function is given by an evaluation oracle and the set by a membership oracle. The algorithm takes \(\widetilde{O}(n^2)\) oracle calls and \(\widetilde{O}(n^3)\) additional arithmetic operations. This results in more efficient reductions among the five basic oracles for convex sets and functions defined by
M. Grötschel et al. [Geometric algorithms and combinatorial optimization. Berlin etc.: Springer-Verlag (1988; Zbl 0634.05001)].
For the entire collection see [Zbl 1443.05002].
For the entire collection see [Zbl 1443.05002].
Citations:
Zbl 0634.05001References:
| [1] | Jacob D. Abernethy and Elad Hazan. Faster convex optimization: Simulated annealing with an efficient universal barrier. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 2520-2528, 2016. |
| [2] | Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. Journal of the ACM (JACM), 51(4):540-556, 2004. · Zbl 1204.90074 · doi:10.1145/1008731.1008733 |
| [3] | Sébastien Bubeck and Ronen Eldan. Multi-scale exploration of convex functions and bandit convex optimization. arXiv preprint arXiv:1507.06580, 2015. · Zbl 1435.52001 |
| [4] | Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 273-282. ACM, 2011. · Zbl 1288.94127 |
| [5] | Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Algorithms and Combinatorics, 1988. · Zbl 0634.05001 |
| [6] | A. T. Kalai and S. Vempala. Simulated annealing for convex optimization. Math. Oper. Res., 31(2):253-266, 2006. · Zbl 1278.90311 · doi:10.1287/moor.1060.0194 |
| [8] | Yin Tat Lee, Satish Rao, and Nikhil Srivastava. A new approach to computing maximum flows using electrical flows. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 755-764. ACM, 2013. · Zbl 1293.05148 |
| [9] | Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o(sqrt(rank)) iterations and faster algorithms for maximum flow. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 424-433. IEEE, 2014. |
| [10] | Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 230-249. IEEE, 2015. |
| [11] | Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 1049-1065. IEEE, 2015. |
| [12] | L. Lovász and S. Vempala. Fast algorithms for logconcave functions: sampling, rounding, integration and optimization. In FOCS, pages 57-68, 2006. |
| [13] | Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 253-262. IEEE, 2013. |
| [14] | Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, Apr 2017. · Zbl 1380.90220 |
| [15] | V. Yu. Protasov. Algorithms for approximate calculation of the minimum of a convex function from its values. Mathematical Notes, 59(1):69-74, 1996. · Zbl 0870.90088 · doi:10.1007/BF02312467 |
| [16] | Jonah Sherman. Nearly maximum flows in nearly linear time. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 263-269. IEEE, 2013. |
| [17] | Jonah Sherman. Area-convexity, \(l_{\infty }\) regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 452-460, 2017. · Zbl 1370.90050 |
| [18] | Stefan Steinerberger. Sharp l 1-poincaré inequalities correspond to optimal hypersurface cuts. Archiv der Mathematik, 105(2):179-188, 2015. · Zbl 1337.46028 · doi:10.1007/s00013-015-0778-x |
| [19] | P. |
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.
