Timezone: »
The weighted k-nearest neighbors algorithm is one of the most fundamental non-parametric methods in pattern recognition and machine learning. The question of setting the optimal number of neighbors as well as the optimal weights has received much attention throughout the years, nevertheless this problem seems to have remained unsettled. In this paper we offer a simple approach to locally weighted regression/classification, where we make the bias-variance tradeoff explicit. Our formulation enables us to phrase a notion of optimal weights, and to efficiently find these weights as well as the optimal number of neighbors efficiently and adaptively, for each data point whose value we wish to estimate. The applicability of our approach is demonstrated on several datasets, showing superior performance over standard locally weighted methods.
Author Information
Oren Anava (Technion)
Kfir Y. Levy (Technion)
More from the Same Authors
-
2021 Poster: Faster Neural Network Training with Approximate Tensor Operations »
Menachem Adelman · Kfir Levy · Ido Hakimi · Mark Silberstein -
2021 Poster: STORM+: Fully Adaptive SGD with Recursive Momentum for Nonconvex Optimization »
Kfir Levy · Ali Kavis · Volkan Cevher -
2020 Poster: Adaptive Sampling for Stochastic Risk-Averse Learning »
Sebastian Curi · Kfir Y. Levy · Stefanie Jegelka · Andreas Krause -
2019 Poster: A Domain Agnostic Measure for Monitoring and Evaluating GANs »
Paulina Grnarova · Kfir Y. Levy · Aurelien Lucchi · Nathanael Perraudin · Ian Goodfellow · Thomas Hofmann · Andreas Krause -
2019 Poster: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2019 Spotlight: UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization »
Ali Kavis · Kfir Y. Levy · Francis Bach · Volkan Cevher -
2018 Poster: Online Adaptive Methods, Universality and Acceleration »
Kfir Y. Levy · Alp Yurtsever · Volkan Cevher -
2017 Workshop: NIPS 2017 Time Series Workshop »
Vitaly Kuznetsov · Oren Anava · Scott Yang · Azadeh Khaleghi -
2017 Poster: Online to Offline Conversions, Universality and Adaptive Minibatch Sizes »
Kfir Levy -
2017 Poster: Non-monotone Continuous DR-submodular Maximization: Structure and Algorithms »
Yatao Bian · Kfir Levy · Andreas Krause · Joachim M Buhmann -
2016 Workshop: Time Series Workshop »
Oren Anava · Marco Cuturi · Azadeh Khaleghi · Vitaly Kuznetsov · Sasha Rakhlin -
2016 Poster: Multi-armed Bandits: Competing with Optimal Sequences »
Zohar Karnin · Oren Anava -
2015 Poster: Online Learning for Adversaries with Memory: Price of Past Mistakes »
Oren Anava · Elad Hazan · Shie Mannor -
2015 Poster: Fast Rates for Exp-concave Empirical Risk Minimization »
Tomer Koren · Kfir Y. Levy -
2015 Poster: Beyond Convexity: Stochastic Quasi-Convex Optimization »
Elad Hazan · Kfir Y. Levy · Shai Shalev-Shwartz -
2014 Poster: Bandit Convex Optimization: Towards Tight Bounds »
Elad Hazan · Kfir Y. Levy