A technique for upper bounding the spectral norm with applications to learning

ABSTRACT

We present a general technique to upper bound the spectral norm of an arbitrary function. At the heart of our technique is a theorem which shows how to obtain an upper bound on the spectral norm of a decision tree given the spectral norms of the functions in the nodes of this tree. The theorem applies to trees whose nodes may compute any boolean functions. Applications are to the design of efficient learning algorithms and the construction of small depth threshold circuits (or neural nets). In particular, we present polynomial time algorithms for learning O(log n) clause DNF formulas and various classes of decision trees, all under the uniform distribution with membership queries.

REFERENCES

• Be: M. Bellare, THE SPECTRAL NORM OF FINITE FUNCTIONS, Massachusetts Institute of Technology, Cambridge, MA, 1991
• BR: Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
• Br: J. BaUCK. Harmonic Analysis of Polynomial Threshold Functions. SIAM J. Discrete Math. 3(2), 168-177 (1990).
• BS: J. BgUCK AND R. SMOLr. NSKY. Polynomial Threshold Functions, AC~ Functions, and Spectral Norms. Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Sczence, IEEE (1990).
• FJS: M. FUI~ST, J. JACKSON AND S. SMITH. Learning AC~ Functions Sampled under Mutually Independent Distributions. Manuscript (October 1990).
• HMPST: A. HAJNAL, W. MAASS, P. PUDLAK, M. SZEGEDY AND G. TURAN. Threshold Circuits of Bounded Depth. Proceedings of the ~8th Annual IEEE Symposium ou the Foundations of Computer Science, IEEE (1987).
• KKL: J. KAHN, G. KALAI AND N. LINIAL. The Influence of Variables on Boolean Functions. Proceedings of the ~9th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1988).
• KM: Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103466]
• LMN: N. LINIAL, Y. MANSOUR AND N. NISAN. Constant Depth Circuits, Fourier Transform, and Learnability. Proceedings of the 30th Annual IEEE Symposium on the Foundatwns of Computer Science, IEEE (1989).
• SB: K. SIu AND J. BaUCK. On the Power of Threshold Circuits with Small Weights. Manuscript.
• Va: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Ve: K. VERBEURGT. Learning DNF under the uniform distribution in polynomial time. Proceedings of the Second Annual Workshop on Computational Learning Theory, Morgan Kaufmann Publishers Inc. (1989).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Theory, Verification