# Enhancing Multistep Brent Oil Price Forecasting with a Multi-Aspect
Metaheuristic Optimization Approach and Ensemble Deep Learning Models

Mohammed Alruqimi<EMAIL_ADDRESS>Luca Di Persio
<EMAIL_ADDRESS>
###### Abstract

Accurate crude oil price forecasting is crucial for various economic
activities, including energy trading, risk management, and investment
planning. Although deep learning models have emerged as powerful tools for
crude oil price forecasting, achieving accurate forecasts remains challenging.
Deep learning models’ performance is heavily influenced by hyperparameters
tuning, and they are expected to perform differently under various
circumstances. Furthermore, price volatility is also sensitive to external
factors such as world events. To address these limitations, we propose a
hybrid approach combining metaheuristic optimisation and an ensemble of five
popular neural network architectures used in time series forecasting. Unlike
existing methods that apply metaheuristics to optimise hyperparameters within
the neural network architecture, we exploit the GWO metaheuristic optimiser at
four levels: feature selection, data preparation, model training, and forecast
blending. The proposed approach has been evaluated for forecasting three-ahead
days using real-world Brent crude oil price data, and the obtained results
demonstrate that the proposed approach improves the forecasting performance
measured using various benchmarks, achieving 0.000127 of MSE.

###### keywords:

Crude oil price forecasting , Brent oil forecasting , Grey Wolf Optimizer ,
ensemble model , time series forecasting.

††journal: Applied Energy

[uinvr]organization=University of Verona,country=Italy

##  1 Introduction

Time series forecasting plays a crucial role in various industries, from
finance to logistics to energy, as it provides valuable insights into future
trends and helps businesses make informed decisions. However, crude oil
forecasting is particularly challenging due to the complex dynamics of the oil
market and the non-linear and volatile nature of crude oil prices.

In recent years, deep learning techniques have gained prominence for their
ability to capture intricate patterns in time series data. Long Short-Term
Memory (LSTM) and Gated Recurrent Unit (GRU) networks have emerged as popular
choices for modelling temporal dependencies in such forecasting tasks [1, 2].
Their success is attributed to their inherent ability to handle long-range
dependencies, making them particularly suitable for time series data with
varying temporal patterns.

Nonetheless, achieving accurate predictions remains a challenge. Individual
deep-learning models typically struggle to capture all data patterns, and
their performance is heavily dependent on the training configuration. The
effectiveness of individual models varies depending on the given dataset and
conditions. Furthermore, many external factors influence crude oil prices,
including geopolitical events and global economic conditions [3, 4, 5, 6].

In other words, the capacity to enhance the capture of dataset patterns,
identify external factors influencing the formation of these patterns, and
select the appropriate network architecture while configuring it optimally are
critical factors that significantly impact forecasting performance. The
optimal choice often varies depending on the dataset’s characteristics and the
specific forecasting problem at hand.

To address these challenges, we propose a hybrid approach to combine the Grey
Wolf Optimizer (GWO) with an ensemble of five deep learning networks- LSTM,
GRU, CNN-LSTM, CNN-LSTM-attention, and an encoder-decoder-LSTM. GWO is a bio-
inspired metaheuristic optimisation algorithm which simulates the leadership
hierarchy and grey wolf hunting mechanism in nature. The objective is to make
a significant contribution to the advancement of research in the field of
crude oil forecasting, building upon the recognition of the challenges
mentioned above and the advantages of meta-heuristic optimisation and
conditional forecast combination. This approach can be particularly beneficial
in forecasting tasks where different models of diverse structures and data
assumptions are expected to perform differently under various conditions. For
example, one neural network can perform better than another in a specific
dataset and vice-versa.

Metaheuristic optimisation techniques present a powerful solution for optimal
hyperparameters tuning [7, 8]. Metaheuristics excels in reaching near-optimal
solutions with limited information and computational resources. These
algorithms generally give better results and converge faster than blind
approaches like Exhaustive Grid Search. This makes them particularly valuable
in optimising deep learning methods for time series forecasting.

Although some researchers have already exploited metaheuristic optimisation
for tunning hyperparameters (such as epochs numbers, batch size) of ML models
to improve WTI crude oil forecasting, i.e. [9], we believe this exploitation
can be extended to optimise the entire process including parameters outside
the ML network structures such as feature selection, defining the suitable
sliding window, and to fuse multiple forecasts.

The main contributions of this work are summarised as follows:

  * 1.

An ensemble model to enhance the prediction accuracy of crude oil price.

  * 2.

Evaluating five different neural network (NN) models with various
architectures for multi-step crude oil forecasting.

  * 3.

Identifying an optimal configuration for each model using the GWO meta-
heuristic algorithm.

  * 4.

Introducing a novel method to implement weighted ensemble learning through a
meta heuristic optimisation algorithm.

##  2 Related works

Methods used to forecast crude oil prices can be categorised into three
primary groups: statistical, econometric, and machine learning-based
approaches. Statistical methods provide a foundation for understanding and
analysing historical oil price data. They are handy for identifying trends,
seasonal patterns, and cyclical fluctuations in oil prices [10, 11]. Common
statistical techniques employed in crude oil forecasting include time series
analysis and statistical forecasting models, such as autoregressive integrated
moving average (ARIMA) [11]. Statistical methods are relatively simple to
understand and implement. However, statistical methods are limited in
capturing the nonlinear and unpredictable nature of oil price movements,
especially in response to exogenous events. Econometric methods are grounded
in statistical theory and economic principles, and they are particularly
useful for understanding the causal relationships between economic variables
and oil prices. Vector Autoregression (VAR) is a common econometric model used
in crude oil forecasting [12, 13]. However, Econometric models often make
assumptions about the underlying data distribution and the relationship
between variables. Violations of these assumptions lead to less reliable
forecasts.

Deep learning techniques have become increasingly popular in the field of time
series forecasting in general due to their ability to capture non-linear and
more complex patterns in the data [14, 15]. Researchers have harnessed various
deep learning architectures, including long short-term memory (LSTM) networks
[1, 2, 16, 17], gated recurrent units (GRUs) [18, 17, 19], convolutional
neural networks (CNNs) [20, 21], and transformer models [22], to forecast
crude oil prices accurately.

In recent years, GRU (Gated Recurrent Unit) and LSTM (Long Short-Term Memory)
networks have emerged as prominent choices for deep learning applications in
crude oil price forecasting due to their ability to capture long-term
dependencies and handle sequential data effectively. Several studies have
demonstrated the superiority of GRU and LSTM networks for crude oil price
forecasting [14]. To further enhance their forecasting capabilities,
researchers have explored various hybrid and combination methods, such as
integrating convolutional neural networks (CNN) and attention mechanisms into
GRU and LSTM architectures [20, 19, 18, 23, 24, 25, 26]. Additionally,
incorporating external factors has been a focus, with studies demonstrating
the effectiveness of these strategies in refining crude oil price predictions
[27, 28, 25, 29].

However, the efficacy of these approaches often hinges on the quality and
comprehensiveness of feature engineering and the availability of extensive
historical data [27], in addition to the optimal hyperparameters setup.
Recently, metaheuristic algorithms have been popular for optimising machine
learning models training [7, 30]. These algorithms have been employed to some
extent for optimising ML models for crude oil forecasting, i.e. [9], leading
to improved prediction accuracy. On the other hand, This work falls within the
few research works that utilise the Brent crude oil database, as most research
typically relies on the Texas crude oil database.

##  3 Preliminaries

###  3.1 Metaheuristic optimisation

At the core of machine learning models is the process of optimisation, wherein
algorithms are trained to perform functions with optimal efficiency.
Successful hyperparameter optimisation is essential for achieving precision in
a model. The thoughtful selection of model configurations profoundly impacts
accuracy and proficiency in handling specific tasks. However, the optimisation
of hyperparameters can present a challenging undertaking. Metaheuristics have
become powerful optimisation tools, thanks to their simplicity and capability
to effectively address complex NP-hard problems with practical computational
resources [31, 32]. Metaheuristic optimisation algorithms are a family of
mathematical-concepts-based methods used to find good solutions to complex
optimisation problems. This type of algorithm provides efficient solutions in
scenarios where traditional methods may struggle due to complex and dynamic
environments. They are designed to explore the search space in a way that is
likely to find good solutions, even if they do not always find the optimal
solution. Metaheuristics are not bound by specific problem structures, do not
need gradient information and can adapt to various optimisation challenges.
Their efficiency in solving real-world problems with limited resources and
uncertainties makes metaheuristics one of the most notable achievements of the
last two decades in operations research [30, 33, 34]. Metaheuristic algorithms
can be grouped into different families based on the natural phenomena they use
to guide the search process, such as, for example, evolution or ant behaviour
[33]. Over the past few years, population-based methods have been successfully
employed to address a diverse range of real-world challenges, including
COVID-19 surveillance and forecasting, cloud-edge computing optimisation,
energy-efficient cloud computing, feature selection, global optimisation,
credit card fraud detection, air pollution forecasting, network intrusion
detection, and optimisation of various machine learning models [7]. However,
the choice of an algorithm largely depends on the optimisation problem at
hand. There is no agreed guideline for large-scale nonlinear global
optimisation problems for how to choose and what to choose [33].

###  3.2 Grey Wolf Optimizer (GWO)

