<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Mallory;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
h1
{mso-style-priority:9;
mso-style-link:"Heading 1 Char";
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:24.0pt;
font-family:"Calibri",sans-serif;
font-weight:bold;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.Heading1Char
{mso-style-name:"Heading 1 Char";
mso-style-priority:9;
mso-style-link:"Heading 1";
font-family:"Calibri",sans-serif;
font-weight:bold;}
span.odd
{mso-style-name:odd;}
span.date-display-single
{mso-style-name:date-display-single;}
span.date-display-range
{mso-style-name:date-display-range;}
span.date-display-start
{mso-style-name:date-display-start;}
span.date-display-end
{mso-style-name:date-display-end;}
span.fn
{mso-style-name:fn;}
span.map-icon
{mso-style-name:map-icon;}
span.locality
{mso-style-name:locality;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1027" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72" style='word-wrap:break-word'><div class=WordSection1><p class=MsoNormal style='background:white'><span style='color:black'><a href="https://statistics.yale.edu/" title="Department of Statistics and Data Science
"><span style='font-size:22.0pt;font-family:"Arial",sans-serif;color:#286DC0;text-decoration:none'><img border=0 width=150 height=49 style='width:1.5625in;height:.5104in' id=logo src="cid:image001.jpg@01D9469F.BBF17C10" alt="Department of Statistics and Data Science
"></span></a></span><span style='font-family:"Arial",sans-serif;color:black'> <a href="https://statistics.yale.edu/" title=Home><b><span style='font-size:22.0pt;color:#286DC0'>Department of Statistics and Data Science </span></b></a></span><b><i><u><span style='font-size:22.0pt;font-family:"Arial",sans-serif;color:#286DC0'> <o:p></o:p></span></u></i></b></p><h1 style='mso-margin-top-alt:.1in;margin-right:0in;margin-bottom:0in;margin-left:0in;background:white'><span style='font-size:14.0pt;font-family:"Arial",sans-serif;color:black'><a href="https://statistics.yale.edu/seminars/ilias-zadik"><span style='color:black;background:white;text-decoration:none'>Ilias Zadik</span></a></span><span style='font-size:14.0pt;font-family:"Arial",sans-serif;color:#222222'>, </span><span class=odd><span style='font-size:14.0pt;font-family:"Arial",sans-serif;color:#222222'>MIT</span></span><span style='font-size:14.0pt;font-family:"Arial",sans-serif;color:#222222;font-weight:normal'><o:p></o:p></span></h1><p class=MsoNormal style='background:white'><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
<v:stroke joinstyle="miter" />
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0" />
<v:f eqn="sum @0 1 0" />
<v:f eqn="sum 0 0 @1" />
<v:f eqn="prod @2 1 2" />
<v:f eqn="prod @3 21600 pixelWidth" />
<v:f eqn="prod @3 21600 pixelHeight" />
<v:f eqn="sum @0 0 1" />
<v:f eqn="prod @6 1 2" />
<v:f eqn="prod @7 21600 pixelWidth" />
<v:f eqn="sum @8 21600 0" />
<v:f eqn="prod @7 21600 pixelHeight" />
<v:f eqn="sum @10 21600 0" />
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" />
<o:lock v:ext="edit" aspectratio="t" />
</v:shapetype><v:shape id="Picture_x0020_2" o:spid="_x0000_s1026" type="#_x0000_t75" style='position:absolute;margin-left:0;margin-top:.4pt;width:102.75pt;height:123.3pt;z-index:251658240;visibility:visible;mso-wrap-style:square;mso-width-percent:0;mso-height-percent:0;mso-wrap-distance-left:9pt;mso-wrap-distance-top:0;mso-wrap-distance-right:9pt;mso-wrap-distance-bottom:0;mso-position-horizontal:absolute;mso-position-horizontal-relative:text;mso-position-vertical:absolute;mso-position-vertical-relative:text;mso-width-percent:0;mso-height-percent:0;mso-width-relative:page;mso-height-relative:page'>
<v:imagedata src="cid:image002.jpg@01D9469F.BBF17C10" o:title="" />
<w:wrap type="square"/>
</v:shape><![endif]--><![if !vml]><img width=137 height=164 style='width:1.427in;height:1.7083in' src="cid:image003.jpg@01D946BA.7C66E600" align=left hspace=12 v:shapes="Picture_x0020_2"><![endif]><span class=date-display-single><span style='font-size:13.5pt;font-family:Mallory;color:black'>Date: Thursday, February 23, 2023</span></span><span class=date-display-single><span style='font-size:13.5pt;font-family:Mallory'><o:p></o:p></span></span></p><p class=MsoNormal style='background:white'><span class=date-display-single><span style='font-size:13.5pt;font-family:Mallory;color:black'>Time: </span></span><span class=date-display-start><span style='font-size:13.5pt;font-family:Mallory;color:black'>10:30AM</span></span><span class=date-display-range><span style='font-size:13.5pt;font-family:Mallory;color:black'> to </span></span><span class=date-display-end><span style='font-size:13.5pt;font-family:Mallory;color:black'>11:30AM</span></span><span style='font-size:13.5pt;font-family:Mallory'><o:p></o:p></span></p><p class=MsoNormal style='background:white'><span class=fn><span style='font-size:13.0pt;font-family:Mallory;color:black'>Dunham Lab. Room 220</span></span><span class=map-icon><span style='font-size:12.0pt;font-family:Mallory;color:black;letter-spacing:.6pt'> </span></span><span style='font-size:13.0pt;font-family:Mallory'><o:p></o:p></span></p><p class=MsoNormal style='background:white'><span style='font-size:13.0pt;font-family:Mallory;color:black'>10 Hillhouse Avenue, 2nd Floor</span><span style='font-size:13.0pt;font-family:Mallory'><o:p></o:p></span></p><p class=MsoNormal style='background:white'><span class=locality><span style='font-size:13.0pt;font-family:Mallory;color:black'>New Haven</span></span><span style='font-size:13.0pt;font-family:Mallory'><o:p></o:p></span></p><p class=MsoNormal style='background:white'><span style='font-size:13.0pt;font-family:Mallory;color:#222222'><a href="https://iliaszadik.github.io/"><span style='font-size:12.0pt;color:#003C76'>Website</span></a><o:p></o:p></span></p><p class=MsoNormal style='background:white'><b><span style='font-size:13.0pt;font-family:Mallory;color:#222222'><o:p> </o:p></span></b></p><p class=MsoNormal style='background:white'><b><span style='font-size:13.0pt;font-family:Mallory;color:#222222'><o:p> </o:p></span></b></p><p class=MsoNormal style='background:white'><b><span style='font-size:15.0pt;font-family:Mallory;color:#222222'>Title: The price of computational efficiency in high-dimensional estimation<o:p></o:p></span></b></p><p class=MsoNormal style='background:white'><b><span style='font-size:13.0pt;font-family:Mallory;color:#222222'><o:p> </o:p></span></b></p><p class=MsoNormal style='background:white'><b><span style='font-size:13.0pt;font-family:Mallory;color:#222222'>Information and Abstract: <o:p></o:p></span></b></p><p style='mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:0in;background:white;box-sizing: inherit'><span style='font-size:13.0pt;font-family:Mallory;color:#222222'>In recent years we have experienced a remarkable growth on the number and size of available datasets. Such growth has led to the intense and challenging pursuit of estimators which are provably both computationally efficient and statistically accurate. Notably, the analysis of polynomial-time estimators has revealed intriguing phenomena in several high dimensional estimation tasks, such as their apparent failure of such estimators to reach the optimal statistical guarantees achieved among all estimators (that is the presence of a non-trivial “computational-statistical trade-off”). <o:p></o:p></span></p><p style='mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:0in;background:white;box-sizing: inherit'><span style='font-size:13.0pt;font-family:Mallory;color:#222222'>In this talk, I will present new such algorithmic results for the well-studied planted clique model and for the fundamental sparse regression model. For planted clique, we reveal the surprising severe failure of the Metropolis process to work in polynomial-time, even when simple degree heuristics succeed. In particular, our result resolved a well-known 30-years old open problem on the performance of the Metropolis process for the model, posed by Jerrum in 1992. For sparse regression, we show the failure of large families of polynomial-time estimators, such as MCMC and low-degree polynomial methods, to improve upon the best-known polynomial-time regression methods. As an outcome, our work offers rigorous evidence that popular regression methods such as LASSO are optimally balancing their computational and statistical recourses.<o:p></o:p></span></p><p class=MsoNormal><span style='font-family:"Arial",sans-serif'><o:p> </o:p></span></p><p class=MsoNormal><b><i><o:p> </o:p></i></b></p><p class=MsoNormal><span style='font-size:12.0pt;font-family:"Arial",sans-serif;color:black'>For more details and upcoming events visit our website at <a href="http://statistics.yale.edu/"><span style='color:black'>http://statistics.yale.edu/</span></a></span><o:p></o:p></p><p class=MsoNormal><span style='font-family:"Arial",sans-serif'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:18.0pt;font-family:"Arial",sans-serif'>Department of Statistics and Data Science<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial",sans-serif;color:black'>Yale University<br>24 Hillhouse Avenue<br>New Haven, CT 06511<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial",sans-serif;color:black'>t 203.432.0666<br>f 203.432.0633<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>