Source-linked AI summary
A new perspective on least squares under convex constraint
Sourav Chatterjee
TL;DR
The paper studies estimation of a Gaussian mean constrained to a convex set, where least squares projects the data onto that set. It relates the error to expected maxima of Gaussian processes, establishes a universal constant-factor guarantee against competitors, and exhibits a setting where least squares is not minimax rate-optimal.
Problem
Existing empirical-process theory gives upper bounds on constrained least-squares error, but not explicit lower bounds or an approximation to the actual error.
Source: §1.2 · p. 3Method
The paper characterizes the error through expected maxima of Gaussian processes and proves a general comparison theorem for the constrained least squares estimator.
Source: §1.2 · p. 3Results
The error concentrates around its characterized scale, while least squares is not always minimax rate-optimal and is competitive with any estimator up to a universal factor somewhere on K.
Source: §1.2 · p. 3, §1.3 · p. 6Takeaways & Limitations
The characterization is applied to derive error bounds for lasso with nonsingular design and isotonic regression.
Source: §2.1 · p. 9, §2.2 · p. 10The theorem for lasso does not establish the result when L, the constraint radius, is chosen using the data.
Source: §2.1 · p. 9
Abstract
from arXiv · showhide
Consider the problem of estimating the mean of a Gaussian random vector when the mean vector is assumed to be in a given convex set. The most natural solution is to take the Euclidean projection of the data vector on to this convex set; in other words, performing "least squares under a convex constraint." Many problems in modern statistics and statistical signal processing theory are special cases of this general situation. Examples include the lasso and other high-dimensional regression techniques, function estimation problems, matrix estimation and completion, shape-restricted regression, constrained denoising, linear inverse problems, etc. This paper presents three general results about this problem, namely, (a) an exact computation of the main term in the estimation error by relating it to expected maxima of Gaussian processes (existing results only give upper bounds), (b) a theorem showing that the least squares estimator is always admissible up to a universal constant in any problem of the above kind and (c) a counterexample showing that least squares estimator may not always be minimax rate-optimal. The result from part (a) is then used to compute the error of the least squares estimator in two examples of contemporary interest.
1. Theory.
The paper studies Gaussian mean estimation under a convex constraint, where the least squares estimator is the Euclidean projection of the data onto the constraint set. It gives an error characterization, a universal constant-factor guarantee against competitors, and a counterexample to minimax rate-optimality.
1.2. Main result.
- Although empirical-process theory provides error upper bounds, the paper uses expected maxima of Gaussian processes to approximate the actual error; exact computation of t_µ is generally difficult.Strict concavity permits upper and lower bounds on t_µ, and hence on the estimation error, from evaluations at a small number of points.Source: §1.2 · pp. 3–5
- Theorem 1.1 characterizes the estimation-error scale through the unique maximizer t_µ of a strictly concave function and shows the error concentrates around it when t_µ is large.The function is built from expected maxima of Gaussian processes; the theorem also gives a tail bound, including when µ lies outside K.Source: §1.2 · p. 3
- For a p-dimensional subspace K, corresponding to linear regression, rotational invariance reduces the relevant Gaussian process to a p-dimensional standard Gaussian and permits exact evaluation.The resulting example illustrates how the general characterization can yield an explicit error scale.Source: §1.2 · p. 4
1.3. The LSE is admissible up to a universal constant.
- For every estimator and every closed convex K, some µ in K has the competitor’s squared risk at least a universal constant times the least squares estimator’s risk.In ℓ1-constrained regression, this means any alternative procedure has prediction error at least that factor times the lasso’s error for some admissible β.Source: §1.3 · pp. 5–6
1.4. The LSE may not be minimax rate-optimal.
- A closed convex-set counterexample has least squares maximum risk at least C1 n^1/2, while the estimator using the average of the data coordinates has maximum risk at most C2.The constants do not depend on n, so least squares need not be minimax rate-optimal; the paper also gives a sufficient condition: risk of the same order everywhere on K.Source: §1.4 · p. 6
2. Examples.
This section applies Theorem 1.1 to the lasso with nonsingular design and isotonic regression. The examples show how estimation error depends on the lasso penalty and provide risk bounds and concentration results for isotonic regression.
2.1. Lasso with nonsingular design.
- The lasso example demonstrates the critical importance of setting L equal to |β|1, although the result is restricted to nonsingular design matrices.The authors expect the phenomenon to hold more generally, but do not establish that here.Source: §2.1 · p. 8
- For the lasso, squared prediction error equals n^(1/2+o(1)) when L > |β|1, is of order n when L < |β|1, and is bounded above by a constant multiple of log n when L = |β|1.Theorem 2.1 does not prove anything when L is chosen using the data.Source: §2.1 · pp. 8–9
2.2. Isotonic regression.
- When the mean coordinates are strictly increasing, their individual errors are typically order n^-1/3, while Theorem 1.1 yields finite-sample global-risk bounds and concentration of the global error around its mean.The section notes that the global error is therefore naturally expected to be order n^1/6 in the strictly increasing case.Source: §2.2 · p. 9
- For isotonic regression, Theorem 2.2 adds a lower bound on expected mean-squared error to an upper bound available from earlier results, and Theorem 1.1 implies concentration around the expected value.The upper bound itself can be derived from existing results such as Zhang.Source: §2.2 · p. 10
3. Proof sketches.
The proof sketches explain how convexity and Gaussian concentration support the paper’s main results. For Theorem 1.1, the maximizers of a random and an expected strictly concave function are shown to be close; for Theorem 1.4, a probability argument compares an arbitrary estimator with least squares.
3. Proof sketches.
- For Theorem 1.1, convexity makes the random function and its expectation strictly concave, and Gaussian concentration makes their maximizers close with high probability.The random maximizer equals the least-squares error norm, while the expected-function maximizer is tμ.Source: §3 · p. 10
- Theorem 1.4’s sketch chooses a distribution over a small ball around μ*, then compares two conditionally i.i.d. parameter draws to lower-bound the risk of an arbitrary estimator.The proof seeks to make the probability that the second draw falls outside a ball around the first exceed a universal threshold.Source: §3 · pp. 10–11
- A maximizer ν* of the Gaussian inner product over B0 turns the estimator’s average risk into E∥ν*−g(Y′)∥², with Y′ formed from an independent Gaussian draw.The proof then uses a second conditionally i.i.d. draw and bounds the probability that it lies outside a ball around ν*.Source: §3 · p. 11
- The proof controls the probability of the second draw leaving that ball by choosing μ* to maximize E(M1) and making E(M2) small through the ball-radius constant.The authors describe the intervening concentration and second-moment steps as technically delicate.Source: §3 · pp. 11–12
4. Proofs.
This section develops proofs of earlier results, establishing propositions and theorems while advancing risk-comparison and bound arguments. The proofs use concavity, Gaussian concentration and inequalities, auxiliary lemmas, and finite-covering arguments, including an upper bound and a lower-bound step.
Proofs of Theorem 1.1, Corollary 1.2, and Proposition 1.3
- Theorem 1.1 identifies the projection estimator with the point maximizing the random concave function, so its error norm equals the maximizer’s radius.Strict concavity ensures a unique maximizer.Source: §4 · pp. 13–15
- The proof derives Corollary 1.2’s inequalities from Theorem 1.1 and uses strict concavity of f_μ to establish Proposition 1.3’s assertions.For μ ∈ K, it also uses f_μ(0) = 0.Source: §4 · pp. 15–16
Preparatory lemmas for Theorem 1.4
- For diam(K) ≥ 2, Lemma 4.7 establishes t_μ ≥ c2 n^-1/2 for every μ in K.The proof uses convexity to find a point at unit distance from each μ and applies Proposition 1.3.Source: §4 · p. 18
Proof of Theorem 1.4
- When diam(K) ≤ 2, Theorem 1.4’s proof finds a mean where any estimator has risk at least c1 diam(K)^2, while projection risk is at most diam(K)^2.The lower bound follows by restricting to a line segment of length diam(K); the upper bound uses that all points in K are within that diameter.Source: §4 · p. 20
4. Proofs.
- The proof of Proposition 1.5 verifies the set K is closed and convex and carries out computations to check the conditions of Proposition 1.3.The text identifies closedness directly and convexity through the definition of K.Source: §4 · p. 25
- Proposition 1.6 follows from Theorem 1.4, which supplies a point µ0 ∈ K where R2(µ0) is at least a universal constant times R1(µ0).The proof applies this risk comparison directly to establish the proposition.Source: §4 · pp. 26–27
- The proof derives a probably new set of inequalities for additive functions of Gaussian variables under covariance-eigenvalue and finite-second-moment conditions.Lemma 4.13 assumes each coordinate has variance 1 and places bounds in terms of the largest and smallest eigenvalues of the covariance matrix.Source: §4 · p. 29
- Theorem 2.1 is proved across the cases δ > 0, δ = 0, and δ < 0 using Lemmas 4.14–4.17 and Proposition 1.3.For δ > 0, Lemmas 4.14 and 4.15 give comparisons used with Proposition 1.3 to bound tµ; the other cases follow from Lemmas 4.16 and 4.17.Source: §4 · p. 35
- Theorem 2.2’s proof begins by localizing K around µ and applying modified entropy bounds to construct a finite cover.The preceding adapted bound is stated in Lemma 4.20.Source: §4 · pp. 36–37
- When A > 0, choosing β sufficiently small and then α smaller gives r1 < r2 and fµ(r1) ≤ fµ(r2), so Proposition 1.3 implies tµ ≥ r1.If A = 0, the theorem’s lower bound is automatic.Source: §4 · p. 40