Communications of the ACM

Moitra, A, and Stewart, A. Being robust (in high dimensions) can be practical. In Proceedings of the

34th 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 38th 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 34th 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 51st 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 25th 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 48th 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 5th International Conference on Learning Representations, 2017.

Tim Roughgarden is a professor in the computer science department at Columbia University, New York, NY, USA.

and providing a road map for more robust guarantees. While work in beyond worst-case analysis makes strong assumptions relative to the norm in theoretical computer science, these assumptions are usually weaker than the norm in statistical machine learning. Research in the latter field often resembles average-case analysis, for example when data points are modeled as independent and identically distributed samples from some ( possibly parametric) distribution. The semi-random models described earlier in this article are role models in blending adversarial and average-case modeling to encourage the design of algorithms with robustly good performance. Recent progress in computationally efficient robust statistics shares much of the same spirit. 19

Conclusion

With algorithms, silver bullets are few and far between. No one design technique leads to good algorithms for all computational problems. Nor is any single analysis framework— worst-case analysis or otherwise—suitable for all occasions. A typical algorithms course teaches several paradigms for algorithm design, along with guidance about when to use each of them; the field of beyond worst-case analysis holds the promise of a comparably diverse toolbox for algorithm analysis.

Even at the level of a specific problem, there is generally no magical, always-optimal algorithm—the best algorithm for the job depends on the instances of the problem most relevant to the specific application. Research in beyond worst-case analysis acknowledges this fact while retaining the emphasis on robust guarantees that is central to worst-case analysis. The goal of work in this area is to develop novel methods for articulating the relevant instances of a problem, thereby enabling rigorous explanations of the empirical performance of known algorithms, and also guiding the design of new algorithms optimized for the instances that matter.

With algorithms increasingly dom-
inating our world, the need to under-
stand when and why they work has
never been greater. The field of be-
yond worst-case analysis has already
produced several striking results, but
there remain many unexplained gaps
between the theoretical and empiri-
cal performance of widely used algo-
rithms. With so many opportunities
for consequential research, I suspect
the best work in the area is yet to come.

Acknowledgments. I thank Sanjeev Arora, Ankur Moitra, Aravindan Vijayaraghavan, and four anonymous reviewers for several helpful suggestions. This work was supported in part by NSF award CCF-1524062, a Google Faculty Research Award, and a Guggenheim Fellowship. This article was written while the author was at Stanford University.

References

1. Ackerman, M. and Ben-David, S. Clusterability: A theoretical study. In Proceedings of the 12th 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 49th 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 49th 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 30th 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 43rd 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 57th 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

50th 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.,
Watch the author discuss
this work in the exclusive
Communications video.
https://cacm.acm.org/videos/
beyond-worst-case-analysis