The Grey Wolf Optimizer (GWO) is a bio-inspired swarm intelligence
optimisation algorithm inspired by grey wolves, which has been introduced in
[35] in 2014. This algorithm mimics the leadership hierarchy and hunting
mechanism of grey wolves in nature. To simulate the leadership hierarchy in
the GWO, four types of grey wolves—alpha $(\alpha)$, beta $(\beta)$, delta
$(\delta)$, and omega $(\omega)$—are employed. These categories simulate the
leadership hierarchy, where the optimisation process is guided by three wolves
($\alpha,\beta$, and $\delta$), while the omega $(\omega)$ wolves follow. As
observed in the hunting process, grey wolves tend to encircle their prey, a
phenomenon mathematically modelled by equations (1) and (2).

$\displaystyle\vec{D}=|\vec{C}.\vec{X}_{p}(t)-\vec{X}(t)|$ (1)
$\displaystyle\vec{X}(t+1)=\vec{X}_{p}(t)-\vec{A}.\vec{D}$ (2)

Where $t$ is the current iteration, $\vec{A}$ and $\vec{C}$ are coefficient
vectors, $\vec{X}_{p}$ is the vector of the prey position, and $\vec{X}$
indicates the vector of the grey wolf position. $\vec{A}$ and $\vec{C}$
vectors can be calculated as illustrated in equations (3) and (4).

$\displaystyle\vec{A}=2\vec{a}.\vec{r_{1}}-\vec{a}$ (3)
$\displaystyle\vec{C}=2.\vec{r_{2}}$ (4)

The elements of vector a undergo a linear decrease from 2 to 0 across
iterations, with $r_{1}$ and $r_{2}$ being random vectors within the [0, 1]
range. In emulating the hunting behaviour of grey wolves, it is assumed that
$\alpha$ (the top candidate solution), $\beta$, and $\delta$ possess superior
knowledge regarding the potential prey positions. Consequently, the three best
solutions obtained thus far are preserved, compelling other search agents
(including $\omega$) to adjust their positions based on the optimal search
agent positions. Further insights into the GWO algorithm can be found in [35,
36].

Figure 1: Typical wolf-pack hunting behaviours: (A) chasing, approaching, and
tracking prey (B–D) pursuing, harassing, and encircling (E) stationary
situation and attack [37].

###  3.3 Deep learning architectures for time series forecasting

LSTM (Long Short-Term Memory) and GRU (Gated Recurrent Unit) are two types of
recurrent neural networks (RNNs) that have gained immense popularity in time
series forecasting due to their ability to capture temporal dependencies in
data effectively. These dependencies, often characterised by patterns that
persist over time, are crucial for accurate forecasting. LSTM and GRU have
demonstrated superior performance in various time series forecasting tasks,
ranging from energy price prediction to weather forecasting [14]. Their
ability to handle complex temporal dynamics and relatively simple architecture
compared to more advanced models like transformers and GANs have made them the
go-to choice for many time series forecasting applications. Researchers are
constantly exploring ways to enhance the forecasting accuracy of LSTM and GRU
models by combining them with convolutional neural networks (CNNs) to extract
spatial features from time series data, incorporating attention mechanisms to
focus on relevant portions of the input sequence, incorporating relevant
external factors, and integrating statistical approaches to leverage the
strengths of both neural networks and traditional forecasting methods [20, 23,
24, 25, 27, 26]. In this work, we examine the following popular deep-learning
architectures:

  * 1.

Bi-LSTM, which is a bidirectional Long Short-Term Memory (Bi-LSTM) model; one
LSTM layer followed by two full connected layers with relu activation
function.

  * 2.

Bi-GRU, is a bidirectional Gated Recurrent Unit (Bi-GRU) model; one GRU layer
followed by two fully connected layers with a relu activation function.

  * 3.

CNN-Bi-LSTM, This model combines two convolutional neural networks (CNNs) to
extract input features and two LSTM layers for learning temporal dependencies
in the data, followed by a fully connected layer with relu activation
function.

  * 4.

CNN-Bi-LSTM-Attention, which adds an attention technique for the previous one.

  * 5.

Encoder-decoder-Bi-LSTM is an encoder-decoder architecture with two LSTMs with
128 units for the encoder and another LSTM with 200 units for the decoder.

To sum up, We train five models to predict three ahead-days, using the GWO
metaheuristic optimisation to optimise training hyperparameters and
incorporating two external factors (USDX and SENT) as described in the dataset
section.

##  4 Proposed approach

In this work, We propose to combine the Grey Wolf Optimizer (GWO) with an
ensemble of five deep learning networks- LSTM, GRU, CNN-LSTM, CNN-LSTM-
attention, an encoder-decoder-LSTM for enhancing Brent crude oil price
forecasting.

Figure 2: Proposed Approach

The aim is to enhance the predictive accuracy of crude oil prices by
leveraging the acknowledged benefits of both metaheuristic optimisation and
ensemble forecasting methods. The proposed approach is implemented in two main
stages, as shown in the figure (2). In the first stage, we train five deep
neural networks, proven for their proficiency in handling time series
prediction. In this stage, the GWO algorithm is used to find optimal
parameters for tuning the neural networks’ training. This stage also
encompasses optimisation of feature selection and determining the window size.
In the second stage, The GWO is utilised to blend the predictions obtained in
the first stage at the optimal configuration for each neural network. To
implement our approach, we build our code upon mealpy library [34], where
users can select from a wide range of advanced population-based metaheuristic
algorithms.

###  4.1 Multi-aspect metaheuristic optimisation

The Grey Wolf Optimization (GWO) algorithm is employed at four different
stages to optimise crucial aspects of the ensemble forecasting process:
feature selection, sliding window size determination, model hyperparameter
tuning, and final forecast blending. This systematic approach ensures that the
ensemble model leverages the strengths of all constituent models and produces
highly accurate predictions

####  4.1.1 Feature selection

Forecasting crude oil prices is significantly influenced by external factors,
which play a pivotal role in shaping the market dynamics. Factors such as
geopolitical events, economic indicators, global demand-supply imbalances, and
environmental policies can substantially impact oil prices [29]. Understanding
and incorporating these external factors into forecasting models is crucial
for accurate predictions, as they contribute to the volatility and
unpredictability of the oil market. USD index rate and sentiment analysis
index are two popular external variables that have been widely applied by
researchers in the tasks of forecasting crude oil price [6, 26, 4, 38]. The
USDX index, reflecting the performance of the U.S. dollar against a basket of
major currencies, offers valuable information on currency strength and global
economic conditions. Considering the substantial influence of currency
fluctuations on oil prices, the USDX index is a crucial indicator.
Simultaneously, sentiment analysis, which gauges market sentiment from news
and social media, contributes to understanding market psychology and potential
price movements. Integrating eternal factors enhances the model’s ability to
capture complex relationships and dynamic market influences, consequently
improving the accuracy of crude oil price forecasts [27, 28].In this work, we
examined integrating both indices, USDX and sentiment score, individually and
combined.

####  4.1.2 Determination of sliding window size

The determination of the sliding window size plays a pivotal role in time
series forecasting. This parameter represents the temporal scope of historical
data used to train a model, influencing its ability to capture patterns and
trends. Selecting an optimal sliding window size is a delicate balance between
incorporating sufficient historical information for meaningful pattern
recognition and avoiding overfitting or loss of relevance. A smaller window
may lead to overlooking essential patterns, while a more significant window
might introduce noise or outdated information. Thus, carefully considering and
optimising the sliding window size is crucial to ensure the trained model
learns from past data effectively, contributing to more accurate and reliable
crude oil price forecasts.

####  4.1.3 Tuning of model hyperparameters

Hyperparameter tuning, the process of carefully adjusting the settings of a
deep learning model, is crucial for optimal performance of deep learning
networks. Finding optimal hyperparameters (such as learning rate, optimiser,
hidden and unite number) significantly impacts training efficiency and model
accuracy. However, tuning these hyperparameters is challenging due to their
effects’ interplay and the search space’s high dimensionality. Manual
exploration can be time-consuming and error-prone, while automated techniques
like grid search and Bayesian optimisation can be computationally expensive.
The emergence of metaheuristic algorithms like genetic algorithms and particle
swarm optimisation offers promising avenues for efficient hyperparameter
tuning. These algorithms can explore the search space more effectively and
efficiently, leading to better-performing models.

####  4.1.4 Blending of final forecasts

Ensemble forecast methods can enhance accuracy by combining forecasts of
diverse models that capture different aspects of the data. This often leads to
better generalisation and robustness. However, the success of the ensemble
methods depends on the individual models’ diversity and quality and the nature
of the data. In practice, ensemble methods are known to provide performance
improvements in many cases, but there are situations where individual models
might perform equally well or even outperform an ensemble. Variant-Weight
technique is a well-established method for ensemble forecasting, in which
multiple models are combined by assigning distinct weights to their respective
predictions [24, 23]. The success of this method hinges on identifying the
optimal weight allocation for each model. To this end, we employ GWO to
optimise the weight distribution for our target models.

##  5 Experiments

This section outlines the dataset, details the experimental setup, and delves
into the obtained results.

###  5.1 Dataset

