Semidefinite programs simulate approximate message passing robustly
- URL: http://arxiv.org/abs/2311.09017v1
- Date: Wed, 15 Nov 2023 15:00:48 GMT
- Title: Semidefinite programs simulate approximate message passing robustly
- Authors: Misha Ivkov, Tselil Schramm
- Abstract summary: Approximate message passing (AMP) is a family of iterative algorithms that generalize power.
AMP algorithms are known to optimally solve many average-case optimization problems.
- Score: 3.1528188401664137
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Approximate message passing (AMP) is a family of iterative algorithms that
generalize matrix power iteration. AMP algorithms are known to optimally solve
many average-case optimization problems. In this paper, we show that a large
class of AMP algorithms can be simulated in polynomial time by \emph{local
statistics hierarchy} semidefinite programs (SDPs), even when an unknown
principal minor of measure $1/\mathrm{polylog}(\mathrm{dimension})$ is
adversarially corrupted. Ours are the first robust guarantees for many of these
problems. Further, our results offer an interesting counterpoint to strong
lower bounds against less constrained SDP relaxations for average-case
max-cut-gain (a.k.a. "optimizing the Sherrington-Kirkpatrick Hamiltonian") and
other problems.
Related papers
- Private Geometric Median [10.359525525715421]
We study differentially private (DP) algorithms for computing the geometric median (GM) of a dataset.
Our main contribution is a pair of DP algorithms for the task of private GM with an excess error guarantee that scales with the effective diameter of the datapoints.
arXiv Detail & Related papers (2024-06-11T16:13:09Z) - Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
We present the first tractable algorithm with minimax optimal regret of $widetildemathrmO(sqrtmathrmsp(h*) S A T)$.
Remarkably, our algorithm does not require prior information on $mathrmsp(h*)$.
arXiv Detail & Related papers (2024-06-03T11:53:44Z) - No-Regret Reinforcement Learning in Smooth MDPs [24.249446550171307]
We introduce a novel structural assumption on the decision processes (MDPs) that generalizes most of the settings proposed so far.
We propose two algorithms for regret minimization in $nu-$smoothness.
We compare our results with state-of-the-art ones from RL theory, showing that our algorithms achieve the best guarantees.
arXiv Detail & Related papers (2024-02-06T08:18:14Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
This work considers a large family of bandit problems where the unknown underlying reward function is non-concave.
Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality.
We show that the standard optimistic algorithms are sub-optimal by dimension factors.
arXiv Detail & Related papers (2021-07-09T16:04:24Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary.
Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z) - Lossless Compression of Efficient Private Local Randomizers [55.657133416044104]
Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting.
In many cases the best known LDP algorithms require sending prohibitively large messages from the client device to the server.
This has led to significant efforts on reducing the communication cost of LDP algorithms.
arXiv Detail & Related papers (2021-02-24T07:04:30Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model.
The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22:24Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions.
A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples.
We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
arXiv Detail & Related papers (2020-05-10T19:52:03Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
This paper considers the peak Constrained Markov Decision Process (PCMDP), where the agent chooses the policy to maximize total reward in the finite horizon as well as satisfy constraints at each epoch with probability 1.
We propose a model-free algorithm that converts PCMDP problem to an unconstrained problem and a Q-learning based approach is applied.
arXiv Detail & Related papers (2020-03-11T23:23:29Z)
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.