Beyond worst-case analysis

Abstract

The need for deeply understanding when algorithms work (or not) has never been greater.

References

1. Ackerman, M. and Ben-David, S. Clusterability: A theoretical study. In Proceedings of the 12^th International Conference on Artificial Intelligence and Statistics, 2009, 1--8.
2. Albers, S., Favrholdt, L.M. and Giel, O. On paging with locality of reference. J. Computer and System Sciences 70, 2 (2005), 145--175.
3. Alon, N., Krivelevich, M. and Sudakov, B. Finding a large hidden clique in a random graph. Random Structures & Algorithms 13, 3--4 (1998), 457--466.
4. Angel, O., Bubeck, S., Peres, Y., and Wai, F. Local MAX-CUT in smoothed polynomial time. In Proceedings of the 49^th Annual ACM Symposium on Theory of Computing, 2017, 429--437.
5. Angelidakis, H., Makarychev, K., and Makarychev, Y. Algorithms for stable and perturbation-resilient problems. In Proceedings of the 49^th Annual ACM Symposium on Theory of Computing, pages 438--451, 2017.
6. Arora, S., Ge, R., Halpern, Y. Mimno, D.M., Moitra, A., Sontag, D., Wu, Y. and Zhu, M. A practical algorithm for topic modeling with provable guarantees. In Proceedings of the 30^th International Conference on Machine Learning, 2013, 280--288.
7. Arthur, D., Manthey, B., and Roglin, H. Smoothed analysis of the k-means method. JACM 58, 5 (2011), Article No. 18.
8. Awasthi, P., Blum, A. and Sheffet, O. Center-based clustering under perturbation stability. Information Processing Letters 112, 1--2 (2012), 49--54.
9. Balcan, M.-F., Blum, A. and Gupta, A. Clustering under approximation stability. JACM 60, 2 (2013), Article No. 8.
10. Balcan, M.-F., Haghtalab, N. and White, C. k-center clustering under perturbation resilience. In Proceedings of the 43^rd Annual International Colloquium on Automata, Languages, and Programming, 2016, Article No. 68.
11. Barak, B., Hopkins, S.B., Kelner, J.A., Kothari, P., Moitra, A., and Potechin, A. A nearly tight sum-of squares lower bound for the planted clique problem. In Proceedings of the 57^th Annual IEEE Symposium on Foundations of Computer Science, 2016, 428--437.
12. Bilu, Y. and Linial, N. Are stable instances easy? Combinatorics, Probability & Computing 21, 5 (2012), 643--660.
13. Blum, A. and Spencer, J.H. Coloring random and semi-random k-colorable graphs. J. Algorithms 19, 2 (1995), 204--234.
14. Borgwardt, K.H. The Simplex Method: A probabilistic analysis. Springer-Verlag, 1980.
15. Candes, E.J., Romberg, J.K., and Tao, T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete Fourier information. IEEE Trans. Information Theory 52, 2 (20006), 489--509.
16. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M, and Saurabh, S. Parameterized Algorithms. Springer, 2015.
17. Dadush, D. and Huiberts, S. A friendly smoothed analysis of the simplex method. In Proceedings of the 50^th Annual ACM Symposium on Theory of Computing, 2018, 390--403.
18. Daniely, A., Linial, N. and M. Saks. Clustering is difficult only when it does not matter. arXiv:1205.4891, 2012.
19. Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A, and Stewart, A. Being robust (in high dimensions) can be practical. In Proceedings of the 34^th International Conference on Machine Learning, 2017, 999--1008.
20. Donoho, D.L. Compressed sensing. IEEE Trans. Information Theory 52, 4 (2006), 1289--1306.
21. Elsasser, R. and Tscheuschner, T. Settling the complexity of local max-cut (almost) completely. In Proceedings of the 38^th Annual International Colloquium on Automata, Languages, and Programming, 2011, 171--182.
22. Etscheid, M. and Roglin, H. Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algorithms 13, 2 (2017), Article No. 12.
23. Fagin, R., Lotem, A. and Naor, M. Optimal aggregation algorithms for middleware. J. Computer and System Sciences 66, 4 (2003), 614--656.
24. Feige, U. and Kilian, J. Heuristics for semirandom graph problems. J. Computer and System Sciences 63, 4 (2001), 639--671.
25. Goodfellow, I., Bengio, Y. and Courville, A. Deep Learning. MIT Press, 2016.
26. Gupta, R. and Roughgarden, T. Application-specific algorithm selection. SIAM J. Computing 46, 3 (2017), 992--1017.
27. Jerrum, M. Large cliques elude the Metropolis process. Random Structures and Algorithms 3, 4 (1992), 347--359.
28. Jin, C, Ge, R., Netrapalli, P., Kakade, S.M. and Jordan, M.I. How to escape saddle points efficiently. In Proceedings of the 34^th International Conference on Machine Learning, 2017, 1724--1732.
29. Kumar, A. and Kannan, R. Clustering with spectral norm and the k-means algorithm. In Proceedings of the 51^st Annual IEEE Symposium on Foundations of Computer Science, 2010, 299--308.
30. Makarychev, K., Makarychev, Y. and Vijayaraghavan, A. Bilu-Linial stable instances of max cut and minimum multiway cut. In Proceedings of the 25^th Annual ACM-SIAM Symposium on Discrete Algorithms, 2014, 890--906.
31. Moitra, A., Perry, W. and Wein, A.S. How robust are reconstruction thresholds for community detection? In Proceedings of the 48^th Annual ACM Symposium on Theory of Computing, 2016, 828--841.
32. Moore, C. The computer science and physics of community detection: Landscapes, phase transitions, and hardness. Bulletin of EATCS 121 (2017), 1--37.
33. Neyshabur, B. Implicit Regularization in Deep Learning. Ph.D. thesis, Toyota Technological Institute at Chicago, 2017.
34. Ostrovsky, R., Rabani, Y., Schulman, L.J. and Swamy, C. The effectiveness of Lloyd-type methods for the k-means problem. JACM 59, 6 (2012), Article No. 22.
35. Papadimitriou, C.H., Raghgavan, P., Tamaki, H. and Vemapala, S. Latent semantic indexing: A probabilistic analysis. J. Computer and System Sciences 61, 2 (2000), 217--235.
36. Roughgarden, T. CS264 lecture notes on beyond worst-case analysis. Stanford University, 2009--2017. Available at http://www.timroughgarden.org/notes.html.
37. Sleator, D.D. and Tarjan, R.E. Amortized efficiency of list update and paging rules. Commun. ACM 28, 2 (1985), 202--208.
38. Spielman, D.A. and Teng, S.-H. Smoothed analysis: Why the simplex algorithm usually takes polynomial time. JACM 51, 3 (2004), 385--463.
39. Trevisan, L. Inapproximability of combinatorial optimization problems. Paradigms of Combinatorial Optimization: Problems and New Approaches. V.T. Paschos, ed. Wiley, 2014.
40. Zhang, C., Bengio, S., Hardt, M., Recht, B. and Vinyals, O. Understanding deep learning requires rethinking generalization. In Proceedings of the 5^th International Conference on Learning Representations, 2017.

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

• Theory of computation

  • Design and analysis of algorithms