SUMMARY 81
Table 10.3 Summary of time complexity analysis
Methods Time Complexity Methods Time Complexity
UP O(n
m
)/O(m
7
n
8
) SP/GRW/M0 O(mn)
EG O(mn) Anticor O(N
3
m
2
n)
ONS O(m
3
n) B
K
/B
NN
/CORN O(N
2
mn
2
)+O(Nmn
2
)
PAMR O(mn) CWMR O(mn)
the additional projection, as sometimes the stochastic b may be out of the simplex
domain. To better understand the two aspects, let us continue the Cover’s game in
Table 10.2. For the first case, let μ = (0.5, 0.5) and diag() = (0.25, 0.25). We draw
stochastic b for 10,000 times, and the average b after projection is (0.5038, 0.4962)
(before projection, the value is (0.5070, 0.4993)), which slightly deviates from the
optimal mean and will result in different performance. For the second case, let μ =
(0, 1) and diag() = (0.1, 0.4). We draw and project 10,000 stochastic b, and get an
average bof(0.1391, 0.8609),whichisfar from the optimal mean(0, 1). Inbothcases,
stochastic CWMR tends to deviate from the optimal mean, and thus underperforms
the deterministic one, which is shown in the related experiments (Li et al. 2013,
Table VII).
Since computational time is of crucial importance for certain trading scenarios,
such as high-frequency trading (Aldridge 2010), which can occur in fractions of a
second, we finally show CWMR’s time complexity. In the implementation, we only
consider the diagonal elements of ; thus, its inverse costs linear time. Moreover,
the projection (Line 3 in Algorithm 10.1) can be implemented in O(m) time (Duchi
et al. 2008). Thus, in total, CWMR algorithms (Algorithm 10.1) take O(m) time per
period. Straightforwardly, OLPS with CWMR (Algorithm 10.2) takes O(mn) time.
Table 10.3 compares CWMR’s time complexity with that of existing strategies.
∗
Clearly, CWMR takes no more time than any others.
10.5 Summary
In this chapter, we proposed a novel online portfolio selection (OLPS) strategy named
confidence-weighted mean reversion (CWMR), which effectively learns portfolios
by exploiting the mean reversion property in financial markets and the second-order
information of a portfolio. CWMR’s update schemes are obtained by solving two
optimization problems that consider both first- and second-order information of a
portfolio vector, which goes beyond any existing approaches that only consider first-
order information. As shown in Part IV, the proposed approach beats a number of
∗
Nonparametric learning approaches (B
K
,B
NN
, and CORN) require to solve a nonlinear optimization
each period, that is,b
t+1
= arg max
b∈
m
i
(b
x
i
), whose time complexityis generally high. To produce
an approximate solution, batch gradient projection algorithms (Helmbold etal. 1997)take O(mn), while the
batch convex Newton method (Agarwal et al. 2006) takes O(m
3
n). In the table, we set the step O(mn) time
complexity. In our implementation, we adopt MATLAB
Optimization Toolbox
TM
(function fmincon
with active-set) to obtain exact solutions.
T&F Cat #K23731 — K23731_C010 — page 81 — 9/28/2015 — 21:24
82 CONFIDENCE-WEIGHTED MEAN REVERSION
competing state-of-the-art approaches on various up-to-date datasets collected from
the real market.
In future, we plan to study in detail the cause behind the existence of the mean
reversion property in the financial markets. This will help us to further understand the
nature of the markets. Second, we also intend to explore the possibility of combining
both the trend-following and mean reversion principles to provide more practically
effective solutions. Finally, we note that an interesting future direction is to extend
our analysis for long-short portfolios.
∗
∗
Long-short portfolios can have negative weights, which denote the short positions.
T&F Cat #K23731 — K23731_C010 — page 82 — 9/28/2015 — 21:24
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.