Minimax Limits for Low-Rank Tensor Estimation

Why Minimax Rates Matter

A low-rank model can reduce the amount of information needed to estimate a tensor, but “low rank” alone does not say how much the error should shrink. A minimax rate makes that question precise: among all estimators, how small can the worst-case expected error be over a specified parameter class? For Gaussian observations, the answer depends on the noise variance and on how many independent directions the low-rank tensor can vary in.

This tutorial studies a localized Tucker-rank model. Localization matters: near a particular tensor, the set of admissible tensors must have enough regular structure for a dimension-based lower bound to apply. We make that condition explicit rather than treating the rank count as an automatic minimax theorem.

Model and Effective Degrees of Freedom

Let $Y\in\mathbb R^{d_1\times\cdots\times d_K}$ be observed according to

Y=T+E,\qquad E_{i_1,\ldots,i_K}\overset{\mathrm{ind}}{\sim}N(0,\sigma^2).

Here $T$ is the unknown mean tensor, $\sigma^2$ is known, and loss is squared Frobenius error, $\|\widehat T-T\|_F^2$. A tensor has Tucker rank at most $\boldsymbol r=(r_1,\ldots,r_K)$ when the matrix unfolding along mode $j$ has rank at most $r_j$, for every $j$. We assume $1\le r_j\le d_j$; for tensors of exact multilinear rank $\boldsymbol r$, the tuple must also be feasible for a core tensor to have all the required unfolding ranks.

Definition: The effective degrees of freedom for Tucker rank $\boldsymbol r$ are $$ D_{\boldsymbol r}=\prod_{j=1}^K r_j+\sum_{j=1}^K r_j(d_j-r_j). $$ The first term counts entries in the core. The $j$th term in the sum counts the degrees of freedom in the $r_j$-dimensional mode-$j$ subspace, after accounting for its choice of basis.

This is a dimension count, not a claim that the statistical problem is exactly a $D_{\boldsymbol r}$-dimensional linear model. In particular, the rank-constrained set is curved and nonconvex. The rate result below uses both a Gaussian complexity bound for that set and a local regularity condition around the tensor being estimated.

A Local Minimax Statement

Fix a tensor $T_0$ of exact Tucker rank $\boldsymbol r$. Assume that, in a neighborhood of $T_0$, the exact-rank tensors admit a one-to-one smooth coordinate chart with $D_{\boldsymbol r}$ real coordinates. Assume also that the chart and its inverse are Lipschitz on a chart ball of radius $\tau_0>0$. These conditions hold on a sufficiently small neighborhood of a regular point of the exact-rank Tucker model; $\tau_0$ records how far that neighborhood can safely be used.

For $0<\rho\le\tau_0$, define the local parameter set $\mathcal T(\rho)=\{T:\operatorname{rank}_{\mathrm{Tucker}}(T)\le\boldsymbol r,\ \|T-T_0\|_F\le\rho\}$. Its minimax risk is

\mathcal R(\rho)=\inf_{\widehat T}\sup_{T\in\mathcal T(\rho)} E_T\|\widehat T-T\|_F^2.

Theorem: For fixed $K$, there are positive constants $c,C$, depending at most on $K$ and the chart’s Lipschitz constants, such that $$ c\min\{\rho^2,\sigma^2D_{\boldsymbol r}\} \le \mathcal R(\rho) \le C\min\{\rho^2,\sigma^2D_{\boldsymbol r}\}. $$ The lower bound uses the stated local-chart condition. The upper bound applies to the rank-constrained Gaussian model and does not need a local chart.

The two terms represent distinct limitations. The neighborhood cannot contribute more than order $\rho^2$ squared error. When it is large relative to the noise scale, the effective dimension contributes order $\sigma^2D_{\boldsymbol r}$. Constants are not asserted to be exact finite-sample thresholds.

Upper Bound: Least Squares on the Rank Class

Let $\mathcal C_{\boldsymbol r}$ be the closed set of tensors of Tucker rank at most $\boldsymbol r$, and let $\widehat T$ minimize $\|Y-X\|_F^2$ over $X\in\mathcal C_{\boldsymbol r}$. A minimizer exists: a minimizing sequence can be restricted to a bounded set, and a convergent subsequence has a limit in the closed feasible set. If necessary, take a measurable minimizer. Since $T\in\mathcal C_{\boldsymbol r}$, least squares gives the basic inequality below, where $\Delta=\widehat T-T$.

\|Y-\widehat T\|_F^2\le\|Y-T\|_F^2 \quad\Longrightarrow\quad \|\Delta\|_F^2\le 2\langle E,\Delta\rangle.

Each mode unfolding of $\Delta$ has rank at most $2r_j$: it is the difference of two matrices of rank at most $r_j$. The following Gaussian complexity fact turns the basic inequality into an estimation rate. Write $\boldsymbol s=(\min(2r_1,d_1),\ldots,\min(2r_K,d_K))$.

Gaussian complexity bound: For a fixed number of modes, if $E$ has independent $N(0,\sigma^2)$ entries and $\mathcal S_{\boldsymbol s}$ is the set of unit-Frobenius tensors whose mode-$j$ ranks are at most $s_j$, then $$ E\left[\sup_{A\in\mathcal S_{\boldsymbol s}}|\langle E,A\rangle|^2\right] \le C_K\sigma^2D_{\boldsymbol s}. $$

For justification, cover each possible mode subspace by a net in the corresponding Grassmann space and cover the unit core by a Euclidean net. The number of coordinates in these nets is bounded by a constant times $D_{\boldsymbol s}$; at resolution $\epsilon$, their product gives $\log N(\epsilon,\mathcal S_{\boldsymbol s},\|\cdot\|_F)\le C_KD_{\boldsymbol s}\log(C_K/\epsilon)$. For two net points $A,B$, the Gaussian increment $\langle E,A-B\rangle$ has variance $\sigma^2\|A-B\|_F^2$. Applying the Gaussian tail bound to increments between successive nets at resolutions $2^{-m}$, and summing their expected maxima, bounds the supremum by a constant times $\sigma\int_0^1\sqrt{D_{\boldsymbol s}\log(C_K/\epsilon)}\,d\epsilon$. The integral is finite and is at most a constant times $\sigma\sqrt{D_{\boldsymbol s}}$; squaring yields the displayed bound. The same covering and tail argument applies to the absolute supremum.

On the event $\Delta\ne0$, divide the basic inequality by $\|\Delta\|_F$ and apply the bound to $\Delta/\|\Delta\|_F$. This gives $\|\Delta\|_F\le2\sup_{A\in\mathcal S_{\boldsymbol s}}|\langle E,A\rangle|$; the inequality also holds when $\Delta=0$. For fixed $K$, $D_{\boldsymbol s}\le C_KD_{\boldsymbol r}$: doubling each rank increases the core product by at most $2^K$, while each subspace term increases by at most a constant factor. Taking expectations therefore gives

\sup_{T\in\mathcal C_{\boldsymbol r}} E_T\|\widehat T-T\|_F^2 \le C_K\sigma^2D_{\boldsymbol r}.

For a local ball, the constant estimator $T_0$ has worst-case risk at most $\rho^2$. Use that estimator when $\rho^2\le\sigma^2D_{\boldsymbol r}$, and the least-squares estimator otherwise. This proves the upper bound in the theorem.

Lower Bound: Packing and Fano’s Inequality

The local chart supplies a $D_{\boldsymbol r}$-dimensional patch. Its Lipschitz properties imply that, for a sufficiently small fixed chart radius, Euclidean distances between coordinate points and Frobenius distances between their tensor images bound one another up to fixed factors. In a $D$-dimensional coordinate ball of radius $R$, a volume comparison gives a packing with separation proportional to $h$ and log cardinality at least $c_0D$, provided the ball radius is $Lh$ for a fixed sufficiently large $L$. Indeed, a maximal separated set covers the ball by balls of radius proportional to $h$; comparing volumes forces at least $(cL)^D$ points. Transfer this packing through the chart.

Set $R_0$ to a fixed constant times $\rho$, small enough that the chart patch of radius $R_0$ lies in $\mathcal T(\rho)$ and within the regular neighborhood. Choose $h=q\min\{R_0,\sigma\sqrt{D_{\boldsymbol r}}\}$, with $q>0$ a small constant. Use the packing inside a coordinate ball of radius $Lh$, choosing $q$ small enough that $Lh\le R_0$. Its tensor images $T_1,\ldots,T_M$ satisfy $\|T_i-T_j\|_F\ge c_1h$ for $i\ne j$, and $\log M\ge c_0D_{\boldsymbol r}$.

For Gaussian observations with common covariance $\sigma^2I$, the Kullback–Leibler divergence from the law at $T_i$ to the law at $T_0$ is $\|T_i-T_0\|_F^2/(2\sigma^2)$. Since every packing point lies within chart distance $Lh$ of the center and the chart is Lipschitz,

\frac{1}{M}\sum_{i=1}^M \operatorname{KL}(P_{T_i},P_{T_0}) \le \frac{C L^2h^2}{2\sigma^2} \le C'L^2q^2D_{\boldsymbol r}.

The last inequality follows from $h\le q\sigma\sqrt{D_{\boldsymbol r}}$. Choose $q$ small enough that the right side is at most, for example, $(c_0/8)D_{\boldsymbol r}$. Fano’s inequality then bounds the probability of incorrectly identifying the packing point away from zero. Any tensor estimator induces a nearest-packing-point classifier; if that classifier is wrong, its estimation error is at least $c_1h/2$. Thus its maximum expected squared error is at least a constant times $h^2$, which is a constant times $\min\{\rho^2,\sigma^2D_{\boldsymbol r}\}$. This proves the lower bound. $\square$

