Self-improving algorithms

ABSTRACT

We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an arbitrary, unknown input distribution. We give such self-improving algorithms for sorting and clustering. The highlights of this work: (i) a sorting algorithm with optimal expected limiting running time; and (ii) a k-median algorithm over the Hamming cube with linear expected limiting running time. In all cases, the algorithm begins with a learning phase during which it adjusts itself to the input distribution (typically in a logarithmic number of rounds), followed by a stationary regime in which the algorithm settles to its optimized incarnation.

REFERENCES

• 1: Susanne Albers , Jeffery Westbrook, Self-Organizing Data Structures, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.13-51, January 1998
• 2: Brian Allen , Ian Munro, Self-Organizing Binary Search Trees, Journal of the ACM (JACM), v.25 n.4, p.526-535, Oct. 1978 [doi>10.1145/322092.322094]
• 3: N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
• 4: N. Alon and J. Spencer. The probabilistic method. John Wiley, 2nd edition, 2000.
• 5: Noga Alon , Benny Sudakov, On two segmentation problems, Journal of Algorithms, v.33 n.1, p.173-184, Oct. 1999 [doi>10.1006/jagm.1999.1024]
• 6: Sigal Ar , Bernard Chazelle , Ayellet Tal, Self-customized BSP trees for collision detection, Computational Geometry: Theory and Applications, v.15 n.1-3, p.91-102, Feb.1.2000 [doi>10.1016/S0925-7721(99)00049-8]
• 7: Mihai Bâdoiu , Kenneth L. Clarkson, Smaller core-sets for balls, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 9: Jon L. Bentley , Catherine C. McGeoch, Amortized analyses of self-organizing sequential search heuristics, Communications of the ACM, v.28 n.4, p.404-411, April 1985 [doi>10.1145/3341.3349]
• 10: J. R. Bitner. Heuristics that dynamically organize data structures, SIAM J. Comput., 8:82--110, 1979.
• 11: A. Blum. On-line algorithms in machine learning, Online Algorithms: The state of the art, 1441, 1998.
• 12: Avrim Blum , Shuchi Chawla , Adam Kalai, Static optimality and dynamic search-optimality in lists and trees, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-8, January 06-08, 2002, San Francisco, California
• 13: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 14: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 15: W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780550]
• 16: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 17: Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
• 18: Abraham D. Flaxman , Adam Tauman Kalai , H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 19: Fredman, M. L. How good is the information theory bound in sorting?, Theoretical Computer Science 1 (1976), 355--361.
• 20: Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights, Games and Economic Behavior, 29:79--103, 1999.
• 21: G. H. Gonnet, J. I. Munro, and H. Suwanda. Exegesis of self-organizing linear search, SIAM J. Comput., 10:613--637, 1981.
• 22: S. Har-Peled, Clustering Motion, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.84, October 14-17, 2001
• 23: Sariel Har-Peled , Akash Kushal, Smaller coresets for k-median and k-means clustering, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064114]
• 24: Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007400]
• 25: J. H. Hester , D. S. Hirschberg, Self-organizing linear search, ACM Computing Surveys (CSUR), v.17 n.3, p.295-311, Sept. 1985 [doi>10.1145/5505.5507]
• 26: Mary Inaba , Naoki Katoh , Hiroshi Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract), Proceedings of the tenth annual symposium on Computational geometry, p.332-339, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178042]
• 27: A. Kalai and S. Vempala. Efficient algorithms for the online decision problem, In Proc. 16 COLT, 2003.
• 28: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 29: Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward Efficient Agnostic Learning, Machine Learning, v.17 n.2-3, p.115-141, Nov./Dec. 1994 [doi>10.1007/BF00993468]
• 30: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
• 31: Amit Kumar , Yogish Sabharwal , Sandeep Sen, A Simple Linear Time (1+ ") -Approximation Algorithm for k-Means Clustering in Any Dimensions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.454-462, October 17-19, 2004 [doi>10.1109/FOCS.2004.7]
• 32: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
• 33: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 34: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 35: J. McCabe. On serial files with relocatable records, Operations Research, 13:609--618, 1965.
• 36: B. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary, In Proc. 17th COLT, 2004.
• 37: Kurt Mehlhorn, Sorting and Searching (Eatcs Monographs on Theoretical Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 1984
• 38: Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
• 39: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 40: Rafail Ostrovsky , Yuval Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM (JACM), v.49 n.2, p.139-156, March 2002 [doi>10.1145/506147.506149]
• 41: Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
• 42: Albers S. and M. Mitzenmacher. Average case analyses of list update algorithms, Algorithmica, 21:312--329, 1998.
• 43: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 44: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 45: F. Takens. Detecting strange attractors in turbulence, Dynamical Systems and Turbulence, 898:366--381, 1981.
• 46: Mikkel Thorup, Quick k-Median, k-Center, and Facility Location for Sparse Graphs, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.249-260, July 08-12, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning