FTRL algorithm - Revision history

SYSEN5800TAs at 21:11, 16 December 2024

2024-12-16T21:11:45Z

← Older revision		Revision as of 17:11, 16 December 2024
Line 1:		Line 1:
	Author: Tsz Ki Peter Wei (tmw86), Nhi Nguyen (npn25), Colin Erb (cte24) (ChemE 6800 Fall 2024) <br>		Author: Tsz Ki Peter Wei (tmw86), Nhi Nguyen (npn25), Colin Erb (cte24) (ChemE 6800 Fall 2024)

			Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu<br>

	== Introduction ==		== Introduction ==

Fall2024 Wiki Team15: /* Example 1: Linear Loss with Quadratic Regularization */

2024-12-16T04:03:35Z

Example 1: Linear Loss with Quadratic Regularization

← Older revision		Revision as of 00:03, 16 December 2024
Line 203:		Line 203:
	* Iteration 3:[[File:FTRL_Linear_Loss_Stabilization_Corrected.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]		* Iteration 3:[[File:FTRL_Linear_Loss_Stabilization_Corrected.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]
	<math>		<math>
	w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) + (-0.25) ~~+ 0.05~~}{3} = 0.4.		w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) + 1.75 + (-1.95)}{3} = 0.4.
	</math>		</math>

Fall2024 Wiki Team15: /* Example 1: Linear Loss with Quadratic Regularization */

2024-12-16T04:02:28Z

Example 1: Linear Loss with Quadratic Regularization

← Older revision		Revision as of 00:02, 16 December 2024
Line 189:		Line 189:

	'''Step-by-Step Calculation:'''		'''Step-by-Step Calculation:'''
	Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = -0.25</math>, <math>a_3 = 0.05</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 3</math>.		Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = 1.75</math>, <math>a_3 = -1.95</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 3</math>.

	* Iteration 1:		* Iteration 1:

Fall2024 Wiki Team15 at 04:01, 16 December 2024

2024-12-16T04:01:04Z

← Older revision		Revision as of 00:01, 16 December 2024
Line 198:		Line 198:
	* Iteration 2:		* Iteration 2:
	<math>		<math>
	w_2 = -\frac{a_1 + a_2}{\lambda} = -\frac{(-1) + ~~(-0~~.~~25)~~}{3} = -0.25.		w_2 = -\frac{a_1 + a_2}{\lambda} = -\frac{(-1) + 1.75}{3} = -0.25.
	</math>		</math>

Fall2024 Wiki Team15: /* Numerical Examples */

2024-12-16T03:54:06Z

Numerical Examples

← Older revision		Revision as of 23:54, 15 December 2024
Line 201:		Line 201:
	</math>		</math>

	* Iteration 3:[[File:~~FTRL_Linear_Loss_Stabilization~~.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]		* Iteration 3:[[File:FTRL_Linear_Loss_Stabilization_Corrected.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]
	<math>		<math>
	w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) + (-0.25) + 0.05}{3} = 0.4.		w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) + (-0.25) + 0.05}{3} = 0.4.

Fall2024 Wiki Team15: /* Example 1: Linear Loss with Quadratic Regularization */

2024-12-16T03:34:00Z

Example 1: Linear Loss with Quadratic Regularization

← Older revision		Revision as of 23:34, 15 December 2024
Line 189:		Line 189:

	'''Step-by-Step Calculation:'''		'''Step-by-Step Calculation:'''
	Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = 0.25</math>, <math>a_3 = -3</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 3</math>.		Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = -0.25</math>, <math>a_3 = 0.05</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 3</math>.

	* Iteration 1:		* Iteration 1:
Line 198:		Line 198:
	* Iteration 2:		* Iteration 2:
	<math>		<math>
	w_2 = -\frac{a_1 + a_2}{\lambda} = -\frac{(-1) + 0.25}{3} = -0.5.		w_2 = -\frac{a_1 + a_2}{\lambda} = -\frac{(-1) + (-0.25)}{3} = -0.25.
	</math>		</math>

	* Iteration 3:[[File:FTRL_Linear_Loss_Stabilization.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]		* Iteration 3:[[File:FTRL_Linear_Loss_Stabilization.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]
	<math>		<math>
	w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) ~~+ 2~~ + (-3)}{3} = 1.		w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) + (-0.25) + 0.05}{3} = 0.4.
	</math>		</math>

Fall2024 Wiki Team15: /* Numerical Examples */

2024-12-16T03:32:20Z

Numerical Examples

← Older revision		Revision as of 23:32, 15 December 2024
Line 189:		Line 189:

	'''Step-by-Step Calculation:'''		'''Step-by-Step Calculation:'''
	Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = 2</math>, <math>a_3 = -3</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 3</math>.		Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = 0.25</math>, <math>a_3 = -3</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 3</math>.

	* Iteration 1:		* Iteration 1:
	<math>		<math>
	w_1 = -\frac{a_1}{\lambda} = -\frac{-1}{2} = 0.5.		w_1 = -\frac{a_1}{\lambda} = -\frac{-1}{3} = 0.33.
	</math>		</math>

	* Iteration 2:		* Iteration 2:
	<math>		<math>
	w_2 = -\frac{a_1 + a_2}{\lambda} = -\frac{(-1) + 2}{2} = -0.5.		w_2 = -\frac{a_1 + a_2}{\lambda} = -\frac{(-1) + 0.25}{3} = -0.5.
	</math>		</math>

	* Iteration 3:[[File:FTRL_Linear_Loss_Stabilization.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]		* Iteration 3:[[File:FTRL_Linear_Loss_Stabilization.png\|thumb\|450px\|alt=Stabilizing effects of FTRL for linear loss function\|'''Fig 1.''' Stabilizing effects of FTRL for linear loss function. <br> Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over tim]]
	<math>		<math>
	w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) + 2 + (-3)}{2} = 1.		w_3 = -\frac{a_1 + a_2 + a_3}{\lambda} = -\frac{(-1) + 2 + (-3)}{3} = 1.
	</math>		</math>

