×

FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. (English) Zbl 07625892

Summary: We present FrankWolfe.jl, an open-source implementation of several popular Frank-Wolfe and conditional gradients variants for first-order constrained optimization. The package is designed with flexibility and high performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia’s unique multiple dispatch feature, and it interfaces smoothly with generic linear optimization formulations using MathOptInterface.jl.

MSC:

90Cxx Mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Antonello N, Stella L, Patrinos P, van Waterschoot T (2018) Proximal gradient algorithms: Applications in signal processing. Preprint, submitted March 5, https://arxiv.org/abs/1803.01621.Google Scholar
[2] Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65-98.Crossref, Google Scholar · Zbl 1356.68030 · doi:10.1137/141000671
[3] Braun G, Pokutta S, Zink D (2017) Lazifying conditional gradient algorithms. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (PMLR, UK), 566-575.Google Scholar
[4] Braun G, Pokutta S, Tu D, Wright S (2019) Blended conditional gradients: The unconditioning of conditional gradients. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., vol. 97 (PMLR, UK), 735-743.Google Scholar
[5] Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Foundations Comput. Math. 9(6):717-772.Crossref, Google Scholar · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[6] Candès EJ, Tao T (2010) The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory 56(5):2053-2080.Crossref, Google Scholar · Zbl 1366.15021 · doi:10.1109/TIT.2010.2044061
[7] Candès EJ, Wakin MB (2008) An introduction to compressive sampling. IEEE Signal Processing Magazine 25(2):21-30.Crossref, Google Scholar · doi:10.1109/MSP.2007.914731
[8] Combettes CW, Pokutta S (2021) Complexity of linear minimization and projection on some sets. Oper. Res. Lett. 49(4):565-571.Crossref, Google Scholar · Zbl 1525.90394 · doi:10.1016/j.orl.2021.06.005
[9] Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295-320.Crossref, Google Scholar · Zbl 1368.90002 · doi:10.1137/15M1020575
[10] Fazel M (2002) Matrix rank minimization with applications. PhD thesis, Stanford University, Stanford, CA.Google Scholar
[11] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1-2):95-110.Crossref, Google Scholar · doi:10.1002/nav.3800030109
[12] Guélat J, Marcotte P (1986) Some comments on Wolfe’s “away step.” Math. Programming 35(1):110-119.Crossref, Google Scholar · Zbl 0592.90074 · doi:10.1007/BF01589445
[13] Harper FM, Konstan JA (2015) The MovieLens datasets: History and context. ACM Trans. Interactive Intelligent Systems 5(4):Article 19.Google Scholar
[14] Hazan E, Luo H (2016) Variance-reduced and projection-free stochastic optimization. Balcan MF, Weinberger KQ, eds. Proc. 33th Internat. Conf. Machine Learn., vol. 48 (PMLR, UK), 1263-1271.Google Scholar
[15] Lacoste-Julien S, Jaggi M (2015) On the global linear convergence of Frank-Wolfe optimization variants. Cortes C, Lee DD, Sugiyama M, Garnett R, eds. Proc. 29th Conf. Neural Inform. Processing Systems, vol. 1 (MIT Press, Cambridge, MA), 496-504.Google Scholar
[16] Legat B, Dowson O, Garcia JD, Lubin M (2021a) MathOptInterface: A data structure for mathematical optimization problems. INFORMS J. Comput., ePub ahead of print October 22, https://doi.org/10.1287/ijoc.2021.1067.Google Scholar
[17] Legat B, Timme S, Deits R, de Laat D, Huchette J, Saba E, Forets M, Breiding P (2021b) JuliaAlgebra/MultivariatePolynomials.jl: v0.3.13. Accessed April 1, 2022, https://doi.org/10.5281/zenodo.4656033.Google Scholar
[18] Lehoucq RB, Sorensen DC, Yang C (1998) ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar · Zbl 0901.65021 · doi:10.1137/1.9780898719628
[19] Levitin ES, Polyak BT (1966) Constrained minimization methods. USSR Comput. Math. Math. Phys. 6(5):1-50.Crossref, Google Scholar · Zbl 0184.38902 · doi:10.1016/0041-5553(66)90114-5
[20] Mogensen PK, Riseth AN (2018) Optim: A mathematical optimization package for Julia. J. Open Source Software 3(24):Article 615.Crossref, Google Scholar · doi:10.21105/joss.00615
[21] Mokhtari A, Hassani H, Karbasi A (2020) Stochastic conditional gradient methods: From convex minimization to submodular maximization. J. Machine Learn. Res. 21(1):1-49.Google Scholar · Zbl 1507.68249
[22] Orban D, Siqueira AS (2020) JSOSolvers.jl: JuliaSmoothOptimizers optimization solvers. Accessed April 1, 2022, https://github.com/JuliaSmoothOptimizers/JSOSolvers.jl.Google Scholar
[23] Pauphilet J, Bertsimas D, Cory-Wright R (2021) Mixed-projection conic optimization: A new paradigm for modeling rank constraints. Oper. Res., ePub ahead of print December 20, https://pubsonline.informs.org/doi/10.1287/opre.2021.2182.Google Scholar
[24] Pedregosa F, Negiar G, Askari A, Jaggi M (2020) Linearly convergent Frank-Wolfe with backtracking line-search. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., vol. 108 (PMLR, UK), 1-10.Google Scholar
[25] Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400-407.Crossref, Google Scholar · Zbl 0054.05901 · doi:10.1214/aoms/1177729586
[26] Tibshirani R (1996) Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. B 58(1):267-288.Crossref, Google Scholar · Zbl 0850.62538 · doi:10.1111/j.2517-6161.1996.tb02080.x
[27] Udell M, Townsend A (2019) Why are big data matrices approximately low rank? SIAM J. Math. Data Sci. 1(1):144-160.Crossref, Google Scholar · Zbl 1513.68057 · doi:10.1137/18M1183480
[28] Udell M, Mohan K, Zeng D, Hong J, Diamond S, Boyd S (2014) Convex optimization in Julia. 2014 First Workshop High Performance Tech. Comput. Dyn. Languages (IEEE, Piscataway, NJ), 18-28.Google Scholar
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.