Comptes Rendus
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

Afonso S. Bandeira1
1 Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02142, USA
Comptes Rendus. Mathématique, Volume 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
Afonso S. Bandeira 1

1 Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02142, USA 
@article{CRMATH_2016__354_3_329_0,
     author = {Afonso S. Bandeira},
     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},
}
TY  - JOUR
AU  - Afonso S. Bandeira
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
DO  - 10.1016/j.crma.2015.11.009
LA  - en
ID  - CRMATH_2016__354_3_329_0
ER  - 
%0 Journal Article
%A Afonso S. Bandeira
%T A note on probably certifiably correct algorithms
%J Comptes Rendus. Mathématique
%D 2016
%P 329-333
%V 354
%N 3
%I Elsevier
%R 10.1016/j.crma.2015.11.009
%G en
%F CRMATH_2016__354_3_329_0
Afonso S. Bandeira. A note on probably certifiably correct algorithms. Comptes Rendus. Mathématique, Volume 354 (2016) no. 3, pp. 329-333. doi : 10.1016/j.crma.2015.11.009. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2015.11.009/

[1] E. Abbe; A.S. Bandeira; A. Bracher; A. Singer 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] E. Abbe; A.S. Bandeira; G. Hall Exact recovery in the stochastic block model, IEEE Trans. Inf. Theory, Volume 62 (2016) no. 1, pp. 471-487

[3] E. Abbe; C. Sandon 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] N. Agarwal; A.S. Bandeira; K. Koiliaris; A. Kolla Multisection in the stochastic block model using semidefinite programming, 2015 (available online at) | arXiv

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

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

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

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

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

[10] A.S. Bandeira; Y. Khoo; A. Singer 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] B. Barak; D. Steurer Sum-of-squares proofs and the quest toward optimal algorithms, Survey, ICM 2014, 2014

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

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

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

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

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

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

[18] J. Kuczynski; H. Wozniakowski 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] E. Mossel; J. Neeman; A. Sly Consistency thresholds for the planted bisection model, July 2014 (available online at) | arXiv

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

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

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

Cité par Sources :

Commentaires - Politique