Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
Authors: Jourdain Lamperski
Haeseong Yang
Oleg Prokopyev
Venue: ICML 2025 poster (2025)
Keywords: Approximation algorithms
Bayesian E-optimal design
matrix concentration inequalities
maximum algebraic connectivity augmentation
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: The paper derives a new matrix concentration inequality to establish an approximation guarantee for a simple algorithm for max-min eigenvalue augmentation in a practically motivated regime that has yet to be studied from a theoretical standpoint.

Abstract: We consider the *max-min eigenvalue augmentation* problem: given $n \times n$ symmetric positive semidefinite matrices $M,A_1,\ldots, A_m$ and a positive integer $k < m$, the goal is to choose a subset $I \subset \{1,\ldots,m\}$ of cardinality at most $k$ that maximizes the minimum eigenvalue of the matrix $M + \sum_{i \in I} A_i$. The problem captures both the  *Bayesian E-optimal design* and *maximum algebraic connectivity augmentation* problems. In contrast to the existing work, we do not assume that the *augmentation matrices* are rank-one matrices, and we focus on the setting in which $k < n$. We show that a *simple* randomized rounding method provides a constant-factor approximation if the *optimal increase* is sufficiently large, specifically, if $\mathrm{OPT} - \lambda_{\mathrm{min}}(M) = \Omega(R \ln k)$, where $\mathrm{OPT}$ is the optimal value, and $R$ is the maximum trace of an augmentation matrix. To establish the guarantee, we derive a matrix concentration inequality that is of independent interest. The inequality can be interpreted as an *intrinsic dimension* analog of the matrix Chernoff inequality for the minimum eigenvalue of a sum of independent random positive semidefinite matrices; such an inequality has already been established for the maximum  eigenvalue, but not for the minimum eigenvalue.

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
Jourdain Lamperski Haeseong Yang'
Oleg A. Prokopyev
Abstract
sider the max-min eigenvalue augmentation problem:
max {Amin M Σ 21Aii) 1|=1lo s k
We consider the max-min eigenvalue augmenta- tion problem: given n X n symmetric positive semidefinite matrices M, A1...., Am and a pos- itive integer k < m. the goal is to choose a subset 1 C {1,..., m of cardinality at most & that maximizes the minimum eigenvalue of the matrix M + Eiet Aq. The problem captures both the Bayesian E-optimal design and maxi- mum algebraic connectivity augmentation prob- lems. In contrast to the existing work, we do not assume that the augmentation matrices are rank- one matrices, and we focus on the setting in which k < n. We show that a simple randomized round- ing method provides a constant- factor approxima- tion if the optimal increase is sufficiently large, specifically, if OPT Amia (M) S2(RI In k). where OPT is the optimal value, and R is the maximum trace of an augmentation matrix. To es- tablish the guarantee, we derive matrix concen- tration inequality that is of independent interest. The inequality can be interpreted as an intrinsic di- mension analog of the matrix Chernoff inequality for the minimum eigenvalue of a sum of indepen- dent random positive semidefinite matrices; such inequality has already been established for the maximum eigenvalue, but not for the minimum cigenvalue.
(1)
where Amin (M + Ex= 2,A;) denotes the minimum eigen- value of the matrix M + E A; and ||=||o is equal to the number of non-zero entries z. Problem (1) captures the Bayesian E-oplimal design problem and the maximum algebraic connectivity augmentation problem, which we outline in more detail below.
Bayesian E-optimal design. When running experiments to collect data to build a statistical model, it is naturally of interest to run fewer experiments to obtain the same level of "model quality." The goal in optimal linear exper- imental design to determine which experiments to run in order minimize the "variance" of a linear regression model, subject to some cardinality constraint on the number of the experiments (Fedorov, 2013; Goos & Jones, 201 I; Pukelsheim, 2006). (Note that linear regression models are unbiased under mild conditions (Hastie et al., 2009).)
More formally, consider design points Z1...., I' E R" that each correspond a potential experiment. we run the experiment associated with design point z;, then we observe outcome ys E R. Suppose that we run at most k experiments. Running the experiments associated with design points FG, i E I C [m] := (l....., m} (where [T] < k) provides us with data {( 9: hie,, which then can be used to construct a linear regression model. The goal in optimal linear experimental design is to select subset I that optimizes function ʃ (referred as an optimality criterion) of the information matrix Eier v..... There number of optimality criteria; each captures different notion of variance.
1. Introduction
Let St. denote the set of symmetric positive semidefinite (PSD) matrices. Given M STh augmentation matrices Am S and positive integer k < m, we con-
The goal in E-optimal design is to maximize the E- optimality criterion, which is given by the minimum eigen- value Amia(Eigs xxx²]) of the information matrix. E- optimal design is a special case of (1) with M 0 and augmentation matrices A, x i E [m]] In Bayesian E-optimal design, we are also given prior matrix, which translates to an instance of (1) with M # 0 and the augmen- tation matrices given by A; = .ęn i E [m]] This setup assumes that the experiments can be run individually and hence, the augmentation matrices are each of rank one, If the
DDeaartment of Industrial Engineering, University of Pittsburgh, 1025 Benedum Hall, Pittsburgh, PA 15261, USA 'Department of Business Administration, University of Zurich, Plattenstrasse 14, CH 8032 Zurich. Correspondence to: Jourdain Lamperski <lamperski@ pitt.edu>.
Proceedings of the 4rnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
experiments can only be run in certain batches, then, as in the previous application setting, we must consider augmen- tation matrices of general rank (Revilla Sancho; Derezinski et al., 2020; Tantipongpipat, 2020: Che et al., 2024).
method for max-min eigenvalue augmentation. More pre- cisely, consider the following semidefinite programming relaxation of (I):
m
m
Maximum algebraic connectivity augmentation. In the maximum algebraic connectivity augmentation prob- lem, the goal is to add at most k edges to given graph G = (V, F)) in order to maximize the graph's ' algebraic connectivity (Ghosh & Boyd, 2006; Kim, 2009; Kolla et al., 2010; Mosk-Aoyama, 2008; Somisetty et al., 2024; Wei et al., 2014). The algebraic connectivity of a graph is the second smallest eigenvaee eigenvalue (L) of its Laplacian ma- trix L = Lee E deug where de E R for each edge e = ij E E is defined by de = e; eg, where e, and ej are the i-th and j-th standard n-dimensional unit vectors, respectively (De Abreu, 2007; Fiedler, 1973).
{1: M + Σ 24 - n and Σ =E|0,I]">,,eE
max
2: S
k).
(2)
where I is the n x n identity matrix. Let (Zadp. ?sdp) E
[0, 1 x R denote an optimal solution to the relaxation
(2). We study the randomized method that, for each E [m], rounds the i-th entry of Asdp to be equal to with probability [asdple and 0, otherwise. In other words, we study the random vector Zround E {0, 1) 1 defined by
P(ZroomaJ: 1) - [zedplis
Vi E [m]]
Algebraic connectivity provides measure of a graph's connectivity. In particular, (L) > O if and only if G is connected. Furthermore, larger values of (G) indicate that G' is, in sense, more connected. Indeed, algebraic connectivity appears as a factor in the convergence rates of various dynamic processes (e.g., Markov chains) on graphs (Ogiwara et al., 2015). Intuitively, one would expect a dynamic process to converge faster (e.g.. Markov chain to mix quicker) if the graph is, to some extent, more connected. Algebraic connectivity provides us with exactly this notion of connectivity.
Note that 2round might not be feasible for (1) because Σ -i (roundds k with positive probability; recall that k m.
The maximum algebraic connectivity augmentation (Kolla et al., 2010; Wei et al., 2014) and E-optimal design (Allen- Zhu et al., 2021; Avron & Boutsidis, 2013; Lau & Zhou, 2022) studies also investigate approximately solving the max-min eigenvalue augmentation problem (1). Our study is different from these works in the following two key ways. First, unlike these studies, we do not assume that the augmentation matrices A A. are rank-one matrices, which allows us to capture more practical considerations (e.g., situations in which edges cannot be individually added to a graph, or experiments must be run in certain batches). Second, we focus on the regime in which k < n. The (non- Bayesian) E-optimal design studies assume that k 2 n; otherwise, the E-optimal design problem is not interesting because Amin (Eier 2;z, ) 0 for all I C [m]] such that [Z] < n. To the best of our knowledge, the Bayesian E- optimal design problem remains unexplored in the k < n setting. In contrast, the existing maximum algebraic connec- tivity augmentation work considers the case when & < n. However, in the algebraic connectivity setting, the augmen- tation matrices are of a particular form; recall our earlier discussion their structure. Thus, the maximum algebraic connectivity augmentation problem does not capture the full generality of the max-min eigenvalue augmentation prob- lem (1), even under the assumption that the augmentation matrices are rank-one matrices.
The maximum algebraic connectivity augmentation problem finds applications in settings in which it is of interest to add edges to a graph in order to make the graph more robust with respect to potential edge disruptions. Consider, for example, adding flight routes to air transportation network in order to improve its resiliency to bad weather and airport closures (Wei et al., 2014).
More formally, it can be shown that (z = Amin (L + 11 11"), where 1 is the n-dimensional vector of all ones; we provide a short proof of this fact in Appendix B. Accord- ingly. we can formulate the maximum algebraic connec- tivity augmentation problem
special case of (1) with M L + 11 and the augmentation matrices given by A, = a, e & E. The outlined setup assumes that the edges can be individually added, which gives rise to rank- one augmentation matrices. If the edges must be added in
groups (e.g., as particular subgraphs), then one must con- sider augmentation matrices of general rank.
Finally, as we discuss in more detail in Subsection 1.1, our study boils down to understanding the extent to which we can (in some very particular sense) approximate PSD matrix with a sum of random PSD matrices in terms of the intrinsic dimension of the matrix being approximated. The results that we develop in this direction are more generally applicable and are of independent interest.
Simple randomized rounding. The max-min eigenvalue augmentation problem (1) is P-rrd because the maxi- mum algebraic connectivity augmentation problem is N P- hard Mosk--Aoyma 2008). The E-optimal design problem is similarly P-hrd (Civril & Magdon-Isman Ismail, 2009).
In this work, we study a simple randomized rounding
2

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
1.1. Summary of approach, contributions, and organization
Approach. Let OPT denote the optimal objective function value of the max-mi min eigenvalue augmentation problem (1). Define
INC = Amin M +
Σ Eeddle Awin (M)
to be the increase in the minimum eigenvalue provided by 2sdp' Note that INC is an upper bound on the optimal increase. That is, INC 2 OPT - Amin (M). We show that if INC (or more weakly, the optimal increase) is sufficiently large, then simple randomized rounding provides constant- factor approximation.
||]] s 1} (or UeR:: Rd
{a Rd a Qu S(Q.a)
Figure I. Illustration of set a)) where Q is positive definite matrix and a 2 O.
We exploit the following observation. If LNC is larger, then the quadratic form x. (2 (e,)p]:A,)e can only be on the order of INC in smaller (actually no larger, but we are speaking informally) number of directions x E 55-1 = {z I²" ||ж||| = 1}. where ||.||| is the Euclidean norm of æ. (We refer points on the unit sphere as directions.) More precisely, for 0 < 1, the set
with the quantity
intdim Ai tr E [=sdp]i
>INC
(5)
which we refer to as the intrinsic dimension of [zsdpliA4
S Eedpl IoAi, (NNC
relative to yINC, and we lower-bound the probability of (4)
(3)
in terms of intdim() " AA,, >INC).
E E 1m-1;
x T
E1 (lsdnlleAd) x
More generally, we consider generic sum X -E X; of independent random PSD matrices X XI,..., Xm E S
We develop an upper bound for
of directions is smaller when INC is larger; see Figure I for an illustration.
IP E S(E|X], a) x Xx S 10 (1-e)a)
(6)
Hence, when INC is larger, it is sufficient to en- sure that E [Zround]] is good approximation of Ee [2ddp l A, with respect to smaller number of direc- the quadratic form x. Mx must already be large, so we do not need to account for these directions.) More formally, for some e E (0, 1), it is sufficient to ensure that
in terms of intdim [B[X],a) where a 0. Suppose that
Amia (B[X)) (in which case > 0 if E[X] is positive definite). Then, S(E[X),, a)) 5 and it follows that the probability given in (6) equals
tions. (For x &
(Estp]e
P(3x Sn-1 x T Xx S (1 - e) Amin (E[X))
P(Amin (X) S (1 A) (E(X))).
m Froundli44) (1-NNICC
Accordingly, we, in some sense, develop "intrinsic di- mension" lower-tail bound for the minimum eigenvalue Amiu (X) minzesa-1 x.' Xx. Although, it is more pre- cise to state that we develop an intrinsic dimension lower-tail bound for the quantity mitlzes(E|x))e x Xx. Furthermore, we note that the tail bound that develop is only interest- ing when
x:
(4)
Vz E S D Dssspl:A,,
with some amount of probability. One would imagine that it is "easier" to ensure (4) when [ 7INC) is smaller, i.e., when INC is larger.
Amin (E[X])-
Contributions and organization. First, we provide some background on matrix Chernoff incqualities for Amin (X) and Amax in Section In particular, we point out that an intrinsic dimension matrix Chernoff inequality has been established for Amax (X), but not for (X). As stated
We show that we can ensure (4) with a higher amount of probability when the set 5(E""[eedplee (ICC) <INC) is smaller. Towards this end, we measure the size of the set
3

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
above, our work develops an intrinsic dimension analog of the matrix Chernoff inequality for Amin (X). In Section 2 we also provide reformulation of the existing matrix Chernoff inequality for Amia (X) that plays key role in our analysis; see Theorem 2.5 for a statement of the reformulation.
let V St such that V > B[X]. For X Di=1 X,,
Minax = Xmax ( and & 2 T/ //maxxx + 1,
(7)
(
(lmmae/ /L
2 (pmma) S 2 iV
Remark 2.3. We define the intrinsic dimension of a ma- trix relative to a scalar value, but Tropp defines intrinsic dimension of a PSD matrix to be equal to the quantity tr(V)/Amax/ (V). Our definition is more general and pro- vides an an upper bound on Tropp's intrinsic dimension. The upper bound is convenient for lower bounding x _ Xx over E S(E[X), a)), rather than just upper bounding x' "x over E Sm-1.
We derive the intrinsic dimension concentration inequality for Amin (X) in Section 3; see Theorem 3.1 for a statement of the inequality. The derivation boils down to a careful application of the existing matrix Chernoff inequalities (in- cluding the reformulated inequality provided in Theorem 2.5) with respect to subsets of directions that lie in certain subspaces.
In Section we use the intrinsic dimension concentration inequality stated in Theorem 3.1 show that simple random- ized rounding provides a constant-factor approximation if INC (2 In k), where R max4e im] tr(4,); see The- orem 4.1. Our proof of this result follows the argument pro- viddd above in the summary of our approach. If we instead applied the existing matrix Chernoff inequality for Amin (X). then we would obtain the condition INC = S2W In).. where W == gax Amax A,)) This condition, however, does not shed light the setting of interest in which k < n..
Next, consider the following matrix Chernoff inequality for the minimum eigenvalue of a sum of independent random PSD matrices that are surely bounded.
Theorem 2.4 ((Tropp et al., 2015), Theorem 5.1.1). Let X1y..., Xm E Ruxx be independent random PSD ma- trices such that (X,x S L for each i E [m]. For X = E Xi Mmin = -mmiaa (mii((([]) and c C (0.
P(Amiu
(Xmii(() (X) S (1 ())mmin) ne -
Unlike Theorem 2.1, an intrinsic dimension analog has yet to be developed for Theorem 2.4. As pointed out in (Tropp et al., 2015), the techniques employed to establish Theo- rem 2.2 do not seem apply in the context of the minimum eigenvalue.
2. Background and preliminaries
First, in Subsection 2.1, we provide background on ma- trix Chernoff inequalities for the minimum and maximum eigenvalue of a sum of random PSD matrices. Then, in Subsection 2.2, we present a reformulation of the inequality for the minimum eigenvalue.
It is also worthwhile to note that we cannot upper bound (6) with Theorem 2.4. It there is a direction x per which σ E[X]== = 0, and hence Amin Amin (E[X]) = O, then Theorem 2.4 provides us with a trivial guarantee. The existence of
2.1. Matrix Chernoff inequalities
such a direction, however, should not impact upper bound- ing (6). One might hope that can directly apply Theorem 2.4 to the set S(E[X], a),, but the set is not subspace (as seen in Figure 1). Although, an idea along these lines is exploited in the proof of Theorem 3.1; see Lemma 3.2.
All inequalities that we present in this subsection are taken from Tropp (Tropp et al., 2015). Consider the following matrix Chernoff inequality for the maximum eigenvalue of sum of independent random PSD matrices that are surely bounded (in terms of their maximum eigenvalue).
2.2. One-sided approximation inequality
Theorem 2.1 ((Tropp et al., 2015), Theorem 5.1.1). Lei XI...., ..... E Ruxn be independent random PSD ma- trices such that (max((x)) < L for each i E [m]. For X = -Em Xz, pmax = Xmax (B[X)) and > 0,
Let XI,..., Xmm be independent random PSD matrices such that Amaax (X,) < L for each i E [m]. X = Em X;. Pmii = Amin ( (E(x)): and E (0, 1]. Theorem 2.4 enables us to ensure that
P(Amaax (X) 2 t(mmax) S n (c) f/max/L
min x Xx = Amin (X) zESn-1
> (1 - (e=e)) Amin (E[X])
The dimension factor of n in Theorem 2.1 can essentially be replaced with a factor of the intrinsic dimension of the ma- trix [[ relative to Amax (E[X]). We only need to include an additional factor of and enforce 2 L/ //maax +
(1 c) min E[X]x 2ES
with some amount of probability. In this subsection show that we can more strongly ensure that
Theorem 2.2 (CTropp et al., 2015), Theorem 7.2.1). Let X1,...,XX XXm E R2 be independent random PSD ma- trices such that (X,) S L. for each i E [m]. Also,
x Xx > (1 - c)x 3)xTE[[], E[X] Vr E S
x x x1

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
with the same amount of probability. That is, we show that we can ensure that X is one-sided approximation of [[X]. A precise statement of the result that we establish is as follows.
to be constant, in which case the theorems provide similar guarantees.
Consider the extreme case in which a Amin (E(X)), which is still possible under the assumptions of Theorem 3.1. Using the fact that (x( Σ n (T[ it then fol- lows that Theorem 3.1 provides a weaker guarantee than Theorem 2.4. Thus, as mentioned the end of Subsection 1.1, the result is non-trivial when a > Amia [E]])
Theorem 2.5. Let XI...., Xm E Ruxx be independent random PSD matrices such that (X,) S L for each i E [m]] For X = Eiz Xi, Jmmin = Amin (E(]), and e E (0, 11
P(X& + (1 - E|(IX]
The remainder of this section is dedicated to outlining the proof of Theorem 3.1. First, we establish preliminaries and then, we present the proof outline.
= PI E TR" \ [0} x T Xx S (1 - -c)x -))]T((())))) [(
S -eemn//22/22
Proof preliminaries. Let X1,..., Xm E &R be inde- pendent random PSD matrices such that Amax (X.) S L for each E [m]] Also, let X > X
Proof. See Appendix B.I.
In our proof of Theorem 2.5, we first construct transforma- tions Y, i E [m]. of the matrices X,, E [m], respectively, with the property that E Yi] I. Then, we apply Theorem 2.4 to the transformed matrices, and the desired result follows. So, Theorem 2.4 implies Theorem 2.5, but clearly Theorem 2.5 implies Theorem 2.4, so Theorem 2.5 is best thought of as a reformulation of Theorem 2.4.
Let u1 u1...., the be orthonormal eigenvectors of B[X], and let d AI,..., An denote the corresponding respective eigen- values. That is, E[X [u dsu, for each i [ni]. We collect the eigenvectors into the columns of the orthonormal matrix U == [w1] -.. [us.]. and we collect the eigenvalues into the diagonal of the diagonal matrix A := diag(Aı,.... Ån). The spectral decomposition of TE| [[X] is then given by [[X] = UAU
Ultimately, we need Theorem 2.5 (instead of Theorem 2.4)
in Section 3 to derive the intrinsic dimension concentration inequality. We direct the reader Remark 3.4 the end of Section 3 for explanation.
For 3 > 0, define the sets
= (ie)= R 3)
and
3. Intrinsic dimension concentration inequality
(2(3) : [n] 11() (i E [m] : 2 3),
We provide a statement of the intrinsic dimension concen- tration inequality that we develop in Theorem 3.1 below.
which partition [r]] based on the size of the eigenvalues Å A.,.... .......A. Am. ilarly, (2()) + 0 if > Amia (E[[]) but we do not exploit this fact.
Theorem 3.1. Let X1....; Xm E Raxx be independent random PSD matrices. Suppose that XX,) S L for each [m]. For X Em Xi e E (0, 1}, and L/e2 < a Amax (E|]).
Note that 7, (B) * 0 if 3 S Amax ( [X]) Sim-
For 3 > 0 and E [2) such that 1,(8) * 0, we collect the eigenvectors u,, E (3) into the columns of the matrix (B). Then, we collect the eigenvalues &r. i (3)), into the diagonal of the diagonal matrix A,) and define
Pl E S(E[X), x. T (1- I 48e2 intdim ( aae L)
-
Proof. See Appendix B.4.
L,(3) = (U,(8)= π E R (
Theorem 3.1 tells us that we can guarantee that the quadratic
to be the subspace spanned by the eigenvectors u., E I,(3). Next, let
form x. Xx is larger on a smaller set of directions x E S(B[X], a) per which the quadratic form x E E[ is is larger. Accordingly, there is a tradeoff: For larger values of a, we can guarantee x Xx is larger, albeit in a smaller number of directions x. When we apply Theorem 3.1 in Section 4 towards developing an approximation guarantee for simple randomized rounding, we choose a to optimize this trade- off. On a related note, observe that Theorem 3.1 does not preserve dependence on e like Theorem 2.2. In our approxi- mation analysis of simple randomized rounding, we take
((0)
to be the set of points with unit Euclidean norm that lie within the subspace LB(3), and we define the independent random PSD matrices
YT = UB() XXU,(3), (1,5) E [m] x [2]
as well as Y, = Em Yu= =
5

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
Note that each matrix Yey is (1,()))))))( matrix. Also, note that
Lemma 3.3. For 3 > such that I1(3), + 0, and 2 max [T/B + +1, 2,
E[y -,,(8)
IP max x² Xxx =E
xxx 2 13) S PeiidiimEE(X),... -5/1.
= UUU
= AA:
Proof. See Appendix B.3.
and that for each i E [mm].
A sketch of the proof of Theorem 3.1 is as follows. The aim is to ensure that x Xx > (1 - <)a for all x E SS([E) o)) with some amount of probability. Fix x E S(E[X], a) First, we carefully specify a value of / > 0 (details behind the specification to come). Assume that [5(3) o 0 for each [2]. (The proof otherwise ends up being straightforward. Because (3) is the orthogonal complement of L2(3), we can decompose x E S(E[X), (3) as = 21 + I2, where 21 E I, (3) and x2 E (3). Because X is random PSD matrix, we can factor X as X X1/2X" x1/2, where X1/2 is a random matrix. From x = I1 + x2 and X = X1/2x1/2, we have that
Amax (Yy)) = Amax (U) (3U S Smaxx (xa) C (,) L
(8)
where the first inequality follows from the same argument provided in the proof of Theorem 2.5 in Appendix B.1 (specifically, see Lemma B.2); the second inequality follows from Amax (X,) S L together with Amax (B) ( (B)) = Amax (1) 1. Below we apply Theorem 2.5 and 2.2 with respect to the matrices Y11. i E [m]] and 22, E [m], re- spectively, and use the facts (7) and (8) in the process.
TT Xx = x. Xx1 + 2x X1/2 + 3/2 X
Proof outline. For larger values of 3 > O, the dimension of the subspace L1 (3) is smaller (or at least no larger). Ac- cordingly, applying Theorem 2.5 with respect to matrices Yn, i [m]. which capture the behavior of the matrices X i e [mi] on the subspace L1 (5), we should be able to guar- antee a better one-sided approximation on L (3) for larger values of B, as captured by the factor of intdim (ondim(E[Xx) [E[X],9) ()) in Lemma 3.2 below. This intrinsic dimension factor ap- pears (as opposed to n)) because the dimension of L, (B) is bounded above by it.
2 2 Xx, - 2 x7 Xxi v
/x
Xx² + 2 Xx²
a =Vax Xox -V Xx2)
(9)
where the inequality follows from the Cauchy-Schward in- equality. Taking 33 to be sufficiently small, we can ensure that 22 Xxx is sufficiently small by Lemma 3.3, and we can ensure that x. Xx, 1 is sufficiently large by Lemma 3.2.
Remark 3.4. To ensure that 2; Xx1 is sufficiently large, it seems critical that we use the one-sided approximation
Lemma 3.2. For B >> 0 such that (3) + 0, and d E (0, 1]. holds that
3i Xx1 > (1 - <) E []æ; provided by Lemma 3.2 (which ultimately traces back to Theorem 2.5), rather than a
P(Br e (1(9) \ (0) Txxx S (1 5)x T E(X]a)
weaker lower bound of the form 2. Xxx/ /1 1|2 > (1 (1 which could be obtained from Theorem 2.4. When || is small, the weaker bound is not helpful, but we can regardless apply the one-sided approximation as long as æ B[X]ar is sufficiently large.
S intdim (E B) 8/22))
Proof. See Appendix B.2.
LI
4. Approximation guarantee for simple randomized rounding
Lemma 3.2 provides us with one-sided approximation guarantee for the directions Si (3), while Theorem 3.1 states a weaker guarantee for the larger set of directions (E 2 Si Accordingly, we work towards showing that Lemma 3.2 implies the weaker guarantee for the directions Si (E( 3) \ (3).
We present our main approximation result for simple ran- domized rounding in Theorem 4.1 below. The theorem states that simple randomized rounding provides a constant- factor approximation if INC = Q In k)), where recall that where R := max4e[m] tr (r(A.). Note that the theorem does not account for the fact that Zround should be feasible for (1), i.e., satisfy ||=round llo < k; we address this issue further below. Also, note that the constants specified in the theorem are chosen to make the verification of the proof more conve- nient. For instance, the constant in the lower bound on INC could be increased to obtain better approximation factor.
We are only missing the following ingredient. Applying Theorem 2.2 to the matrices Y2,, i mm], which capture the behavior of the matrices X, i E [m] with respect to the directions S2()), we can ensure that the quadratic form x Xx is not too large in each direction x E (2)). Because Theorem 2.2 provides an intrinsic dimension inequality. we obtain an intrinsic dimension inequality:
6

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
Theorem 4.1. Suppose that & 2 2. IfINC 2 22422Rin
we have that F[] Frounalo S k) 2 Pround < 1/2, where the second inequality follows from the fact that Zround |lo + Z is Poisson binomial random variable with mean k.
then
m
IP Xunin
M
2
(eronnd 2 (1/4)OPT) 61//4.
With (10) in hand, we obtain the following corollary to Theorem 4.1:
Proof. See Appendix B.5.
Corollary 4.3. Suppose that 2 IfTNC 2 24 Rlnk,
Our proof of Theorem 4.1 utilizes Theorem 3.1 and follows the argument outlined in Subsection 1.1. Recall that W := maXi[[m] (A,) Following a similar proof, one could instead apply the matrix Chernoff inequality provided in Theorem 2.4 to obtain the condition INC = S?(W In nn), which unlike our guarantee, does not shed light the k < n setting. However, the condition INC Ω(W In does depend on W < R. If the augmentation matrices are rank- one matrices, then R = W, and there is no advantage to this alternative condition.
then
m
P (Amiu (M +
>
(round) (1/4)OPT, ||=11o - k) 1=1
2 29/64.
5. Discussion
To further motivate Theorem 4.1, it is worthwhile to note that it is possible that INC Rk. Consider the following instance of the max-min eigenvalue augmentation problem (I). Suppose that the augmentation matrices are rank-one matrices, in which case R = W. Further suppose that M = Wk(T - eieT) ) where e1 is the 1st standard unit vector. Finally suppose that there are ls (amongst the m) augmentation matrices that are all equal to W Weiej- Then, is clearly optimal select these k matrices. It follows that INC- Wk,, which for sufficiently large l implies that INC > 224g2Rln k. from which we can conclude from Theorem 4.1 that simple randomized rounding provides factor approximation. However, no matter how large we take k. we can always take n such that & << Inn, n, in which case INC- = Wk does not imply that INC O(W In..
We considered the max-min eigenvalue augmentation prob- lem (1) and focused on the setting in which k < n. We showed that simple randomized rounding provides a constant-factor approximation if the optimal increase is sufficiently large. specifically if OPT -minn( SRR In k); see Theorem 4.1. To establish the guarantee, we derived matrix concentration inequality that is of inde- pendent interest; see Theorem 3.1. The inequality can be interpreted as an intrinsic dimension analog of the matrix Chernoff inequality for the minimum eigenvalue of sum of independent random PSD matrices.
There are number of directions that we aim to pursue for future work. First, we aim to investigate the extent to which we can improve the dependence on in Theorem 3.1. It is also of interest to determine the extent to which Theorem 4.1 is tight. One would imagine that it is tight (up to a constant factor) given that Theorem 2.4 is tight; see (Tropp et al., 2015). Finally, we plan to explore the empirical approximation performance of simple randomized rounding through computational study.
Feasibility of 2round- To establish guarantee that addition- ally ensures Zround is feasible, we make use of Proposition 4.2 below. (Curiously, we were not able to find state- ment/proof of this fact in a more recent reference.)
Proposition 4.2 (JJogdeo & Samuels, 1968), Theorem 3.2). Suppose that the mean μ E[X] of Poisson binomial random variable X is an integer. Then, μ is the median of X.
Acknowledgments
This work was partially supported by the ONR grant N00014-22-1-26744, The authors would like to thank the anonymous referees for their helpful and constructive com- ments that allowed us to improve this paper.
Observe that the quantity ||=roumdll llo is a Poisson binomial random variable with mean ||=edp]|i I k. follows that
Frounal llo < k) > 1/2.
(10)
Impact Statement
Indeed, if |=sdpp1 k. then (10) follows immediately from Proposition 4.2. Suppose that || || < k (which is possi- ble, as we only require (Esdp- Nsdp)) be optimal for the relax- ation (2)). For a Poisson binomial random variable Z that has mean k- |2 |1 and that is independent of ||2roundllo. llo.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
|

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
References
Kolla, A., Makarychev, Y., Saberi, A., and Teng. S.-H. Sub- graph sparsification and nearly optimal ultrasparsifiers. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 57-66, 2010.
Allen-Zhu, Z., Li, Y., Singh, A., and Wang, Y. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Prociea Programming, 186:439-478, 2021.
Lau, L. and Zhou, H. A local search framework for experimental design. SIAM Journal Computing, 51(4): 900-951, 2022.
Avron, H. and Boutsidis, C. Faster subset selection for ma- trices and applications. SIAM Journal on Matrix Analysis and Applications, 34(4):1464-1499 2013.
Mosk-Aoyama, D. Maximum algebraic connectivity aug- mentation is np-hard. Operations Research Letters, 36 (6):677-679, 2008.
Che, E., Jiang, D. R., Namkoong, H., and Wang, J. Optimization-driven adaptive experimentation. arXiv preprint arXiv:2408.04577 04570, 2024.
Ogiwara, K., Fukami, T., and Takahashi, N. Maximizing algebraic connectivity in the space of graphs with fixed number of vertices and edges. IEEE Transactions on Control of Network Systems, 4(2):359-36,, 2015.
Civril, and Magdon-Ismail, M. On selecting a maxi- mum volume sub-matrix of matrix and related problems. Theoretical Computer Science, 410(47-49):4401-44 -811,, 2009.
Pukelsheim, F. Optimal design of experiments. SIAM, 2006.
Revilla Sancho, L. experDesign: Design Experiments for Batches.
De Abreu, N. M. M. Old and results algebraic nectivity of graphs. Linear algebra and its applications, (23(1):53-73,2000
Somisetty, N., Nagarajan, H., and Darbha, S. Optimal robust network design: Formulations and algorithms for maximizing algebraic connectivity. IEEE Transactions on Control of Network Systems, 2024.
Derezinski, M., Liang, F., and Mahoney, M. Bayesian exper- imental design using regularized determinantal point pro- cesses. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, vol- ume 108 of Proceedings of Machine Learning Research, pp. 3197-3207, PMLR, 2020.
Tantipongpipat, U. X-regularized a-optimal design and its approximation by X-regularized proportional volume sam- pling. CoRR, abs/2006. 1116.11112,,,,01111 2020.
Tropp. J. A. et al. An introduction to matrix concentra- tion inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
Fedorov, V. V. Theory of optimal experiments. Elsevier, 2013.
Fiedler, M. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298-305, 1973.
Wei, P., Chen, I.,, and Sun, D. Algebraic connectivity max- imization of an air transportation network: The flight routes' addition/deletion problem. Trunsportution Re- search Part E: Logistics and Transportation Review, 61: 13-27, 2014.
Ghosh, A. and Boyd, S. Growing well-connected graphs. In Proceedings of the 45th IEEE Conference Decision and Control, pp. 6605-6611, IEEE, 2006.
Goos, P. and Jones, Optimal design of experiments: a case study approach. John Wiley & Sons, 2011.
Hastie, T., Tibshirani, R., Friedman, J. H., and Friedman, H. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
Jogdeo, K. and Samuels, S. M. Monotone convergence of binomial probabilities and a generalization of ramanu- jan's equation. The Annals of Mathematical Statistics, (4):1191-1195, 1968.
Kim, Y. Bisection algorithm increasing algebraic connec- tivity by adding an edge. IEEE Transactions on Automatic Control, 55(1): 2009.
8

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
A. Omitted proofs
B. Algebraic connectivity minimum eigenvalue
Lemma B.1. Let G be a simple undirected graph. Then, A2(L) = Amin (L 117), where L is the Laplacian of G.
Proof. Because L positive semidefinite and L1 0, it holds that an eigenvector of with eigenvalue Amin (L) O. We consider two cases:
Case Suppose that is disconnected. Then A²(L) = 0, and it follows that there is an eigenvector u of L that has
eigenvalue 0 and is orthogonal 1. Hence (L + 11 )u = 0, implying that Amin (L 11 0, as + 11 T is positive semidefinite. Thus (L)
Amin (L + ).
Case 2. Suppose that is connected. Hence (L > 0. Let Mi..... Un be orthonormal cigenvectors of with eigenvalues (L) S S X, (L), respectively. Because Amin (L)
(L). it follows that u1
Note that (L. + 11 1 ml, and (L+ 11 )u,; (L),, for each 2 < S n. As result, the eigenvalues of L. 11 (2)),. ..... A, (L). Thus, the desired result follows from the fact that (L) S n.
B.1. Proof of Theorem 2.5
If Umin 0, then the theorem trivially holds. Hence, suppose that jmmnn > Let E[X]. Because Amin (Q) - Mmin >> the matrix Q is positive definite. Accordingly, can factor Q as Q Q1/221/2 12, where Q1/2 is
invertible matrix.
Define the random PSD matrices Y; == Q 1/2 1122X--110 1/2, i E [m]] Also, define Y :- > Y; Q- x X112xx-11// 1/2.
Our proof of Theorem 2.5 follows from applying Theorem 2.4 to the matrices Y,, i E [m]. Towards this end, note that B|| = 110///((X))) ( 1/22 = =T, and hence, Amin (T[( = 1. Also, make note of the observations captured in Lemmas B.2 and B.3 below.
Lemma B.2. A (Y)) S T./ Pmii for each [m].
Proof. Note that for each E [m]] we have that:
Amax (Y:) max
x TY
#ESn-1
TT-11/2 -112 1/2x
max xES--1
T QQ11/2X,Q -1/2gg xm5a-1
max 11211/2/112
max
11Q -1/12x11
max yESu-1
D X(y)
max x TQ- ZESa-1
Amax Xx) Amaxma( (Q-)
S L/ Pmius
where the third equality follows from the change of variables 1==1-=//11--/// 1/2xx]] and the last inequality follows from (X,) < L and Aunax (Q- ) = 1/ Amii (Q) = 1/mmin.
Lemma B.3. (X x (1 { = (V * (1 T).
Proof. It is sufficient to show that {X> > (1 -1-63 []]] = (Y > (1)) Suppose that X > - cx)]] For x e S we have that
TYr= 1120--111--010
> (1 -1-68 c)x \/2 1/2 (1- -1-0) c)x TIx
where the inequality follows from X > (1 - (1-e)E[X) E[X]. Thus, >
1 we have that Suppose that Y (1 (1- For
x Xx x T /2 12 > ()-c)x² T Qz = (1 T1 E[X]a,
where the inequality follows from Y (1 - T. Thus, X - [Ix)
9

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
We now prepared prove Theorem 2.5:
Theorem 2.5. From Lemma B.3, have that
P(X y (1 - ( = P(Y y (1 - e)) = P(Amin 1 ( -)) S ne Ammn
where the inequality follows from Theorem 2.4, which can be applied due to Lemma B.2.
B.2. Proof of Lemma 3.2
Lemma 3.2. For notational convenience, we suppress dependence on and write [16), (1)), (1)), (1()), and (1
1, In, S1. U1 and A1, respectively.
First, note that tr(B[X]) 2i d Di d and hence:
141/, where the second inequality follows from the definition of /
14
Intdim(B[X],5))
(11)
3
From the definition of L1, we have the following sequence:
P(Ex E L, \ [0} : x T Xx - (1 - 8)x E[X]z)
P(am 4 \ {0) x U, XU s (1 B(XJUU)
P(3T E RR 1 {0) x 1i S (1 - 6) A
|e 5 Amin (2L)
intdim (B[X], 3)e 8 minser, \/(22)
intdim (atdim(E[X],3550 8)c 6 (/((2))
where the second equality follows from U UTUAUU A1; the first inequality follows from applying Theorem 2.5 with respect to the matrices Yn, i [m]; the second inequality follows from (11) and Amin ( min A; and the last inequality follows from the fact that 2 2 3 for i I1.
B.3. Proof Lemma 3.3
Lemma 3.3. For notational convenience, we suppress dependence on B in the same spirit as the proof of Lemma 3.2. Take any index 11, and let B[Y2] + Bu,uJ. We introduce V to apply Theorem 2.2 with V. Note that V > [[]] because B > 0. Also, note that the eigenvalues of V are given by dn E T2, and B, so Amaze (V) 3 because Å; < 8 for each i E Tz by definition. Finally, note that
tr (v) = (E(2)) + tr(22) +
3 Σ r tr(E]
(12)
IEI2
1=1
where the inequality follows from 3 Σ > for j E 41. From the definition of S2,
TP max xE3,
Xx 1 P max π UU. XU 2 1.3
-1
Amaxe (02) t. P
P Xumaxe (Yz) Dimaae AV)
< 2 intdimm(, Amax (V)) Arann (V)/I. taana(V)
2 tr(V)
Dimax (V)LL
Amaxx (V)
2 (r(E(X)) L3/L
1
< 2 intdim (E[XX, 13)e 43/L
10

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
where the first inequality follows from Theorem 2.2 with respect Y/2- E [m]] (here the supposition that
t 2 B//B + L/ Amax (V (V) by Amax (V) = the second inequality follows from (12) and Amax (V) = A and the last inequality follows from 2 e?.
B.4. Proof of Theorem 3.1
Theorem 3.1. Let 3 = e'a/ For notational convenience, suppress dependence on / and for each j [2] write
(3), (8), S,(3), (B),, and (3(3) as 1,. L3. Sj. Uj and Aj. respectively.
First, note that because 3 < S Amax (X), it holds that 1 + 0. Thus, from Lemma 3.2 with & = c/4, we have that:
P(Er E L \ (0) : x Xx $ (1 c/4)x [[X
S (indiim([[X]] B)e -
16c (a(dim(E(X]))) ca)e a'a((522e
(13)
where the equality follows from 8 ==2aa(166e)
Suppose that S2 = 0. Then, it holds that S = 5n-1, From the definition of S(E[X],
F( E ( o) x Xx - ()-
P(rr S(E[X], a) : Xx S (1 - c) B[X]a)
$ P(ar $1 x Xx S (1 - c)x [(
< P(3r E S : T Xx < (1 e/4)zz E[X]x)
16e intdim (a) -d0
where the second inequality follows from S Sn S(E[X], a). and the last inequality follows from (13). Thus, the desired result follows, so let us assume that S2 0.
Then, note that L/B 16. 2 < because 2 16e L/e² L/e² (recall the conditions in the theorem statement). Hence, we can apply Lemma 3.3 with t = e² to obtain that
max x Xxx 2 233) < intdiim 8/8 rES2
32e (addimE[[X],rm (a)e
(14)
where the equality follows from 3 = ===a((16e2) Accordingly, for the following conditions:
Xxx > (1 (1-e/4)x* TEX]a, Vo E L \ x T Xx 23,
(15)
Va E S2,
(16)
we have from (13) and (14) that
P((15) and (16) hold)
16e² intdim -d0 -2e intdim(E[X)) (a)xx Pa/(116))
> 2 intdim(EE(X), Pa) (a) 2 (0022/10122))))
where the second inequality follows from - aa/(166) < (31222(312221) Thus, taking x E S(E[X), a) and assuming that (15)-(16) hold, it is sufficient to show that
x T Xx > (1- c)a.
(17)
Because I is the orthogonal complement of Lz, there exists a point #1 Ln and point 22 Loz such that æ1 + 52.

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
Because x o))
S B[X] x TUATA x
x U'UAA x x U2A2U2 x
S xx SUTUAAUT + Amax(U2A2(g])
-xTUTAIU max A sEL2
S 8 x UAUUT+++ x E
(18)
where the second inequality follows from a E sn-1; the third equality follows from the fact that the eigenvalues of U2A2U2 are d; E I2; and the last inequality follows from the definition of Jz. Rearranging (18) gives
(1 2 2/(16e²))a = x T UAAU, x
-UUUAUUTA 21
=ITUAUT Ø1
x [[[
(19)
where the first equality follows from x = 21 + 12 and U,T 222 = O, and the second equality follows from U,7 21 -0. From (19), we see that 21 * 0, so 21 E L1 \ {0]. Hence, from (15) we have that
Xxx
e/4)= 2 e/4)) e² (1666)))))) (1 (1- e1-4/4)a,
(20)
where the second inequality follows from (19).
We claim that
1 Xx (e2 (e2/16)a.
(21)
If i2 0, then clearly (21) holds. So, suppose that 22 # 0. Because ||> I 1 as well, we have that
2 Xx
Xxa
< < = (2211)aa.
where the second inequality follows from (16).
Finally, recall from (9) that
x Xx
(1 xxxxx Xx1 - V
> (V(1- - c v(e2/16)))
= (1 - - e²/ 24/4ja
> (1 c)a.
where the second inequality follows from x. Xx > (1 - e/4) > (1/16)e > xxJ Xxz; recall (20) and (21). Thus, (17) holds, and the proof is complete.
B.5. Proof of Theorem 4.1
Theorem 4.1. Let C' = 214,2, so we have INC 2 CR We apply Theorem 3.1 with respect to the random PSD matrices X; = |Fround],A,, . i E [m]. We take L = max4e[m] Amax (A₂) (which is clearly a valid choice), 1/2, and = IN.. Verifying the final condition of the theorem, we have that
16c² L/22 5 21422 S INC S Amaax Σ (RodpkA.))
5
12

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
where the second inequality follows from INC 24 2 64e (recall R2 L), and the last inequality follows from the fact that INC Amiu (M D/ (eddp) A, Amin (M) I Amax - | (sddp)
Thus, the last condition of Theorem 3.1 holds, and we obtain that
P Bx E S Ae, ( T
Σ
Ground):A)) 1:11) (1/4)INC)
1=1
m Σ
< 48e intdim
Ae (1/8)INC) (NC/(2'(22L)
384e intdim
Eedpli A,C) INC/(2"+e2L)
< 384c² intdim
Redplss As, CRInk e- RRin/LL
384
tr
Σ Rink
m i==
e--
214
384
k
In
214
In k:
128
In l:
3
(22)
64
where the second inequality follows from the supposition INC 2 CR and C 21 the third inequality follows from I S Rk and S and the last inequality follows from In 2 (1/2) (as 2).
tr(E." th (2adp)))))))) S R
From (22), it holds with probability at least 61/64 that
Irroundd A1)x > (1/4)INC Vx S Σ AsdpliA, (1/2)INC..
(23)
Fix x E 5m-11 Then, it is sufficient to show that
TT(Ma M +
Fr. (1/4)OPT
(24)
1=1
under the assumption that (23) holds.
Case 2.1. Suppose that æ & S(E S [zddpl (1/4)INC). Because & E Sn-1
m S S < Σ 2=1 where the second inequality follows from $ S(E [sedpliA (1/4)INC). Now observe that
m
Amin
M +
[2ddpl 1:A,)
(2ndpl:4i) < x Mx + (1/4)INC,
(25)
i=
xr
T
M
Fround); (: 2 xF Ma
m
Amin M +
32dp (. (1/4)INC
Amin(M) + (3/4)INC
2 (3/4)(>miin(M)) INC)
m
(3/4))min (M Σ
[Zedpli As
(3/4)OPT (1/4)OPT
13

---

Simple Randomized Rounding for Max-Min Eigenvalue Augmentation
where the strict inequality follows from rearranging (25), while the first and last equalities follow from the definition of INC.
Case 2.2. Suppose that a E S(2 T i-
1 [FddpiiA, (1/4)INC). Then we have that
x T M +
Fround]e
Amin (m)) + (1/4)LNC
2 (1/4) (M) +INC)
-(144)mmi (M + >
[zdpp] Az
2m
2 (1/4)OPT,
where the strict inequality follows from T definition of INC.
Mx 2 Amin (M) (as 5m=1) and (23), and the equality follows from the
14


Reviews:
[{"review_id": "bwma1NIJOK", "reviewer": "Reviewer_4TVg", "summary": "This paper presents a matrix concentration on the minimum eigenvalue of the sum of PSD matrices, where the lower bound is parameterized via a generalization of the intrinsic dimension of the expected sum of the matrices. This complements the existing upper bounds e.g. from Joel Tropp's monograph on matrix concentration.\n\nThe paper shows that this concentration can be used to prove that a simple SDP relaxation + randomized rounding scheme achieves a constant factor approximation to the \"max min eigenvalue augmentation problem\" with constant probability in a regime where previous results did not give guarantees. This max min eigenvalue augmentation problem is a generalization of certain optimal design and resilient graph design problems.\n\nWhile the regime that this paper studies appears to be less common invocations of these optimal design and graph problems, but seem like natural problems to study.\n\nPaper is entirely theory; no experiments at all.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our manuscript! Below we include our responses for each relevant section. We focus most of our response on your main line of inquiry. \n\n${\\bf \\text{Theoretical Claims/Other Strengths and Weaknesses:}}$  \n\nThese are greats points. In what follows, we aim to shed light on them and discuss how we can address them in the manuscript. Hopefully this ties everything together. \n\nConsider [Lines 144-156, right]. These lines state that the minimum eigenvalue is a special case of the main quantity of interest when $\\alpha = \\lambda_{\\mathrm{min}}(\\mathbb{E}[X])$, as you point out in your 2nd comment under Theoretical Claims. While this is the case, our results do not imply anything interesting when $\\alpha = \\lambda_{\\mathrm{min}}(\\mathbb{E}[X])$; this seems to be what you are asking about in your 2nd and 3rd comment. Our writing then seems to be unintentionally misguiding. Our concentration inequality is only interesting when $\\alpha > \\lambda_{\\mathrm{min}}(\\mathbb{E}[X])$. Per this work, it is best to think of main random quantity $\\min_{x \\in S(\\mathbb{E}[X],\\alpha)}x^{\\top}Xx$ as being intimately related to the minimum eigenvalue $\\lambda_{\\mathrm{min}}(X)$, but not ever the minimum eigenvalue itself. We can add clarification here as well as a forward references to later parts of the work for more detailed clarification (specifically, see the paragraph that follows the next two.) \n\nRegarding your comment about intrinsic dimension, we can modify the discussion of Remark 2.3. Our notion of intrinsic dimension provides an upper bound on Tropp’s intrinsic dimension. The upper bound is convenient for lower bounding $x^{\\top}Xx$ over $x \\in S(\\mathbb{E}[X],\\alpha)$, rather than upper bounding $x^{\\top}Xx$ over $x \\in S^{n-1}$, but it also generalizes Tropp’s definition, so we refer to it as intrinsic dimension. \n\nAs you point out, it would be nice to understand how the novel concentration result compares with the minimum (and maximum) eigenvalue concentration result. In this spirit, it is natural to wonder why we cannot just apply the existing minimum eigenvalue concentration result? To position the reader’s thinking, we can explain after Theorem 2.4 why we cannot upper bound (6) with the matrix Chernoff inequality presented in Theorem 2.4. If there is a direction $x$ per which $x^{\\top}\\mathbb{E}[X]x = 0$, and hence $\\lambda_{\\mathrm{min}}(\\mathbb{E}[X]) = 0$, then Theorem 2.4 provides us with a trivial guarantee. The existence of such a direction, however, should not impact upper bounding (6). One might hope that we can directly apply Theorem 2.4 to the set $S(E[X],\\alpha)$, but the set is not a subspace (as seen in Figure 1), so we cannot do this. Although, this idea is exploited in the proof of Theorem 3.1; see Lemma 3.2. \n\nTo address your point that the core result needs more discussion (and positioning with respect to the other concentration results), we can include the following discussion following Theorem 3.1. \n- Theorem 3.1 tells us that we can guarantee that $x^{\\top}Xx$ is larger on a smaller set of directions $x \\in S(\\mathbb{E}[X],\\alpha)$ per which the quadratic form $x^{\\top}\\mathbb{E}[X]x$ is larger. Accordingly, there is a tradeoff: For large values of $\\alpha$, we can guarantee $x^{\\top}Xx$ is larger, albeit in a smaller number of directions $x$. Ultimately, in the proof of Theorem 4.1, we choose $\\alpha$ to optimize this tradeoff.  \n- Consider the extreme case in which $\\alpha = \\lambda_{\\mathrm{min}}(\\mathbb{E}[X])$, which is still possible under the assumptions of Theorem 3.1. Using the fact that $\\mathrm{tr}(\\mathbb{E}[X]) \\geq n \\lambda_{\\mathrm{min}}(\\mathbb{E}[X])$, it then follows that Theorem 3.1 provides a weaker guarantee than Theorem 2.4.\n\nFollowing Theorem 4.1, we could discuss in slightly more detail how the proof follows from carefully choosing alpha based on the tradeoff inherent in Theorem 3.1 discussed above, i.e. taking $\\alpha = \\Omega(R ln k)$. \n\n${\\bf \\text{Other Comments Or Suggestions:}}$ \n\nWe would like to include essentially all of your recommendations. We just make note of two spots in which we would like to keep the manuscript as is. \n\n- 1. Adding the matrix of all ones “pushes” the eigenvalue for the eigenvector of all ones to the top of the spectrum so that we can consider the minimum eigenvalue instead of the second smallest eigenvalue. \n- 9. At this point, we are hesitant to make this update so that we do not introduce any errors in the proofs that follow in later sections.", "claims_and_evidence": "The paper is entirely theory.\n\nThe paper can be partitioned into two parts: proving the matrix concentration result, and proving that the concentration result is helpful for the max min eigenvalue augmentation problem.\n\nMost of the paper focuses on the former, and shows how a certain partitioning of the unit sphere plus the existing matrix concentration literature can be used to prove this new minimum eigenvalue concentration result. It's a short and clever series of arguments.\n\nThere's a smaller section of the paper that argues how the SDP relaxation + randomized rounding algorithm provides a good (constant factor) solution to the max min eigenvalue augmentation problem, which seems to rely on relatively standard machinery as far as I can tell. It's good, but the emphasis is on the matrix concentration imo.", "methods_and_evaluation_criteria": "There's no empirical evidence in this paper.\n\nNot a problem per se, just a statement.", "theoretical_claims": "I checked some of the proofs in detail, but not all. They seem essentially correct.\n\nMy main interest in examining the theoretical claims is in better understanding how the core novel concentration result, Theorem 3.1, compares directly with the existing results on both 1) minimum eigenvalue concentration without an intrinsic dimension term and 2) maximum eigenvalue concentration with an intrinsic dimension term. The claim seems to be correct, but I don't have a very clear sense of how it really compares to the prior work.\n\nIn particular, there's a few nonstandard terms in here:\n1. The definition of intrinsic dimension used in their result is a generalization of the standard definition. In particular, the intrinsic dimension of a matrix, as defined in the Tropp monograph, is the ratio of trace to spectral norm. In this paper, it's the ratio of the trace to some parameter $\\alpha$ which is less than or equal to the spectral norm. It's not nearly as intuitive to think about what this generalized intrinsic dimension is or should be.\n2. They don't directly tackle the minimum eigenvalue problem. Instead, they do something more general I suppose. They have a parameter $\\alpha$. They show that for all vectors $\\vec v$ such that $\\vec v^\\intercal E[X] \\vec v \\geq \\alpha$, we have $\\vec v^\\intercal X \\vec v \\leq (1-\\varepsilon)\\alpha$ with high probability, where $X$ is our sum of independent PSD matrices. This concentration result only holds for values of $\\alpha$ between $O(L / \\varepsilon^2)$ and $O(\\| E[X] \\|_{op})$, where L is a uniform upper bound on the operator norms of each summand. Further, the failure probability scales with $\\frac1{\\varepsilon^2 \\alpha}$. When $\\alpha = \\| E[X] \\|_{op}$, this should recover the usual definition of intrinsic dimension, but in this case very few vectors $\\vec v$ will be covered in this theorem statement. It's not made 100% clear how this result translates to a genuine minimum eigenvalue guarantee, and I think the paper would benefit from a bit more discussion of this.\n3. I note that the authors do have some light discussion of this, but it feels insufficient to me. Adding an appendix to think about the shape of this concentration result for (e.g.) and IID sum of terms and meditating on when a minimum eigenvalue guarantee follows would be rather beneficial in my perspective.\n\nBut the claims seem to be correct. The core results just needs more discussion imo.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "This concentration result seems like it might be a powerful short little result. This is why I harped on it in my review above. I don't fully appreciate how this result compares to the existing machinery, and I think the paper would benefit from having more of a discussion on this point.\n\nI'd like to better understand that concentration in order to better understand the potential broader applicability of such a result.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper has nice writing, especially in its proof sketches. It's pretty intuitive, and feels nicely self-contained as well.", "other_comments_or_suggestions": "List of typos and recommended edits. Feel free to ignore anything and everything here.\n\n1. [Line 87, left] Shouldn't L be a PSD matrix? So shouldn't you have to subtract the all-ones matrix?\n2. [Lines 95-101, right] While true, I'm not clear what's the point of the end of this paragraph.\n3. [Lines 126-132, left] This \"larger/smaller\" language is awkward throughout. Say something like \"If INC increases, then the number of quadratic forms x'Ax that are Omega(INC) decreases. More precisely, letting S = {...} be the set of directions (we refer to unit vectors as directions), we have that for any gamma ....\"\n4. [Lines 160-162, left] This break between paragraphs is awkwards and repetitive. Rephrase.\n5. [Figure 1] Add more to the caption. Explain that $\\alpha = \\gamma INC$ maybe, and that increasing $\\gamma$ makes the black boundary smaller. Also, make the colors print better in black and white\n6. [Line 131, right] Define the intrinsic dimension you use directly with a clear definition. intdim(A,alpha) = tr(A)/alpha.\n7. [Line 202, left] Specify page 61 for the thm statement, since it's not exactly the statement of thm 5.1.1. Same for theorem 2.4.\n8. [Theorems 2.1, 2.2, 2.4, 2.5] I'd try to be more consistent between always writing these bounds in terms of t or 1-eps. Either is fine, but being more consistent would help.\n9. [Line 210, right] This leftrightarrow symbol is kinda confusing here, because it sounds like you're more strongly asserting this iff claim. I would remove the leftrightarrow and replace it with parenthesis, so it instead says something like \"(i.e. X > (1-eps) E[X])\".\n10. [Line 229, left] Remove \"a\"\n11. [Line 230, left] Remove first \"i \\in [m]\"\n12. [Thm 3.1] Discuss when such an alpha exists. Because it doesn't always exist.\n13. [Line 271, left] remove subscript on X_i in E[X_i].\n14. [Line 291, left] Subscript on L should be 1 not j.\n15. Consider having a more concrete theorem statement for E-optimal design or algebraic connectivity augmentation problem. It's just a corollary. But it'd be good to write out.", "questions_for_authors": "See theory discussion -- what's the right way to think of the underlying concentration argument?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KG2SQyUsuL", "reviewer": "Reviewer_XV8x", "summary": "This paper studies the max-min eigenvalue augmentation problem: choose a subset of at most $k$ PSD matrices $A_i$ to augment a PSD matrix $M$ to maximize the minimum eigenvalue of $M + \\sum_i A_i$.\n\nThis problem generalizes the Bayesian E-optimal design (where certain experiments need to run together) and maximum algebraic connectivity augmentation problems (to $k < n$).\n\nThis paper gives a simple randomized rounding method of an SDP relaxation of the max-min eigenvalue augmentation problem, and proves that if the optimal increase (OPT - $\\lambda_{min}(M)$) is sufficiently large, then the rounding method gives a constant-factor approximation.\n\nThe analysis depends on a new Chernoff-type matrix concentration inequality for the minimum eigenvalue of a sum of independent random PSD matrices.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our manuscript! Below we include our responses for each relevant section. \n\n${\\bf \\text{Questions For Authors:}}$\n\nWe left the lower bound as a direction for future work, but since our original submission, we have realized that it is tight and would be happy to include this result. The result more-or-less follows from the fact that the matrix Chernoff inequality for the minimum eigenvalue (i.e., Theorem 2.4) is sharp (see 5.1.2. of Tropp). More specifically, the idea is to take $M$ to be a diagonal matrix whose first $n-k$ diagonal entries that are large and whose last $k$ other diagonal entries equal to $0$. We restrict the augmentation matrices to the las $k$ dimensions and take them as specified in Tropp. We could include the result as a short proposition and place its proof in the appendix.", "claims_and_evidence": "In this theoretical papers, all claims are proved, or citations are provided.", "methods_and_evaluation_criteria": "This is a theoretical paper with proofs but not evaluation.", "theoretical_claims": "I checked the claims up to Section 2, and did not find any problems.", "experimental_designs_or_analyses": "This paper does not have experiments.", "relation_to_broader_scientific_literature": "This paper proves a new Chernoff-type matrix concentration inequality for the minimum eigenvalue of a sum of independent random PSD matrices, while the literature only has such inequality for the maximum eigenvalue.\n\nThis paper gives an approximation algorithm for the max-min eigenvalue augmentation problem, which generalizes the Bayesian E-optimal design and maximum algebraic connectivity augmentation problems.", "essential_references_not_discussed": "I am not aware of essential references not discussed in this paper.", "other_strengths_and_weaknesses": "(As stated in the paper and in the summary above,) the randomized rounding algorithm is very simple: include a matrix $A_i$ with probability exactly the value in the SDP relaxation. And the analysis appears to be intuitive.\n\nHowever, this reader may appreciate some discussion on the technical restriction on the optimal increase ($OPT - \\lambda_{min}(M) = \\Omega(R\\ln k)$): whether this restriction is necessary (e.g., due to lower bounds), or whether it arises naturally in practice.", "other_comments_or_suggestions": "This paper is very well written, and I don't have suggestions.", "questions_for_authors": "For the technical restriction on the optimal increase ($OPT - \\lambda_{min}(M) = \\Omega(R\\ln k)$), besides “it works”, is it necessary (e.g., due to matching lower bounds), or is it a mild assumption in practice?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No ethical review needed."}}, {"review_id": "yLyEcSntCa", "reviewer": "Reviewer_gow2", "summary": "In this work, the authors provided a new algorithm for the max-min eigenvalue augmentation problem. The method is able to achieve a constant approximation to the optimal value with a constant probability, given that the augmentation improvement is sufficiently large. The results are established by proving an extension of the matrix concentration inequality. Please see the following sections for my detailed comments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our manuscript! Below we include our responses for each relevant section. \n\n$\\text{Other Comments or Suggestions:\\}$ \n1. Yes, nice catch, we should have 1 instead of j here; we can make this update. \n2. We agree that the exposition would benefit from this discussion. Regarding Lemma 3.2, the dimension of $L_1(\\beta)$ is bounded by the intrinsic dimension. Regarding Lemma 3.3, there is a typo in the sentence preceding the lemma: it should read “Because Theorem 2.2. provides…” instead of “Because Theorem 2.4 provides…”. This sentence would then explain how intrinsic dimension comes into play. \n3. Our reasoning is for $29/64$ is as follows. Taking $E_1$ and $E_2$ to be the events of interest, we have \n$$P(E_1 \\cap E_2) = P(E_1) + P(E_2) - P(E_1 \\cup E_2) \\geq 1/2 + 61/64 - 1 = 29/64.$$\n4. We agree with you (and ourselves for that matter!). We have already run some synthetic  (maximum algebraic connectivity and bayesian optimal design) experiments along these lines. We would be happy to include them, assuming that it is within scope; there is room for a small additional section, but we are not sure if it is standard to incorporate something like this at this point. We compare against Federov’s exchange algorithm because (1) the algorithm is the primary algorithm used in state-of-the-art software implementations, and (2) the algorithm can readily be applied in the general-rank and $k < n$ setting. Our main observations: Federov’s algorithm typically provides a better approximation, but it can take a significantly longer time to find an approximation that is on par with simple randomized rounding (even accounting for the SDP solve). Perhaps this would be better suited for future work.", "claims_and_evidence": "Due to the time limit, I did not check the correctness of the theory, except those briefly mentioned in the main paper. The theoretical claims seem correct by checking the main paper.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense to me.", "theoretical_claims": "Due to the time limit, I did not check the correctness of the theory. The theoretical claims and the proofs in the main paper seem correct.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "This paper is related to the topic of ICML conference and should be interesting to audiences from machine learning and numerical methods fields.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Please see my comments in other sections.", "other_comments_or_suggestions": "- Line 275, left column: If $\\beta$ is larger, I think only $L_1(\\beta)$ will have a smaller dimension? This seems to be consistent with the fact that Lemma 3.2 only considers $L_1(\\beta)$.\n\n- It would be better if the authors could explain how the bound changes from the dimension $n$ in Theorem 2.5 to the intrinsic dimension. The same comment applies to Lemma 3.3.\n\n- I wonder why the probability bound in Corollary 4.3 is 29/64 instead of 61/128?\n\n\n- As pointed out by the authors, it would be important to include empirical results of the proposed algorithm. Although the contributions of this paper is on the theory side, it is helpful to show the value of the proposed algorithm by exhibiting the empirical performance. It would be particularly interesting to compare the new algorithm with existing algorithms designed for a specific application, such as the Bayesian E-optimal design problem and the maximum algebraic connectivity augmentation problem.", "questions_for_authors": "Please see my comments in other sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X3IXJilaVP", "reviewer": "Reviewer_Zjro", "summary": "This paper researches the $\\textbf{max-min eigenvalue augmentation}$ problem: given symmetric PSD matrices $M, A_1, \\cdots, A_m \\in \\mathbb{R}^{n \\times n}$ and a positive integer $k < m$, the goal is to solve the following optimization problem $$\\max_{z \\in \\\\{0, 1\\\\}^m, \\\\|z\\\\|_0 \\le k} \\lambda\\_{\\min} \\left( M + \\sum\\_{i=1}^{m} z_i A_i \\right),$$which is a general case of $\\textbf{Bayesian E-optimal design}$ and $\\textbf{Maximum algebraic connectivity augmentation}$. Since this problem is NP-hard, this paper turns to solving its relaxed version $$\\max\\_{z \\in [0, 1]^m, \\eta \\in \\mathbb{R}} \\left\\\\{\\eta \\bigg| M + \\sum\\_{i=1}^{m} z_i A_i \\succeq \\eta I, \\sum\\_{i=1}^{m} z_i \\le k \\right\\\\},$$which is an SDP problem, and utilizes the randomized rounding technique to get an approximate solution. Specifically, let $(z\\_{\\text{sdp}}, \\eta\\_{\\text{sdp}})$ be the returned solution, $R := \\max \\\\{ \\text{tr}(A_i) \\\\}\\_{i=1}^{m}$, and $$\\text{INC} := \\lambda\\_{\\min} \\left(M + \\sum\\_{i=1}^{m} [z\\_{\\text{sdp}}]_i A_i \\right) - \\lambda\\_{\\min}(M).$$This paper establishes the guarantee that if $\\text{INC} = \\Omega( R \\ln k)$, the randomized rounding method yields a constant-factor approximate solution to the original problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our manuscript! Below we include our responses for each relevant section. \n\n$\\text{Other Strengths And Weaknesses:\\}$ \n1. Yes, the optimal increase might not always be sufficiently large in practice. Although, if it is not sufficiently large, then it might also be the case that it is not worth the cost of running design experiments (BED) or removing edges (MACA). Perhaps we should mention something like this in the paper, but we also do not want to give the impression of overselling our work. \n2. We would be happy to add experiments (that we have already ran). Please see our response to reviewer gow2 (specifically, bullet number 4) for further discussion. \n\n$\\text{Other Comments Or Suggestions:\\}$\n1. We agree and will repeat them in subsequent sections. \n2. $L$ is the Laplacian matrix of the graph given in a problem instance (i.e., the graph without any edges removed). Taking $M = \\mathbf{1}\\mathbf{1}^{\\top}$ corresponds to the case in which the given graph is empty. \n3. We will update this typo. \n\n$\\text{Questions For Authors:\\}$\n\nIn the bullets below, we discuss existing theoretical guarantees and run times for BED and MACA, respectively. Note that all work that we discuss considers the case in which the augmentation matrices are rank-one matrices.\n- BED. Work on BED focuses on the setting in which $k \\geq n$. Most notably, (Allen-Zhu et al.. 2021) develop an algorithm that provides a $(1-\\epsilon)$-approximation under the condition that $k = \\Omega(\\frac{n}{\\epsilon^2})$. Because we focus on the setting in which $k < n$, our theoretical guarantee is not comparable. Regarding run times, their algorithm runs in $\\tilde{O}(mn^2)$ time, while our algorithm runs in $\\tilde{O}(m)$ time. That said, the main bottleneck is solving the SDP relaxation, so this runtime comparison is not relevant, unless one developed a method for approximately solving the relaxation in better than $\\tilde{O}(mn^2)$ time.  \n- MACA. (Kolla et al., 2010) provide guarantees for an algorithm that hold in both the $k < n$ and $k \\geq n$ settings. Their algorithm provides a constant-factor approximation  under the assumption that the optimal increase is $\\Omega(1)$, whereas our algorithm provides a constant-factor approximation under the assumption that $\\Omega(\\ln k)$, as $R = \\sqrt{2}$ in this case. The runtime of their algorithm is again larger than simple randomized rounding’s runtime.\nWe are happy to include this discussion in the manuscript. Additional references could be discussed, but these are the most relevant to your question.", "claims_and_evidence": "Yes, this paper provides a strict proof for the main theorem.", "methods_and_evaluation_criteria": "This paper is purely theoretical and doesn't include experiments.", "theoretical_claims": "The proofs seem correct since I didn't read all the proofs carefully.", "experimental_designs_or_analyses": "None.", "relation_to_broader_scientific_literature": "The max-min eigenvalue augmentation (MMEA) problem studied in this paper can be taken as a generalization of the Bayesian E-optimal design (BED) and the maximum algebraic connectivity augmentation (MACA). However, there are two different aspects: (1) the augmentation matrix $A_i$, $i \\in [m]$ is symmetric PSD, while it's a rank-one matrix in BED and MACA; (2) MMEA imposes the constraint $k < n$, which differs from the settings in BED and MACA.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "$\\textbf{Strengths:}$ (1) The core technical contribution is a novel intrinsic dimension concentration inequality for the minimum eigenvalue of a sum of random PSD matrices, filling a gap in matrix concentration inequalities.   \n(2) This work proves that the proposed method provides a constant-factor approximation when the optimal increase in the minimum eigenvalue is sufficiently large.   \n(3) Unlike many prior works, the approach accommodates augmentation matrices of arbitrary rank rather than just rank-one matrices.  \n$\\textbf{Weaknesses:}$ (1) The theoretical guarantee holds only when the optimal increase is large enough, which might not always be the case in practice.  \n(2) There is no empirical evaluation or computational study to support the practical performance of the method.", "other_comments_or_suggestions": "(1) The definitions of quantities $R$ and $W$ only appear in Abstract and Introduction (Line 184). It would be helpful to repeat them when they appear in subsequent sections.  \n(2) In Line 92, for the maximum algebraic connectivity augmentation problem, it should be $M = \\mathbf{1} \\mathbf{1}^\\top$ since $L$ is the Laplacian matrix corresponding to $A_e$.  \n(3) In Line 342, \" It also of interest\" -> \"It is also of interest\".", "questions_for_authors": "The max-min eigenvalue augmentation (MMEA) is closely related to the Bayesian E-optimal design (BED) and the maximum algebraic connectivity augmentation (MACA). Could you compare this paper with existing works on BED and MACA in terms of theoretical guarantees and running time?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper gives an approximation algorithm for a variant of the E-Optimal Design problem, called the Max-Min Eigenvalue Augmentation problem. The main result is a constant factor approximation via SDP relaxation and simple rounding when the augmentation is large enough. The main technical contribution is a new variant of the matrix Chernoff bound. The reviewers found the paper's result and techniques interesting, while noting some limitations (no experimental results, and primarily the condition on the augmentation being large). The paper would make a nice addition to the ICML program.
Decision: Accept (poster)