skip to main content

Title: Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
; ;
Ranzato, M.; Beygelzimer, A.; Dauphin, Y.; Liang, P.S.; Wortman Vaughan, J.
Award ID(s):
Publication Date:
Journal Name:
Advances in neural information processing systems
Page Range or eLocation-ID:
9317 - 9329
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We introduce and investigate $d$-convex union representable complexes: the simplicial complexes that arise as the nerve of a finite collection of convex open sets in ${\mathbb{R}}^d$ whose union is also convex. Chen, Frick, and Shiu recently proved that such complexes are collapsible and asked if all collapsible complexes are convex union representable. We disprove this by showing that there exist shellable and collapsible complexes that are not convex union representable; there also exist non-evasive complexes that are not convex union representable. In the process we establish several necessary conditions for a complex to be convex union representable such as that such a complex $\Delta $ collapses onto the star of any face of $\Delta $, that the Alexander dual of $\Delta $ must also be collapsible, and that if $k$ facets of $\Delta $ contain all free faces of $\Delta $, then $\Delta $ is $(k-1)$-representable. We also discuss some sufficient conditions for a complex to be convex union representable. The notion of convex union representability is intimately related to the study of convex neural codes. In particular, our results provide new families of examples of non-convex neural codes.
  2. We prove that the torsion of any closed space curve which bounds a simply connected locally convex surface vanishes at least 4 times. This answers a question of Rosenberg related to a problem of Yau on characterizing the boundary of positively curved disks in Euclidean space. Furthermore, our result generalizes the 4 vertex theorem of Sedykh for convex space curves, and thus constitutes a far reaching extension of the classical 4 vertex theorem. The proof involves studying the arrangement of convex caps in a locally convex surface, and yields a Bose type formula for these objects.