On maximum-likelihood estimation in the all-or-nothing regime

• URL: http://arxiv.org/abs/2101.09994v1
• Date: Mon, 25 Jan 2021 10:20:36 GMT
• Title: On maximum-likelihood estimation in the all-or-nothing regime
• Abstract summary: The analysis is carried out in the sparse setting, where the underlying signal has a support that scales sublinearly with the total number of dimensions. We show that for Bernoulli distributed signals, the MLE undergoes an emphall-or-nothing (AoN) phase transition, already established for the minimum mean-square-error estimator (MMSE) in the same problem.
• Score: 14.192301094399765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of estimating a rank-1 additive deformation of a Gaussian tensor according to the \emph{maximum-likelihood estimator} (MLE). The analysis is carried out in the sparse setting, where the underlying signal has a support that scales sublinearly with the total number of dimensions. We show that for Bernoulli distributed signals, the MLE undergoes an \emph{all-or-nothing} (AoN) phase transition, already established for the minimum mean-square-error estimator (MMSE) in the same problem. The result follows from two main technical points: (i) the connection established between the MLE and the MMSE, using the first and second-moment methods in the constrained signal space, (ii) a recovery regime for the MMSE stricter than the simple error vanishing characterization given in the standard AoN, that is here proved as a general result.

Related papers

• Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry [2.15242029196761]
  We study distributed optimization with gradients and finite-bit communication modeled by random (unbiased) quantization.<n>Under restricted secant inequality (RSI), a constant step-size yields a linear contraction to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity.<n>Under PolyakLojasiewicz (PL) inequality, we obtain linear-to-neighborhood convergence in the same quantized setting.
  arXiv  Detail & Related papers  (2026-06-09T18:18:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent [13.27202712518471]
  This paper proposes and analyzes a gradient-type algorithm based on Burer-Monteiro factorization, called the Asymmetric Descented Gradient (APGD)
  arXiv  Detail & Related papers  (2025-04-28T07:13:23Z)
• Mean-Field Langevin Dynamics for Signed Measures via a Bilevel Approach [4.577104493960515]
  Mean-field Langevin dynamics (MLFD) is a class of interacting particle methods that tackle convex optimization over probability measures on a manifold. We show how to extend the MFLD framework to convex optimization problems over signed measures.
  arXiv  Detail & Related papers  (2024-06-24T18:15:12Z)
• Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities [0.5592394503914488]
  We introduce a method for identifying and approximating a target measure $pi$ as a perturbation of a given reference measure $mu$. Our main contribution unveils a connection between the emphdimensional logarithmic Sobolev inequality (LSI) and approximations with this ansatz.
  arXiv  Detail & Related papers  (2024-06-18T20:02:44Z)
• Fundamental limits of Non-Linear Low-Rank Matrix Estimation [18.455890316339595]
  Bayes-optimal performances are characterized by an equivalent Gaussian model with an effective prior. We show that to reconstruct the signal accurately, one requires a signal-to-noise ratio growing as $Nfrac 12 (1-1/k_F)$, where $k_F$ is the first non-zero Fisher information coefficient of the function.
  arXiv  Detail & Related papers  (2024-03-07T05:26:52Z)
• Randomized Physics-Informed Machine Learning for Uncertainty Quantification in High-Dimensional Inverse Problems [49.1574468325115]
  We propose a physics-informed machine learning method for uncertainty quantification in high-dimensional inverse problems. We show analytically and through comparison with Hamiltonian Monte Carlo that the rPICKLE posterior converges to the true posterior given by the Bayes rule.
  arXiv  Detail & Related papers  (2023-12-11T07:33:16Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
  arXiv  Detail & Related papers  (2023-12-02T13:01:29Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  Sub-gradient method (SubGM) is used to recover a low-rank matrix from a limited number of measurements. We show that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values.
  arXiv  Detail & Related papers  (2022-02-17T17:50:04Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.of estimating the partition of the lattice induced by the constancy regions of the unknown signal. We prove that a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigma2 k*
  arXiv  Detail & Related papers  (2021-05-27T23:41:01Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
  We make the assumption of sub-Gaussian measurements, which is satisfied by a wide range of measurement models. We show that our result can be extended to the uniform recovery guarantee under the assumption of a so-called local embedding property.
  arXiv  Detail & Related papers  (2020-06-22T16:43:35Z)
• Information theoretic limits of learning a sparse rule [22.10167304165091]
  We prove a variational formula for the mutual information per sample when the system size grows to infinity. We find that, for such signals and suitable scalings of the sparsity and vanishing rate, the MMSE is nonincreasing piecewise constant. We discuss an all-or-nothing phenomenon for the generalization error with a sublinear set of training examples.
  arXiv  Detail & Related papers  (2020-06-19T18:29:10Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.