Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy

• URL: http://arxiv.org/abs/2208.09550v1
• Date: Fri, 19 Aug 2022 21:21:06 GMT
• Title: Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy
• Authors: Michael Celentano
• Abstract summary: We derive a comparison inequality method involving properties related but distinct free energy. We prove a conjecture involving El Alaoui et al. (2022) involving an algorithm of related but distinct free energy.
• Score: 0.6091702876917281
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In many problems in modern statistics and machine learning, it is often of interest to establish that a first order method on a non-convex risk function eventually enters a region of parameter space in which the risk is locally convex. We derive an asymptotic comparison inequality, which we call the Sudakov-Fernique post-AMP inequality, which, in a certain class of problems involving a GOE matrix, is able to probe properties of an optimization landscape locally around the iterates of an approximate message passing (AMP) algorithm. As an example of its use, we provide a new, and arguably simpler, proof of some of the results of Celentano et al. (2021), which establishes that the so-called TAP free energy in the $\mathbb{Z}_2$-synchronization problem is locally convex in the region to which AMP converges. We further prove a conjecture of El Alaoui et al. (2022) involving the local convexity of a related but distinct TAP free energy, which, as a consequence, confirms that their algorithm efficiently samples from the Sherrington-Kirkpatrick Gibbs measure throughout the "easy" regime.

Related papers

• Non-asymptotic estimates for accelerated high order Langevin Monte Carlo algorithms [8.058385158111207]
  We propose two new algorithms, namely aHOLA and aHOLLA, to sample from high-dimensional target distributions. We establish non-asymptotic convergence rates for aHOLA in Wasserstein-1 and Wasserstein-2 distributions.
  arXiv  Detail & Related papers  (2024-05-09T11:12:03Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA [21.9585534723895]
  We show that, given a suitable iterate between the GPMs generated by at least geometrically bound to some threshold, the GPMs decrease to some threshold with the residual part of certain "-resi decomposition" In this paper, we demonstrate the superior performance with sub-Gaussian noise settings using the PCA technique.
  arXiv  Detail & Related papers  (2023-12-06T11:41:17Z)
• Mean-field variational inference with the TAP free energy: Geometric and statistical properties in linear models [20.311583934266903]
  We show that the landscape of the TAP free energy is strongly convex in an extensive neighborhood of a local minimizer. We prove analogous properties for a local minimizer of the TAP free energy reachable by and show posterior inference based on this minimizer remains correctly.
  arXiv  Detail & Related papers  (2023-11-14T17:35:01Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Nearest neighbor empirical processes [7.034466417392574]
  An empirical measure based on the responses from the nearest neighbors to a given point $x$ is introduced and studied as a central statistical quantity. A uniform non-asymptotic bound is established under a well-known condition, often referred to as Vapnik-Chervonenkis, on the uniform entropy numbers. This suggests the possibility of using standard formulas to estimate the variance by using only the nearest neighbors instead of the full data.
  arXiv  Detail & Related papers  (2021-10-27T08:15:20Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Local convexity of the TAP free energy and AMP convergence for Z2-synchronization [17.940267599218082]
  We study mean-field variational Bayesian inference using the TAP approach for Z2-synchronization. We show that for any signal strength $lambda > 1$, there exists a unique local minimizer of the TAP free energy functional near the mean of the Bayes posterior law.
  arXiv  Detail & Related papers  (2021-06-21T22:08: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.