The dataset used for the experiments consists of the daily observations of the
Brent crude oil price for the period from (January 3, 2012, to April 1, 2021),
obtained from Bloomberg, including the period where the COVID-19 pandemic has
affected energy and stock markets. It also includes Two external factors: the
daily USD closing price (USDX) from Bloomberg and a daily cumulative
sentimental score (SENT) obtained by the CrudeBERT model described in [39].
CrudeBERT is a variant of FinBERT that has been fine-tuned towards assessing
the impact of market events on crude oil prices, focusing on frequently
occurring market events and their impact on market prices according to Adam
Smith’s theory of supply and demand. Mainly, CrudeBERT dataset used headlines
originating from 1034 unique news sources, published on the Dow Jones
newswires (approx. 21,200), Reuters (approx. 3,000), Bloomberg (approx.
1,100), and Platts (approx. 870). The sentimental score data is described and
publicly available in [39]. The period from 2012 to 2021 was chosen for
analysis due to the availability of sentiment scores during this time frame.
Figure 3 displays the time-series plot of the daily closing price of Brent for
this period. The dataset has been cleaned, normalised, and then split as
follows: 80% for training, 10% for validation, and 10% for testing.

Figure 4 illustrates the trends of Brent price, USD index (USDX), and the
sentiment score (SENT) for the period from 2012 to 2021.

Figure 3: Brent oil price trend from 2012 to 2021 Figure 4: Brent price, USD
index (USDX), and the sentiment score (SENT) for the period from 2012 to 2021

###  5.2 Experimental setup

As mentioned earlier, our experiments are conducted in two stages. In the
first stage, the objective is to identify optimal values for hyperparameters
of each model (optimal configuration). The targeted models are described in
Section (3.3), and the targeted hyperparameters are described in Table (1).
Subsequently, we train and evaluate each model individually using its
corresponding optimal configuration. The forecasts obtained from each model
serve as inputs for the second stage. In the second stage, we aim to optimally
blend the forecasts obtained individually from each model in the first stage
to produce the final forecast.

In order to determine the optimal configuration for each model, the Grey Wolf
Optimization (GWO) has been executed through five independent runs for each
network. The objective function is specifically designed to minimize Mean
Squared Error (MSE) loss, aiming to attain the best global solution. The best
global solution is simply a vector containing the optimal values identified
for the targeted hyperparameters, corresponding to the smallest Mean Squared
Error (MSE) at these values.

Table 1: The list of hyperparameters to be optimised by the GWO algorithm for
each network, combined with the external features and the window size. The
’range’ column shows the bound of the search space defined for the GWO.

Parameter |  Range |  Description
---|---|---
learning rate |  (0.0001 - 0.1) |  this parameter, crucial for controlling the step size during model training
hidden unites |  ($2^{n}$, where $1\leq n\leq 8$) |  the number of hidden units
optimiser |  7 options |  The optimisation algorithm employed during training, the seven options are (SGD, RMSprop, Adagrad, Adadelta, AdamW, Adam, and Adamax)
dropout |  (0.2 - 0.5) |  Dropout is a regularisation technique that randomly drops nodes from the network during training to prevent model overfitting.
time-steps |  (3-30) |  The number of timesteps used to represent the input data is crucial for capturing the temporal dynamics of the series.
external factors |  4 options |  to examine the impact of integrating external factors. The range includes the following options (None, USDX, SENT, and USDX + SENT)

Generally, implementation of the GWO metaheuristic optimisation involves
defining the main following procedures: problem preparation, objective
function definition, population initialisation, and optimisation process.
Firstly, the problem preparation involves specifying the hyperparameters to be
optimised and establishing their respective ranges. The objective function is
a pivotal element, representing the metric that the metaheuristic aims to
either maximise or minimise during the optimisation process. This function
typically encapsulates the performance of the deep learning model, such as
accuracy or loss. The population in the context of metaheuristic optimisation
refers to a collection of candidate solutions simultaneously. The
metaheuristic explores and refines this population throughout the optimisation
iterations to iteratively improve the model’s performance. A larger population
generally provides more diversity and allows for a more thorough search space
exploration, but it also increases computational cost. The hyperparameters and
their respective ranges (bounds or search space) are as shown in Table (1).

To reduce the problem dimension for the sake of alleviating resources
consumption during the running of the GWO, we selected the most essential
hyperparameters. The batch size and epoch number have also been excluded from
the GWO problem dimensions. Instead, the batch size has been experimentally
set to 16, and the early-stop technique is used to terminate epochs
automatically.

###  5.3 Objective function and evaluation metrics

For each model, the GWO has been run multiple independent runs with an
objective function to minimise the Mean square error (MSE), which can be
calculated according to the equation (5). However, to evaluate the final
ensemble and individual models, we used the traditional ML measurements: mean
square error (MSE), root mean square error (RMSE) - equation (6), and mean
absolute error (MAE)- equation (7):

$\text{MSE}(y,\hat{y})=\frac{\sum_{i=0}^{N-1}(y_{i}-\hat{y}_{i})^{2}}{N}$
$\text{RMSE}(y,\hat{y})=\sqrt{\frac{\sum_{i=0}^{N-1}(y_{i}-\hat{y}_{i})^{2}}{N}}$
$\text{MAE}(y,\hat{y})=(\frac{1}{n})\sum_{i=1}^{n}\left|y_{i}-\hat{y}_{i}\right|$

where $y$ indicates to the actual value, while $\hat{y}$ is the predicted
value.

###  5.4 Weighted ensemble model

Inspired by the advantages of blending forecasts using conditional methods, we
examine a meta-heuristic strategy for blinding the forecasts obtained from
individual models. The weighted ensemble method in forecasting involves a
mathematical approach to combine the predictions of multiple individual models
to improve overall accuracy and robustness. Each model in the ensemble
contributes to the final forecast with a certain weight. The final ensemble
forecast is then obtained by summing the products of each model’s forecast
with its corresponding optimal weight. Mathematically, this can be represented
as the weighted sum:

Weighted ensemble prediction $\displaystyle=\sum_{i=1}^{n}M_{i}W_{i}$ (8)

Here, $W_{i}$ represents an optimal weight assigned to $model_{i}$, where
$0\leq W_{i}\leq 1$, and $\sum W_{i}=1$. While $M_{i}$ represents $model_{i}$
forecasts.

In this experiment, a dynamic weighted ensemble method was employed to blend
the predictions of the top five forecasts obtained from the SENT-Bi-GRU, SENT-
Bi-LSTM, SENT-CNN-Bi-LSTM, SENT-CNN-Bi-LSTM-att, and SENT-USD-encoder-decoder-
LSTM. The weights metric $W$ was optimised using the Grey Wolf Optimization
(GWO) metaheuristic algorithm. The experiments showed that this metaheuristic-
calibration-based weighted ensemble method achieves better results than
traditional method or other naive ensemble methods and that the ensemble model
outperforms the individual models, achieving a mean square error of
(0.000165), with a success ratio of reducing the MSE 0.024%, compared to the
best-performing individual model as shown in Table 4.

##  6 Results and discussion

In this section, we first present the optimal configuration obtained for each
model identified by the GWO algorithm. Then, we discuss the accuracy of the
forecast achieved by blending the best forecasts and evaluate the performance
of the ensemble model by comparing the MAE, MSE and RMSE values to the
individual model’s selected benchmark models.

###  6.1 Models optimal configurations

Table 2 shows the best solution found by GWO for each selected model. The
first column (MSE) shows the best MSE achieved by each model, while the other
columns show the corresponding optimal configuration values. The results
obtained from the GWO-optimised five benchmark models, in Table 2, showed that
the best-performing model is based on the Bi-GRU architecture when
incorporating the sentimental score (SENT-Bi-GRU), with the best MSE of
0.000137. The corresponding optimal configuration identified in this model is
AdamW as the optimiser with a sliding window of 5 lagged steps, 0.003154571 as
the learning rate, 0.0399269013 as the dropout value, and 2 hidden units.
Integrating the sentimental score index (SENT) generally gives better results
than integrating the USDX index. While combining both factors improved the
results only with the encoder-decoder-LSTM architecture. The optimal values
for sliding windows are (5, 6, 10, 17). These figures align consistently with
typical workdays, as 5 corresponds to the number of working days a week.

Table 2: Best solutions found by GWO (models optimal configuration). TS = time
steps, and h is the number of hidden units

Model | MSE |  TS | LR | Dropout | h | Optimiser
---|---|---|---|---|---|---
SENT-Bi-GRU | 0.000137 |  5 | 0.0031 | 0.3992 | 2 | AdamW
SENT-Bi-LSTM | 0.000194 |  17 | 0.0032 | 0.3205 | 12 | Adam
SENT-CNN-Bi-LSTM | 0.000280 |  5 | 0.01 | 0.3439 | 8 | Adagrad
SENT-CNN-Bi-LSTM-Att | 0.000300 |  6 | 0.0045 | 0.4399 | 8 | Adam
SENT-USD-CNN-Bi-LSTM-Att | 0.000349 |  10 | 0.0043 | 0.3140 | 4 | RMSprop
SENT-encoder-decoder-Bi-LSTM | 0.000358 |  10 | 0.0060 | 0.2573 | 64 | Adam
SENT-USD-encoder-decoder-LSTM | 0.000344 |  17 | 0.0080 | 0.2747 | 64 | AdamW

Conversely, Figure 6 illustrates global objective and run-time charts. The
global objective chart shows the movement curve towards the optimal solution
to minimise the MSE for a single model. Like manual hyperparameter tuning, the
GWO algorithm takes longer to find a near-optimal solution with the encoder-
decoder-LSTM and CNN-LSTM-att models. At the same time, finding a near-optimal
solution with LSTM and GRU is faster. Experimentally, GWO reaches a near-
optimal solution during the first 30 epochs.

###  6.2 GWO-ensemble model accuracy evaluation

Table 3: GWO-ensemble model optimal weights

