<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <!-- The above 3 meta tags *must* come first in the head; any other head content must come *after* these tags -->

  <meta name="description" content="Holden Lee's Research Notebook">
  <meta name="author" content="Holden Lee">
    
  <title>Convexity</title>

  <!-- Bootstrap core CSS -->
  <link href="../../../../bootstrap/css/bootstrap.min.css" rel="stylesheet">

  <!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
  <!-- <link href="../../assets/css/ie10-viewport-bug-workaround.css" rel="stylesheet"> -->

  <!-- Custom styles for this template -->
  <link href="../../../../css/blog.css" rel="stylesheet">
  <link href="../../../../css/default.css" rel="stylesheet">

  <!-- Extension : Footnotes -->
  <link href="../../../../footnotes/css/footnotes.css" rel="stylesheet">

  <!-- Extension : InlineDisqussions @ https://github.com/tsi/inlineDisqussions -->
  

  <!-- Extension : Collapsible lists @ http://code.stephenmorley.org/javascript/collapsible-lists/-->
  <link href="../../../../collapsible_lists/css/collapsible.css" rel="stylesheet">
  <script type="text/javascript" src="../../../../collapsible_lists/js/CollapsibleLists.js"></script>

</head>

<body>

<!-- Navigation bar. navbar-inverse is black, navbar-default is white.-->
<!-- To make a button active (pressed), use <li class="active"> -->
<div id="header">
  <nav class="navbar navbar-inverse navbar-fixed-top">
    <div class="container">
      <div class="navbar-header">
        <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false" aria-controls="navbar">
          <span class="sr-only">Toggle navigation</span>
          <span class="icon-bar"></span>
          <span class="icon-bar"></span>
          <span class="icon-bar"></span>
        </button>
        <a class="navbar-brand" href="../../../../">Notebook</a>
      </div>
      <div id="navbar" class="collapse navbar-collapse">
        <ul class="nav navbar-nav">
          <li><a href="../../../../">Home</a></li>
          <li><a href="../../../../sitemap.html">Sitemap</a></li>
<!-- TODO: Distinguish between PAPERS, RESEARCH QUESTIONS, BOOKS -->
<!-- TODO: make this part a for loop over main pages -->
        </ul>
      </div><!--/.nav-collapse -->
    </div>
  </nav>
</div>
<!-- Content -->
<!--div id="content">
  <h1>Mental Wilderness</h1>-->



<div class="container">
  <div id="content">
    <div class="page header">
      <h1>Convexity</h1>
    </div>
    <div class="info">
      
       
        <p>Posted: 2016-04-23 
          , Modified: 2016-04-23 
	</p>
      
       <p>Tags: <a href="../../../../tags/convex%20optimization.html">convex optimization</a></p> 
    </div>
    
  </div>
  <!--/div-->

  <div class="toc"> <ul>
 <li><a href="#questions">Questions</a></li>
 <li><a href="#answers">Answers</a></li>
 </ul> </div>

  <div class="blog-main">
    <h2 id="questions">Questions</h2>
