<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-21T22:00:22Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/8596" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/8596</identifier><datestamp>2017-03-21T21:06:45Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="c798fed7-7b64-440e-84ce-948257bca865" confidence="600">Kushagra, Shrinu</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2014-08-01T19:22:52Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2014-08-01T19:22:52Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2014-08-01</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2014</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/8596</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Various machine learning algorithms like Neural Networks, Linear Regression, Feature&#xd;
Learning etc. are being employed successfully in a wide variety of applications like computer vision, speech recognition, bioinformatics etc. However, many of these learning algorithms have been shown to be NP-Hard. Furthermore some of these algorithms are even hard NP-Hard approximate. The intuition behind the success of these algorithms is that in practical applications the input data is not `worst-case&amp;apos; and has certain `nice&amp;apos; properties. In this thesis, we take a few small steps towards bridging the apparent gap between what is predicted by theory and what is actually happening in practice. We consider two different niceness assumptions.&#xd;
The notion of Metric Distortion is fairly common for dimensionality reduction techniques.&#xd;
The goal is to obtain reduction techniques such that the distortion is small for all&#xd;
pairs of points. We show via an example that Metric Distortion is not good at modeling&#xd;
dimensionality reduction techniques which would perform quite well in practice. We introduce Retaining Distances, a probabilistic notion for modeling dimensionality reduction techniques which preserve most of the inter-point distances. Retaining Distance can viewed as a relaxation of Metric Distortion. We prove that common techniques like PCA can be modeled by our notion.&#xd;
Another niceness assumption inherent in many machine learning algorithms is that&#xd;
`close points tend to have same labels&amp;apos;. A notion of Probabilistic Lipschitzness (PL) was&#xd;
introduced by Urner et. al [28] to capture this intuition. In this work, we propose a new&#xd;
definition of PL. We show that both these definitions are orthogonal to one another, in the&#xd;
sense that, one is not implied by (or a relaxation of) the other. We give sample complexity&#xd;
upper bounds for Nearest Neighbor under this new definition.&#xd;
The crux of the thesis is combining the two notions to show that information (niceness)&#xd;
is preserved across dimensions. We prove that if we have PL in a higher dimension and any dimensionality-reduction technique retains distances then we have PL in reduced dimension as well. That is, a distance retaining reduction preserves PL. In other words, the niceness properties that existed in the original dimension also exist in reduced dimension space.&#xd;
Towards the end, we validate both our notions experimentally. We show how our notion&#xd;
of retaining distance maybe employed in practice to capture the `usefulness&amp;apos; of a reduction technique. We also perform experiments to show how the two notions of PL compare in practice.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Probabilistic Lipschitzness</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Retaining Distance</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Dimensionality Reduction</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">PCA</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Niceness assumptions for Learning Algorithms</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>