Fall2024 Wiki Team15: /* Example 1: Linear Loss with Quadratic Regularization */

2024-12-16T03:30:33Z

Example 1: Linear Loss with Quadratic Regularization

← Older revision		Revision as of 23:30, 15 December 2024
Line 189:		Line 189:

	'''Step-by-Step Calculation:'''		'''Step-by-Step Calculation:'''
	Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = 2</math>, <math>a_3 = -3</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 2</math>.		Let the gradient of the loss functions be <math>a_1 = -1</math>, <math>a_2 = 2</math>, <math>a_3 = -3</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 3</math>.

	* Iteration 1:		* Iteration 1:

Fall2024 Wiki Team15: /* Example 1: Linear Loss with Quadratic Regularization */

2024-12-16T01:42:57Z

Example 1: Linear Loss with Quadratic Regularization

← Older revision		Revision as of 21:42, 15 December 2024
Line 209:		Line 209:
	The updates for <math>w</math> gradually converge rather than overshooting or oscillating, thanks to regularization reducing large shifts with the term <math>\lambda</math> in the update rule. Decision variables calculated with and without the regularization term in the update rule (i.e. setting <math>\lambda=1</math>) are compared for 10 iterations to demonstrate this stabilizing effect.		The updates for <math>w</math> gradually converge rather than overshooting or oscillating, thanks to regularization reducing large shifts with the term <math>\lambda</math> in the update rule. Decision variables calculated with and without the regularization term in the update rule (i.e. setting <math>\lambda=1</math>) are compared for 10 iterations to demonstrate this stabilizing effect.
	* Without Regularization: Updates (<math>w_t</math>) exhibit significant fluctuations as they respond solely to the cumulative gradients <math>\sum_{i=1}^t a_i</math>.		* Without Regularization: Updates (<math>w_t</math>) exhibit significant fluctuations as they respond solely to the cumulative gradients <math>\sum_{i=1}^t a_i</math>.
	* With Regularization: Updates are smoother, as the regularization term <math>\lambda w</math> reduces the influence of cumulative gradients, stabilizing the updates over time.		* With Regularization: Updates are smoother, as the regularization term <math>\lambda</math> reduces the influence of cumulative gradients, stabilizing the updates over time.

	=== Example 2: Quadratic Loss with Quadratic Regularization ===		=== Example 2: Quadratic Loss with Quadratic Regularization ===
Line 229:		Line 229:

	'''Step-by-Step Calculation:'''		'''Step-by-Step Calculation:'''
	Let coefficients <math>b_1 = 1</math>, <math>b_2 = 2</math>, <math>b_3 = 3</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = ~~0.5~~</math>.		Let coefficients <math>b_1 = 1</math>, <math>b_2 = 2</math>, <math>b_3 = 3</math>, initialize <math>w_0 = 0</math>, and choose <math>\lambda = 2</math>.

	* Iteration 1:		* Iteration 1:
	<math>		<math>
	w_1 = \frac{b_1}{1 + \lambda} = \frac{1}{1 + ~~0.5~~} = 0.33.		w_1 = \frac{b_1}{1 + \lambda} = \frac{1}{1 + 2} = 0.33.
	</math>		</math>

Fall2024 Wiki Team15: /* Numerical Examples */

2024-12-16T01:39:34Z

Numerical Examples

← Older revision		Revision as of 21:39, 15 December 2024
Line 207:		Line 207:

	'''Observation:'''		'''Observation:'''
	The updates for <math>w</math> gradually converge rather than overshooting or oscillating, thanks to regularization reducing large shifts with the term <math>\lambda</math> in the update rule. Decision variables calculated with and without the regularization term (i.e. setting <math>\lambda=1</math> ~~in the update rule~~) are compared for 10 iterations to demonstrate this stabilizing effect.		The updates for <math>w</math> gradually converge rather than overshooting or oscillating, thanks to regularization reducing large shifts with the term <math>\lambda</math> in the update rule. Decision variables calculated with and without the regularization term in the update rule (i.e. setting <math>\lambda=1</math>) are compared for 10 iterations to demonstrate this stabilizing effect.
	* Without Regularization: Updates (<math>w_t</math>) exhibit significant fluctuations as they respond solely to the cumulative gradients <math>\sum_{i=1}^t a_i</math>.		* Without Regularization: Updates (<math>w_t</math>) exhibit significant fluctuations as they respond solely to the cumulative gradients <math>\sum_{i=1}^t a_i</math>.
	* With Regularization: Updates are smoother, as the regularization term <math>\lambda w</math> reduces the influence of cumulative gradients, stabilizing the updates over time.		* With Regularization: Updates are smoother, as the regularization term <math>\lambda w</math> reduces the influence of cumulative gradients, stabilizing the updates over time.