FTRL algorithm

Author: Tsz Ki Peter Wei (tmw86), Nhi Nguyen (npn25), Colin Erb (cte24) (ChemE 6800 Fall 2024)

Algorithm Discussion

Example 1: Linear Loss with Quadratic Regularization

Problem Setup:

• Decision variable: $w\in \mathbb {R}$,
• Loss functions: $f_{t}(w)=a_{t}w$, where $a_{t}$ are coefficients provided by the environment. In the case of a linear loss function, $a_{t}$ determines the slope or gradient of the loss function $f_{t}(w)$,
• Regularization: $R(w)={\frac {\lambda }{2}}w^{2}$, where $\lambda$ is a hyperparameter that determines the update rate.

FTRL Update Rule: The update rule is: $w_{t+1}=\arg \min _{w}\left(\sum _{i=1}^{t}a_{i}w+{\frac {\lambda }{2}}w^{2}\right).$

To minimize, take the derivative and set it to zero: ${\frac {\partial }{\partial w}}\left(\sum _{i=1}^{t}a_{i}w+{\frac {\lambda }{2}}w^{2}\right)=\sum _{i=1}^{t}a_{i}+\lambda w=0.$

Rearranging gives: $w_{t+1}=-{\frac {\sum _{i=1}^{t}a_{i}}{\lambda }}.$

Step-by-Step Calculation: Let the gradient of the loss functions be $a_{1}=2$, $a_{2}=3$, $a_{3}=-1$, initialize $w_{0}=0$, and choose $\lambda =2$.

• Iteration 1:

$w_{1}=-{\frac {a_{1}}{\lambda }}=-{\frac {2}{2}}=-1.$

• Iteration 2:

$w_{2}=-{\frac {a_{1}+a_{2}}{\lambda }}=-{\frac {2+3}{2}}=-2.5.$

• Iteration 3:

$w_{3}=-{\frac {a_{1}+a_{2}+a_{3}}{\lambda }}=-{\frac {2+3-1}{2}}=-2.$

Observation: The updates for $w$ gradually converge rather than overshooting or oscillating, thanks to regularization reducing large shifts with the term $\lambda w$ in the update rule. Decision variables calculated with and without the regularization term are compared for 10 iterations to demonstrate this stabilizing effect.

Figure 1: Stabilizing Effects of FTRL for Linear Loss Function

Stabilizing effects of FTRL for linear loss function. Without regularization (blue), updates fluctuate significantly. With regularization (orange), updates stabilize over time.

• Without Regularization: Updates ($w_{t}$) exhibit significant fluctuations as they respond solely to the cumulative gradients $\sum _{i=1}^{t}a_{i}$.
• With Regularization: Updates are smoother, as the regularization term $\lambda w$ reduces the influence of cumulative gradients, stabilizing the updates over time.

Example 2: Quadratic Loss with Quadratic Regularization

Problem Setup:

• Quadratic loss function: $f_{t}(w)={\frac {1}{2}}(w-b_{t})^{2}$, where $b_{t}$ is the target set by the adversary,
• Regularization: $R(w)={\frac {\lambda }{2}}w^{2}$.

FTRL Update Rule: The update rule becomes: $w_{t+1}=\arg \min _{w}\left(\sum _{i=1}^{t}{\frac {1}{2}}(w-b_{i})^{2}+{\frac {\lambda }{2}}w^{2}\right).$

Simplifying: $w_{t+1}={\frac {\sum _{i=1}^{t}b_{i}}{t+\lambda }}.$

Step-by-Step Calculation: Let coefficients $b_{1}=1$, $b_{2}=2$, $b_{3}=3$, initialize $w_{0}=0$, and choose $\lambda =1$.

• Iteration 1:

$w_{1}={\frac {b_{1}}{1+\lambda }}={\frac {1}{1+1}}=0.5.$

• Iteration 2:

$w_{2}={\frac {b_{1}+b_{2}}{2+\lambda }}={\frac {1+2}{2+1}}=1.$

• Iteration 3:

$w_{3}={\frac {b_{1}+b_{2}+b_{3}}{3+\lambda }}={\frac {1+2+3}{3+1}}=1.5.$

Observation: The denominator $t+\lambda$ ensures that updates become smaller over time, stabilizing the solution as more data is observed. Decision variables calculated with and without the regularization term are compared for 10 iterations to demonstrate this stabilizing effect in Figure 2.

