<div dir="ltr"><div>FYI, the theory lunch this week (Wednesday) might be of interest to you. Please see the message below.</div><div> </div><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Nicolas Resch</b> <span dir="ltr"><<a href="mailto:nresch@cs.cmu.edu">nresch@cs.cmu.edu</a>></span><br>Date: Mon, Oct 9, 2017 at 8:50 AM<br>Subject: This Week at Theory Lunch: Ellen Vitercik<br>To: <a href="mailto:theory-announce@cs.cmu.edu">theory-announce@cs.cmu.edu</a><br><br><br><div style="word-wrap:break-word">Hi all,<div><br></div><div>Please join us Wednesday at noon in GHC 6115 for a talk by Ellen Vitercik, where lunch will be provided. A video recording of the talk will be available on the <a href="https://www.youtube.com/channel/UCWFp4UWNiOv71j0sPbdNiqw" target="_blank">CMU Youtube Theory channel</a>. </div><div><br></div><div><div style="margin:0px;line-height:normal"><span style="font-kerning:none"><b>Location/Time:</b> Wednesday, </span><span>October 11</span><span style="font-kerning:none">, 12-1pm </span></div><div style="margin:0px;line-height:normal"><span style="font-kerning:none"><b>Speaker: </b></span><span>Ellen Vitercik</span></div><div style="margin:0px;line-height:normal"><span style="font-kerning:none"><b>Title:</b> </span>Differentially private algorithm and auction configuration</div><div style="margin:0px;line-height:normal"><span style="font-kerning:none"><b>Abstract: </b></span></div><div style="margin:0px;line-height:normal"><span style="font-kerning:none"><b><br></b></span></div><div style="margin:0px;line-height:normal"><span style="font-kerning:none">Algorithm configuration is an important aspect of modern data science and algorithm design. Algorithms regularly depend on tunable parameters which have a substantial effect on run-time and solution quality. Researchers have developed machine learning techniques for automated parameter tuning which use a training set of problem instances to determine a configuration with high expected performance over future instances. This line of work has inspired breakthroughs in diverse fields including combinatorial auctions, scientific computing, vehicle routing, and SAT. The resulting configuration depends on the training set, implying that without proper precautions, it may leak sensitive information about problem instances contained therein.<br><br>In this work, we address this problem by showing that a natural adaptation of the exponential mechanism provides strong privacy and utility guarantees for a wide range of algorithm configuration problems. We uncover a structural property shared among many problems which ensures this algorithm’s success: these problems reduce to maximizing piecewise L-Lipschitz functions. We call upon techniques from high-dimensional geometry to efficiently implement this algorithm when the algorithm parameter space is multi-dimensional. We apply our differentially private algorithm to many configuration problems where privacy preservation is essential, such as integer quadratic programming and greedy algorithm configuration. We also show that our differentially private algorithm can be used to design auctions and pricing mechanisms based on consumer data, thus further exhibiting the algorithm’s broad applicability.</span></div><div style="margin:0px;line-height:normal"><span style="font-kerning:none"><b><br></b></span></div><div style="margin:0px;line-height:normal"><span style="font-kerning:none">See you there!</span></div><div style="margin:0px;line-height:normal"><span style="font-kerning:none">Ellis and Nic</span></div></div></div></div><br></div>