Learning With Kernels: A Local Rademacher Complexity-Based Analysis With Application to Graph Kernels.

Area of Science:

• Machine Learning
• Graph Theory
• Statistical Learning Theory

Background:

• Selecting appropriate kernels and hyperparameters is crucial for kernel methods, especially with complex structured data like graphs.
• Existing resampling techniques for kernel selection are often computationally expensive.
• The relationship between different graph kernels and their learning properties remains unclear, necessitating exhaustive search.

Purpose of the Study:

• To develop an efficient method for bounding the global Rademacher complexity (RC) of kernel-induced hypothesis spaces.
• To demonstrate the utility of RC in assessing the accuracy and expressivity of various graph kernels.
• To provide a more efficient alternative to exhaustive search for graph kernel selection.

Main Methods:

• Introduced a novel approach to efficiently bound the global Rademacher complexity (RC), addressing its NP-Hard exact computation.
• Utilized Rademacher complexity measures (RC and LRC) to analyze kernel properties and generalization error.
• Conducted experiments on real-world graph datasets to validate the proposed method.

Main Results:

• Successfully developed an efficient bounding method for global Rademacher complexity (RC).
• Demonstrated that RC can effectively estimate the accuracy and expressivity of different graph kernels.
• Experimental results on diverse graph datasets confirm the efficacy of the approach.

Conclusions:

• The proposed efficient RC bounding method offers a viable alternative to time-consuming resampling and exhaustive search for graph kernels.
• Rademacher complexity provides a powerful theoretical tool for understanding and comparing graph kernels.
• This work facilitates more informed and efficient selection of graph kernels for machine learning tasks.