東京大学 情報理工学系研究科 コンピュータ科学専攻 2017年8月実施 専門科目II 問題5 Author 祭音Myyura (co-authored with GPT 5.6 SOL)
Description Denote the set of real numbers with R \mathbb R R w w w ∣ w ∣ |w| ∣ w ∣ d d d w \boldsymbol w w i i i w i w_i w i ∥ w ∥ 1 = ∣ w 1 ∣ + ∣ w 2 ∣ + ⋯ + ∣ w d ∣ \|\boldsymbol w\|_1=|w_1|+|w_2|+\cdots+|w_d| ∥ w ∥ 1 = ∣ w 1 ∣ + ∣ w 2 ∣ + ⋯ + ∣ w d ∣ ∥ w ∥ 2 = w 1 2 + w 2 2 + ⋯ + w d 2 \|\boldsymbol w\|_2=\sqrt{w_1^2+w_2^2+\cdots+w_d^2} ∥ w ∥ 2 = w 1 2 + w 2 2 + ⋯ + w d 2 w \boldsymbol w w w ⊤ \boldsymbol w^\top w ⊤
A vector g ∈ R d \boldsymbol g\in\mathbb R^d g ∈ R d f f f x ∈ R d \boldsymbol x\in\mathbb R^d x ∈ R d
∀ z ∈ R d , f ( z ) ≥ f ( x ) + g ⊤ ( z − x ) \forall\boldsymbol z\in\mathbb R^d,\quad
f(\boldsymbol z)\ge f(\boldsymbol x)+\boldsymbol g^\top(\boldsymbol z-\boldsymbol x) ∀ z ∈ R d , f ( z ) ≥ f ( x ) + g ⊤ ( z − x ) holds. The set of subgradients of a convex function f f f x \boldsymbol x x { g ∈ R d ∣ ∀ z ∈ R d , f ( z ) ≥ f ( x ) + g ⊤ ( z − x ) } \{\boldsymbol g\in\mathbb R^d\mid\forall\boldsymbol z\in\mathbb R^d,\ f(\boldsymbol z)\ge f(\boldsymbol x)+\boldsymbol g^\top(\boldsymbol z-\boldsymbol x)\} { g ∈ R d ∣ ∀ z ∈ R d , f ( z ) ≥ f ( x ) + g ⊤ ( z − x )} f f f x \boldsymbol x x ∂ f ( x ) \partial f(\boldsymbol x) ∂ f ( x )
(i) A differentiable convex function f ( x ) f(\boldsymbol x) f ( x )
∂ f ( x ) = { ∇ f ( x ) } , ∇ f ( x ) = ( ∂ f ( x ) / ∂ x 1 ⋮ ∂ f ( x ) / ∂ x d ) . \partial f(\boldsymbol x)=\{\nabla f(\boldsymbol x)\},\qquad
\nabla f(\boldsymbol x)=
\begin{pmatrix}
\partial f(\boldsymbol x)/\partial x_1\\
\vdots\\
\partial f(\boldsymbol x)/\partial x_d
\end{pmatrix}. ∂ f ( x ) = { ∇ f ( x )} , ∇ f ( x ) = ∂ f ( x ) / ∂ x 1 ⋮ ∂ f ( x ) / ∂ x d . (ii) For convex functions f 1 f_1 f 1 f 2 f_2 f 2 ∂ ( f 1 + f 2 ) ( x ) = { g 1 + g 2 ∣ g 1 ∈ ∂ f 1 ( x ) , g 2 ∈ ∂ f 2 ( x ) } \partial(f_1+f_2)(\boldsymbol x)=\{\boldsymbol g_1+\boldsymbol g_2\mid \boldsymbol g_1\in\partial f_1(\boldsymbol x),\ \boldsymbol g_2\in\partial f_2(\boldsymbol x)\} ∂ ( f 1 + f 2 ) ( x ) = { g 1 + g 2 ∣ g 1 ∈ ∂ f 1 ( x ) , g 2 ∈ ∂ f 2 ( x )} 0 ∈ ∂ f ( w ∗ ) 0\in\partial f(\boldsymbol w^*) 0 ∈ ∂ f ( w ∗ ) f ( w ) f(\boldsymbol w) f ( w ) w = w ∗ \boldsymbol w=\boldsymbol w^* w = w ∗
Answer the following questions.
(1) (a) For f ( w ) = ∣ w ∣ f(w)=|w| f ( w ) = ∣ w ∣ w ∈ R w\in\mathbb R w ∈ R ∂ f ( w ) \partial f(w) ∂ f ( w ) f ( w ) = ∥ w ∥ 1 f(\boldsymbol w)=\|\boldsymbol w\|_1 f ( w ) = ∥ w ∥ 1 w ∈ R d \boldsymbol w\in\mathbb R^d w ∈ R d ∂ f ( w ) \partial f(\boldsymbol w) ∂ f ( w )
(2) For f ( w ) = 1 2 ( w − z ) 2 + β ∣ w ∣ f(w)=\frac12(w-z)^2+\beta|w| f ( w ) = 2 1 ( w − z ) 2 + β ∣ w ∣ w , z ∈ R w,z\in\mathbb R w , z ∈ R 0 < β ∈ R 0<\beta\in\mathbb R 0 < β ∈ R ∂ f ( w ) \partial f(w) ∂ f ( w ) w ∗ ∈ R w^*\in\mathbb R w ∗ ∈ R f ( w ) f(w) f ( w )
(3) For f ( w ) = 1 2 ∥ w − z ∥ 2 2 + β ∥ w ∥ 1 f(\boldsymbol w)=\frac12\|\boldsymbol w-\boldsymbol z\|_2^2+\beta\|\boldsymbol w\|_1 f ( w ) = 2 1 ∥ w − z ∥ 2 2 + β ∥ w ∥ 1 w , z ∈ R d \boldsymbol w,\boldsymbol z\in\mathbb R^d w , z ∈ R d 0 < β ∈ R 0<\beta\in\mathbb R 0 < β ∈ R ∂ f ( w ) \partial f(\boldsymbol w) ∂ f ( w ) w = w ∗ ∈ R d \boldsymbol w=\boldsymbol w^*\in\mathbb R^d w = w ∗ ∈ R d f ( w ) f(\boldsymbol w) f ( w ) j j j 1 ≤ j ≤ d 1\le j\le d 1 ≤ j ≤ d w j ∗ = 0 w_j^*=0 w j ∗ = 0
Consider the problem of predicting one dimensional real-valued label y ∈ R y\in\mathbb R y ∈ R d d d x ∈ R d \boldsymbol x\in\mathbb R^d x ∈ R d n n n
{ ( x i , y i ) ∣ x i ∈ R d , y i ∈ R , i = 1 , 2 , … , n } \{(\boldsymbol x_i,y_i)\mid\boldsymbol x_i\in\mathbb R^d,\ y_i\in\mathbb R,\ i=1,2,\ldots,n\} {( x i , y i ) ∣ x i ∈ R d , y i ∈ R , i = 1 , 2 , … , n } is given where ( x i , y i ) (\boldsymbol x_i,y_i) ( x i , y i ) y i y_i y i x i \boldsymbol x_i x i
By using a d d d w ∈ R d \boldsymbol w\in\mathbb R^d w ∈ R d
L ( w ) = 1 2 n ∑ i = 1 n ( y i − w ⊤ x i ) 2 . L(\boldsymbol w)=\frac1{2n}\sum_{i=1}^n(y_i-\boldsymbol w^\top\boldsymbol x_i)^2. L ( w ) = 2 n 1 i = 1 ∑ n ( y i − w ⊤ x i ) 2 . We formulate the training of a predictor as the following optimization problem with a positive real value λ \lambda λ
w ∗ = argmin w ∈ R d { L ( w ) + λ ∥ w ∥ 1 } . \boldsymbol w^*=\underset{\boldsymbol w\in\mathbb R^d}{\operatorname{argmin}}
\{L(\boldsymbol w)+\lambda\|\boldsymbol w\|_1\}. w ∗ = w ∈ R d argmin { L ( w ) + λ ∥ w ∥ 1 } . The following algorithm is known for obtaining the optimal solution w ∗ \boldsymbol w^* w ∗ † \dagger † w ( 0 ) ∈ R d \boldsymbol w^{(0)}\in\mathbb R^d w ( 0 ) ∈ R d η t > 0 \eta_t>0 η t > 0
w ( t + 1 ) = argmin w ∈ R d { ∇ L ( w ( t ) ) ⊤ ( w − w ( t ) ) + λ ∥ w ∥ 1 + 1 2 η t ∥ w − w ( t ) ∥ 2 2 } , t = 0 , 1 , 2 , … (†) \boldsymbol w^{(t+1)}
=\underset{\boldsymbol w\in\mathbb R^d}{\operatorname{argmin}}
\left\{
\nabla L(\boldsymbol w^{(t)})^\top(\boldsymbol w-\boldsymbol w^{(t)})
+\lambda\|\boldsymbol w\|_1
+\frac1{2\eta_t}\|\boldsymbol w-\boldsymbol w^{(t)}\|_2^2
\right\},
\qquad t=0,1,2,\ldots
\tag{†} w ( t + 1 ) = w ∈ R d argmin { ∇ L ( w ( t ) ) ⊤ ( w − w ( t ) ) + λ ∥ w ∥ 1 + 2 η t 1 ∥ w − w ( t ) ∥ 2 2 } , t = 0 , 1 , 2 , … ( † ) Answer the following question.
(4) Express a ∈ R a\in\mathbb R a ∈ R η t \eta_t η t λ \lambda λ w j ( t ) − η t ∂ L ∂ w j ( w ( t ) ) ∈ [ − a , a ] w_j^{(t)}-\eta_t\frac{\partial L}{\partial w_j}(\boldsymbol w^{(t)})\in[-a,a] w j ( t ) − η t ∂ w j ∂ L ( w ( t ) ) ∈ [ − a , a ] w j ( t + 1 ) = 0 w_j^{(t+1)}=0 w j ( t + 1 ) = 0 j j j 1 ≤ j ≤ d 1\le j\le d 1 ≤ j ≤ d
题目描述
以 R \mathbb R R ∣ w ∣ |w| ∣ w ∣ w w w w ∈ R d \boldsymbol w\in\mathbb R^d w ∈ R d w i w_i w i i i i w T \boldsymbol w^{\mathsf T} w T ∥ w ∥ 1 = ∑ i = 1 d ∣ w i ∣ \|\boldsymbol w\|_1=\sum_{i=1}^d|w_i| ∥ w ∥ 1 = ∑ i = 1 d ∣ w i ∣ ∥ w ∥ 2 = ( ∑ i = 1 d w i 2 ) 1 / 2 \|\boldsymbol w\|_2=(\sum_{i=1}^dw_i^2)^{1/2} ∥ w ∥ 2 = ( ∑ i = 1 d w i 2 ) 1/2 g , x ∈ R d \boldsymbol g,\boldsymbol x\in\mathbb R^d g , x ∈ R d z ∈ R d \boldsymbol z\in\mathbb R^d z ∈ R d
f ( z ) ≥ f ( x ) + g T ( z − x ) , f(\boldsymbol z)\ge f(\boldsymbol x)+\boldsymbol g^{\mathsf T}(\boldsymbol z-\boldsymbol x), f ( z ) ≥ f ( x ) + g T ( z − x ) , 则称 g \boldsymbol g g f f f x \boldsymbol x x ∂ f ( x ) \partial f(\boldsymbol x) ∂ f ( x ) ∂ ( f 1 + f 2 ) \partial(f_1+f_2) ∂ ( f 1 + f 2 ) 0 ∈ ∂ f ( w ∗ ) 0\in\partial f(\boldsymbol w^*) 0 ∈ ∂ f ( w ∗ ) w ∗ \boldsymbol w^* w ∗ f f f
（1）求（a）f ( w ) = ∣ w ∣ f(w)=|w| f ( w ) = ∣ w ∣ w ∈ R w\in\mathbb R w ∈ R ∂ f ( w ) \partial f(w) ∂ f ( w ) f ( w ) = ∥ w ∥ 1 f(\boldsymbol w)=\|\boldsymbol w\|_1 f ( w ) = ∥ w ∥ 1 w ∈ R d \boldsymbol w\in\mathbb R^d w ∈ R d ∂ f ( w ) \partial f(\boldsymbol w) ∂ f ( w )
（2）对 f ( w ) = 1 2 ( w − z ) 2 + β ∣ w ∣ f(w)=\frac12(w-z)^2+\beta|w| f ( w ) = 2 1 ( w − z ) 2 + β ∣ w ∣ w , z ∈ R , β > 0 w,z\in\mathbb R,\beta>0 w , z ∈ R , β > 0 ∂ f ( w ) \partial f(w) ∂ f ( w ) w ∗ ∈ R w^*\in\mathbb R w ∗ ∈ R
（3）对 f ( w ) = 1 2 ∥ w − z ∥ 2 2 + β ∥ w ∥ 1 f(\boldsymbol w)=\frac12\|\boldsymbol w-\boldsymbol z\|_2^2+
\beta\|\boldsymbol w\|_1 f ( w ) = 2 1 ∥ w − z ∥ 2 2 + β ∥ w ∥ 1 w , z ∈ R d , β > 0 \boldsymbol w,\boldsymbol z\in\mathbb R^d,\beta>0 w , z ∈ R d , β > 0 ∂ f ( w ) \partial f(\boldsymbol w) ∂ f ( w ) w ∗ ∈ R d \boldsymbol w^*\in\mathbb R^d w ∗ ∈ R d j j j 1 ≤ j ≤ d 1\le j\le d 1 ≤ j ≤ d w j ∗ = 0 w_j^*=0 w j ∗ = 0
现由 x ∈ R d \boldsymbol x\in\mathbb R^d x ∈ R d y ∈ R y\in\mathbb R y ∈ R n n n { ( x i , y i ) ∣ x i ∈ R d , y i ∈ R , i = 1 , … , n } \{(\boldsymbol x_i,y_i)\mid\boldsymbol x_i\in\mathbb R^d,\ y_i\in\mathbb R,\ i=1,\ldots,n\} {( x i , y i ) ∣ x i ∈ R d , y i ∈ R , i = 1 , … , n } y i y_i y i x i \boldsymbol x_i x i w ∈ R d \boldsymbol w\in\mathbb R^d w ∈ R d ℓ 1 \ell_1 ℓ 1 λ > 0 \lambda>0 λ > 0
L ( w ) = 1 2 n ∑ i = 1 n ( y i − w T x i ) 2 , w ∗ = arg min w ∈ R d { L ( w ) + λ ∥ w ∥ 1 } . L(\boldsymbol w)=\frac1{2n}\sum_{i=1}^n(y_i-\boldsymbol w^{\mathsf T}\boldsymbol x_i)^2,
\qquad
\boldsymbol w^*=\arg\min_{\boldsymbol w\in\mathbb R^d}\{L(\boldsymbol w)+\lambda\|\boldsymbol w\|_1\}. L ( w ) = 2 n 1 i = 1 ∑ n ( y i − w T x i ) 2 , w ∗ = arg w ∈ R d min { L ( w ) + λ ∥ w ∥ 1 } . 从 w ( 0 ) ∈ R d \boldsymbol w^{(0)}\in\mathbb R^d w ( 0 ) ∈ R d η t > 0 \eta_t>0 η t > 0
w ( t + 1 ) = arg min w ∈ R d { ∇ L ( w ( t ) ) T ( w − w ( t ) ) + λ ∥ w ∥ 1 + 1 2 η t ∥ w − w ( t ) ∥ 2 2 } , t = 0 , 1 , 2 , … . \boldsymbol w^{(t+1)}=\arg\min_{\boldsymbol w\in\mathbb R^d}
\left\{
\nabla L(\boldsymbol w^{(t)})^{\mathsf T}(\boldsymbol w-\boldsymbol w^{(t)})
+\lambda\|\boldsymbol w\|_1
+\frac1{2\eta_t}\|\boldsymbol w-\boldsymbol w^{(t)}\|_2^2
\right\},\qquad t=0,1,2,\ldots. w ( t + 1 ) = arg w ∈ R d min { ∇ L ( w ( t ) ) T ( w − w ( t ) ) + λ ∥ w ∥ 1 + 2 η t 1 ∥ w − w ( t ) ∥ 2 2 } , t = 0 , 1 , 2 , … . （4）设 j j j 1 ≤ j ≤ d 1\le j\le d 1 ≤ j ≤ d η t \eta_t η t λ \lambda λ a ∈ R a\in\mathbb R a ∈ R
w j ( t ) − η t ∂ L ∂ w j ( w ( t ) ) ∈ [ − a , a ] w_j^{(t)}-\eta_t\frac{\partial L}{\partial w_j}(\boldsymbol w^{(t)})
\in[-a,a] w j ( t ) − η t ∂ w j ∂ L ( w ( t ) ) ∈ [ − a , a ] 成为 w j ( t + 1 ) = 0 w_j^{(t+1)}=0 w j ( t + 1 ) = 0
Kai （1）
∂ ∣ w ∣ = { { − 1 } , w < 0 , [ − 1 , 1 ] , w = 0 , { 1 } , w > 0. \partial|w|=
\begin{cases}
\{-1\},&w<0,\\
[-1,1],&w=0,\\
\{1\},&w>0.
\end{cases} ∂ ∣ w ∣ = ⎩ ⎨ ⎧ { − 1 } , [ − 1 , 1 ] , { 1 } , w < 0 , w = 0 , w > 0. 并且
∂ ∥ w ∥ 1 = { g ∈ R d ∣ g i ∈ ∂ ∣ w i ∣ ( i = 1 , … , d ) } . \partial\|\boldsymbol w\|_1
=\{\boldsymbol g\in\mathbb R^d\mid g_i\in\partial|w_i|\ (i=1,\ldots,d)\}. ∂ ∥ w ∥ 1 = { g ∈ R d ∣ g i ∈ ∂ ∣ w i ∣ ( i = 1 , … , d )} . （2）
∂ f ( w ) = w − z + β ∂ ∣ w ∣ . \partial f(w)=w-z+\beta\,\partial|w|. ∂ f ( w ) = w − z + β ∂ ∣ w ∣. 由 0 ∈ ∂ f ( w ∗ ) 0\in\partial f(w^*) 0 ∈ ∂ f ( w ∗ )
w ∗ = sgn ( z ) ( ∣ z ∣ − β ) + = { z − β , z > β , 0 , ∣ z ∣ ≤ β , z + β , z < − β . w^*=\operatorname{sgn}(z)(|z|-\beta)_+
=\begin{cases}
z-\beta,&z>\beta,\\
0,&|z|\le\beta,\\
z+\beta,&z<-\beta.
\end{cases} w ∗ = sgn ( z ) ( ∣ z ∣ − β ) + = ⎩ ⎨ ⎧ z − β , 0 , z + β , z > β , ∣ z ∣ ≤ β , z < − β . （3）
∂ f ( w ) = w − z + β ∂ ∥ w ∥ 1 . \partial f(\boldsymbol w)
=\boldsymbol w-\boldsymbol z+\beta\,\partial\|\boldsymbol w\|_1. ∂ f ( w ) = w − z + β ∂ ∥ w ∥ 1 . 各坐标相互独立，故
w j ∗ = 0 ⟺ ∣ z j ∣ ≤ β . w_j^*=0\quad\Longleftrightarrow\quad |z_j|\le\beta. w j ∗ = 0 ⟺ ∣ z j ∣ ≤ β . （4）
令
q j = w j ( t ) − η t ∂ L ∂ w j ( w ( t ) ) . q_j=w_j^{(t)}-\eta_t\frac{\partial L}{\partial w_j}(\boldsymbol w^{(t)}). q j = w j ( t ) − η t ∂ w j ∂ L ( w ( t ) ) . 配方后，每个坐标的子问题是
1 2 η t ( w j − q j ) 2 + λ ∣ w j ∣ \frac1{2\eta_t}(w_j-q_j)^2+\lambda|w_j| 2 η t 1 ( w j − q j ) 2 + λ ∣ w j ∣
w j ( t + 1 ) = 0 ⟺ ∣ q j ∣ ≤ η t λ . w_j^{(t+1)}=0
\Longleftrightarrow |q_j|\le\eta_t\lambda. w j ( t + 1 ) = 0 ⟺ ∣ q j ∣ ≤ η t λ . 因此 a = η t λ \boxed{a=\eta_t\lambda} a = η t λ