Moitra, A, and Stewart, A. Being robust (in high
dimensions) can be practical. In Proceedings of the
34th International Conference on Machine Learning,
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),
27. Jerrum, M. Large cliques elude the Metropolis
process. Random Structures and Algorithms 3, 4
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,
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
36. Roughgarden, T. CS264 lecture notes on beyond worst-case analysis. Stanford University, 2009–2017. Available
37. Sleator, D.D. and Tarjan, R.E. Amortized efficiency of
list update and paging rules. Commun. ACM 28, 2
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.
© 2019 ACM 0001-0782/19/3 $15.00.
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.
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
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-
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),
13. Blum, A. and Spencer, J.H. Coloring random and
semi-random k-colorable graphs. J. Algorithms 19, 2
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,
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