Model |  Optimal weight
---|---
SENT-Bi-GRU |  0.0860
SENT-Bi-LSTM |  0.6266
SENT-Bi-CNN-LSTM-att |  0.0889
SENT-encoder-decoder-LSTM |  0.1057
SENT-USDX-encoder-decoder-LSTM |  0.0927

As shown in the table, the GWO-ensemble model outperformed the other models,
achieving a 0.000127 of MSE. The best final forecast has been acquired by
blending the forecasts obtained from SENT-Bi-GRU, SENT-Bi-LSTM, SENT-Bi-CNN-
LSTM-attention, SENT-encoder-decoder-LSTM and SENT-USDX-encoder-decoder-LSTM
models. The optimal weights assigned for each model are illustrated in Table
(3).

Table 4: Forecasting accuracy evaluation

Model | MAE | MSE | RMSE
---|---|---|---
GWO-Ensemble | 0.007414 | 0.000127 | 0.011269
SENT-BI-GRU | 0.008300 | 0.000137 | 0.011704
SENT-BI-LSTM | 0.009800 | 0.000194 | 0.013928
SENT-CNN-BI-LSTM | 0.012650 | 0.000280 | 0.016733
SENT-CNN-BI-LSTM-att | 0.013550 | 0.000300 | 0.017306
SENT-USD-CNN-BI-LSTM-att | 0.014400 | 0.000349 | 0.018682
SENT-Encoder-Decoder-BI-LSTM | 0.012550 | 0.000359 | 0.018934
SENT-USD-Encoder-Decoder-BI-LSTM | 0.012900 | 0.000344 | 0.018547

Figure 5 illustrates the forecasting performances for all targeted models. The
figure shows the plot chart of Actual vs. predicted results. Table (4) shows
the overall comparison of the GWO-ensemble model with the other benchmark
models.

Figure 5:  Actual vs. predicted results of the examined models: (a). Ensemble
model, (b). SENT-Bi-GRU, (c). SENT-Bi-LSTM, (d). SENT-CNN-Bi-LSTM, (e). SENT-
CNN-Bi-LSTM-att, (f). SENT-USD-Encoder-decoder-Bi-LSTM

Figure 6:  Objective function and run time charts of a single GWO run for the
following models: (a,b):LSTM, (c,d): GRU, (e,f): CNN-LSTM-att, (g,h): encoder-
decoder

##  7 Limitations

Although metaheuristic optimisation algorithms effectively tune deep learning
models, they require significant computational resources. This limitation has
forced us to restrict our hyperparameter search to a limited number of
parameters. However, expanding the problem dimension to include a broader
range of parameters could improve forecasting performance. Suppose we need to
run GWO 20 independent runs for the Bi-LSTM model with 30 epochs and a
population size of 10. Each Bi-LSTM model will be trained 6,000 times (20 runs
* 30 epochs * 10 population size).

##  8 Conclusions

In this study, we have introduced a hybrid approach that combines deep
learning networks with metaheuristic optimisation to enhance the forecasting
of Brent crude oil prices. The main idea is to harness the capabilities of
metaheuristic optimisation to identify optimal configurations at various
stages of constructing a forecasting solution, alongside the power of
combining forecasts with multiple deep learning models. The well-known Grey
Wolf Optimizer (GWO) algorithm was employed to optimise feature selection,
dataset preparation, tuning hyperparameters for five individual deep learning
networks, and the fusion of their forecasts. The results demonstrated that
this approach improved the accuracy for each model and that the presented
ensemble model outperforms benchmark models and achieves an MSE of 0.000127.

## References

  * [1] L. Jovanovic, D. Jovanovic, N. Bacanin, A. Jovancai Stakic, M. Antonijevic, H. Magd, R. Thirumalaisamy, M. Zivkovic, Multi-step crude oil price prediction based on lstm approach tuned by salp swarm algorithm with disputation operator, Sustainability 14 (21) (2022).  doi:10.3390/su142114616.
URL https://www.mdpi.com/2071-1050/14/21/14616

  * [2] Z. Cen, J. Wang, Crude oil price prediction model with long short term memory deep learning based on prior knowledge data transfer, Energy 169 (12 2018).  doi:10.1016/j.energy.2018.12.016.
  * [3] J. Li, Z. Xu, H. Xu, L. Tang, L. Yu, Forecasting oil price trends with sentiment of online news articles, Asia-Pacific Journal of Operational Research 34 (02) (2017) 1740019.  doi:10.1142/S021759591740019X.
URL https://doi.org/10.1142/S021759591740019X

  * [4] L.-T. Zhao, Y.-Y. Xing, Q.-R. Zhao, X.-H. Chen, Dynamic impacts of online investor sentiment on international crude oil prices, Resources Policy 82 (2023) 103506.  doi:https://doi.org/10.1016/j.resourpol.2023.103506.
URL https://www.sciencedirect.com/science/article/pii/S0301420723002143

  * [5] H. Miao, S. Ramchander, T. Wang, D. Yang, Influential factors in crude oil price forecasting, Energy Economics 68 (2017) 77–88.  doi:https://doi.org/10.1016/j.eneco.2017.09.010.
URL https://www.sciencedirect.com/science/article/pii/S0140988317303134

  * [6] Y. Fang, W. Wang, P. Wu, Y. Zhao, A sentiment-enhanced hybrid model for crude oil price forecasting, Expert Systems with Applications 215 (2023) 119329.  doi:https://doi.org/10.1016/j.eswa.2022.119329.
URL https://www.sciencedirect.com/science/article/pii/S0957417422023478

  * [7] M. Kaveh, M. S. Mesgari, Application of meta-heuristic algorithms for training neural networks and deep learning architectures: A comprehensive review, Neural Processing Letters 55 (4) (2023) 4519–4622.  doi:10.1007/s11063-022-11055-6.
URL https://doi.org/10.1007/s11063-022-11055-6

  * [8] C. Stoean, M. Zivkovic, A. Bozovic, N. Bacanin, R. Strulak-Wójcikiewicz, M. Antonijevic, R. Stoean, Metaheuristic-based hyperparameter tuning for recurrent deep learning: Application to the prediction of solar energy generation, Axioms 12 (3) (2023).  doi:10.3390/axioms12030266.
URL https://www.mdpi.com/2075-1680/12/3/266

  * [9] T. Zhang, Z. Tang, J. Wu, X. Du, K. Chen, Multi-step-ahead crude oil price forecasting based on two-layer decomposition technique and extreme learning machine optimized by the particle swarm optimization algorithm, Energy 229 (2021) 120797.  doi:https://doi.org/10.1016/j.energy.2021.120797.
URL https://www.sciencedirect.com/science/article/pii/S0360544221010458

  * [10] H. Mohammadi, L. Su, International evidence on crude oil price dynamics: Applications of arima-garch models, Energy Economics 32 (5) (2010) 1001–1008.  doi:https://doi.org/10.1016/j.eneco.2010.04.009.
URL https://www.sciencedirect.com/science/article/pii/S0140988310000654

  * [11] Y. Xiang, X. H. Zhuang, Application of arima model in short-term prediction of international crude oil price, in: Advances in Applied Science and IndFotios Petropoulostrial Technology, Vol. 798 of Advanced Materials Research, Trans Tech Publications Ltd, 2013, pp. 979–982.  doi:10.4028/www.scientific.net/AMR.798-799.979.
  * [12] H.-L. Zhang, C.-X. Liu, M.-Z. Zhao, Y. Sun, Economics, fundamentals, technology, finance, speculation and geopolitics of crude oil prices: an econometric analysis and forecast based on data from 1990 to 2017, Petroleum Science 15 (2) (2018) 432–450.  doi:10.1007/s12182-018-0228-z.
URL https://doi.org/10.1007/s12182-018-0228-z

  * [13] K. Drachal, Forecasting crude oil real prices with averaging time-varying var models, Resources Policy 74 (2021) 102244.  doi:https://doi.org/10.1016/j.resourpol.2021.102244.
URL https://www.sciencedirect.com/science/article/pii/S0301420721002555

  * [14] P. Lara-Benítez, M. Carranza-García, J. C. Riquelme, An experimental review on deep learning architectures for time series forecasting, International Journal of Neural Systems 31 (03) (2021) 2130001.  doi:10.1142/s0129065721300011.
URL http://dx.doi.org/10.1142/S0129065721300011

  * [15] A. Sen, K. Dutta Choudhury, Forecasting the crude oil prices for last four decades using deep learning approach, Resources Policy 88 (2024) 104438.  doi:https://doi.org/10.1016/j.resourpol.2023.104438.
URL https://www.sciencedirect.com/science/article/pii/S0301420723011492

  * [16] Hu, Zhenda, Crude oil price prediction using ceemdan and lstm-attention with news sentiment index, Oil Gas Sci. Technol. - Rev. IFP Energies nouvelles 76 (2021) 28.  doi:10.2516/ogst/2021010.
URL https://doi.org/10.2516/ogst/2021010

  * [17] L. Guo, X. Huang, Y. Li, H. Li, Forecasting crude oil futures price using machine learning methods: Evidence from china, Energy Economics 127 (2023) 107089.  doi:https://doi.org/10.1016/j.eneco.2023.107089.
URL https://www.sciencedirect.com/science/article/pii/S014098832300587X

  * [18] S. Zhang, J. Luo, S. Wang, F. Liu, Oil price forecasting: A hybrid gru neural network based on decomposition–reconstruction methods, Expert Systems with Applications 218 (2023) 119617.  doi:https://doi.org/10.1016/j.eswa.2023.119617.
