From Symmetry to Geometry: Tractable Nonconvex Problems

• URL: http://arxiv.org/abs/2007.06753v4
• Date: Fri, 8 Jul 2022 18:57:15 GMT
• Title: From Symmetry to Geometry: Tractable Nonconvex Problems
• Authors: Yuqian Zhang, Qing Qu, and John Wright
• Abstract summary: We discuss the role of curvature in the landscape and the different roles of symmetries. This is rich with observed phenomena open problems; we close by directions for future research.
• Score: 20.051126124841076
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As science and engineering have become increasingly data-driven, the role of optimization has expanded to touch almost every stage of the data analysis pipeline, from signal and data acquisition to modeling and prediction. The optimization problems encountered in practice are often nonconvex. While challenges vary from problem to problem, one common source of nonconvexity is nonlinearity in the data or measurement model. Nonlinear models often exhibit symmetries, creating complicated, nonconvex objective landscapes, with multiple equivalent solutions. Nevertheless, simple methods (e.g., gradient descent) often perform surprisingly well in practice. The goal of this survey is to highlight a class of tractable nonconvex problems, which can be understood through the lens of symmetries. These problems exhibit a characteristic geometric structure: local minimizers are symmetric copies of a single "ground truth" solution, while other critical points occur at balanced superpositions of symmetric copies of the ground truth, and exhibit negative curvature in directions that break the symmetry. This structure enables efficient methods to obtain global minimizers. We discuss examples of this phenomenon arising from a wide range of problems in imaging, signal processing, and data analysis. We highlight the key role of symmetry in shaping the objective landscape and discuss the different roles of rotational and discrete symmetries. This area is rich with observed phenomena and open problems; we close by highlighting directions for future research.

Related papers

• Exceptional Points and Stability in Nonlinear Models of Population Dynamics having $\mathcal{PT}$ symmetry [49.1574468325115]
  We analyze models governed by the replicator equation of evolutionary game theory and related Lotka-Volterra systems of population dynamics. We study the emergence of exceptional points in two cases: (a) when the governing symmetry properties are tied to global properties of the models, and (b) when these symmetries emerge locally around stationary states.
  arXiv  Detail & Related papers  (2024-11-19T02:15:59Z)
• Learning Infinitesimal Generators of Continuous Symmetries from Data [15.42275880523356]
  We propose a novel symmetry learning algorithm based on transformations defined with one- parameter groups. Our method is built upon minimal inductive biases, encompassing not only commonly utilized symmetries rooted in Lie groups but also extending to symmetries derived from nonlinear generators.
  arXiv  Detail & Related papers  (2024-10-29T08:28:23Z)
• SymmetryLens: A new candidate paradigm for unsupervised symmetry learning via locality and equivariance [0.0]
  We develop a new, unsupervised symmetry learning method that starts with raw data. We demonstrate that this coupling between symmetry and locality, together with a special optimization technique developed for entropy estimation, results in a highly stable system. The symmetry actions we consider are group representations, however, we believe the approach has the potential to be generalized to more general, nonlinear actions of non-commutative Lie groups.
  arXiv  Detail & Related papers  (2024-10-07T17:40:51Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning. We introduce a novel approach to disentangled representation learning based on quadratic optimal transport. We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• Symmetry Induces Structure and Constraint of Learning [0.0]
  We unveil the importance of the loss function symmetries in affecting, if not deciding, the learning behavior of machine learning models. Common instances of mirror symmetries in deep learning include rescaling, rotation, and permutation symmetry. We show that the theoretical framework can explain intriguing phenomena, such as the loss of plasticity and various collapse phenomena in neural networks.
  arXiv  Detail & Related papers  (2023-09-29T02:21:31Z)
• Symmetries, flat minima, and the conserved quantities of gradient flow [20.12938444246729]
  We present a framework for finding continuous symmetries in the parameter space, which carves out low-loss valleys. To generalize this framework to nonlinear neural networks, we introduce a novel set of nonlinear, data-dependent symmetries.
  arXiv  Detail & Related papers  (2022-10-31T10:55:30Z)
• Degradation-agnostic Correspondence from Resolution-asymmetric Stereo [96.03964515969652]
  We study the problem of stereo matching from a pair of images with different resolutions, e.g., those acquired with a tele-wide camera system. We propose to impose the consistency between two views in a feature space instead of the image space, named feature-metric consistency. We find that, although a stereo matching network trained with the photometric loss is not optimal, its feature extractor can produce degradation-agnostic and matching-specific features.
  arXiv  Detail & Related papers  (2022-04-04T12:24:34Z)
• Deep Networks on Toroids: Removing Symmetries Reveals the Structure of Flat Regions in the Landscape Geometry [3.712728573432119]
  We develop a standardized parameterization in which all symmetries are removed, resulting in a toroidal topology. We derive a meaningful notion of the flatness of minimizers and of the geodesic paths connecting them. We also find that minimizers found by variants of gradient descent can be connected by zero-error paths with a single bend.
  arXiv  Detail & Related papers  (2022-02-07T09:57:54Z)
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems [71.60601421935844]
  Many machine learning problems can be formulated as minimax problems such as Generative Adversarial Networks (GANs) We provide a comprehensive generalization analysis of examples from training gradient methods for minimax problems.
  arXiv  Detail & Related papers  (2021-05-08T22:38:00Z)
• On the Tightness of Semidefinite Relaxations for Rotation Estimation [49.49997461835141]
  We show that semidefinite relaxations have been successful in numerous applications in computer vision and robotics. A general framework based on tools from algebraic geometry is introduced for analyzing semidefinite relaxations. We show that for some problem, an appropriate pararization guarantees tight relaxations.
  arXiv  Detail & Related papers  (2021-01-06T15:42:02Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.