Projection-free accelerated method for convex optimization. (English) Zbl 1501.90067
Summary: In this paper, we propose a projection-free accelerated method for solving convex optimization problems with unbounded feasible set. The method is an accelerated gradient scheme such that each projection subproblem is approximately solved by means of a conditional gradient scheme. Under reasonable assumptions, it is shown that an \(\varepsilon \)-approximate solution (concept related to the optimal value of the problem) is obtained in at most \((\mathcal{O}(1/\sqrt{\varepsilon})\) gradient evaluations and \(\mathcal{O}(1/\varepsilon)\) linear oracle calls. We also discuss a notion of approximate solution based on the first-order optimality condition of the problem and present iteration-complexity results for the proposed method to obtain an approximate solution in this sense. Finally, numerical experiments illustrating the practical behaviour of the proposed scheme are discussed.
MSC:
| 90C25 | Convex programming |
| 90C06 | Large-scale problems in mathematical programming |
| 90C22 | Semidefinite programming |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
projection-free method; accelerated method; first-order methods; conditional gradient methodReferences:
| [1] | Bach, F., Duality between subgradient and conditional gradient methods, SIAM J. Optim., 25, 1, 115-129 (2015) · Zbl 1358.90155 · doi:10.1137/130941961 |
| [2] | Beck, A.; Teboulle, M., A conditional gradient method with linear rate of convergence for solving convex linear systems, Math. Methods Oper. Res., 59, 2, 235-247 (2004) · Zbl 1138.90440 · doi:10.1007/s001860300327 |
| [3] | Bredies, K.; Lorenz, D.; Maass, P., A generalized conditional gradient method and its connection to an iterative shrinkage method, Comput. Optim. Appl., 42, 2, 173-193 (2009) · Zbl 1179.90326 · doi:10.1007/s10589-007-9083-3 |
| [4] | Dunn, J. C., Convergence rates for conditional gradient sequences generated by implicit step length rules, SIAM J. Control Optim., 18, 5, 473-487 (1980) · Zbl 0457.65048 · doi:10.1137/0318035 |
| [5] | Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Log. Q., 3, 1-2, 95-110 (1956) · doi:10.1002/nav.3800030109 |
| [6] | Freund, R.; Grigas, P., New analysis and results for the FrankWolfe method, Math. Programm., 155, 1-32 (2014) |
| [7] | Guzmán, C.; Nemirovski, A., On lower complexity bounds for large-scale smooth convex optimization, J. Complex., 31, 1, 1-14 (2015) · Zbl 1304.65155 · doi:10.1016/j.jco.2014.08.003 |
| [8] | Harchaoui, Z.; Juditsky, A.; Nemirovski, A., Conditional gradient algorithms for norm-regularized smooth convex optimization, Math. Program., 152, 12, 75-112 (2015) · Zbl 1336.90069 · doi:10.1007/s10107-014-0778-9 |
| [9] | He, Y.; Monteiro, R., An accelerated hpe-type algorithm for a class of composite convex-concave saddle-point problems, SIAM J. Optim., 26, 1, 29-56 (2016) · Zbl 1329.90179 · doi:10.1137/14096757X |
| [10] | Jaggi, M., Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning (ICML-13) (2013), vol. 28, pp. 427-435. |
| [11] | Kolossoski, O.; Monteiro, R. D.C., An accelerated non-euclidean hybrid proximal extragradient-type algorithm for convex-concave saddle-point problems, Optim. Methods Softw., 32, 6, 1244-1272 (2017) · Zbl 1375.90236 · doi:10.1080/10556788.2016.1266355 |
| [12] | Lan, G., The complexity of large-scale convex programming under a linear optimization oracle. Available on http://www.optimization-online.org. |
| [13] | Lan, G.; Zhou, Y., Conditional gradient sliding for convex optimization, SIAM J. Optim., 26, 2, 1379-1409 (2016) · Zbl 1342.90132 · doi:10.1137/140992382 |
| [14] | Luss, R.; Teboulle, M., Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint, SIAM Rev., 55, 1, 65-98 (2013) · Zbl 1263.90094 · doi:10.1137/110839072 |
| [15] | Monteiro, R. D.C.; Ortiz, C.; Svaiter, B. F., An adaptive accelerated first-order method for convex optimization, Comput. Optim. Appl., 64, 1, 31-73 (2016) · Zbl 1344.90049 · doi:10.1007/s10589-015-9802-0 |
| [16] | Nemirovski, A.; Yudin, D., Problem Complexity and Method Efficiency in Optimization (1983), Wiley, New York · Zbl 0501.90062 |
| [17] | Nesterov, Y. E., Introductory Lectures on Convex Optimization: a Basic Course (2004), Kluwer Academic Publ.: Kluwer Academic Publ., Boston · Zbl 1086.90045 |
| [18] | Nesterov, Y. E., Smooth minimization of nonsmooth functions, Math. Programm., 103, 127-152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5 |
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.
