More Like this

1. Convex Union Representability and Convex Codes

   https://doi.org/10.1093/imrn/rnz055  

   Jeffs, R Amzi; Novik, Isabella (April 2019, International Mathematics Research Notices)

   null (Ed.)

   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. 

   more » « less
2. About every convex set in any generic Riemannian manifold

   https://doi.org/10.1515/crelle-2021-0058  

   Lytchak, Alexander; Petrunin, Anton (October 2021, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract We give a necessary condition on a geodesic in a Riemannian manifold that can run in some convex hypersurface.As a corollary, we obtain peculiar properties that hold true for every convex set in any generic Riemannian manifold ( M , g ) {(M,g)} .For example, if a convex set in ( M , g ) {(M,g)} is bounded by a smooth hypersurface, then it is strictly convex. 

   more » « less
3. On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

   Li, Xiaoyu; Orabona, Francesco (April 2019, Proceedings of Machine Learning Research)

   Stochastic gradient descent is the method of choice for large scale optimization of machine learning objective functions. Yet, its performance is greatly variable and heavily depends on the choice of the stepsizes. This has motivated a large body of research on adaptive stepsizes. However, there is currently a gap in our theoretical understanding of these methods, especially in the non-convex setting. In this paper, we start closing this gap: we theoretically analyze in the convex and non-convex settings a generalized version of the AdaGrad stepsizes. We show sufficient conditions for these stepsizes to achieve almost sure asymptotic convergence of the gradients to zero, proving the first guarantee for generalized AdaGrad stepsizes in the non-convex setting. Moreover, we show that these stepsizes allow to automatically adapt to the level of noise of the stochastic gradients in both the convex and non-convex settings, interpolating between O(1/T) and O(1/sqrt(T)), up to logarithmic terms. 

   more » « less
4. Sparse Approximation via Generating Point Sets

   https://doi.org/10.1137/1.9781611974331.ch40  

   Blum, Avrim; Har-Peled, Sariel; Raichel, Benjamin (December 2015, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2016))

   For a set P of n points in the unit ball b ⊆ R d , consider the problem of finding a small subset T ⊆ P such that its convex-hull ε-approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of T and the convex hull of P should be at most ε. We present an efficient algorithm to compute such an ε ′ -approximation of size kalg, where ε ′ is a function of ε, and kalg is a function of the minimum size kopt of such an ε-approximation. Surprisingly, there is no dependence on the dimension d in either of the bounds. Furthermore, every point of P can be ε- approximated by a convex-combination of points of T that is O(1/ε2 )-sparse. Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset T of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input. 

   more » « less
5. A unifying convex analysis and switching system approach to consensus with undirected communication graphs

   Goebel, R.; Sanfelice, R. (January 2018, 2018 IEEE Conference on Decision and Control)

   Switching between finitely many continuous-time autonomous steepest descent dynamics for convex functions is considered. Convergence of complete solutions to common minimizers of the convex functions, if such minimizers exist, is shown. The convex functions need not be smooth and may be subject to constraints. Since the common minimizers may represent consensus in a multi-agent system modeled by an undirected communication graph, several known results about asymptotic consensus are deduced as special cases. Extensions to time-varying convex functions and to dynamics given by set-valued mappings more general than subdifferentials of convex functions are included. 

   more » « less