Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

Details Efficient Regression in Metric Spaces via Approximate Lipschitz Extension Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

2011-11-18

arxiv.org/abs/1111.4470v1

Computer Science

Learning

Scientific paper

We present a framework for performing efficient regression in general metric spaces. Roughly speaking, our regressor predicts the value at a new point by computing a Lipschitz extension -- the smoothest function consistent with the observed data -- while performing an optimized structural risk minimization to avoid overfitting. The offline (learning) and online (inference) stages can be solved by convex programming, but this naive approach has runtime complexity O(n^3), which is prohibitive for large datasets. We design instead an algorithm that is fast when the the doubling dimension, which measures the "intrinsic" dimensionality of the metric space, is low. We use the doubling dimension multiple times; first, on the statistical front, to bound fat-shattering dimension of the class of Lipschitz functions (and obtain risk bounds); and second, on the computational front, to quickly compute a hypothesis function and a prediction based on Lipschitz extension. Our resulting regressor is both asymptotically strongly consistent and comes with finite-sample risk bounds, while making minimal structural and noise assumptions.

Affiliated with

Also associated with

No associations

Rating

Efficient Regression in Metric Spaces via Approximate Lipschitz Extension does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Regression in Metric Spaces via Approximate Lipschitz Extension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Regression in Metric Spaces via Approximate Lipschitz Extension will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-513994