Converting Projected Gradient Regret for Squared Loss

From Online Regret to Regression Risk

Projected online gradient descent controls the losses incurred by a sequence of predictions relative to a fixed comparator. In regression, the practical goal is different: we want a predictor whose population squared risk is close to the best risk available in a specified parameter set. The conversion is useful because an online regret guarantee can be obtained without knowing the data distribution, while iid sampling connects its sequential losses to population risk.

We work with linear predictors and an averaged parameter output. The resulting rate is an expected excess-risk bound of order $n^{-1/2}$. It depends on bounded features and responses, and it does not by itself assert a pathwise or high-probability guarantee.

Setup and Assumptions

For each round $t=1,\ldots,n$, observe an iid pair $(X_t,Y_t)$, where $X_t\in\mathbb{R}^d$ is a feature vector and $Y_t\in\mathbb{R}$ is a response. The predictor indexed by $\theta\in\mathbb{R}^d$ is $X_t^\top\theta$, and we use the squared loss $\ell(\theta;(x,y))=(y-x^\top\theta)^2$, without a factor of one half.

Definition: Let $K\subset\mathbb{R}^d$ be a nonempty compact convex set. Its diameter is $D=\sup_{\theta,\theta'\in K}\|\theta-\theta'\|_2$. Assume $\|\theta\|_2\le R$ for every $\theta\in K$, $\|X_t\|_2\le B$ almost surely, and $|Y_t|\le M$ almost surely, for finite constants $R,B,M$. Define the population risk by $R(\theta)=E[(Y-X^\top\theta)^2]$, for an iid pair $(X,Y)$ with the same distribution as the observations.

The loss is convex and differentiable as a function of $\theta$. Its gradient is

\nabla_\theta \ell(\theta;(x,y))=2(x^\top\theta-y)x.

For $\theta\in K$, the Cauchy–Schwarz inequality gives $|x^\top\theta|\le BR$. Thus the gradient norm is bounded by

\|\nabla_\theta \ell(\theta;(x,y))\|_2 =2|x^\top\theta-y|\,\|x\|_2 \le 2B(BR+M)=G.

This bound holds for every feasible parameter and every observation in the assumed support. Compactness of $K$, together with bounded observations, also ensures that $R$ is finite and continuous on $K$. Therefore a population risk minimizer $\theta^\star\in K$ exists.

Projected Gradient Regret Bound

Start from any $\theta_1\in K$. After observing $(X_t,Y_t)$, let $g_t=\nabla_\theta\ell(\theta_t;(X_t,Y_t))$ and update by projecting a gradient step back into $K$:

\theta_{t+1}=\Pi_K(\theta_t-\eta g_t),

where $\eta>0$ is a fixed step size and $\Pi_K$ is Euclidean projection onto $K$. The regret against a fixed $\theta\in K$ is the difference between the algorithm's accumulated losses and the losses that the fixed parameter would have incurred on the same observations.

Theorem: Under the setup above, for every sequence of observations satisfying the stated bounds, every $\theta\in K$, and every $\eta>0$, projected online gradient descent satisfies $$ \sum_{t=1}^n\left\{\ell(\theta_t;(X_t,Y_t))-\ell(\theta;(X_t,Y_t))\right\} \le \frac{D^2}{2\eta}+\frac{\eta nG^2}{2}. $$

Proof. Euclidean projection onto a nonempty closed convex set has the property $\|\Pi_K(v)-\theta\|_2^2\le\|v-\theta\|_2^2$ for $\theta\in K$. Applying it to the update and expanding the square gives

\begin{aligned} \|\theta_{t+1}-\theta\|_2^2 &\le \|\theta_t-\eta g_t-\theta\|_2^2\\ &=\|\theta_t-\theta\|_2^2 -2\eta g_t^\top(\theta_t-\theta)+\eta^2\|g_t\|_2^2. \end{aligned}

Rearrange and divide by $2\eta$. Convexity and differentiability of the squared loss imply $\ell(\theta_t;(X_t,Y_t))-\ell(\theta;(X_t,Y_t))\le g_t^\top(\theta_t-\theta)$. Also, $\|g_t\|_2\le G$. Consequently,

\ell(\theta_t;(X_t,Y_t))-\ell(\theta;(X_t,Y_t)) \le \frac{\|\theta_t-\theta\|_2^2-\|\theta_{t+1}-\theta\|_2^2}{2\eta} +\frac{\eta G^2}{2}.

Summing over $t$ makes the squared-distance terms telescope. The remaining distance difference is at most $\|\theta_1-\theta\|_2^2\le D^2$, since both parameters are in $K$. This proves the stated bound. $\square$

If $D>0$ and $G>0$, choosing $\eta=D/(G\sqrt{n})$ balances the two terms: $D^2/(2\eta)=DG\sqrt{n}/2$ and $\eta nG^2/2=DG\sqrt{n}/2$. The regret is then at most $DG\sqrt{n}$. Dividing by $n$ gives an average regret bound of $DG/\sqrt{n}$. If $D=0$, $K$ contains just one parameter and the regret is zero; if $G=0$, all feasible gradients vanish and the same regret bound is zero.

Worked Example: Calculating a Bounded-Regret Rate

Take $K=[-1,1]$, scalar features with $|X_t|\le1$, and responses with $|Y_t|\le1$. Then $D=2$, $R=1$, $B=1$, and $M=1$. The gradient bound is $G=2B(BR+M)=2(1)(1+1)=4$.

For $n$ observations, the balancing step size is $\eta=D/(G\sqrt{n})=2/(4\sqrt{n})=1/(2\sqrt{n})$. The two terms in the regret bound are

\frac{D^2}{2\eta} =\frac{4}{1/\sqrt{n}}=4\sqrt{n}, \qquad \frac{\eta nG^2}{2} =\frac{(1/(2\sqrt{n}))n(16)}{2}=4\sqrt{n}.

Thus regret is at most $8\sqrt{n}$, and average regret is at most $8/\sqrt{n}$. This is a valid worst-case bound from the stated constants; it need not be numerically tight for a particular distribution.

Converting Regret into Population Excess Risk

Define the averaged parameter by $\bar\theta_n=n^{-1}\sum_{t=1}^n\theta_t$. Convexity of $K$ ensures $\bar\theta_n\in K$, and convexity of squared loss means its loss is no greater than the average loss of the iterates, observation by observation.

Theorem: Under the bounded iid setup, run projected online gradient descent with the fixed step size $\eta=D/(G\sqrt{n})$, where $D,G>0$. Then its averaged parameter satisfies $$ E\!\left[R(\bar\theta_n)-\min_{\theta\in K}R(\theta)\right] \le \frac{DG}{\sqrt{n}}. $$ The expectation is over the training sample.

Proof. Choose a population minimizer $\theta^\star\in K$. Since squared loss is convex in its parameter, for every realized sample and every $z=(x,y)$,

\ell(\bar\theta_n;z) \le \frac{1}{n}\sum_{t=1}^n\ell(\theta_t;z).

Integrating this pointwise inequality with respect to the population distribution gives $R(\bar\theta_n)\le n^{-1}\sum_{t=1}^n R(\theta_t)$, for each realized training sample. Each $\theta_t$ is determined by observations before round $t$, so it is independent of the fresh iid pair $(X_t,Y_t)$. Boundedness ensures integrability, and hence

E[\ell(\theta_t;(X_t,Y_t))]=E[R(\theta_t)].

The comparator $\theta^\star$ is fixed, so $E[\ell(\theta^\star;(X_t,Y_t))]=R(\theta^\star)$. Apply the pathwise regret bound with comparator $\theta^\star$, take expectations, and combine these facts:

\begin{aligned} E[R(\bar\theta_n)-R(\theta^\star)] &\le \frac{1}{n}\sum_{t=1}^n E[R(\theta_t)-R(\theta^\star)]\\ &= \frac{1}{n}E\!\left[\sum_{t=1}^n \{\ell(\theta_t;(X_t,Y_t))-\ell(\theta^\star;(X_t,Y_t))\}\right]\\ &\le \frac{1}{n}\left(\frac{D^2}{2\eta}+\frac{\eta nG^2}{2}\right) =\frac{DG}{\sqrt{n}}. \end{aligned}

Because $R(\theta^\star)=\min_{\theta\in K}R(\theta)$, this is the claimed expected excess-risk bound. $\square$

Worked Example: An Explicit Iid Regression Model

Let $X=1$ with probability one, let $Y$ be Bernoulli with success probability $1/2$, and take $K=[0,1]$. The population risk is

R(\theta)=\tfrac12(1-\theta)^2+\tfrac12\theta^2 =\left(\theta-\tfrac12\right)^2+\tfrac14.

Therefore $\theta^\star=1/2$ and $R(\theta^\star)=1/4$. The assumptions hold with $D=1$, $B=1$, $M=1$, and $R=1$, giving $G=2(1)(1+1)=4$. The theorem guarantees expected excess risk at most $4/\sqrt{n}$.

For a concrete two-observation run, use $\eta=0.1$, start at $\theta_1=0$, and suppose the observed responses are $Y_1=1,Y_2=0$. The first gradient is $2(0-1)=-2$, so $\theta_2=0-0.1(-2)=0.2$. The averaged output is $\bar\theta_2=(0+0.2)/2=0.1$, whose population excess risk is $(0.1-0.5)^2=0.16$. On this particular sample, the sequential losses are $1$ and $0.04$; the comparator losses at $\theta^\star=0.5$ are $0.25$ and $0.25$, giving regret $1.04-0.50=0.54$. The example illustrates the calculations, while the theorem's guarantee concerns expectation over samples, not a bound of $4/\sqrt{2}$ on every realized excess risk.

Worked Example: A Projected Update at the Boundary

Take $K=[-1,1]$, $\theta_1=0$, $\eta=0.5$, and one observation with $x=1,y=2$. The gradient at $\theta_1$ is $2(0-2)(1)=-4$. The unprojected step is $0-0.5(-4)=2$, so projection gives $\theta_2=1$.

The loss at the iterate is $(2-0)^2=4$; the loss of comparator $\theta=1$ on the same observation is $(2-1)^2=1$. The regret for this round is $4-1=3$. Projection is essential: the unprojected parameter $2$ is not in $K$, so it cannot be treated as a feasible output or comparator.

Interpretation and a Common Pitfall

The rate $DG/\sqrt{n}$ follows from two ingredients with different roles. Projected gradient descent supplies a regret bound for the sequence of observed losses. Iid sampling lets us identify the expected loss of each pre-observation iterate with its population risk, and convexity transfers the average of those risks to the averaged parameter. Boundedness supplies the uniform gradient control and finite expectations required by these steps.

Common mistake: A small empirical regret, or a small empirical squared loss, does not automatically imply a small population excess risk for every realized data set. The conversion above uses independence to obtain an equality in expectation, and its conclusion is explicitly an expected-risk bound. It does not turn that equality into a pathwise equality or a high-probability claim. Also, the comparator must be fixed independently of the current observation; the proof uses the population minimizer $\theta^\star$, not a comparator selected after seeing each response.

The result is relative to the best predictor in $K$. If the true regression function is not representable by a parameter in $K$, that approximation issue is not removed by online regret: the theorem controls excess risk above $\min_{\theta\in K}R(\theta)$, not risk above an unrestricted ideal predictor.

Check Your Understanding

Work through these questions using the assumptions and arguments above.

Why does the gradient bound contain the term $BR+M$, and where does the factor $2$ come from?
For $D=3$, $G=2$, and sample size $n$, what step size balances the two terms in the regret bound, and what is the resulting average regret bound?
Which independence fact is needed to replace expected sequential loss by expected population risk in the conversion proof?
Why does convexity of $K$ matter for the averaged parameter, and why does convexity of squared loss matter separately?
Does the expected excess-risk theorem imply the same $DG/\sqrt{n}$ bound for every realized sample? Explain.