Yuille-Poggio's Flow and Global Minimizer of Polynomials through Convexification by Heat Evolution

• URL: http://arxiv.org/abs/2301.00326v2
• Date: Tue, 7 May 2024 09:57:37 GMT
• Title: Yuille-Poggio's Flow and Global Minimizer of Polynomials through Convexification by Heat Evolution
• Abstract summary: This study examines the convexification version of the backward differential flow algorithm for the global minimization ofs, introduced by O. Arikan textitet al in citeABK. We employ the heat evolution method for convexification combined with filtering, which acts as a cumulative form of Steklov's regularization. For quartics, our analysis not only reflects the results of O. Arikan et al. citeABK but also presents a significantly simpler version of Newton's method that can always globally minimize quartics without convexification.
• Score: 5.976447444084449
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This study examines the convexification version of the backward differential flow algorithm for the global minimization of polynomials, introduced by O. Arikan \textit{et al} in \cite{ABK}. It investigates why this approach might fail with high-degree polynomials yet succeeds with quartic polynomials. We employ the heat evolution method for convexification combined with Gaussian filtering, which acts as a cumulative form of Steklov's regularization. In this context, we apply the fingerprint theory from computer vision. Originally developed by A.L. Yuille and T. Poggio in the 1980s for computer vision, the fingerprint theory, particularly the fingerprint trajectory equation, is used to illustrate the scaling (temporal) evolution of minimizers. In the case of general polynomials, our research has led to the creation of the Yuille-Poggio flow and a broader interpretation of the fingerprint concepts, in particular we establish the condition both sufficient and necessary for the convexified backward differential flow algorithms to successfully achieve global minimization. For quartic polynomials, our analysis not only reflects the results of O. Arikan et al. \cite{ABK} but also presents a significantly simpler version of Newton's method that can always globally minimize quartic polynomials without convexification.

Related papers

• Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models [1.4816117998909835]
  We give a quasipolynomial-time learner for $mathsfAC0$ under graphical models with strong spatial mixing and growth.<n>The framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs.
  arXiv  Detail & Related papers  (2026-07-09T09:46:05Z)
• Learning $\mathsf{AC}^0$ Under Graphical Models [21.66293630099673]
  We show how new sampling algorithms allow us to transfer statements about low-degree approximation under the uniform setting to graphical models.<n>Our approach is general enough to extend to other well-studied function classes, like monotone functions and halfspaces.
  arXiv  Detail & Related papers  (2026-04-07T17:20:35Z)
• Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers [33.99209000786153]
  Certifying nonnegativity of quadratics is a well-known NP-hard problem.<n>A sufficient condition for nonnegativity is the Sum of 200 Squares (SOS) property.<n>We introduce the first learning Transformer-training algorithm to certify SOS criterion.
  arXiv  Detail & Related papers  (2025-10-15T11:42:38Z)
• Hellinger-Kantorovich Gradient Flows: Global Exponential Decay of Entropy Functionals [52.154685604660465]
  We investigate a family of gradient flows of positive and probability measures, focusing on the Hellinger-Kantorovich (HK) geometry. A central contribution is a complete characterization of global exponential decay behaviors of entropy functionals under Otto-Wasserstein and Hellinger-type gradient flows.
  arXiv  Detail & Related papers  (2025-01-28T16:17:09Z)
• The Complexity of Algebraic Algorithms for LWE [0.0]
  We revisit the Arora-Ge model to study complexity of Gr"obner basis computations on LWE systems. We generalize the Gr"obner basis algorithm of Semaev & Tenti to arbitrary systems with a finite degree of regularity.
  arXiv  Detail & Related papers  (2024-02-12T17:59:26Z)
• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  We prove upper bounds on the covering number of sets in Euclidean space. We show that bounds improve the best known general bound by Yomdin-Comte. We illustrate the power of the result on three computational applications.
  arXiv  Detail & Related papers  (2023-11-09T03:06:59Z)
• A Unified Algebraic Perspective on Lipschitz Neural Networks [88.14073994459586]
  This paper introduces a novel perspective unifying various types of 1-Lipschitz neural networks. We show that many existing techniques can be derived and generalized via finding analytical solutions of a common semidefinite programming (SDP) condition. Our approach, called SDP-based Lipschitz Layers (SLL), allows us to design non-trivial yet efficient generalization of convex potential layers.
  arXiv  Detail & Related papers  (2023-03-06T14:31:09Z)
• Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs [52.52570805621925]
  We investigate efficient learning from higher-order graph convolution and learning directly from adjacency matrix for node classification. We show that the resulting model lead to new graphs and residual scaling parameter. We demonstrate that the proposed methods obtain improved accuracy for node-classification of non-homophilous parameters.
  arXiv  Detail & Related papers  (2022-09-12T04:46:55Z)
• A framework for overparameterized learning [0.0]
  An explanation for the success of deep neural networks is a central question in theoretical machine learning. We propose a framework consisting of a prototype learning problem, which is general enough to cover many popular problems. We then demonstrate that supervised learning, variational autoencoders and training with gradient penalty can be translated to the prototype problem.
  arXiv  Detail & Related papers  (2022-05-26T17:17:46Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  We develop and analyze DASHA: a new family of methods for noneps distributed optimization problems. Unlike MARINA, the new methods DASHA, DASHA-MVR send compressed vectors only and never synchronize the nodes, which makes them more practical for learning.
  arXiv  Detail & Related papers  (2022-02-02T20:10:40Z)
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks [3.198144010381572]
  We study feedforward deep ReLU ANNs with an arbitrarily large number of hidden layers. We prove convergence of the risk of the GD optimization method with randoms in the training of such ANNs. We also study solutions of gradient flow differential equations.
  arXiv  Detail & Related papers  (2021-12-17T18:55:40Z)
• Semi-Sparsity for Smoothing Filters [1.1404527665142667]
  We show a new semi-sparsity smoothing algorithm based on a novel sparsity-inducing framework. We show many benefits to a series of signal/image processing and computer vision applications.
  arXiv  Detail & Related papers  (2021-07-01T17:31:42Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
  arXiv  Detail & Related papers  (2020-08-05T17:52:10Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)

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.