- Rating
- 4
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies optimal experimental design for linear regression with heavy-tailed errors under a bounded -moment assumption. The authors present a convex design criterion that encompasses classical G-optimality and establish nearly matching upper and lower bounds on the estimation. They show that G-optimal designs can be polynomially suboptimal under heavy-tailed errors.
Critical strengths
-
The proposed criterion provides a convex formulation for experimental design under heavy-tailed errors. The nearly matching upper and lower bounds offer a statistical justification for the proposed criterion.
-
The paper provides a constructive approach to experimental design when the moment exponent is unknown, with approximation guarantees and lower bounds.
Critical weaknesses
-
Theorem 1 shows an upper bound depending on , where Theorem 2 gives a lower bound proportional to using instances satisfying . The authors should clarify the exact parameter class under which the claimed optimality holds.
-
The experiments mainly compare the proposed design with G-optimality. Uniform sampling can serve as a useful baseline. Moreover, the errors with the best average performance among multiple estimators make it difficult to isolate the benefit of the proposed sampling design.
Questions for authors
-
Can the authors clarify whether the claimed minimax optimality requires ?
-
In Lemma 1, it states that raising the inverse of a concave function to the power preserves convexity because this power is convex and nonincreasing. However, is concave and increasing for .
-
In Theorems 4 and 5, can the authors explain whether this gap is fundamental or can be closed by improving the mixture construction?
-
Can the authors include uniform sampling as a baseline and compare the different designs using the same fixed robust estimator?
We thank the reviewer for their positive assessment and thoughtful questions. Our responses are as follows.
On the Parameter Class and the Dependence on B.
The B term appears because our estimator is affected by variation in x⊤θ∗ across observations, not just by the noise. With a stronger sample size constraint perhaps depending on B, we expect to first obtain a warm start for θ∗ and subtract its predictions before estimating the remaining error. The bound would then depend on the error of this warm start rather than on the full signal magnitude B. Whether Mα still gives near-matching bounds when Bα≫ν is not established by the paper. The matching guarantee concerns Bα≤ν, up to logarithmic factors and the saturation in Theorem 2, we will reemphasize this in the paper.
On the Convexity Argument.
The convexity argument in Lemma 1 applies the map t→t−(α−1), which is convex and nonincreasing for t>0, to the concave inner infimum in Equation (4), giving a convex function of λ. The phrase "Raising the inverse to the power α−1" in the proof sketch refers to this negative power. We will write the full map explicitly in the sketch to avoid ambiguity.
On the Approximation Gap for Unknown α.
The weights in Theorem 4 leave some of the sampling probability on the uniform design. This controls exponents beyond the finite grid, but assigns unnecessarily small probabilities to the designs optimized at the grid exponents, increasing the approximation factor. We believe that allocating more probability to these designs through a sharper choice of weights may improve the upper bound enough to close the loglogd gap, without computing additional designs.
On Uniform Sampling and a Fixed Estimator.
For the action set in Figure 2, the Mα-optimal design at α=4/3 is nearly uniform over the Hadamard and coordinate actions, and uniform sampling achieves the same dimension dependence.
However, we can construct action sets where uniform sampling and A-optimality are both polynomially worse than G-optimality and therefore also than Mα-optimality. We introduce one such action set to demonstrate this suboptimality and verify the separation empirically. Let h1,…,hd/2∈Rd be the normalized Hadamard basis supported on the first d/2 coordinates, and let e1,…,ed be the standard basis. The action set is
:1\le i\le d/2 \rbrace \cup \lbrace \frac{1+j/d^2}{d^{1/4}}h_i,\ \frac{1+j/d^2}{d^{3/4}}e_{d/2+i} :1\le i\le d/2,\ 1\le j\le d^2 \rbrace.$$ Uniform sampling assigns most observations to the added shorter actions, whereas $A$-optimality (another possible baseline suggested by reviewer H5Ng) concentrates on the last $d/2$ coordinates. The "Theory" row in the table below gives the order of $M_{4/3}(\lambda;\mathcal A)^{3/4}$, the design dependence in Theorems 1 and 2. Relative to $M_\alpha$-optimality, the polynomial losses are $d^{1/2}$ for uniform sampling and $d^{3/8}$ for $A$-optimality, compared with $d^{1/4}$ for $G$-optimality. We tested these predicted separations under Pareto noise, keeping the dimensions, sample budget, repetitions, and estimator collection identical to Figure 2. For each design and dimension, the table reports the lowest average maximum estimation error among estimators that completed all repetitions, together with its standard error. | $d$ | Uniform | $A$-optimal | $G$-optimal | $M_\alpha$-optimal | |---:|---:|---:|---:|---:| | 32 | $0.064\pm0.008$ | $0.047\pm0.002$ | $0.038\pm0.002$ | $0.033\pm0.003$ | | 64 | $0.110\pm0.006$ | $0.085\pm0.005$ | $0.058\pm0.003$ | $0.038\pm0.002$ | | 128 | $0.218\pm0.013$ | $0.142\pm0.008$ | $0.097\pm0.003$ | $0.049\pm0.002$ | | 256 | $0.378\pm0.019$ | $0.231\pm0.006$ | $0.151\pm0.010$ | $0.058\pm0.004$ | | 512 | $0.670\pm0.028$ | $0.377\pm0.016$ | $0.215\pm0.009$ | $0.071\pm0.002$ | | 1024 | $0.981\pm0.004$ | $0.624\pm0.013$ | $0.305\pm0.020$ | $0.098\pm0.003$ | | 2048 | $0.988\pm0.003$ | $0.990\pm0.003$ | $0.415\pm0.028$ | $0.117\pm0.006$ | | 4096 | $0.877\pm0.021$ | $0.989\pm0.001$ | $0.629\pm0.031$ | $0.133\pm0.005$ | | Theory | $\Theta(d^{3/4})$ | $\Theta(d^{5/8})$ | $\Theta(d^{1/2})$ | $\Theta(d^{1/4})$ | Figures 4 and 5 in the Appendix compare the designs with each estimator held fixed, reporting absolute errors and ratios between designs, respectively.