URL https://www.sciencedirect.com/science/article/pii/S0957417423001185

  * [19] H. Lin, Q. Sun, Crude oil prices forecasting: An approach of using ceemdan-based multi-layer gated recurrent unit networks, Energies 13 (7) (2020).
URL https://www.mdpi.com/1996-1073/13/7/1543

  * [20] Y. Lin, K. Chen, X. Zhang, B. Tan, Q. Lu, Forecasting crude oil futures prices using bilstm-attention-cnn model with wavelet transform, Applied Soft Computing 130 (2022) 109723.  doi:https://doi.org/10.1016/j.asoc.2022.109723.
URL https://www.sciencedirect.com/science/article/pii/S1568494622007724

  * [21] H. Wu, T. Hu, Y. Liu, H. Zhou, J. Wang, M. Long, Timesnet: Temporal 2d-variation modeling for general time series analysis, in: International Conference on Learning Representations, 2023.
  * [22] C. Liu, K. Ruan, X. Ma, Dmeformer: A newly designed dynamic model ensemble transformer for crude oil futures prediction, Heliyon 9 (6) (2023) e16715.  doi:https://doi.org/10.1016/j.heliyon.2023.e16715.
URL https://www.sciencedirect.com/science/article/pii/S2405844023039221

  * [23] H. Wu, D. Levinson, The ensemble approach to forecasting: A review and synthesis, Transportation Research Part C: Emerging Technologies 132 (2021) 103357.  doi:https://doi.org/10.1016/j.trc.2021.103357.
URL https://www.sciencedirect.com/science/article/pii/S0968090X21003594

  * [24] X. Wei, X. Sun, J. Sun, J. Yin, J. Sun, C. Liu, A comparative study of multi-model ensemble forecasting accuracy between equal- and variant-weight techniques, Atmosphere 13 (4) (2022).  doi:10.3390/atmos13040526.
URL https://www.mdpi.com/2073-4433/13/4/526

  * [25] Q. Qin, Z. Huang, Z. Zhou, C. Chen, R. Liu, Crude oil price forecasting with machine learning and google search data: An accuracy comparison of single-model versus multiple-model, Engineering Applications of Artificial Intelligence 123 (2023) 106266.  doi:https://doi.org/10.1016/j.engappai.2023.106266.
URL https://www.sciencedirect.com/science/article/pii/S0952197623004505

  * [26] Y. Yang, J. Guo, S. Sun, Y. Li, Forecasting crude oil price with a new hybrid approach and multi-source data, Engineering Applications of Artificial Intelligence 101 (2021) 104217.  doi:https://doi.org/10.1016/j.engappai.2021.104217.
URL https://www.sciencedirect.com/science/article/pii/S0952197621000646

  * [27] J. Beckmann, R. L. Czudaj, V. Arora, The relationship between oil prices and exchange rates: Revisiting theory and evidence, Energy Economics 88 (2020) 104772.  doi:https://doi.org/10.1016/j.eneco.2020.104772.
URL https://www.sciencedirect.com/science/article/pii/S0140988320301122

  * [28] J. Shang, S. Hamori, Do crude oil prices and the sentiment index influence foreign exchange rates differently in oil-importing and oil-exporting countries? a dynamic connectedness analysis, Resources Policy 74 (2021) 102400.  doi:https://doi.org/10.1016/j.resourpol.2021.102400.
URL https://www.sciencedirect.com/science/article/pii/S0301420721004098

  * [29] H. Miao, S. Ramchander, T. Wang, D. Yang, Influential factors in crude oil price forecasting, Energy Economics 68 (2017) 77–88.  doi:https://doi.org/10.1016/j.eneco.2017.09.010.
URL https://www.sciencedirect.com/science/article/pii/S0140988317303134

  * [30] M. Abdel-Basset, L. Abdel-Fatah, A. K. Sangaiah, Chapter 10 - metaheuristic algorithms: A comprehensive review, in: A. K. Sangaiah, M. Sheng, Z. Zhang (Eds.), Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications, Intelligent Data-Centric Systems, Academic Press, 2018, pp. 185–231.  doi:https://doi.org/10.1016/B978-0-12-813314-9.00010-4.
URL https://www.sciencedirect.com/science/article/pii/B9780128133149000104

  * [31] D. Oliva, E. Houssein, S. Hinojosa, Metaheuristics in Machine Learning: Theory and Applications, Studies in Computational Intelligence, Springer International Publishing, 2021.
URL https://books.google.it/books?id=Zlw4EAAAQBAJ

  * [32] L. Calvet, J. de Armas, D. Masip, A. A. Juan, Learnheuristics: hybridizing metaheuristics with machine learning for optimization with dynamic inputs, Open Mathematics 15 (1) (2017) 261–280 [cited 2023-12-24].  doi:doi:10.1515/math-2017-0029.
URL https://doi.org/10.1515/math-2017-0029

  * [33] N. Van Thieu, S. D. Barma, T. Van Lam, O. Kisi, A. Mahesha, Groundwater level modeling using augmented artificial ecosystem optimization, Journal of Hydrology 617 (2023) 129034.  doi:10.1016/j.jhydrol.2022.129034.
  * [34] N. Van Thieu, S. Mirjalili, Mealpy: An open-source library for latest meta-heuristic algorithms in python, Journal of Systems Architecture (2023).  doi:10.1016/j.sysarc.2023.102871.
  * [35] S. Mirjalili, S. M. Mirjalili, A. Lewis, Grey wolf optimizer, Advances in Engineering Software 69 (2014) 46–61.  doi:https://doi.org/10.1016/j.advengsoft.2013.12.007.
URL https://www.sciencedirect.com/science/article/pii/S0965997813001853

  * [36] E. Elhariri, N. El-Bendary, A. E. Hassanien, Bio-inspired optimization for feature set dimensionality reduction, in: 2016 3rd International Conference on Advances in Computational Tools for Engineering Applications (ACTEA), 2016, pp. 184–189.  doi:10.1109/ACTEA.2016.7560136.
  * [37] C. Muro, R. Escobedo, L. Spector, R. Coppinger, Wolf-pack (canis lupus) hunting strategies emerge from simple rules in computational simulations, Behavioural Processes 88 (3) (2011) 192–197.  doi:https://doi.org/10.1016/j.beproc.2011.09.006.
URL https://www.sciencedirect.com/science/article/pii/S0376635711001884

  * [38] J.-M. Kim, H. H. Han, S. Kim, Forecasting crude oil prices with major s&p 500 stock prices: Deep learning, gaussian process, and vine copula, Axioms 11 (8) (2022).  doi:10.3390/axioms11080375.
URL https://www.mdpi.com/2075-1680/11/8/375

  * [39] H. Kaplan, A. Weichselbraun, A. M. P. Braşoveanu, Integrating economic theory, domain knowledge, and social knowledge into hybrid sentiment models for predicting crude oil markets, Cognitive Computation (2023).  doi:10.1007/s12559-023-10129-4.
URL https://doi.org/10.1007/s12559-023-10129-4


C^{\otimes d}$ has weight $B_{1}={t\choose\leq d}=\exp(O(d\log(d)))$. This
lets us write $c_{i}^{\otimes d}=B_{1}\mathbf{v}_{i}$ where
$\mathbf{v}_{i}\in\Delta_{k}$. Thus an instance $I$ which gives a distribution
on $(c_{i},b_{i})$ where $c_{i}\in C$ $b_{i}\in\\{\pm 1\\}$ also gives a
distribution over $(\mathbf{v}_{i},b_{i})\in\Delta_{k}\times\\{\pm 1\\}$.

There exists a degree $d$ polynomial

$p(t)=\sum_{j=0}^{d}\alpha_{j}t^{j}$

such that $|\alpha_{j}|=\exp(O(d\log(d)))$ and $p(c_{i}\cdot
z)=\mathrm{Xor}_{c_{i}}(z)\ \text{for}\ |c_{i}\cdot z|\leq d/2$. If
$|c_{i}\cdot z|\geq d/2$ then $p(c_{i}\cdot z)\in\mathbb{R}$. Since
$c_{i}\in\\{0,1\\}^{n}$, we can multilinearize the terms of the form
$(c_{i}\cdot z)^{j}$ as

$(c_{i}\cdot z)^{j}=\sum_{T\subseteq[n],|T|\leq j}w^{j}_{T}\prod_{i\in
T}c_{i}$

for coefficients $w^{j}_{T}=\exp(O(j\log j))$. So we can write

$\displaystyle p(c_{i}\cdot z)$
$\displaystyle=\sum_{j=0}^{2d}\alpha_{j}(c_{i}\cdot z)^{j}$
$\displaystyle=\sum_{j=0}^{2d}\alpha_{j}\sum_{T\subseteq[n],|T|\leq
j}w^{j}_{T}\prod_{i\in T}c_{i}$ $\displaystyle=\sum_{T\subseteq[n],|T|\leq
2d}\left(\sum_{j\geq|T|}\alpha_{j}w^{j}_{T}\right)\prod_{i\in T}c_{i}$
$\displaystyle=\sum_{T\subseteq[n],|T|\leq 2d}w_{T}^{\prime}\prod_{i\in
T}c_{i}$ $\displaystyle=w^{\prime}\cdot c^{\otimes d}$

for coefficients $w^{\prime}_{T}$ bounded in absolute value by
$|w^{\prime}_{T}|=\exp(O(d\log d))$.

