no. 3
Computer science
A note on probably certifiably correct algorithms
[Une note sur les certificats d'algorithmes valables avec grande probabilité]

Présenté par : the Editorial Board

Bandeira, Afonso S.1
1 Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02142, USA
Comptes Rendus. Mathématique, Tome 354 (2016) no. 3, pp. 329-333.

De nombreux problèmes d'optimisation, bien qu'ils soient difficiles à traiter dans les cas les plus compliqués, peuvent souvent être résolus de manière efficace par des heuristiques lorsque les données du problème sont tirées au hasard (données typiques). Malheureusement, dans la plupart des cas, on ne sait que rarement certifier si l'heuristique produit une solution optimale au problème. Dans cette note, nous décrivons une famille d'algorithmes qui non seulement résolvent le problème sur des données typiques, mais aussi produisent un certificat d'optimalité. À titre d'illustration, nous décrivons un tel algorithme pour le problème du partitionnement de graphe dans le modele stochastique à blocs. D'autres exemples sont aussi discutés brièvement.

Many optimization problems of interest are known to be intractable, and while there are often heuristics that are known to work on typical instances, it is usually not easy to determine a posteriori whether the optimal solution was found. In this short note, we discuss algorithms that not only solve the problem on typical instances, but also provide a posteriori certificates of optimality, probably certifiably correct (PCC) algorithms. As an illustrative example, we present a fast PCC algorithm for minimum bisection under the stochastic block model and briefly discuss other examples.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2015.11.009
Bandeira, Afonso S. 1

1 Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02142, USA 
@article{CRMATH_2016__354_3_329_0,
     author = {Bandeira, Afonso S.},
     title = {A note on probably certifiably correct algorithms},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {329--333},
     publisher = {Elsevier},
     volume = {354},
     number = {3},
     year = {2016},
     doi = {10.1016/j.crma.2015.11.009},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2015.11.009/}
}
TY  - JOUR
AU  - Bandeira, Afonso S.
TI  - A note on probably certifiably correct algorithms
JO  - Comptes Rendus. Mathématique
PY  - 2016
SP  - 329
EP  - 333
VL  - 354
IS  - 3
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2015.11.009/
DO  - 10.1016/j.crma.2015.11.009
LA  - en
ID  - CRMATH_2016__354_3_329_0
ER  - 
%0 Journal Article
%A Bandeira, Afonso S.
%T A note on probably certifiably correct algorithms
%J Comptes Rendus. Mathématique
%D 2016
%P 329-333
%V 354
%N 3
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2015.11.009/
%R 10.1016/j.crma.2015.11.009
%G en
%F CRMATH_2016__354_3_329_0
Bandeira, Afonso S. A note on probably certifiably correct algorithms. Comptes Rendus. Mathématique, Tome 354 (2016) no. 3, pp. 329-333. doi : 10.1016/j.crma.2015.11.009. http://www.numdam.org/articles/10.1016/j.crma.2015.11.009/

[1] Abbe, E.; Bandeira, A.S.; Bracher, A.; Singer, A. Decoding binary node labels from censored edge measurements: phase transition and efficient recovery, IEEE Trans. Netw. Sci. Eng., Volume 1 (2014) no. 1, pp. 10-22

[2] Abbe, E.; Bandeira, A.S.; Hall, G. Exact recovery in the stochastic block model, IEEE Trans. Inf. Theory, Volume 62 (2016) no. 1, pp. 471-487

[3] Abbe, E.; Sandon, C. Community detection in general stochastic block models: fundamental limits and efficient algorithms for recovery, FOCS, 2015, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 2015, pp. 670-688 | DOI

[4] Agarwal, N.; Bandeira, A.S.; Koiliaris, K.; Kolla, A. Multisection in the stochastic block model using semidefinite programming, 2015 (available online at) | arXiv

[5] Alizadeh, F.; Haeberly, J.-P.; Overton, M.L. Complementarity and nondegeneracy in semidefinite programming, Math. Program., Volume 77 (1997) no. 1, pp. 111-128

[6] Amini, Arash A.; Wainwright, Martin J. High-dimensional analysis of semidefinite relaxations for sparse principal components, Ann. Stat., Volume 37 (2009) no. 5B, pp. 2877-2921

[7] Awasthi, P.; Bandeira, A.S.; Charikar, M.; Krishnaswamy, R.; Villar, S.; Ward, R. Relax, no need to round: integrality of clustering formulations, 6th Innovations in Theoretical Computer Science (ITCS 2015), 2015

[8] Bandeira, A.S. Random Laplacian matrices and convex relaxations, 2015 (available online at) | arXiv

[9] Bandeira, A.S.; Boumal, N.; Singer, A. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization, 2014 (available online at) | arXiv

[10] Bandeira, A.S.; Khoo, Y.; Singer, A. Open problem: tightness of maximum likelihood semidefinite relaxations, Proceedings of the 27th Conference on Learning Theory, JMLR W&CP, vol. 35, 2014, pp. 1265-1267

[11] Barak, B.; Steurer, D. Sum-of-squares proofs and the quest toward optimal algorithms, Survey, ICM 2014, 2014

[12] Candès, E.J.; Romberg, J.; Tao, T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, Volume 52 (2006), pp. 489-509

[13] Carlone, L.; Rosen, D.M.; Calafiore, G.C.; Leonard, J.J.; Dellaert, F. Lagrangian duality in 3d slam: verification techniques and optimal solutions, Int. Conf. on Intelligent RObots and Systems (IROS), 2015

[14] Donoho, D.L. Compressed sensing, IEEE Trans. Inf. Theory, Volume 52 (2006), pp. 1289-1306

[15] Hajek, B.; Wu, Y.; Xu, J. Achieving exact cluster recovery threshold via semidefinite programming, 2014 (available online at) | arXiv

[16] Hajek, B.; Wu, Y.; Xu, J. Achieving exact cluster recovery threshold via semidefinite programming: extensions, 2015 (available online at) | arXiv

[17] Iguchi, T.; Mixon, D.G.; Peterson, J.; Villar, S. On the tightness of an SDP relaxation of k-means, 2015 (available online at) | arXiv

[18] Kuczynski, J.; Wozniakowski, H. Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, SIAM J. Matrix Anal. Appl., Volume 13 (1992) no. 4, pp. 1094-1122

[19] Mossel, E.; Neeman, J.; Sly, A. Consistency thresholds for the planted bisection model, July 2014 (available online at) | arXiv

[20] Parrilo, P.A. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, 2000 (PhD thesis)

[21] Perry, W.; Wein, A.S. A semidefinite program for unbalanced multisection in the stochastic block model, 2015 (available online at) | arXiv

[22] So, A.M.-C.; Ye, Y. Theory of semidefinite programming for sensor network localization, Math. Program., Ser. B, Volume 109 (2007) no. 2–3, pp. 367-384

Cité par Sources :