Timezone: »

 
Poster
Distributionally robust weighted k-nearest neighbors
Shixiang Zhu · Liyan Xie · Minghe Zhang · Rui Gao · Yao Xie

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #235
in Poster Session 6 »

Learning a robust classifier from a few samples remains a key challenge in machine learning. A major thrust of research has been focused on developing k-nearest neighbor (k-NN) based algorithms combined with metric learning that captures similarities between samples. When the samples are limited, robustness is especially crucial to ensure the generalization capability of the classifier. In this paper, we study a minimax distributionally robust formulation of weighted k-nearest neighbors, which aims to find the optimal weighted k-NN classifiers that hedge against feature uncertainties. We develop an algorithm, Dr.k-NN, that efficiently solves this functional optimization problem and features in assigning minimax optimal weights to training samples when performing classification. These weights are class-dependent, and are determined by the similarities of sample features under the least favorable scenarios. When the size of the uncertainty set is properly tuned, the robust classifier has a smaller Lipschitz norm than the vanilla k-NN, and thus improves the generalization capability. We also couple our framework with neural-network-based feature embedding. We demonstrate the competitive performance of our algorithm compared to the state-of-the-art in the few-training-sample setting with various real-data experiments.

Author Information

Shixiang Zhu (Carnegie Mellon University)
Liyan Xie (The Chinese University of Hong Kong, Shenzhen)
Minghe Zhang (Georgia Institute of Technology)
Rui Gao (University of Texas at Austin)
Yao Xie (Georgia Institute of Technology)

Yao Xie is an Assistant Professor and Harold R. and Mary Anne Nash Early Career Professor in the H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, which she joined in 2013. She received her Ph.D. in Electrical Engineering (minor in Mathematics) from Stanford University in 2011, M.Sc. in Electrical and Computer Engineering from the University of Florida, and B.Sc. in Electrical Engineering and Computer Science from University of Science and Technology of China (USTC) . From 2012 to 2013, she was a Research Scientist at Duke University. Her research areas include statistics, signal processing, and machine learning, in providing theoretical foundation as well as developing computationally efficient and statistically powerful algorithms for big data in various applications such as sensor networks, imaging, and crime data analysis. She received the National Science Foundation CAREER Award in 2017 and her crime data analytics project received the Smart 50 Award at the Smart Cities Connect Conferences and Expo in 2018.

More from the Same Authors