We renormalize $w^{\prime}$ to be bounded in $[-1,1]^{k}$. We write
$w^{\prime}=wB_{1}$ for $B_{1}=\max_{T}|w^{\prime}_{T}|=\exp(O(d\log d)$. We
have

$P(c_{i}\cdot z)=w^{\prime}\cdot c_{i}^{\otimes d}=B_{1}{t\choose
d}w\cdot\mathbf{v}_{i}.$

Hence if $|c_{i}\cdot z|\leq d/2$, then the quantity above equals
$\mathrm{Xor}_{c_{i}}(z)\in\\{\pm 1\\}$, else it takes on values in
$\mathbb{R}$.

By our choice of $d=\Theta(\sqrt{t\log t})$, we have

$\log\left(B_{1}{t\choose d}\right)=\log B_{1}+O(\log(d\log t))=O(d\log d)\leq
t^{1/2+o(1)}.$

By our choice of $L:=\exp(\log^{c}k)$, we have

$\displaystyle\log L$ $\displaystyle=(\log k)^{c}$ $\displaystyle=(d\log
n)^{c+o(1)}$ (by (11)) $\displaystyle=d^{c+o(1)}(\log n)^{c+o(1)}$
$\displaystyle=t^{c/2+o(1)}(\log n)^{s(1-c+\varepsilon)/2+o(1)}$ (by
$d=\Theta(\sqrt{t\log t})$ and $s=2c/(1-c+\varepsilon)$)
$\displaystyle=t^{c/2+o(1)}t^{(1-c+\varepsilon)/2+o(1)}$ (by
$t=\lfloor\log^{s}n\rfloor$) $\displaystyle=t^{1/2+\varepsilon/2+o(1)}.$ (12)

Therefore, for sufficiently large $n$,

$L\geq aB_{1}{t\choose d},$

for some constant $a$ so that $\tanh(a)\geq 1-\alpha$, where we use our choice
of constant $\alpha:=1/4-\eta/2>0$.

Consider the function
$g(\mathbf{v})=\tanh(L^{\prime}w\cdot\mathbf{v})\in\Sigma_{L}$. We can find
$a^{\prime}\geq a$ such that $L=a^{\prime}B_{1}{t\choose d}$. We have for each
$i\in[m]$,

$\displaystyle g(\mathbf{v}_{i})$ $\displaystyle=\tanh(Lw\cdot\mathbf{v}_{i})$
$\displaystyle=\tanh\left(a^{\prime}B_{1}w\cdot{t\choose\leq
d}\mathbf{v}_{i}\right)$ $\displaystyle=\tanh(a^{\prime}w^{\prime}\cdot
c_{i}^{\otimes d})$ $\displaystyle=\tanh(a^{\prime}p(c_{i}\cdot z)).$

Therefore, $g(\mathbf{v}_{i})\geq 1-\alpha$ if $p(c_{i}\cdot z)=1$, and
$g(\mathbf{v}_{i})\leq-1+\alpha$ if $p(c_{i}\cdot z)=-1$. Moreover, it is
clear that $g(\mathbf{v}_{i})\in[-1,1]$ always holds.

Recall our definition $\alpha:=1/4-\eta/2>0$. If $\mathrm{val}(I)\geq 1-\eta$,
then by taking the function $g$ derived from $z$ such that
$\mathrm{val}(z,I)\geq 1-\eta=1/2+2\alpha$, excluding the at most $\alpha m$
clauses that fail to satisfy $|c_{i}\cdot z|\leq d/2$, we get $g\in\Sigma_{L}$
such that

$\frac{1}{m}\sum_{i=1}^{m}g(\mathbf{v}_{i})b_{i}\geq(1/2+\alpha)\times(1-\alpha)+(1/2-\alpha)\times(-1)\geq\alpha.$

Thus based on the methodology of [DLSS14] (see e.g. Theorem 2.1 in [Dan16]),
we can apply our weak agnostic learning algorithm $A$ to efficiently
distinguish the case with $\mathrm{val}(I)\geq 1-\eta$ and the case with
uniformly random clauses with success probability at least $3/4$, solving the
$t$-XorSat refutation problem.

As long as the running time of algorithm $A$ is bounded by
$k^{\log(L)^{1-\varepsilon}}$ for some $\varepsilon>0$, the running time for
$t$-$\mathrm{XorSat}$ refutation is bounded by

$k^{O(\log(L)^{1-\varepsilon})}\leq n^{O(d\log(L)^{1-\varepsilon})}.$

By (12), we have

$d\log(L)^{1-\varepsilon}=t^{1/2+o(1)}t^{(1-\varepsilon)(1/2+\varepsilon/2+o(1))}=t^{1-\varepsilon^{2}/2+o(1)}.$

Thus the running time for $t$-$\mathrm{XorSat}$ refutation is bounded by
$n^{o(t)}$, as desired. ∎

## References

  * [AB21] Anastasios N Angelopoulos and Stephen Bates.  A gentle introduction to conformal prediction and distribution-free uncertainty quantification.  arXiv preprint arXiv:2107.07511, 2021.
  * [BGHN23] Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran.  A unifying theory of distance from calibration.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, page 1727–1740, 2023.
  * [BGJ+22] Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth.  Practical adversarial multivalid conformal prediction.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 29362–29373. Curran Associates, Inc., 2022.
  * [BLM01] Shai Ben-David, Philip M. Long, and Yishay Mansour.  Agnostic boosting.  In 14th Annual Conference on Computational Learning Theory, COLT, 2001.
  * [Che66] E. Cheney.  Introduction to approximation theory.  McGraw-Hill, New York, 1966.
  * [Dan16] Amit Daniely.  Complexity theoretic limitations on learning halfspaces.  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, page 105–117, New York, NY, USA, 2016. Association for Computing Machinery.
  * [Daw82] A. P. Dawid.  Objective probability forecasts.  University College London, Dept. of Statistical Science. Research Report 14, 1982.
  * [Daw84] A Philip Dawid.  Present position and potential developments: Some personal views statistical theory the prequential approach.  Journal of the Royal Statistical Society: Series A (General), 147(2):278–290, 1984.
  * [DDS+09] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009.
  * [DKR+21] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona.  Outcome indistinguishability.  In ACM Symposium on Theory of Computing (STOC’21), 2021.
  * [DKR+22] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona.  Beyond bernoulli: Generating random outcomes that cannot be distinguished from nature.  In The 33rd International Conference on Algorithmic Learning Theory, 2022.
  * [DLLT23] Cynthia Dwork, Daniel Lee, Huijia Lin, and Pranay Tankala.  From pseudorandomness to multi-group fairness and back.  In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 3566–3614. PMLR, 12–15 Jul 2023.
  * [DLSS14] Amit Daniely, Nati Linial, and Shai Shalev-Shwartz.  From average case complexity to improper learning complexity.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 441–448, New York, NY, USA, 2014. Association for Computing Machinery.
  * [Fei02] Uriel Feige.  Relations between average case complexity and approximation complexity.  In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 534–543. ACM, 2002.
  * [Fel10] Vitaly Feldman.  Distribution-specific agnostic boosting.  In Andrew Chi-Chih Yao, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 241–250. Tsinghua University Press, 2010.
  * [FGKP09] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami.  On agnostic learning of parities, monomials, and halfspaces.  SIAM J. Comput., 39(2):606–645, 2009.
  * [FH18] Dean P. Foster and Sergiu Hart.  Smooth calibration, leaky forecasts, finite recall, and nash dynamics.  Games Econ. Behav., 109:271–293, 2018.
  * [GHK+23] Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder.  Loss Minimization Through the Lens Of Outcome Indistinguishability.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 60:1–60:20, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [GJN+22] Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth.  Online Multivalid Learning: Means, Moments, and Prediction Intervals.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1–82:24, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [GKK20] Surbhi Goel, Adam R. Klivans, and Frederic Koehler.  From boltzmann machines to neural networks and back again.  In Annual Conference on Neural Information Processing Systems 2020, 2020.
  * [GKKT17] Surbhi Goel, Varun Kanade, Adam R. Klivans, and Justin Thaler.  Reliably learning the relu in polynomial time.  In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 1004–1042. PMLR, 2017.
  * [GKR+22] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder.  Omnipredictors.  In Innovations in Theoretical Computer Science (ITCS’2022), 2022\.
  * [GKSZ22] Parikshit Gopalan, Michael P. Kim, Mihir Singhal, and Shengjia Zhao.  Low-degree multicalibration.  In Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 3193–3234. PMLR, 2022.
  * [GPSW17] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In International Conference on Machine Learning, pages 1321–1330. PMLR, 2017.
  * [GR06] Venkatesan Guruswami and Prasad Raghavendra.  Hardness of learning halfspaces with noise.  In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 543–552. IEEE Computer Society, 2006.
  * [GR22] Chirag Gupta and Aaditya Ramdas.  Top-label calibration and multiclass-to-binary reductions.  In International Conference on Learning Representations, 2022.
  * [HKRR18] Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum.  Multicalibration: Calibration for the (computationally-identifiable) masses.  In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018.
  * [JNRR23] Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth.  Batch multivalid conformal prediction.  In International Conference on Learning Representations, 2023.
  * [KF08] Sham Kakade and Dean Foster.  Deterministic calibration and nash equilibrium.  Journal of Computer and System Sciences, 74(1):115–130, 2008.
  * [KF15] Meelis Kull and Peter Flach.  Novel decompositions of proper scoring rules for classification: Score adjustment as precursor to calibration.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 68–85. Springer, 2015.
  * [KK09] Adam Kalai and Varun Kanade.  Potential-based agnostic boosting.  In Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
  * [KKMS08] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio.  Agnostically learning halfspaces.  SIAM J. Comput., 37(6):1777–1805, 2008.
  * [KLST23] Bobby Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng.  U-calibration: Forecasting for an unknown agent.  In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5143–5145. PMLR, 12–15 Jul 2023.
  * [KMV08] Adam Tauman Kalai, Yishay Mansour, and Elad Verbin.  On agnostic boosting and parity learning.  In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 629–638. ACM, 2008.
  * [KPNK+19] Meelis Kull, Miquel Perello-Nieto, Markus Kängsepp, Hao Song, Peter Flach, et al.  Beyond temperature scaling: Obtaining well-calibrated multiclass probabilities with dirichlet calibration.  arXiv preprint arXiv:1910.12656, 2019.
  * [KSJ18] Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain.  Trainable calibration measures for neural networks from kernel mean embeddings.  In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2805–2814. PMLR, 2018.
  * [LSS14] Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir.  On the computational efficiency of training neural networks.  In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 855–863, 2014.
  * [MR95] Rajeev Motwani and Prabhakar Raghavan.  Randomized algorithms.  Cambridge university press, 1995.
  * [NRRX23] Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie.  High-dimensional prediction for sequential decision making.  arXiv preprint arXiv:2310.17651, 2023.
  * [She13] Alexander A. Sherstov.  Making polynomials robust to noise.  Theory of Computing, 9(18):593–615, 2013.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014.
  * [SSS11] Shai Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan.  Learning kernel-based halfspaces with the 0-1 loss.  SIAM J. Comput., 40(6):1623–1646, 2011.
  * [SV08] Glenn Shafer and Vladimir Vovk.  A tutorial on conformal prediction.  Journal of Machine Learning Research, 9(12):371–421, 2008.
  * [Wai09] Martin Wainwright.  Lecture 6 in EECS 281B / STAT 241B: Advanced topics in statistical learning.  https://people.eecs.berkeley.edu/~wainwrig/stat241b/lec6.pdf, 2009\.
  * [ZKS+21] Shengjia Zhao, Michael P. Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon.  Calibrating predictions to decisions: A novel approach to multi-class calibration.  In Advances in Neural Information Processing Systems, 2021.

##  Appendix A Proofs from Section 6

###  A.1 Proof of Theorem 6.1

We break the proof in a sequence of lemmas, starting with simplifying the
objective function.

######  Lemma A.1.

Let $w_{0}=\operatorname*{\mathbf{E}}_{\mathcal{D}}[z\varphi_{\mathbf{v}}]$.
Then $w_{0}\in B_{\Gamma}(s)$ and for any $w\in\Gamma$ we have

$\displaystyle\operatorname*{\mathbf{E}}_{(\mathbf{v},z)\sim\mathcal{D}}[w(\mathbf{v})z]=\langle
w,w_{0}\rangle_{\Gamma}.$ (13)

###### Proof.

For any $w\in\Gamma$ we can write the correlation objective as

$\displaystyle\operatorname*{\mathbf{E}}_{(\mathbf{v},z)\sim\mathcal{D}}[w(\mathbf{v})z]=\operatorname*{\mathbf{E}}[\langle
w,\varphi_{\mathbf{v}}\rangle_{\Gamma}z]=\langle
w,\operatorname*{\mathbf{E}}[z\varphi_{\mathbf{v}}]\rangle_{\Gamma}=\langle
w,w_{0}\rangle_{\Gamma}.$

To bound its norm, observe that

$\displaystyle\|w_{0}\|_{\Gamma}=\|\operatorname*{\mathbf{E}}_{\mathcal{D}}[z\varphi_{\mathbf{v}}]\|_{\Gamma}\leq\max_{\mathbf{v}\in\Delta_{k},z\in\\{\pm
1\\}}\|z\varphi_{\mathbf{v}}\|_{\Gamma}\leq s.$

∎

Next we show that we can approximate $w_{0}$ uniformly from samples by the
function

$\tilde{w}_{0}=\frac{1}{n}\sum_{i=1}^{n}z_{i}\varphi_{\mathbf{v}_{i}}.$

######  Lemma A.2.

For any $\delta\in(0,1/2)$, for some
$n_{0}=O(r^{2}s^{2}\alpha^{-2}\log(1/\delta))$, for any $n\geq n_{0}$ and any
$(\mathbf{v}_{1},z_{1}),\ldots,\allowbreak(\mathbf{v}_{n},z_{n})$ drawn i.i.d.
from $\mathcal{D}$, with probability at least $1-\delta$,

$\displaystyle\left\lVert\tilde{w}_{0}-w_{0}\right\rVert_{\Gamma}\leq\frac{\alpha}{3r}.$
(14)

The proof uses McDiarmid’s inequality (see e.g. Lemma 26.4 of [SSBD14]).

###### Proof.

We can write

$\displaystyle\|\tilde{w}_{0}-w_{0}\|_{\Gamma}=\left\lVert\sum_{i=1}^{n}\frac{z_{i}\varphi_{\mathbf{v}_{i}}}{n}-w_{0}\right\rVert_{\Gamma}=\frac{1}{n}\left\lVert\sum_{i=1}^{n}(z_{i}\varphi_{\mathbf{v}_{i}}-w_{0})\right\rVert_{\Gamma}$

Since each term $z_{i}\varphi_{\mathbf{v}_{i}}-w_{0}$ has expectation $0$, and
the terms are independent, for $i\neq j$

$\operatorname*{\mathbf{E}}[\langle
z_{i}\varphi_{\mathbf{v}_{i}}-w_{0},z_{j}\varphi_{\mathbf{v}_{j}}-w_{0}\rangle_{\Gamma}]=0$

Hence we can bound

$\displaystyle\operatorname*{\mathbf{E}}[\|\tilde{w}_{0}-w_{0}\|_{\Gamma}^{2}]$
$\displaystyle=\frac{1}{n^{2}}\operatorname*{\mathbf{E}}\left[\sum_{i=1}^{n}{\|z_{i}\varphi_{\mathbf{v}_{i}}-w_{0}\|_{\Gamma}^{2}}+\sum_{i\neq
j}\langle
z_{i}\varphi_{\mathbf{v}_{i}}-w_{0},\mathbf{z}_{j}\varphi_{\mathbf{v}_{j}}-w_{0}\rangle\right]$
$\displaystyle=\frac{1}{n}\operatorname*{\mathbf{E}}[\|z_{1}\varphi_{\mathbf{v}_{1}}-w_{0}\|_{\Gamma}^{2}]$
$\displaystyle\leq 4s^{2}/n\leq(\alpha/(6r))^{2}.$

by our choice of $n$. By convexity,

$\displaystyle\operatorname*{\mathbf{E}}[\|\tilde{w}_{0}-w_{0}\|_{\Gamma}]\leq\frac{\alpha}{6r}.$
(15)

Note that each i.i.d. term $z_{i}\varphi_{\mathbf{v}_{i}}$ in the definition
of $\tilde{w}_{0}$ has norm $\|z_{i}\varphi_{\mathbf{v}_{i}}\|_{\Gamma}\leq
s$, so by McDiarmid’s inequality, with probability at least $1-\delta$,

$\big{|}\left\lVert\tilde{w}_{0}-w_{0}\right\rVert_{\Gamma}-\operatorname*{\mathbf{E}}[\left\lVert\tilde{w}_{0}-w_{0}\right\rVert_{\Gamma}]\big{|}\leq\alpha/(6r).$
(16)

Combining this with Equation (15) gives the desired claim. ∎

We need the following simple helper lemma to finish proving Theorem 6.1:

######  Lemma A.3.

Let $w,\tilde{w}$ be elements of a Hilbert space $\Gamma$. If $\tilde{w}\neq
0$, define $\bar{w}=\tilde{w}/\|\tilde{w}\|_{\Gamma}$. If $\tilde{w}=0$,
define $\bar{w}$ to be an arbitrary element of $B_{\Gamma}(1)$. Then

$\langle
w,\bar{w}\rangle\geq\|\tilde{w}\|_{\Gamma}-\|w-\tilde{w}\|_{\Gamma}\geq\|w\|_{\Gamma}-2\|w-\tilde{w}\|_{\Gamma}.$

###### Proof.

We have

$\displaystyle\langle
w,\bar{w}\rangle\geq\langle\tilde{w},\bar{w}\rangle-\|w-\tilde{w}\|_{\Gamma}$
$\displaystyle=\|\tilde{w}\|_{\Gamma}-\|w-\tilde{w}\|_{\Gamma}\geq\|w\|_{\Gamma}-2\|w-\tilde{w}\|_{\Gamma}.\qed$

###### Proof of Theorem 6.1.

In the weak agnostic learning task, we assume that there exists $w\in
B_{\Gamma}(r)$ so that

$\operatorname*{\mathbf{E}}_{(\mathbf{v},\mathbf{z})\sim\mathcal{D}}[w(\mathbf{v})z]\geq\alpha.$

Under this assumption, Lemma A.1 tells us that $\langle
w_{0},w\rangle_{\Gamma}\geq\alpha$. Since $w\in B_{\Gamma}(r)$, we have
$\|w\|_{\Gamma}\leq r$, and by the Cauchy-Schwarz inequality,
$r\,\|w_{0}\|_{\Gamma}\geq\|w_{0}\|_{\Gamma}\|w\|_{\Gamma}\geq\langle
w_{0},w\rangle_{\Gamma}$. Therefore, we can assume that
$\|w_{0}\|_{\Gamma}\geq\alpha/r$ in the weak agnostic learning task.

Lemma A.2 ensures that (14) holds with probability at least $1-\delta$. As
long as (14) holds, by Lemma A.3 we have

$\left\langle
w_{0},\frac{\tilde{w}_{0}}{\|\tilde{w}_{0}\|_{\Gamma}}\right\rangle\geq\|w_{0}\|_{\Gamma}-2\|w_{0}-\tilde{w}\|_{\Gamma}\geq\frac{\alpha}{3r}.$
(17)

The output $w_{2}$ of Algorithm 1 can be expressed as

$w_{2}=\frac{\tilde{w}_{0}}{s\ \|\tilde{w}_{0}\|_{\Gamma}}.$ (18)

Combining (17) and (18), we know that with probability at least $1-\delta$,

$\langle w_{0},w_{2}\rangle\geq\frac{\alpha}{3rs}.$

By Lemma A.1, the inequality above implies the weak learning guarantee,
namely, $\operatorname*{\mathbf{E}}[w_{2}(\mathbf{v})z]\geq\alpha/(3rs)$.
Finally, it is clear that $\|w_{2}\|_{\Gamma}\leq 1/s$, so $w_{2}\in
B_{\Gamma}(1/s)$, as desired. ∎

###  A.2 Proof of Theorem 6.2

Consider a distribution $\mathcal{D}$ of
$(\mathbf{v},\mathbf{y})\in\Delta_{k}\times\mathcal{E}_{k}$, and define
$\mathbf{z}:=\mathbf{y}-\mathbf{v}$. Define
$w_{0}^{(j)}:=\operatorname*{\mathbf{E}}[\mathbf{z}^{(j)}\varphi_{\mathbf{v}}]$,
where $\mathbf{z}^{(j)}$ is the $j$-th coordinate of $\mathbf{z}$. For $n$
i.i.d. data points
$(\mathbf{v}_{1},\mathbf{y}_{1}),\ldots,(\mathbf{v}_{n},\mathbf{y}_{n})$,
define $\mathbf{z}_{i}:=\mathbf{y}_{i}-\mathbf{v}_{i}$. Define
$\tilde{w}_{0}^{(j)}:=\frac{1}{n}\sum_{i=1}^{n}\mathbf{z}_{i}^{(j)}\varphi_{\mathbf{v}_{i}}$.

######  Lemma A.4.

When $n\geq Ckr^{2}s^{2}\varepsilon^{-2}\log(1/\delta)$, with probability at
least $1-\delta$,

$\sum_{j=1}^{k}\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}\leq\alpha/(3r).$
(19)

