International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong

 

Invited Speakers

Young PhD Forum


Beyond Characteristic Function Method to Get Exponential Concentration Bound

Zhide Wei

Peking University

Abstract:
By combining tail bounds with Markov Inequality, we show an exponential concentration bound for random variables whose density function is the Fourier transform of an analytic function, which traditional characteristic function bound can’t handle. As an application, we show that kernel methods with a shift invariant and analytic kernel can be compressed to polylog(n) dimension within 1+ε multiplicative error, indicating a near linear time approximate algorithm for kernel method.

Bio:
Zhide Wei received the B.S. degree in Peking University in 2021. He is currently working toward the Ph.D. degree in theoretical computer science with advisor Kuan Cheng in Center on Frontiers of Computing Studies , Peking University. His research interests include quantum circuit, coding and approximation algorithms.