Figure 2: Stabilizing Effects of FTRL for Quadratic Loss Function

• Without Regularization: Linear and unbounded growth. Updates ($w_{t}$) grow rapidly as they are driven entirely by the cumulative target values $\sum _{i=1}^{t}b_{i}$, leading to unbounded growth over time.
• With Regularization: Gradual convergence with stabilized updates. The denominator $t+\lambda$ dampens the influence of cumulative targets, stabilizing the updates.

Application

The FTRL algorithm is a powerful framework for online learning problems due to its ability to handle large datasets and adapt to new data in real-time. It has been applied in finance, healthcare, and electrical engineering. In finance, the FTRL algorithm has been used in online advertising, e-commerce recommendations, and fraud detection . In healthcare, the FTRL algorithm has been used for the analysis of patient data . In electrical engineering, the FTRL algorithm has been used to optimize the performance of electricity-generating systems . Specific case studies of the FTRL algorithm in each field are shown below.

Finance

The first application that the FTRL algorithm was used for was online advertising by Google . In this case study, the FTRL algorithm was used to predict ad click-through rates (CTR) for sponsored search advertising at Google . They were able to demonstrate the FTRL algorithm’s ability to both predict accurately and also be sparse compared to other online learning algorithms . Additional case studies in the finance sector have been explored such as online portfolio optimization . In this case study, the authors were able to build off the original FTRL algorithm to come up with a new algorithm called VB-FTRL that can maximize a trader’s return on their portfolio while having reduced runtime compared to the best-performing algorithm (Universal Portfolios) .  

Healthcare

In healthcare, the FTRL algorithm was used in a case study to classify thyroid nodules for Thyroid cancer diagnosis . In this case study, the authors proposed a novel FTRL-Deep Neural Network technique to precisely classify thyroid nodules into benign or malignant. The algorithm would analyze ultrasound images of the thyroid nodules and then determine whether or not the patient has thyroid cancer or not . They were able to show that their FTRL-Deep Neural Network algorithm had superior accuracy compared to other algorithms such as the Hybrid Feature Cropping Network and Multi-Channel Convolutional Neural Network .

Electrical Engineering

Recently, FTRL has been applied to electricity-generating systems. A recent case study used FTRL to optimize the output of a solar panel system to offset the effect of non-uniform irradiance . They developed this algorithm to control a system of switches that would determine the optimal configuration of the solar panel array when non-uniform irradiance is detected to maximize the power output from the solar panel . In an earlier case study, researchers were able to use an FTRL algorithm to predict when low voltages would occur in a power distribution system, allowing for better system management .

Softwares and Platforms that Utilize the FTRL Algorithm

Software tools such as H2O Driverless AI and Keras can utilize the FTRL algorithm for various machine-learning applications . In addition, platforms such as Google Ads utilize the FTRL algorithm . These are just a few examples of softwares and platforms where the FTRL algorithm is used. As machine-learning becomes more and more widespread in different applications, the usage of the FTRL algorithm is expected to increase.

Conclusion

The FTRL algorithm is most useful in online learning, where large amounts of data need to be processed in real time to enable accurate predictions. Currently, the FTRL algorithm is used on platforms such as Google Ads and included in software tools such as Keras and H2O driverless AI. In recent years, other areas of application that involve online learning, such as healthcare and power systems, have been explored for the FTRL algorithm.

The algorithm works through a minimization of a linearized loss function considering all historical data and at least one regularization term every time a new point is added. This minimization operation is reasonably space and time-efficient due to linearization, and due to flexibility in how the weight vector is regularized, very versatile. The simplest implementation of the algorithm is equivalent to gradient descent, while more complex versions of the algorithm are able to effectively stabilize the weight vector as the dataset grows and maintain sparsity in its updates through the inclusion of an L1 norm.

From the numerical examples, it is evident that regularization plays a pivotal role in ensuring convergence. For linear loss functions, FTRL mitigates oscillatory behavior by reducing the influence of cumulative gradients. For quadratic loss functions, regularization stabilizes updates over time, resulting in gradual convergence and bounded growth. These properties underline FTRL's adaptability in noisy environments and its capacity to produce reliable predictions.

Looking ahead, potential areas for improvement include enhancing computational efficiency for more complex loss functions and exploring hybrid regularization schemes that combine the strengths of L1, L2, and other techniques. Additionally, further advancements in applying FTRL to evolving fields such as autonomous systems, environmental modeling, and personalized medicine could broaden its impact.

References

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