###### Proof.

We first show that

$\sum_{j=1}^{k}\operatorname*{\mathbf{E}}\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}\leq\alpha/(6r).$

For every $j$,

$\displaystyle\operatorname*{\mathbf{E}}[\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}^{2}]$
$\displaystyle=\operatorname*{\mathbf{E}}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathbf{z}_{i}^{(j)}\varphi_{\mathbf{v}_{i}}-w_{0}^{(j)}\right\|_{\Gamma}^{2}\right]$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}\operatorname*{\mathbf{E}}\|\mathbf{z}_{i}^{(j)}\varphi_{\mathbf{v}_{i}}-w_{0}^{(j)}\|_{\Gamma}^{2}+\frac{1}{n^{2}}\sum_{i\neq
i^{\prime}}\langle\mathbf{z}_{i}^{(j)}\varphi_{\mathbf{v}_{i}}-w_{0}^{(j)},\mathbf{z}_{i^{\prime}}^{(j)}\varphi_{\mathbf{v}_{i^{\prime}}}-w_{0}^{(j)}\rangle$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}\operatorname*{\mathbf{E}}\|\mathbf{z}_{i}^{(j)}\varphi_{\mathbf{v}_{i}}-w_{0}^{(j)}\|_{\Gamma}^{2}$
$\displaystyle=\frac{1}{n}\operatorname*{\mathbf{E}}[\|\mathbf{z}^{(j)}_{1}\varphi_{\mathbf{v}_{1}}-w_{0}^{(j)}\|_{\Gamma}^{2}]$
$\displaystyle\leq\frac{1}{n}\operatorname*{\mathbf{E}}[\|\mathbf{z}^{(j)}_{1}\varphi_{\mathbf{v}_{1}}\|_{\Gamma}^{2}]$
$\displaystyle\leq\frac{s^{2}}{n}\operatorname*{\mathbf{E}}[(\mathbf{z}_{1}^{(j)})^{2}]$

