Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent

• URL: http://arxiv.org/abs/2105.03678v1
• Date: Sat, 8 May 2021 11:22:19 GMT
• Title: Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent
• Authors: Fan Wu, Patrick Rebeschini
• Abstract summary: This paper studies early-stopped mirror descent applied to noisy noisy phase retrieval. We find that a simple algorithm does not rely on explicit regularization or threshold steps to promote sparsity.
• Score: 29.206451882562867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies early-stopped mirror descent applied to noisy sparse phase retrieval, which is the problem of recovering a $k$-sparse signal $\mathbf{x}^\star\in\mathbb{R}^n$ from a set of quadratic Gaussian measurements corrupted by sub-exponential noise. We consider the (non-convex) unregularized empirical risk minimization problem and show that early-stopped mirror descent, when equipped with the hyperbolic entropy mirror map and proper initialization, achieves a nearly minimax-optimal rate of convergence, provided the sample size is at least of order $k^2$ (modulo logarithmic term) and the minimum (in modulus) non-zero entry of the signal is on the order of $\|\mathbf{x}^\star\|_2/\sqrt{k}$. Our theory leads to a simple algorithm that does not rely on explicit regularization or thresholding steps to promote sparsity. More generally, our results establish a connection between mirror descent and sparsity in the non-convex problem of noisy sparse phase retrieval, adding to the literature on early stopping that has mostly focused on non-sparse, Euclidean, and convex settings via gradient descent. Our proof combines a potential-based analysis of mirror descent with a quantitative control on a variational coherence property that we establish along the path of mirror descent, up to a prescribed stopping time.

Related papers

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Stable Phase Retrieval with Mirror Descent [0.5312303275762104]
  We show that mirror descent converges to a critical point of the phase retrieval problem. We provide global convergence guarantees that ensure that with high probability, mirror descent converges to a global minimizer near the true vector.
  arXiv  Detail & Related papers  (2024-05-17T13:07:14Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimiax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm [12.405427902037971]
  We propose a new method for approximate sampling from distributions whose support is a compact and convex set. This algorithm adds an accept-reject filter to the Markov chain induced by a single step of the Mirror Langevin. We obtain an exponentially better dependence on the error tolerance for approximate constrained sampling.
  arXiv  Detail & Related papers  (2023-12-14T11:11:58Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Provable Phase Retrieval with Mirror Descent [1.1662472705038338]
  We consider the problem of phase retrieval, which consists of recovering an $n$-m real vector from the magnitude of its behaviour. For two measurements, we show that when the number of measurements $n$ is enough, then with high probability, for almost all initializers, the original vector recovers up to a sign.
  arXiv  Detail & Related papers  (2022-10-17T16:40:02Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  We present a novel gradient estimator based on two function evaluation and randomization. We consider two types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem.
  arXiv  Detail & Related papers  (2022-05-27T11:23:57Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval [24.17778927729799]
  We analyze continuous-time mirror applied to sparse phase retrieval. It is the problem of recovering sparse signals from a set of only measurements. We provide a convergence analysis algorithm for this problem.
  arXiv  Detail & Related papers  (2020-10-20T10:03:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• The Statistical Complexity of Early-Stopped Mirror Descent [27.393821783237186]
  We study the statistical guarantees on the excess risk achieved by early-stopped unconstrained mirror descent algorithms. By completing an inequality that characterizes convexity for the squared loss, we identify an intrinsic link between offset Rademacher complexities and potential-based convergence analysis of mirror descent methods.
  arXiv  Detail & Related papers  (2020-02-01T11:05:08Z)

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.