<ul>
<li>Define strongly convex. What estimates can you make using strong convexity? Why is it useful?</li>
<li>Define smoothness. What does it give you?</li>
<li>Define condition number for sets and matrices. What is the relationship? What do bounds on <span class="math inline">\(\nb^2\)</span> give on condition number?</li>
</ul>
<h2 id="answers">Answers</h2>
<ul>
<li>Strongly convex means <span class="math display">\[ f(y) \ge f(x) + \nb f(x)^T (y-x) + \fc m2 \ve{y-x}_2^2. \]</span> For twice-differentiable functions, this is equivalent to <span class="math inline">\(\nb^2 f\succeq mI\)</span>. Strong convexity lower-bounds suboptimality: if the gradient is small, then you are not too far from the minimum, because the gradient changes fast. (Ex. for <span class="math inline">\(c+dx+\fc m2x^2\)</span>, the minimum is at <span class="math inline">\(-\fc dm = -\rc m \nb f\)</span>.) The following inequality hold: (bound the optimal value in terms of the gradient, and bound the distance in terms of the gradient.
<span class="math display">\[\begin{align}
p^* &amp;\ge f(x) - \rc{2m}\ve{\nb f(x)}_2^2\\
\ve{x-x^*}_2 &amp; \le \fc 2m \ve{\nb f}_2^2.
\end{align}\]</span></li>
<li>Smoothness means <span class="math display">\[ f(y) \le f(x) + \nb f(x)^T (y-x) + \fc M2 \ve{y-x}_2^2. \]</span> For twice-differentiable functions, this is equivalent to <span class="math inline">\(\nb^2 f\preceq MI\)</span>. Smoothness upper-bounds suboptimality, and ensures that step sizes don't overshoot the minimum (much)
<span class="math display">\[\begin{align}
p^* &amp;\le f(x) - \rc{2M}\ve{\nb f}_2^2.
\end{align}\]</span></li>
<li>The condition number of a convex body <span class="math inline">\(C\)</span> is (<span class="math inline">\(W_{\max},W_{\min}\)</span> are max and min width) <span class="math display">\[ \text{cond} (C) = \fc{W_{\max}^2}{W_{\min}^2}.\]</span> For an ellipsoid defined by <span class="math inline">\(x^TA^{-1}x\le 1\)</span>, <span class="math display">\[ \text{cond} (\mathcal E) = \fc{\la_{\max}(A)}{\la_{\min}(A)} = \ka(A).\]</span> Strong convexity and smoothness together bound the condition number of sublevel sets <span class="math inline">\(C_\al =\set{x}{f(x)\le \al}\)</span>. We have for <span class="math inline">\(p^*&lt;\al\)</span>, <span class="math display">\[B_{\sfc{2(\al-p^*)}{M}}\subeq C_\al \subeq B_{\sfc{2(\al-p^*)}{m}},\]</span> <span class="math inline">\(\text{cond}(C_\al)\le \fc{M}{m}\)</span>. Moreover, <span class="math inline">\(\lim_{\al\to 0^+} \text{cond}(C_\al) = \ka (\nb f(x^*))\)</span>.</li>
</ul>

  </div>

    

    <!-- Extension : Sharing buttons @ www.sharethis.com -->
    <span class="st_facebook_large" displayText="Facebook"></span>
    <span class="st_twitter_large" displayText="Tweet"></span>
    <span class="st_googleplus_large" displayText="Google +"></span>
    <span class="st_reddit_large" displayText="Reddit"></span>
    <span class="st__large" displayText></span>

    <div id="disqus_thread"></div>
    


  
    <script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script>
  </div>
  
</div>


<!-- Footer -->
<div id="footer">
  <div class="container">
    Built with
    <a href="http://jaspervdj.be/hakyll">Hakyll</a> 
    using 
    <a href="http://www.getbootstrap.com">Bootstrap</a>, 
    <a href="http://www.disqus.com">Disqus</a>,
    <a href="http://ignorethecode.net/blog/2010/04/20/footnotes/">Footnotes.js</a>,
    <a href="http://highlightjs.org/">Highlight.js</a>, 
    <a href="http://www.mathjax.org">MathJax</a>, 
    and <a href="http://www.sharethis.com">ShareThis</a>.
  </div>
</div>
</body>

</html>

<!-- SCRIPTS -->
<!-- jQuery-->
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script>
<script src="http://code.jquery.com/jquery-1.10.1.min.js"></script>

<script src="../../../../bootstrap/js/bootstrap.min.js"></script>

<!-- Extension : Highlight.js @ https://highlightjs.org/ -->
<!-- Syntax highlighting tomorrow-night-bright, agate-->
<link rel="stylesheet" href="../../../../highlight/css/tomorrow-night-bright.css">
<script src="../../../../highlight/js/highlight.pack.js"></script>
<script>hljs.initHighlightingOnLoad();</script>

<!-- Extension : MathJax @ https://docs.mathjax.org/en/v2.5-latest/tex.html -->
<!-- MathJax/config/local/local.js contains macros. Need to provide entire URL-->
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML,http://holdenlee.github.io/notebook/MathJax/config/local/local"></script>

<!-- Extension : Footnotes @ http://ignorethecode.net/blog/2010/04/20/footnotes/ -->
<script src="../../../../footnotes/js/footnotes.js"></script>

<!-- Extension : Disqus @ http://disqus.com -->
<!-- Extension : InlineDisqussions @ https://github.com/tsi/inlineDisqussions -->

<script src="../../../../disqus/js/disqus.js"></script>



<!-- Extension : Google Analytics -->
<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-73261814-1', 'auto');
  ga('send', 'pageview');

</script>