Worked Examples

Worked Example: Counting Degrees of Freedom

Consider a three-way tensor of dimensions $20\times15\times10$ and Tucker rank at most $(2,2,2)$. Its effective degrees of freedom are

$D_{\boldsymbol r}=2\cdot2\cdot2+2(20-2)+2(15-2)+2(10-2)=8+36+26+16=86.$

With $\sigma=0.5$, the noise-dimension term is $\sigma^2D_{\boldsymbol r}=0.25(86)=21.5$. If the local radius is $\rho=3$, then $\rho^2=9$, so the rate is of order $\min(9,21.5)=9$. If instead $\rho=10$, the rate is of order $\min(100,21.5)=21.5$. These are rate calculations up to the theorem’s constants, not exact risks.

Worked Example: Unequal Tucker Ranks

For dimensions $100\times80\times50$ and ranks $(3,2,2)$, the core has $3\cdot2\cdot2=12$ entries. The subspace contributions are $3(100-3)=291$, $2(80-2)=156$, and $2(50-2)=96$. Hence $D_{\boldsymbol r}=12+291+156+96=555$.

At noise standard deviation $\sigma=0.2$, the noise-dimension term is $0.2^2(555)=22.2$. For a regular local neighborhood with $\rho=5$, $\rho^2=25$, so the minimax rate is of order $22.2$. Reducing the neighborhood radius to $\rho=2$ changes the rate to order $4$, because even an estimator that knew the neighborhood center could not need more than the squared neighborhood radius in worst-case error.

Worked Example: Rank-One Three-Way Tensors

For dimensions $40\times30\times20$ and rank $(1,1,1)$, $D_{\boldsymbol r}=1+(40-1)+(30-1)+(20-1)=88$. The single core entry contributes one degree of freedom, and the three factors contribute the remaining 87 after their scale and basis redundancies are removed by the dimension formula.

If $\sigma=0.1$, then $\sigma^2D_{\boldsymbol r}=0.01(88)=0.88$. In a regular local ball of radius $\rho=1$, the rate is of order $0.88$; in a ball of radius $\rho=0.4$, it is of order $\min(0.16,0.88)=0.16$. The rate depends on the total number of adjustable directions, not just on the product of the ranks.

Signal Strength, Scope, and a Common Pitfall

In a localized theorem, the center tensor’s signal strength affects the bound through the chart regularity radius $\tau_0$: the lower-bound patch must fit inside a region where the rank model is well behaved. A poorly conditioned center can have a small such neighborhood, so the stated local lower bound cannot automatically be extended to a larger ball. Conversely, for the upper bound, localization caps risk at $\rho^2$. When the ball is large enough and regularity holds on the relevant patch, the familiar noise-times-dimension scale is $\sigma^2D_{\boldsymbol r}$.

Common mistake: Claiming a Fano lower bound from a packing’s minimum separation alone. Separation is a lower bound on pairwise distances; it says nothing about how far the packing points lie from a reference tensor. Consequently, it cannot by itself give an upper bound on the Kullback–Leibler divergences.
Correction: Put the packing inside a controlled-radius patch as well as requiring separation. Here the patch radius is $Lh$, so every point is within a Lipschitz-controlled distance of the center, and the divergence is at most a constant times $L^2h^2/\sigma^2$. Choosing $q$ small makes this compatible with Fano’s inequality while retaining exponentially many well-separated points.
Another pitfall: Treating $D_{\boldsymbol r}$ as a universal lower bound without stating local regularity. The dimension count motivates the rate, but the lower-bound argument needs a patch with that many identifiable, well-conditioned directions.

Key takeaway: Under Gaussian noise, low-rank least squares has squared error of order $\sigma^2D_{\boldsymbol r}$. Locally, the matching minimax rate is capped by $\rho^2$, provided the rank-$\boldsymbol r$ model has a regular $D_{\boldsymbol r}$-dimensional patch at the center.

Check Your Understanding

Work through these questions using the definitions and arguments above.

For dimensions $12\times10\times8$ and Tucker rank $(2,1,2)$, calculate $D_{\boldsymbol r}$.
Why does the least-squares basic inequality involve tensors with mode ranks at most $2r_j$, rather than $r_j$?
For $\sigma=0.3$, $D_{\boldsymbol r}=100$, and $\rho=2$, which term determines the rate?
In the Fano argument, what separate roles do packing separation and the packing patch’s radius play?
Why does a minimax lower bound based on a local chart require a regularity condition at the center tensor?