[HN Gopher] Beyond Smoothed Analysis: Analyzing the Simplex Meth...
       ___________________________________________________________________
        
       Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
        
       Author : sebg
       Score  : 35 points
       Date   : 2025-10-27 16:13 UTC (5 days ago)
        
 (HTM) web link (arxiv.org)
 (TXT) w3m dump (arxiv.org)
        
       | ogogmad wrote:
       | Cool paper!
       | 
       | [EDIT: The following is my own clumsy mistake] Minor note: The
       | definition of "mean width" of a polyhedron P in the paper is not
       | translation invariant, and that's confusing. In other words, the
       | mean width of a polyhedron P can differ from that of P+x := {p+x
       | | p [?] P} where x is some vector. Is that intended? It doesn't
       | agree with how the word "width" is normally used. I would call it
       | a "mean furthest projection". Or maybe "mean peak projection" or
       | "mean shadow"?
        
         | yorwba wrote:
         | I assume you're talking about this?
         | 
         | " _Half the mean width of a polyhedron P is equal to the
         | expected value of_                 max th^T x       subject to
         | x [?] P,
         | 
         | _where th [?] S^(d-1) is uniformly random distributed with
         | respect to the Haar measure on the unit sphere._ "
         | 
         | The expression _max th^T x_ is not translation-invariant: if
         | you replace _x_ with _x + [?]x_ , you get _(max th^T x) + th^T
         | [?]x_. But the expectation of _th^T [?]x_ is 0 so the
         | expectation of the maximum is translation-invariant again.
        
           | ogogmad wrote:
           | I think you're right. Yes, I think it _is_ translation
           | invariant. Ouch, apologies.
        
       ___________________________________________________________________
       (page generated 2025-11-01 23:01 UTC)