By Cauchy-Schwarz,

$\sum_{j=1}^{k}\sqrt{\operatorname*{\mathbf{E}}[(\mathbf{z}_{1}^{(j)})^{2}]}\leq\sqrt{k\sum_{j=1}^{k}\operatorname*{\mathbf{E}}[(\mathbf{z}_{1}^{(j)})^{2}]}\leq\sqrt{k\sum_{j=1}^{k}\operatorname*{\mathbf{E}}|\mathbf{z}_{1}^{(j)}|}\leq\sqrt{2k}.$

Therefore,

$\sum_{j=1}^{k}\operatorname*{\mathbf{E}}\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}\leq\sum_{j=1}^{k}\sqrt{\operatorname*{\mathbf{E}}[\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}^{2}]}\leq\frac{s\sqrt{2k}}{\sqrt{n}}\leq\alpha/(6r).$

Finally, we apply McDiarmid’s inequality to the following function of
$(\mathbf{z}_{1},\mathbf{v}_{1}),\ldots,(\mathbf{z}_{n},\mathbf{v}_{n})$:

$\sum_{j=1}^{k}\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}=\sum_{j=1}^{k}\left\|\frac{1}{n}\sum_{i=1}^{n}\mathbf{z}_{i}^{(j)}\varphi_{\mathbf{v}_{i}}-w_{0}^{(j)}\right\|_{\Gamma}$

and get that with probability at least $1-\delta$,

$\sum_{j=1}^{k}\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}\leq\sum_{j=1}^{k}\operatorname*{\mathbf{E}}\|\tilde{w}_{0}^{(j)}-w_{0}^{(j)}\|_{\Gamma}+\alpha/(6r)\leq\alpha/(3r).\qed$

###### Proof of Theorem 6.2.

In the auditing task, we assume that there exists $w\in B_{\Gamma}(r)^{k}$
such that

$\operatorname*{\mathbf{E}}[\langle\mathbf{y}-\mathbf{v},w(\mathbf{v})\rangle]\geq\alpha.$

Using our definition of $\mathbf{z}:=\mathbf{y}-\mathbf{v}$ and
$w_{0}^{(\ell)}:=\operatorname*{\mathbf{E}}[\mathbf{z}^{(\ell)}\varphi_{\mathbf{v}}]$,
by Lemma A.1 we have

$\sum_{\ell=1}^{k}\|w_{0}^{(\ell)}\|_{\Gamma}\geq\frac{1}{r}\sum_{\ell=1}^{k}\langle
w_{0}^{(\ell)},w^{(\ell)}\rangle_{\Gamma}=\frac{1}{r}\sum_{\ell=1}^{k}\operatorname*{\mathbf{E}}[\mathbf{z}^{(j)}w^{(j)}(\mathbf{v})]=\frac{1}{r}\operatorname*{\mathbf{E}}[\langle\mathbf{y}-\mathbf{v},w(\mathbf{v})\rangle]\geq\alpha/r.$

Lemma A.4 ensures that (19) holds with probability at least $1-\delta$. Define
$\bar{w}_{0}:=\tilde{w}_{0}/\|\tilde{w}_{0}\|_{\Gamma}$ if $\tilde{w}_{0}\neq
0$, and define $\bar{w}_{0}:=0$ if $\tilde{w}_{0}=0$. As long as (19) holds,
by Lemma A.3,

$\sum_{\ell=1}^{k}\langle
w_{0}^{(\ell)},\bar{w}_{0}^{(\ell)}\rangle\geq\sum_{\ell=1}^{k}\|w_{0}^{(\ell)}\|_{\Gamma}-2\sum_{\ell=1}^{k}\|\tilde{w}_{0}^{(\ell)}-w_{0}^{(\ell)}\|_{\Gamma}\geq\alpha/(3r).$

In Algorithm 2, we have $w_{2}^{(\ell)}=\bar{w}_{0}^{(\ell)}/s$, and thus the
inequality above implies

$\sum_{\ell=1}^{k}\langle
w_{0}^{(\ell)},w_{2}^{(\ell)}\rangle\geq\alpha/(3rs).$

Therefore by Lemma A.1, with probability at least $1-\delta$,

$\operatorname*{\mathbf{E}}[\langle\mathbf{y}-\mathbf{v},w_{2}(\mathbf{v})\rangle]=\sum_{\ell=1}^{k}\operatorname*{\mathbf{E}}[\mathbf{z}^{(\ell)}w_{2}^{(\ell)}(\mathbf{v})]=\sum_{\ell=1}^{k}\langle
w_{0}^{(\ell)},w_{2}^{(\ell)}\rangle\geq\alpha/(3rs).$

This proves that the output $w_{2}$ of Algorithm 2 satisfies the requirement
of the auditing task. Finally, it is clear that each $w_{2}^{(\ell)}$ has norm
$\|w_{2}^{(\ell)}\|_{\Gamma}\leq 1/s$, so $w_{2}\in B_{\Gamma}(1/s)^{k}$, as
desired. ∎