Distributed algorithms for convex problems with linear coupling constraints. (English) Zbl 1441.90155
Summary: Distributed and parallel algorithms have been frequently investigated in the recent years, in particular in applications like machine learning. Nonetheless, only a small subclass of the optimization algorithms in the literature can be easily distributed, for the presence, e.g., of coupling constraints that make all the variables dependent from each other with respect to the feasible set. Augmented Lagrangian methods are among the most used techniques to get rid of the coupling constraints issue, namely by moving such constraints to the objective function in a structured, well-studied manner. Unfortunately, standard augmented Lagrangian methods need the solution of a nested problem by needing to (at least inexactly) solve a subproblem at each iteration, therefore leading to potential inefficiency of the algorithm. To fill this gap, we propose an augmented Lagrangian method to solve convex problems with linear coupling constraints that can be distributed and requires a single gradient projection step at every iteration. We give a formal convergence proof to at least \(\varepsilon\)-approximate solutions of the problem and a detailed analysis of how the parameters of the algorithm influence the value of the approximating parameter \(\varepsilon\). Furthermore, we introduce a distributed version of the algorithm allowing to partition the data and perform the distribution of the computation in a parallel fashion.
MSC:
| 90C30 | Nonlinear programming |
References:
| [1] | Aussel, D.; Sagratella, S., Sufficient conditions to compute any solution of a quasivariational inequality via a variational inequality, Math. Methods Oper. Res., 85, 1, 3-18 (2017) · Zbl 1365.49010 |
| [2] | Bertsekas, DP, Nonlinear Programming (1999), Belmont: Athena Scientific, Belmont · Zbl 1015.90077 |
| [3] | Bertsekas, DP, Convex Optimization Algorithms (2015), Nashua, NH, USA: Athena Scientific, Nashua, NH, USA · Zbl 1347.90001 |
| [4] | Bertsekas, DP; Tsitsiklis, JN, Parallel and Distributed Computation: Numerical Methods (1989), Englewood Cliffs: Prentice hall, Englewood Cliffs · Zbl 0743.65107 |
| [5] | Birgin, EG; Martinez, JM, Practical Augmented Lagrangian Methods for Constrained Optimization (2014), Philadelphia: SIAM, Philadelphia · Zbl 1339.90312 |
| [6] | Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends® Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122 |
| [7] | Cannelli, L., Facchinei, F., Scutari, G.: Multi-agent asynchronous nonconvex large-scale optimization. In: 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 1-5. IEEE (2017) |
| [8] | Cassioli, A.; Di Lorenzo, D.; Sciandrone, M., On the convergence of inexact block coordinate descent methods for constrained optimization, Eur. J. Oper. Res., 231, 2, 274-281 (2013) · Zbl 1317.90275 |
| [9] | Chang, CC; Lin, CJ, Libsvm: a library for support vector machines, ACM Trans. Intell. Syst. Technol. (TIST), 2, 3, 27 (2011) |
| [10] | Clarke, FH, Optimization and Nonsmooth Analysis (1990), Philadelphia: SIAM, Philadelphia · Zbl 0696.49002 |
| [11] | Daneshmand, A., Sun, Y., Scutari, G., Facchinei, F., Sadler, B.M.: Decentralized dictionary learning over time-varying digraphs (2018). arXiv preprint arXiv:1808.05933 · Zbl 1434.68403 |
| [12] | Di Pillo, G.; Lucidi, S.; Di Pillo, G.; Giannessi, F., On exact augmented lagrangian functions in nonlinear programming, Nonlinear Optimization and Applications, 85-100 (1996), Boston: Springer, Boston · Zbl 0986.90053 |
| [13] | Di Pillo, G.; Lucidi, S., An augmented lagrangian function with improved exactness properties, SIAM J. Optim., 12, 2, 376-406 (2002) · Zbl 0996.65064 |
| [14] | Facchinei, F.; Kanzow, C., Generalized Nash equilibrium problems, 4OR, 5, 3, 173-210 (2007) · Zbl 1211.91162 |
| [15] | Facchinei, F.; Kanzow, C.; Karl, S.; Sagratella, S., The semismooth Newton method for the solution of quasi-variational inequalities, Comput. Optim. Appl., 62, 1, 85-109 (2015) · Zbl 1331.90083 |
| [16] | Facchinei, F.; Pang, JS, Finite-Dimensional Variational Inequalities and Complementarity Problems (2007), Berlin: Springer, Berlin |
| [17] | Facchinei, F.; Sagratella, S., On the computation of all solutions of jointly convex generalized Nash equilibrium problems, Optim. Lett., 5, 3, 531-547 (2011) · Zbl 1259.91009 |
| [18] | Facchinei, F.; Scutari, G.; Sagratella, S., Parallel selective algorithms for nonconvex big data optimization, IEEE Trans. Signal Process., 63, 7, 1874-1889 (2015) · Zbl 1394.94174 |
| [19] | García, R.; Marín, A.; Patriksson, M., Column generation algorithms for nonlinear optimization, I: convergence analysis, Optimization, 52, 2, 171-200 (2003) · Zbl 1033.65040 |
| [20] | Gondzio, J.; Grothey, A., Exploiting structure in parallel implementation of interior point methods for optimization, Comput. Manag. Sci., 6, 2, 135-160 (2009) · Zbl 1170.90518 |
| [21] | Harchaoui, Z., Juditsky, A., Nemirovski, A.: Conditional gradient algorithms for machine learning. In: NIPS Workshop on Optimization for ML, vol. 3, pp. 3-2 (2012) |
| [22] | Hong, M.; Luo, ZQ, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162, 1-2, 165-199 (2017) · Zbl 1362.90313 |
| [23] | Jaggi, M., Revisiting Frank-Wolfe: projection-free sparse convex optimization, ICML, 1, 427-435 (2013) |
| [24] | Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank-Wolfe optimization variants. In: Advances in Neural Information Processing Systems, pp. 496-504 (2015) |
| [25] | Latorre, V.; Sagratella, S., A canonical duality approach for the solution of affine quasi-variational inequalities, J. Global Optim., 64, 3, 433-449 (2016) · Zbl 1354.90148 |
| [26] | Lin, CJ; Lucidi, S.; Palagi, L.; Risi, A.; Sciandrone, M., Decomposition algorithm model for singly linearly-constrained problems subject to lower and upper bounds, J. Optim. Theory Appl., 141, 1, 107-126 (2009) · Zbl 1168.90556 |
| [27] | Lucidi, S., New results on a class of exact augmented lagrangians, J. Optim. Theory Appl., 58, 2, 259-282 (1988) · Zbl 0628.90060 |
| [28] | Lucidi, S.; Palagi, L.; Risi, A.; Sciandrone, M., A convergent decomposition algorithm for support vector machines, Comput. Optim. Appl., 38, 2, 217-234 (2007) · Zbl 1172.90443 |
| [29] | Mangasarian, O.; Fischer, H.; Riedmüller, B.; Schäffler, S., Machine learning via polyhedral concave minimization, Applied Mathematics and Parallel Computing, 175-188 (1996), Berlin: Springer, Berlin · Zbl 0906.68127 |
| [30] | Manno, A.; Palagi, L.; Sagratella, S., Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training, Comput. Optim. Appl., 71, 1, 115-145 (2018) · Zbl 1405.90095 |
| [31] | Manno, A., Sagratella, S., Livi, L.: A convergent and fully distributable SVMs training algorithm. In: 2016 International Joint Conference on Neural Networks (IJCNN), pp. 3076-3080. IEEE (2016) |
| [32] | Ouyang, H., Gray, A.: Fast stochastic Frank-Wolfe algorithms for nonlinear SVMs. In: Proceedings of the 2010 SIAM International Conference on Data Mining, pp. 245-256. SIAM (2010) |
| [33] | Piccialli, V.; Sciandrone, M., Nonlinear optimization and support vector machines, 4OR, 16, 2, 111-149 (2018) · Zbl 1398.65126 |
| [34] | Rockafellar, RT, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control, 12, 2, 268-285 (1974) · Zbl 0257.90046 |
| [35] | Rockafellar, RT; Wets, RJB, Variational Analysis (2009), Berlin: Springer, Berlin |
| [36] | Sagratella, S., Algorithms for generalized potential games with mixed-integer variables, Comput. Optim. Appl., 68, 3, 689-717 (2017) · Zbl 1390.91023 |
| [37] | Scutari, G.; Facchinei, F.; Lampariello, L., Parallel and distributed methods for constrained nonconvex optimization—part I: theory, IEEE Trans. Signal Process., 65, 8, 1929-1944 (2016) · Zbl 1414.90290 |
| [38] | Scutari, G.; Facchinei, F.; Lampariello, L.; Sardellitti, S.; Song, P., Parallel and distributed methods for constrained nonconvex optimization—part II: applications in communications and machine learning, IEEE Trans. Signal Process., 65, 8, 1945-1960 (2016) · Zbl 1414.90291 |
| [39] | Scutari, G., Facchinei, F., Lampariello, L., Song, P.: Parallel and distributed methods for nonconvex optimization. In: 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 840-844. IEEE (2014) |
| [40] | Woodsend, K.; Gondzio, J., Hybrid MPI/OpenMP parallel linear support vector machine training, J. Mach. Learn. Res., 10, Aug, 1937-1953 (2009) · Zbl 1235.68205 |
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.
