Research map / Learning theory and algorithms / Matrix and tensor methods

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation

ICML 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that simple randomized rounding of an SDP relaxation gives a constant-factor approximation for max-min eigenvalue augmentation with general-rank matrices when the optimal increase is large, via a new intrinsic-dimension lower-tail matrix Chernoff bound for λmin.

Problem

Choosing at most k of m PSD augmentation matrices to maximize the minimum eigenvalue of M plus their sum (NP-hard), motivated by Bayesian E-optimal design and max algebraic connectivity augmentation, in the regime k < n with non-rank-one matrices.

Approach

Apply simple independent randomized rounding to an SDP relaxation and bound the failure probability via a new intrinsic-dimension matrix Chernoff inequality for the minimum eigenvalue, which depends on trace/relative intrinsic dimension rather than the ambient dimension n, yielding a condition OPT - λmin(M) = Ω(R ln k) with R the maximum trace.

Key results

• Simple randomized rounding yields λmin ≥ (1/4)OPT with probability at least 61/64 when INC ≥ 214e²R ln k (k ≥ 2).
• With the feasibility constraint on cardinality (via Poisson binomial median argument), the guarantee holds with probability at least 29/64.
• The new intrinsic-dimension lower-tail matrix Chernoff inequality for λmin replaces the ambient dimension n with intdim(E[X], ϵ²α).

Measured effects reported in the paper

Limitations

• No empirical computational study; theoretical guarantees only.
• Guarantee applies only when optimal increase is large (OPT - λmin(M) = Ω(R ln k)); constant-factor 1/4 and probability 29/64 are loose.
• Tightness of the condition and dependence on epsilon are open.

Experimental setup

Metrics: approximation ratio success probability

Builds on: matrix Chernoff inequality (Tropp et al., 2015) E-optimal design maximum algebraic connectivity augmentation

Closest papers by meaning

• A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP (ICML 2023 · similarity 0.86)
• Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.84)
• Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.84)
• Quasi-Self-Concordant Optimization with $\ell_{\infty}$ Lewis Weights (NeurIPS 2025 · similarity 0.84)
• The Structural Complexity of Matrix-Vector Multiplication (NeurIPS 2025 · similarity 0.83)
• Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.83)