4\Bigg{[}G^{2}+2\lambda^{2}\Bigg{(}\sup_{\mathbf{x}_{i}}\left\|\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}])^{T}\operatorname{vec}(W^{T}W)\right\|^{2}$
$\displaystyle\;\;\;+4\sup_{\mathbf{x}_{i},s_{i}}\left\|\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{s}_{i}\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i},s_{i}])\operatorname{vec}(W^{T}\widehat{P}_{s}^{-1/2})\right\|^{2}\Bigg{)}\Bigg{]},$

by Young’s and Jensen’s inequalities and the assumption that
$\ell(\mathbf{x}_{i},y_{i},\cdot)$ is $G$-Lipschitz. Now,

$\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}])^{T}\operatorname{vec}(W^{T}W)=\sum_{l=1}^{m}\nabla\mathcal{F}_{l}(\mathbf{x}_{i},\bm{\theta})\sum_{j=1}^{k}W_{j,1}W_{j,l},$

which implies

$\|\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}])^{T}\operatorname{vec}(W^{T}W)\|^{2}\leq\sum_{j,l}W_{j,l}^{2}\sup_{l\in[m],\mathbf{x},\bm{\theta}}\|\nabla\mathcal{F}_{l}(\mathbf{x},\bm{\theta})\|^{2}\leq
D^{2}L^{2},$ (38)

by $L$-Lipschitzness of $\mathcal{F}(\cdot,\mathbf{x})$. Also,

$\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{s}_{i}\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i},s_{i}])\operatorname{vec}(W^{T}\widehat{P}_{s}^{-1/2})=\sum_{r=1}^{k}\sum_{j=1}^{m}\nabla{\mathcal{F}}_{j}(\bm{\theta},\mathbf{x}_{i})\frac{\mathbf{s}_{i,r}W_{r,j}}{\sqrt{\hat{p}_{S}(r)}},$

which implies

$\left\|\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{s}_{i}\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i},s_{i}])\operatorname{vec}(W^{T}\widehat{P}_{s}^{-1/2})\right\|^{2}\leq
mk\sum_{r=1}^{k}\sum_{j=1}^{m}\sup_{\mathbf{x}_{i},\bm{\theta}}\|\nabla{\mathcal{F}}_{j}(\bm{\theta},\mathbf{x}_{i})\|^{2}\left(\frac{\mathbf{s}_{i,r}W_{r,j}}{\sqrt{\hat{p}_{S}(r)}}\right)^{2}\leq\frac{mk}{\hat{p}_{S}^{\min}}L^{2}D^{2}.$

Thus,

$\sigma_{\bm{\theta}}^{2}\leq
4G^{2}+32\lambda^{2}D^{2}L^{2}\left(1+\frac{mk}{\hat{p}_{S}^{\min}}\right).$

Combining the $\bm{\theta}$\- and $W$-variance bounds yields the lemma. ∎

######  Lemma 11.

Let

$\displaystyle\widehat{F}(\bm{\theta},W)$
$\displaystyle=\frac{1}{N}\sum_{i\in[N]}\ell(\mathbf{x}_{i},y_{i};\bm{\theta})+\lambda\widehat{\psi}_{i}(\bm{\theta},W)$

where

$\displaystyle\small\widehat{\psi}_{i}(\bm{\theta},W)$
$\displaystyle=-\operatorname{Tr}(W\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i},\bm{\theta})\widehat{\mathbf{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}]W^{T})+2\operatorname{Tr}(W\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\widehat{P}_{s}^{-1/2})-1.$

Then:

  1. 1.

$\widehat{F}$ is $\beta$-smooth, where $\beta=2\left(\beta_{\ell}+2\lambda
Dmb\left(D+\frac{1}{\sqrt{\hat{p}_{S}^{\min}}}\right)+2+8L\left(D+\frac{1}{\sqrt{\hat{p}_{S}^{\min}}}\right)\right)$.

  2. 2.

$\widehat{F}(\bm{\theta},\cdot)$ is $2\lambda\hat{p}_{\widehat{Y}}^{\min}$
-strongly concave for all $\bm{\theta}^{t}$.

  3. 3.

If $\mathcal{W}=B_{F}(0,D)$ with
$D\geq\frac{2}{\hat{p}_{\widehat{Y}}^{\min}\sqrt{\hat{p}_{S}^{\min}}}$, then
Eq. 1 $=\min_{\bm{\theta}}\max_{W\in\mathcal{W}}\widehat{F}(\bm{\theta},W)$.

###### Proof.

We shall freely use the expressions for the derivatives of
$\widehat{\psi}_{i}$ obtained in the proof of Lemma 10.
1\. First,

$\displaystyle\|\nabla_{w}\widehat{F}(\bm{\theta},W)-\nabla_{w}\widehat{F}(\bm{\theta},W^{\prime})\|_{F}$
$\displaystyle\leq
2\sup_{\mathbf{x}_{i}}\|W\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}]-W^{\prime}\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}]\|_{F}$
$\displaystyle\leq 2\|W-W^{\prime}\|_{F},$

since ${\mathcal{F}}_{j}(\bm{\theta},\mathbf{x}_{i})\leq 1$ for all $j\in[m]$.
Next,

$\displaystyle\|\nabla_{w}\widehat{F}(\bm{\theta},W)-\nabla_{w}\widehat{F}(\bm{\theta}^{\prime},W)\|_{F}^{2}$
$\displaystyle\leq
8\sup_{\mathbf{x}_{i},\mathbf{s}_{i},y_{i}}\Bigg{[}D^{2}\left\|\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}]-\mathbb{E}[\mathbf{\widehat{Y}}(\mathbf{x}_{i},\bm{\theta}^{\prime})\mathbf{\widehat{Y}}(\mathbf{x}_{i},\bm{\theta}^{\prime})^{T}|\mathbf{x}_{i}]\right\|_{F}^{2}$
$\displaystyle\;\;\;+\left\|\widehat{P}_{s}^{-1/2}\left(\mathbb{E}[\mathbf{s}_{i}\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i},s_{i}]-\mathbb{E}[\mathbf{s}_{i}\mathbf{\widehat{Y}}(\mathbf{x}_{i},\bm{\theta}^{\prime})^{T}|\mathbf{x}_{i},s_{i}]\right)\right\|_{F}^{2}\Bigg{]}$
$\displaystyle\leq
8\sup_{\mathbf{x}_{i},\mathbf{s}_{i},y_{i}}\Bigg{[}D^{2}\left\|{\mathcal{F}}(\bm{\theta},\mathbf{x}_{i})-{\mathcal{F}}(\bm{\theta}^{\prime},\mathbf{x}_{i})\right\|_{F}^{2}$
$\displaystyle\;\;\;+\sum_{j=1}^{m}\sum_{r=1}^{k}|{\mathcal{F}}_{j}(\bm{\theta},\mathbf{x}_{i})-{\mathcal{F}}_{j}(\bm{\theta}^{\prime},\mathbf{x}_{i})|^{2}\widehat{p}_{s}(r)(r)^{-1}\mathbf{s}_{i,r}^{2}\Bigg{]}$
$\displaystyle\leq
8\sup_{\mathbf{x}_{i},\mathbf{s}_{i},y_{i}}\Bigg{[}D^{2}L^{2}\|\bm{\theta}-\bm{\theta}^{\prime}\|^{2}+\frac{L^{2}}{\hat{p}_{S}^{\min}}\|\bm{\theta}-\bm{\theta}^{\prime}\|^{2}\Bigg{]},$

which implies

$\|\nabla_{w}\widehat{F}(\bm{\theta},W)-\nabla_{w}\widehat{F}(\bm{\theta}^{\prime},W)\|_{F}\leq
8L\left(D+\frac{1}{\sqrt{\hat{p}_{S}^{\min}}}\right)\|\bm{\theta}-\bm{\theta}^{\prime}\|.$

Lastly,

$\displaystyle\|\nabla_{\bm{\theta}}\widehat{F}(\bm{\theta},W)-\nabla_{\bm{\theta}}\widehat{F}(\bm{\theta}^{\prime},W)\|$
$\displaystyle\leq\sup_{\mathbf{x}_{i},y_{i},s_{i}}\Bigg{[}\|\nabla\ell(\mathbf{x}_{i},y_{i},\bm{\theta})-\nabla\ell(\mathbf{x}_{i},y_{i},\bm{\theta}^{\prime})\|$
$\displaystyle\;\;\;+\lambda\left\|\left[-\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}])^{T}+\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{\hat{y}}(\mathbf{x}_{i},\bm{\theta}^{\prime})\mathbf{\hat{y}}(\mathbf{x}_{i},\bm{\theta}^{\prime})^{T}|\mathbf{x}_{i}])^{T}\right]\operatorname{vec}(W^{T}W)\right\|$
$\displaystyle\;\;\;+2\lambda\left\|[\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{s}_{i}\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i},s_{i}])-\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{s}_{i}\mathbf{\hat{y}}(\mathbf{x}_{i},\bm{\theta}^{\prime})^{T}|\mathbf{x}_{i},s_{i}])]\operatorname{vec}(W^{T}\widehat{P}_{s}^{-1/2})\right\|\Bigg{]}$
$\displaystyle\leq\beta_{\ell}\|\bm{\theta}-\bm{\theta}^{\prime}\|+\lambda
D^{2}\sup_{\mathbf{x}}\sum_{l=1}^{m}\|\nabla{\mathcal{F}}_{l}(\bm{\theta},\mathbf{x})-\nabla{\mathcal{F}}_{l}(\bm{\theta}^{\prime},\mathbf{x})\|$
$\displaystyle\;\;\;+2\lambda\sup_{\mathbf{x},r\in[k]}\left\|\sum_{j=1}^{m}\nabla{\mathcal{F}}_{j}(\bm{\theta},\mathbf{x})-\nabla{\mathcal{F}}_{j}(\bm{\theta}^{\prime},\mathbf{x})\hat{p}_{S}(r)^{-1/2}W_{r,j}\right\|$
$\displaystyle\leq\left[\beta_{\ell}+2\lambda\left(D^{2}b+\frac{Db}{\sqrt{\hat{p}_{S}^{\min}}}\right)\right]\|\bm{\theta}-\bm{\theta}^{\prime}\|,$

by Assumption 1. Combining the above inequalities yields part 1.
2\. We have
$\nabla^{2}_{ww}\widehat{F}(\bm{\theta},W)=-2\lambda\widehat{P}_{\hat{y}}$,
which is a diagonal matrix with
$(\nabla^{2}_{ww}\widehat{F}(\bm{\theta},W))_{j,j}=-2\lambda\frac{1}{N}\sum_{i=1}^{N}{\mathcal{F}}_{j}(\mathbf{x}_{i},\bm{\theta})\leq-2\lambda\hat{p}_{\widehat{Y}}^{\min}$,
by Assumption 1. Thus, $\widehat{F}(\cdot,\bm{\theta})$ is
$2\lambda\hat{p}_{\widehat{Y}}^{\min}$-strongly concave for all $\bm{\theta}$.
3\. Our choice of $D$ ensures that
$W^{*}(\bm{\theta}^{*})\in\text{int}(\mathcal{W})$, since

$\displaystyle\|W^{*}(\bm{\theta}^{*})\|_{F}$
$\displaystyle=\|\widehat{P}_{s}^{-1/2}\widehat{P}_{\hat{y},s}(\bm{\theta}^{*})^{T}\widehat{P}_{\hat{y}}(\bm{\theta}^{*})^{-1}\|_{F}$
(39)
$\displaystyle\leq\frac{1}{\hat{p}_{\widehat{Y}}^{\min}\sqrt{\hat{p}_{S}^{\min}}}.$
(40)

Therefore,
$\max_{W\in\mathcal{W}}\widehat{F}(\bm{\theta},W)=\max_{W}\widehat{F}(\bm{\theta},W)$,
which implies part 3 of the lemma.

∎

By Assumption 1 and Lemma 11, our choice of $\mathcal{W}$ implies that
$W^{*}(\bm{\theta}^{*})\in\mathcal{W}$ and hence that the solution of Eq.
FERMI obj. solves

$\min_{\bm{\theta}}\max_{W\in\mathcal{W}}\left\\{\widehat{F}(\bm{\theta},W):=\frac{1}{N}\sum_{i\in[N]}\widehat{\mathcal{L}}(\bm{\theta})+\lambda\widehat{\Psi}(\bm{\theta},W)\right\\}.$

This enables us to establish the convergence of Algorithm 1 (which involves
projection) to a stationary point for the unconstrained min-max optimization
problem Eq. 1 that we consider. The $W^{t}$ projection step in Algorithm 1 is
necessary to ensure that the iterates $W^{t}$ remain bounded, and hence that
the smoothness and bounded variance conditions of $\widehat{F}$ are satisfied
at every iteration.

###  D.1 Proof of Theorem 2

Now we turn to the proof of Theorem 2. We first re-state and prove Proposition
2.

######  Proposition 4 (Restatement of Proposition 2).

Let $\\{z_{i}\\}_{i=1}^{n}=\\{\mathbf{x}_{i},s_{i},y_{i}\\}_{i=1}^{n}$ be
drawn i.i.d. from an unknown joint distribution $\mathcal{D}$. Denote
$\widehat{\psi}_{i}^{(n)}(\bm{\theta},W)=-\operatorname{Tr}(W\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i},\bm{\theta})\widehat{\mathbf{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}]W^{T})+2\operatorname{Tr}\left(W\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}\right)-1$,
where
$\widehat{P}_{s}^{(n)}=\frac{1}{n}\sum_{i=1}^{n}{\rm{diag}}(\mathbbm{1}_{\\{s_{i}=1\\}},\cdots,\mathbbm{1}_{\\{s_{i}=k\\}})$.
Denote
$\Psi(\bm{\theta},W)=-\operatorname{Tr}(WP_{\hat{y}}W^{T})+2\operatorname{Tr}(WP_{\hat{y},s}P_{s}^{-1/2})-1$,
where
$P_{\hat{y}}={\rm{diag}}(\mathbb{E}{\mathcal{F}}_{1}(\bm{\theta},\mathbf{x}),\cdots,\mathbb{E}{\mathcal{F}}_{m}(\bm{\theta},\mathbf{x}))$,
$(P_{\hat{y},s})_{j,r}=\mathbb{E}_{\mathbf{x}_{i},s_{i}}[{\mathcal{F}}_{j}(\bm{\theta},\mathbf{x}_{i})\mathbf{s}_{i,r}]$
for $j\in[m],r\in[k]$, and $P_{s}={\rm{diag}}(P_{S}(1),\cdots,P_{S}(k))$.
Assume $p_{S}(r)>0$ for all $r\in[k]$. Then,

$\small\max_{W}\Psi(\bm{\theta},W)=D_{R}(\widehat{Y}(\bm{\theta});S)$

and

$\small\lim_{n\to\infty}\mathbb{E}[\widehat{\psi}_{i}^{(n)}(\bm{\theta},W)]=\Psi(\bm{\theta},W).$

###### Proof.

The first claim, that
$\max_{W}\Psi(\bm{\theta},W)=D_{R}(\widehat{Y}(\bm{\theta});S)$ is immediate
from Proposition 1 and its proof, by replacing the empirical probabilities
with $\mathcal{D}$-probabilities everywhere. For the second claim, we clearly
have

$\displaystyle\small\vspace{-.05in}\mathbb{E}[\widehat{\psi}_{i}^{(n)}(\bm{\theta},W)]$
$\displaystyle=\mathbb{E}\left[-\operatorname{Tr}(W\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i},\bm{\theta})\widehat{\mathbf{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}]W^{T})\right]+2\mathbb{E}\left[\operatorname{Tr}\left(W\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}\right)\right]-1$
(41)
$\displaystyle=-\operatorname{Tr}(WP_{\hat{y}}W^{T})+2\mathbb{E}\left[\operatorname{Tr}\left(W\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}\right)\right]-1,\vspace{-.05in}$

for any $n\geq 1$. Now, $\widehat{P}_{s}^{(n)}(r)$ converges almost surely
(and in probability) to $p_{S}(r)$ by the strong law of large numbers, and
$\mathbb{E}[\widehat{P}_{s}^{(n)}(r)]=p_{S}(r)$. Thus,
$\widehat{P}_{s}^{(n)}(r)$ is a consistent estimator of $p_{S}(r)$. Then by
the continuous mapping theorem and the assumption that $p_{S}(r)\geq C$ for
some $C>0$, we have that $\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1/2}$
converges almost surely (and in probability) to $p_{S}(r)^{-1/2}$. Moreover,
we claim that there exists $N^{*}\in\mathbb{N}$ such that for any $n\geq
N^{*}$,
$\small\mathrm{Var}\left(\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1/2}\right)\leq\frac{2}{C}<\infty$.
To see why this claim holds, note that the definition of almost sure
convergence of $\widehat{P}_{s}^{(n)}(r)$ to $p_{S}(r)$ implies that, with
probability $1$, there exists $N^{*}$ such that for all $n\geq N^{*}$,

$\small\min_{r\in[k]}\widehat{P}_{s}^{(n)}(r)\geq\min_{r\in[k]}p_{S}(r)-C/2\geq
C/2.$

Thus,
$\small\mathrm{Var}\left(\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1/2}\right)\leq\mathbb{E}\left[\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1}\right]\leq\frac{2}{C}$.
Therefore $\small\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1/2}$is a consistent
estimator with uniformly bounded variance, hence it is asymptotically
unbiased:
$\small\lim_{n\to\infty}\mathbb{E}\left[\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1/2}\right]=p_{S}(r)^{-1/2}$.
Furthermore,
$\small\left|\left(\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}\right)_{j,r}\right|\leq\frac{2}{C}$
for all $n\geq N^{*}$ and
$\small\left(\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}\right)_{j,r}$converges
almost surely to
$\left(\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\left(P_{S}\right)^{-1/2}\right)_{j,r}$
as $n\to\infty$ (for any $j\in[m],r\in[k]$). Thus, by Lebesgue’s dominated
convergence theorem, we have

$\displaystyle\small\vspace{-.2in}\lim_{n\to\infty}\left(\mathbb{E}\left[\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}\right]\right)_{j,r}$
$\displaystyle=\mathbb{E}\left[\mathbb{E}[\widehat{\mathbf{y}}(\mathbf{x}_{i};\bm{\theta})\mathbf{s}_{i}^{T}|\mathbf{x}_{i},s_{i}]\lim_{n\to\infty}\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1/2}\right]$
$\displaystyle=\mathbb{E}\left[\mathbf{s}_{i,r}{\mathcal{F}}_{j}(\bm{\theta},\mathbf{x}_{i})\right]\lim_{n\to\infty}\left(\widehat{P}_{s}^{(n)}(r)\right)^{-1/2}$
$\displaystyle=(P_{\hat{y},s})_{j,r}p_{S}(r)^{-1/2}$
$\displaystyle=(P_{\hat{y},s}P_{s}^{-1/2})_{j,r},\vspace{-.1in}$ (42)

for all $j\in[m],r\in[k]$. Combining Eq. 41 with Sec. D.1 (and using linearity
of trace and matrix multiplication) proves the second claim. ∎

We are now ready to prove Theorem 2.

###### Proof of Theorem 2.

Denote $\Phi(\bm{\theta}):=\max_{W}F(\bm{\theta},W)$ for the population-level
objective
$F(\bm{\theta},W):=\mathcal{L}(\bm{\theta})+\lambda\Psi(\bm{\theta},W)$ (using
the notation in Proposition 2). Let $\bm{\theta}^{*}$ denote the output of the
one-pass/sample-without-replacement version of Algorithm 1, run on the
modified empirical objective where $\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}$
is replaced by the true sensitive attribute matrix $P_{S}^{-1/2}$. That is,
$\bm{\theta}^{*}\sim\textbf{Unif}(\bm{\theta}_{1}^{*},\ldots,\bm{\theta}_{T}^{*})$,
where $\bm{\theta}^{*}_{t}$ denotes the $t$-th iterate of the modified FERMI
algorithm just described. Then, given i.i.d. samples, the stochastic gradients
are unbiased (with respect to the population distribution $\mathcal{D}$) for
any minibatch size, by Corollary 1 and its proof. Further, the without-
replacement sampling strategy ensures that the stochastic gradients are
independent across iterations. Additionally, the proof of Proposition 2 showed
that $\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}$ converges almost surely to
$P_{S}^{-1/2}$. Thus, there exists $N$ such that if $n\geq N\geq
T=\Omega(\epsilon^{-5})$, then $\min_{r\in[k]}\widehat{P}_{s}^{(n)}(r)>0$ (by
almost sure convergence of $\widehat{P}_{s}$, see proof of Proposition 2), and

$\mathbb{E}\|\nabla\Phi(\bm{\theta}^{*})\|^{2}\leq\frac{\epsilon}{4},$ (43)

by Theorem 1 and its proof. Let $\widehat{\bm{\theta}}_{t}^{(n)}$ denote the
$t$-th iteration of the one-pass version of Algorithm 1 run on the empirical
objective (with $\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}$). Now,

$\vspace{-.02in}\nabla_{\bm{\theta}}\widehat{\psi}_{i}(\bm{\theta},W)=-\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i}])^{T}\operatorname{vec}(W^{T}W)+2\nabla_{\bm{\theta}}\operatorname{vec}(\mathbb{E}[\mathbf{s}_{i}\mathbf{\widehat{y}}(\mathbf{x}_{i},\bm{\theta})^{T}|\mathbf{x}_{i},s_{i}])\operatorname{vec}\left(W^{T}\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}\right),\vspace{-.02in}$

which shows that $\widehat{\bm{\theta}}_{t}^{(n)}$ is a continuous (indeed,
linear) function of $\left(\widehat{P}_{s}^{(n)}\right)^{-1/2}$ for every $t$.
Thus, the continuous mapping theorem implies that
$\widehat{\bm{\theta}}_{t}^{(n)}$ converges almost surely to
$\bm{\theta}_{t}^{*}$ as $n\to\infty$ for every $t\in[T]$. Hence, if
$\widehat{\bm{\theta}}^{(n)}\sim\textbf{Unif}\left(\widehat{\bm{\theta}}^{(n)}_{1},\ldots,\widehat{\bm{\theta}}^{(n)}_{T}\right)$,
then $\widehat{\bm{\theta}}^{(n)}$ converges almost surely to
$\bm{\theta}^{*}$. Now, for any $\bm{\theta}$, let us denote
$W(\bm{\theta})=\operatorname*{arg\,max}_{W}F(\bm{\theta},W)$. Recall that by
Danskin’s theorem (Danskin, 1966), we have
$\nabla\Phi(\bm{\theta})=\nabla_{\bm{\theta}}F(\bm{\theta},W(\bm{\theta}))$.
Then,

$\displaystyle\|\nabla\Phi(\widehat{\bm{\theta}}^{(n)})-\nabla\Phi(\bm{\theta}^{*})\|^{2}$
$\displaystyle\leq
2\left\|\nabla_{\theta}F(\widehat{\bm{\theta}}^{(n)},W(\widehat{\bm{\theta}}^{(n)}))-\nabla_{\theta}F(\bm{\theta}^{*},W(\widehat{\bm{\theta}}^{(n)}))\right\|^{2}+2\left\|\nabla_{\theta}F(\bm{\theta}^{*},W(\widehat{\bm{\theta}}^{(n)}))-\nabla_{\theta}F(\bm{\theta}^{*},W(\bm{\theta}^{*}))\right\|^{2}$
$\displaystyle\leq
2\left[\beta^{2}\|\widehat{\bm{\theta}}^{(n)}-\bm{\theta}^{*}\|^{2}+\beta^{2}\|W(\widehat{\bm{\theta}}^{(n)})-W(\bm{\theta}^{*})\|^{2}\right]$
$\displaystyle\leq
2\left[\beta^{2}\|\widehat{\bm{\theta}}^{(n)}-\bm{\theta}^{*}\|^{2}+\frac{2\beta^{2}L^{2}}{\mu^{2}}\|\widehat{\bm{\theta}}^{(n)}-\bm{\theta}^{*}\|^{2}\right],$

where $L$ denotes the Lipschitz parameter of $F$, $\beta$ is the Lipschitz
parameter of $\nabla F$, and $\mu$ is the strong concavity parameter of
$F(\bm{\theta},\cdot)$: see Lemma 11 and its proof (in Appendix D) for the
explicit $\beta$, $L$, and $\mu$. We used Danskin’s theorem and Young’s
inequality in the first line, $\beta$-Lipschitz continuity of $\nabla F$ in
the second line, and $\frac{2L}{\mu}$-Lipschitz continuity of the
$\operatorname*{arg\,max}_{W}F(\bm{\theta},W)$ function for $\mu$-strongly
concave and $L$-Lipschitz $F(\bm{\theta},\cdot)$ (see e.g. (Lowy & Razaviyayn,
2021, Lemma B.2)). Letting $n\to\infty$ makes
$\|\widehat{\bm{\theta}}^{(n)}-\bm{\theta}^{*}\|^{2}\to 0$ almost surely, and
hence
$\|\nabla\Phi(\widehat{\bm{\theta}}^{(n)})-\nabla\Phi(\theta^{*})\|^{2}\to 0$
almost surely. Furthermore, Danskin’s theorem and Lipschitz continuity of
$\nabla_{\theta}F$ implies that
$\|\nabla\Phi(\widehat{\bm{\theta}}^{(n)})-\nabla\Phi(\bm{\theta}^{*})\|^{2}\leq
C$ almost surely for some absolute constant $C>0$ and all $n$ sufficiently
large. Therefore, we may apply Lebesgue’s dominated convergence theorem to get
$\lim_{n\to\infty}\mathbb{E}\|\nabla\Phi(\widehat{\bm{\theta}}^{(n)})-\nabla\Phi(\bm{\theta}^{*})\|^{2}=\mathbb{E}\left[\lim_{n\to\infty}\|\nabla\Phi(\widehat{\bm{\theta}}^{(n)})-\nabla\Phi(\bm{\theta}^{*})\|^{2}\right]=0$.
In particular, there exists $N$ such that $n\geq
N\implies\mathbb{E}\|\nabla\Phi(\widehat{\bm{\theta}}^{(n)})-\nabla\Phi(\bm{\theta}^{*})\|^{2}\leq\frac{\epsilon}{4}$.
Combining this with Eq. 43 and Young’s inequality completes the proof. ∎

##  Appendix E Experiment Details and Additional Results

###  E.1 Model description

For all the experiments, the model’s output is of the form
$O=\mathrm{softmax}(Wx+b)$. The model outputs are treated as conditional
probabilities $\mathbf{p}(\hat{y}=i|x)=O_{i}$ which are then used to estimate
the ERMI regularizer. We encode the true class label $Y$ and sensitive
attribute $S$ using one-hot encoding. We define $\ell(\cdot)$ as the cross-
entropy measure between the one-hot encoded class label $Y$ and the predicted
output vector $O$.

We use logistic regression as the base classification model for all
experiments in Fig. 1. The choice of logistic regression is due to the fact
that all of the existing approaches demonstrated in Fig. 1, use the same
classification model. The model parameters are estimated using the algorithm
described in Algorithm 1. The trade-off curves for FERMI are generated by
sweeping across different values for $\lambda\in[0,10000]$. The learning rates
$\eta_{\theta},\eta_{w}$ is constant during the optimization process and is
chosen from the interval $[0.0005,0.01]$ for all datasets. Moreover, the
number of iterations $T$ for experiments in Fig. 1 is fixed to $2000$. Since
the training and test data for the Adult dataset are separated and fixed, we
do not consider confidence intervals for the test accuracy. We generate ten
distinct train/test sets for each one of the German and COMPAS datasets by
randomly sampling $80\%$ of data points as the training data and the rest
$20\%$ as the test data. For a given method in Fig. 1, the corresponding curve
is generated by taking the average test accuracy on $10$ training/test
datasets. Furthermore, the confidence intervals are estimated based on the
test accuracy’s standard deviation on these $10$ datasets.

To perform the experiments in Sec. 3.3 we use a a linear model with softmax
activation. The model parameters are estimated using the algorithm described
in Sec. 3. The data set is cleaned and processed as described in (Kearns et
al., 2018). The trade-off curves for FERMI are generated by sweeping across
different values for $\lambda$ in $[0,100]$ interval, learning rate $\eta$ in
$[0.0005,0.01]$, and number of iterations $T$ in $[50,200]$. The data set is
cleaned and processed as described in (Kearns et al., 2018).

For the experiments in Sec. 3.4, we create the synthetic color MNIST as
described by Li & Vasconcelos (2019). We set the value $\sigma=0$. In Fig. 6,
we compare the performance of stochastic solver (Algorithm 1) against the
baselines. We use a mini-batch of size $512$ when using the stochastic solver.
The color MNIST data has $60000$ training samples, so using the stochastic
solver gives a speedup of around $100$x for each iteration, and an overall
speedup of around $40$x. We present our results on two neural network
architectures; namely, LeNet-5 (Lecun et al., 1998) and a Multi-layer
perceptron (MLP). We set the MLP with two hidden layers (with $300$ and $100$
nodes) and an output layer with ten nodes. A ReLU activation follows each
hidden layer, and a softmax activation follows the output layer.

Some general advice for tuning $\lambda$: Larger value for $\lambda$ generally
translates to better fairness, but one must be careful to not use a very large
value for $\lambda$ as it could lead to poor generalization performance of the
model. The optimal values for $\lambda$, $\eta$, and $T$ largely depend on the
data and intended application. We recommend starting with $\lambda\approx 10$.
In Appendix E.4, we can observe the effect of changing $\lambda$ on the model
accuracy and fairness for the COMPAS dataset.

###  E.2 More comparison to (Mary et al., 2019)

The algorithm proposed by Mary et al. (2019) backpropagates the batch estimate
of ERMI, which is biased especially for small minibatches. Our work uses a
correct and unbiased implementation of a stochastic ERMI estimator.
Furthermore, Mary et al. (2019) does not establish any convergence guarantees,
and in fact their algorithm does not converge. See Fig. 7 for the evolution of
training loss (i.e. value of the objective function) and test accuracy. For
this experiment, we follow the same setup used in (Mary et al., 2019, Table
1); the minibatch size for this experiment is $128$.

Figure 7: (Mary et al., 2019) fails to converge to a stationary point whereas
our stochastic algorithm easily converges.

###  E.3 Performance in the presence of outliers & class-imbalance

We also performed an additional experiment on Adult (setup of Fig 1) with a
random 10% of sensitive attributes in training forced to 0. FERMI offers the
most favorable tradeoffs on clean test data, however, all methods reach a
higher plateau (see Fig 8). The interplay between fairness, robustness, and
generalization is an important future direction. With respect to imbalanced
sensitive groups, the experiments in Fig 5 are on a naturally imbalanced
dataset, where $\max_{s\in{\cal S}}p(s)/\min_{s\in{\cal S}}p(s)>100$ for 3-18
sensitive attrib, and FERMI offers the favorable tradeoffs.

Figure 8: Comparing FERMI with other methods in the presence of outliers
(random 10% of sensitive attributes in training forced to 0. FERMI still
achieves a better trade-off compared to all other baselines.

###  E.4 Effect of hyperparameter $\lambda$ on the accuracy-fairness tradeoffs

We run ERMI algorithm for the binary case to COMPAS dataset to investigate the
effect of hyper-parameter tuning on the accuracy-fairness trade-off of the
algorithm. As it can be observed in Fig. 9, by increasing $\lambda$ from $0$
to $1000$, test error (left axis, red curves) is slightly increased. On the
other hand, the fairness violation (right axis, green curves) is decreased as
we increase $\lambda$ to $1000$. Moreover, for both notions of fairness
(demographic parity with the solid curves and equality of opportunity with the
dashed curves) the trade-off between test error and fairness follows the
similar pattern. To measure the fairness violation, we use demographic parity
violation and equality of opportunity violation defined in Section equation 3
for the solid and dashed curves respectively.

Figure 9: Tradeoff of fairness violation vs test error for FERMI algorithm on
COMPAS and Adult datasets. The solid and dashed curves correspond to FERMI
algorithm under the demographic parity and equality of opportunity notions
accordingly. The left axis demonstrates the effect of changing $\lambda$ on
the test error (red curves), while the right axis shows how the fairness of
the model (measured by equality of opportunity or demographic parity
violations) depends on changing $\lambda$.

###  E.5 Complete version of Figure 1 (with pre-processing and post-processing
baselines)

In Figure 1 we compared FERMI with several state-of-the-art in-processing
approaches. In the next three following figures we compare the in-processing
approaches depicted in Figure 1 with pre-processing and post-processing
methods including (Hardt et al., 2016; Kamiran et al., 2010; Feldman et al.,
2015).

Figure 10: Tradeoff of demographic parity violation vs test error for FERMI
algorithm on COMPAS, German, and Adult datasets. Figure 11: Tradeoff of
equalized odds violation vs test error for FERMI algorithm on COMPAS, German,
and Adult datasets. Figure 12: Tradeoff of equality of opportunity violation
vs test error for FERMI algorithm on COMPAS, German, and Adult datasets.

###  E.6 Description of datasets

All of the following datasets are publicly available at UCI repository.

German Credit
Dataset.999https://archive.ics.uci.edu/ml/datasets/statlog+(german+credit+data)
German Credit dataset consists of $20$ features ($13$ categorical and $7$
numerical) regarding to social, and economic status of $1000$ customers. The
assigned task is to classify customers as good or bad credit risks. Without
imposing fairness, the DP violation of the trained model is larger than
$20\%$. We choose $80\%$ of customers as the train data and the remaining
$20\%$ customers as the test data. The sensitive attributes are gender, and
marital-status.

Adult Dataset.101010https://archive.ics.uci.edu/ml/datasets/adult. Adult
dataset contains the census information of individuals including education,
gender, and capital gain. The assigned classification task is to predict
whether a person earns over 50k annually. The train and test sets are two
separated files consisting of $32,000$ and $16,000$ samples respectively. We
consider gender and race as the sensitive attributes (For the experiments
involving one sensitive attribute, we have chosen gender). Learning a logistic
regression model on the training dataset (without imposing fairness) shows
that only 3 features out of 14 have larger weights than the gender attribute.
Note that removing the sensitive attribute (gender), and retraining the model
does not eliminate the bias of the classifier. the optimal logistic regression
classifier in this case is still highly biased. For the clustering task, we
have chosen 5 continuous features (Capital-gain, age, fnlwgt, capital-loss,
hours-per-week), and $10,000$ samples to cluster. The sensitive attribute of
each individual is gender.

Communities and Crime
Dataset.111111http://archive.ics.uci.edu/ml/datasets/communities+and+crime The
dataset is cleaned and processed as described in (Kearns et al., 2018).
Briefly, each record in this dataset summarizes aggregate socioeconomic
information about both the citizens and police force in a particular U.S.
community, and the problem is to predict whether the community has a high rate
of violent crime.

COMPAS Dataset.121212https://www.kaggle.com/danofer/compass Correctional
Offender Management Profiling for Alternative Sanctions (COMPAS) is a famous
algorithm which is widely used by judges for the estimation of likelihood of
reoffending crimes. It is observed that the algorithm is highly biased against
the black defendants. The dataset contains features used by COMPAS algorithm
alongside with the assigned score by the algorithm within two years of the
decision.

Colored MNIST Dataset.131313https://github.com/JerryYLi/Dataset-REPAIR/ We use
the code by Li & Vasconcelos (2019) to create a Colored MNIST dataset with
$\sigma=0$. We use the provided LeNet-5 model trained on the colored dataset
for all baseline models of Baharlouei et al. (2020); Mary et al. (2019); Cho
et al. (2020b) and FERMI, where we further apply the corresponding regularizer
in the training process.


A Scheduling Perspective on Modular Educational Systems in Europe

imc]Rubén Ruiz-Torrubianocor1

untis]Sebastian Knopp

untis]Lukas Matthias Wolf

imc]Andreas Krystallidis

[imc]organization=IMC Krems University of Applied Sciences,
addressline=Piaristengasse 1,

[untis]organization=Untis GmbH,
addressline=Belvederegasse 11,

[cor1]Corresponding author.

In modular educational systems, students are allowed to choose a part of their own curriculum themselves.
This is typically done in the final class levels which lead to maturity for university access.
The rationale behind letting students choose their courses themselves is to enhance
self-responsibility, improve student motivation, and allow a focus on specific areas of interest.
A central instrument for bringing these systems to fruition is the timetable.
However, scheduling the timetable in such systems can be an extremely challenging and time-consuming task.
In this study, we present a framework for classifying
modular educational systems in Europe that reflects different degrees of freedom regarding student choices,
and explore the consequences from the perspective of scheduling a timetable that satisfies all requirements
from the organizational and the pedagogical perspective. For this purpose, we conducted interviews in Austria,
Germany, Finland, Switzerland, the Netherlands, and Luxembourg and apply the framework to these educational systems,
finding that among them the Finnish system shows the highest degree of modularity. After
analyzing the consequences of modularity from the scheduling perspective, we assess the necessity for automated scheduling methods,
which are central for realizing the potential and many benefits of modular education in practice.

* We present a category framework to classify educational systems according to their degree of modularity.

* A graphical comparison is given that shows how different educational systems score on modularity according to our framework.

* A scheduling perspective is provided where the challenges regarding building timetables for modular educational systems are investigated.

* To the best of our knowledge, this is the first study of this kind to date.

Modular education

§ INTRODUCTION

Curriculum design is one of the central activities of stakeholders involved in educational systems
in order to steer and implement strategic goals that education should fulfill in a given country or region.

One of these goals can be considered in general to meet the current needs and demands of society
and the expectations of the population, especially students, parents and teachers.
Depending on the stakeholders and the output of this activity, different levels of curriculum
design can be defined <cit.>: international/comparative (supra),
system/nation/state (macro), school or institution (meso), classroom (micro) and
individual level (nano). The international or supra level is usually associated with comparative studies
(e.g., PISA) and reflects on aims and quality of education in general. The macro level is focused on the
particular implementation of those goals in a given societal context. This is normally achieved in the
form of national syllabi or concrete objectives. The meso level is concerned with the implementation
of the curriculum in the context of a particular school. For instance, a school might decide to offer
additional electives or make decisions on how parts of the curriculum are delivered. Finally, the micro and
nano levels are mostly concerned with the classroom implementation of the curriculum and how it is
handled by teachers and students.

In particular, it is important to consider how to enhance student engagement (i.e., the nano level)
already at the macro level. In practice, this means laying the regulatory groundwork for
improving student involvement and particupation at the lower levels. One of the most effective
approaches in this context is the introduction of electives in the curriculum, which is often
referred to as modular course design. The origins of modularization in education can be traced
back to Harvard University the 19th century <cit.>, where an elective system was introduced to increase
the choices available for students and increase the flexibility of the curriculum. This development
was explicitly encouraged in Britain in the 1960s and 1970s for increasing participation rates and
enhance teacher and student mobility. Moreover, modular education has been shown to
significantly decrease school dropout rates <cit.> and improve student
achievement <cit.>.

When implementing curricula at the meso (school) level, one of the most challenging operative and
organizational questions is how to schedule courses in a timetable, possibly including both modular
and non-modular components. How courses are scheduled can affect the academic performance of students
<cit.>. From the organizational perspective, the timetable can be considered
as the central school resource plan that coordinates how educational resources (teachers, rooms,
laboratories, etc) are used. Constraints arising from a variety of sources, including teacher and
room availability, students timetable quality and pedagogical considerations can make timetabling very
challenging in practice.

In this study, we aim to answer the following research question: How do different educational systems
in Europe implement modular education and how this relates to timetable scheduling from an
organizational and pedagogical perspective?". We note that the focus of our work is placed on
secondary rather than tertiary eduction. To answer the research question, a novel theoretical framework
is developed to assess the degree of modularity in those systems in a qualitative and quantitative way.
We focus on the educational systems of Austria, Germany, Finland, the Netherlands, Switzerland and
Luxembourg and perform semi-structured interviews with experts and practitioners to gather insights
into how modularity influences
scheduling and what are the most important problems in practice. This framework is the
first step in a larger effort to propose efficient computational methods for solving the scheduling
problem in modular educational systems in practice. To the best of our knowledge, this is
the first study that investigates modular education from a scheduling perspective.

This article is organized as follows. In Section <ref> we outline the methodology used for
this study and introduce central definitions used throughout the paper. Section <ref> presents
the results of the interviews and the proposed framework. A detailed discussion of our findings is
provided in Section <ref> and we conclude in Section <ref> with a summary and
future work.

§ METHODOLOGY

§.§ General methodology

We perform a qualitative content analysis <cit.> based on Mayring's
approach <cit.>. The main difference between this approach and standard
content analysis is that quantitative analysis (e.g., frequency analysis) is not used as a means for
evaluating the resulting categories. Instead a systematic, theory-guided approach is used for
text-analysis that takes the context into account. Therefore, the focus of the analysis is on
the qualities, the processes and the meanings rather than on experimentally measurable entities.
Furthermore, Mayring's approach is theory-guided, which allows the integration of previous
knowledge and theoretical frameworks into the analytic process.

Our study can be framed as an instance of case study research. The goal of case study research
is to investigate phenomena within their context <cit.>. Case study as a
research strategy is particularly well suited when the subject of the investigation includes
organizational or managerial processes <cit.>, as in the current context. Our focus
is on the organizational processes dedicated to scheduling in the context of the particular
modular educational system under consideration. Therefore, we conducted semi-structured interviews
with 12 experts with direct experience in scheduling timetables in modular
educational systems. The interviews were performed from January until July 2023.
Additionally, interview notes and internal documents were also incorporated into the analysis.
After conducting the interviews, an inductive approach was used to develop and refine
the categories. Coding was performed in a collaborative way by iteratively achieving mutual consent
regarding the results of the analysis in what is known
as communicative validation <cit.>.

§.§ Interview partners and regions

In Table <ref> we provide a summary of all the interview partners involved, including
a short description of their expertise and the country/region they work in. As can be seen from
the table, seven of the experts are timetablers and therefore with relevant practical expertise
in the organizational processes of the school. Additionally, six interview partners are experts in
timetabling software with extensive knowledge of their respective modular education system.
Finally, one of the interview partners works at the local Ministry of Education and contributes with
extensive knowledge on the educational system. Note that in total eight out of the total of twelve experts
come from a German-speaking country, and several German regions are represented separately. The reason
is that the authors already have experience with these regions. Additionally, the federal nature
of the German educational system makes it necessary to investigate regions separately, as
differences in curricula and school types can be significant.

ID     Country (region)     Description     Experience

E1     Austria     High school timetabler     More than 5 years

(Lower Austria)     (Gymnasium)
E2     Germany     Timetabling-software expert     More than 25 years

E3     Germany     High school timetabler and     More than 25 years

(Baden-Wurttemberg)     timetabling-software expert
E4     Germany     High school timetabler and     More than 25 years

(Bavaria)     timetabling-software expert
E5     Germany     Timetabling-software expert     More than 15 years

(Lower Saxony)
E6     Germany     High school timetabler     More than 25 years

E7     Germany     Modular education expert     More than 25 years

(Rheinland-Palatinate)     at local Ministry
E8     Netherlands     High school timetabler     More than 25 years

E9     Luxembourg     High school timetabler     More than 5 years

(European school)
E10     Luxembourg     High school timetabler     More than 10 years

(European school)
E11     Switzerland     Timetabling-software expert     More than 25 years

E12     Switzerland     Timetabling-software expert     More than 10 years

Summary of interview partners.

§.§ Coding of the interviews

Once conducted, the interviews were transcripted and annotated. Since the authors have
extensive experience with different educational systems, this a-priori knowledge was
incorporated in the coding process as a set of pre-defined codes. These codes included
terms like "election", "module", "scheduling" and "choices". Once the interviews were
encoded using these terms, the codes were refined to take recurrent themes like
"election systems", "class level overlaps", "number of choices", etc, into account. The refined codes
were obtained inductively by finding commonalities and recurrent themes between the contents of the different
interviews. For instance, it was a common theme to describe what the system of electives
looked like in terms of number of electives or student choices made.

After going through several iterations of this method, consensus was reached on the final categories,
including a categorization of each individual educational system into this set of categories. In
Section <ref>, we present the result of this categorization in detail.

§.§ Basic definitions

In this section, we define some basic terms that will be used later on
to classify the modular education systems that we study in this paper.

Class A group of students that attend all regular lessons together. By
regular lessons we mean those that are mandatory for all students (i.e., they cannot be

Class level/grade The yearly part of a class, e.g., the fourth grade, the fifth grade, etc.
Typically, there are several classes belonging to a given class level (i.e., the classes
4a, 4b, etc.). In what follows we will refer to class levels meaning groups of classes with the same yearly part.

Lesson A lesson is an event where a group of students belonging to one or several classes are taught in a given subject. Usually
the total regular weekly duration of a lesson is split into sessions that can have different lengths.
For instance, a math lesson can have a regular duration of 3 hours per week and be split
into one two-hour and one one-hour session. Sessions are normally constrained by standard times defined
in a time grid. For instance, a school might define that each day lessons start at 8.00 am
and each session has a duration of 50 minutes. In this case, instead of talking about hours we will normally talk
about time slots or periods (both terms are interchangeable).

Courses/Electable lessons
Lessons are called electable if they are not mandatory for a student, i.e., they can be selected
eventually subject to some restrictions (e.g., pre-conditions like previous knowledge/attended courses).
In this paper, we will use the term course to mean an electable lesson.

Student election/choice We will refer to the action of a student selecting a course/module
as an election or choice (these terms can be used interchangeably).

Term This is a subdivision of a school year into disjoint intervals. Most typically,
a term can represent a semester (e.g., fall/spring semesters), but other, shorter terms are also possible.

§ RESULTS

We now describe the category system resulting from encoding the case-study interviews
presented in Section <ref>. First we describe the category system, which is composed
of a total of eight categories. Then, we apply these categories to the individual educational systems
that were investigated in the conducted interviews by evaluating each category in the specific
context of each system. In Section <ref>, a visual comparison between the
investigated educational systems regarding their degree of modularity is provided along with a detailed discussion of the results.

§.§ Categories

After conducting the qualitative content analysis and coding process described in
Section <ref>, the following categories were identified:

Proportion of electable periods (PEP)
Each modular educational system investigated in this study shows varying degrees regarding the
proportion of electable lessons. Given a class level, we define the proportion of electable periods in
that class level as the total number of periods of courses that can be elected by students in that class level
divided by the total number of periods of all lessons (electable and mandatory). So
for example, if there are 5 lessons in class level 8,
and 2 of the 5 lessons are courses, and all lessons have a duration of 2 periods,
the PEP of class level 8 would be $(2 \cdot 2)/(5 \cdot 2)=0.4$, or 40%. We take the maximum of all
class levels as the PEP of a given school form. E.g., if in one class level everything can be chosen freely,
we consider this as 100%, even if in lower class levels nothing can be chosen.

Election systems (ES)
In general, there are different ways of offering electable lessons to students. After conducting the
interviews, we distinguish between three different module selection systems:

Each student is assigned only to lessons that are planed for the class the student belongs to.

Each student can choose one out of a list of pre-defined profiles. A profile determines a set of
courses which all students who have chosen the same profile take together. For example, it might be
possible in a given school to choose between natural sciences and humanities. The profile
natural sciences could include the courses mathematics, physics and chemistry and humanities
could include greek, latin and philosophy. All the other lessons are taught class-based (i.e. are mandatory).

Each student can choose among a pool of courses individually with a given level of freedom. Consequently, each
course can be composed of a different group of students that might be unique for that course. Note that
in individual election systems it might also be the case that some proportion of the lessons are taken
class-based (i.e., core subjects like mathematics and history).

As will be shown later, it is also possible to have profile-based systems where students can choose additional
subjects outside of their profile (e.g. in the Netherlands). We consider theses systems to be halfway between a profile-based and a pure
individual election system.

Number of student elections (SE)
During their stay at school, students in modular systems will need to make
a number of elections for courses taught in a given class level (e.g. by filling some forms).
For example, if students are asked to select courses only in each of the last three years,
we define the number of student elections to be three.

Proportion of module-oriented class levels (ML)
This is the proportion of class levels offering either profile-based or individual course elections. For example,
if there are 5 class levels and 3 of them offer electable lessons, this proportion would be $3/5=0.6$ or 60%.

Number of terms per year (T)
The number of different periods of time characterized by different regular timetables. In systems where there is a
fall and a spring semester, the number of terms per year would be 2. In other systems (e.g. Finland) there might
be an arbitrary number of terms higher than 2.

Scheduling workflow (SW)
We identified two different scheduling workflows from the experts for creating timeables in modular systems.
Either the timetable is created first and students choose courses based on the known timetable
or students select courses based only on their preferences without knowing the timetable in advance.
In this last case, the timetable is created taking all student elections into consideration. We call the
first workflow the timetable-first and the second the election-first workflow.

Proportion of courses with class level overlap (CLO)
We say that a course shows class level overlap if students from different class levels are allowed to attend
the course (i.e., the course is electable for students in different class levels). For instance, a philosophy course
might be offered as electable for all students in the seventh and the eighth grade, which means that potentially
students from both levels can be taught that course simultaneously.

School course collaborations (SC)
In some systems, rare or unusual subjects requiring teachers with special qualifications might be offered
collectively by two or more schools to reduce costs and optimize attendance. In this case, guest students from
other schools are allowed to attend a course given in a specific host school.

Table <ref> presents a general overview of our category system. In addition to the
name of the category, the abbreviation, and a short description, the last column specifies which range of values
each category is allowed to take. For proportions, in general we divide the range of possible values in three
intervals low, medium and high that correspond each to one third of the $[0, 100]$ interval.
Cardinal values are positive integers. All the other categories take values in a definite set (e.g., "Yes/No"). In the
following, we review the secondary modular educational systems of Austria, Germany (for selected federal states),
Switzerland, Finland, Luxembourg and the Netherlands.

Category Name     Abbr.     Description     Values

Prop. electable periods     PEP     How many periods are     Low, medium,

electable?      high

Election systems     ES     Which framework is used for     Class, profile,

electable courses?      individual

No. student elections     SE     How often have students to     Low, medium,

select courses?      high

Module-oriented class levels     ML     How many class levels     Low-medium,

contain modular courses?      high

No. terms/year     T     How many different terms      Cardinal

take place in a school year?

Scheduling workflow     SW     How is the timetable      Timetable-first,

scheduled?     Election-first

Prop. courses with class     CLO     How many courses are mixed      Low, medium

overlap         among class levels?     high

School collaborations     SC     Are courses offered among       Yes/No

different schools?

Summary of the resulting categories.

§.§ Austria

In Austria, secondary education is distributed among different school types <cit.>. The type of high school
known as Gymnasium is the most relevant from the point of view of modular education. In general,
class levels are grouped into two cycles of four years each, the lower cycle (or Unterstufe, US) from the
first until the fouth grade and the upper cycle (or Oberstufe, OS) from the fifth until the eigth grade. From
the sixth until the eighth grade there is a minimum of four and a maximum of ten hours per week of
electives that can be offered by each school autonomously. Modular education is still under development in Austria.
One of the earliest forms of modularization in secondary education
was the MOST (modular uppper cycle), which has been tried individually at some schools since the late 2000s. This school
form was unified in what was called NOVI (new upper cycle with strengthened individualization), which is being tested at
the time of this writing in about 30 schools. This model is planned to evolve into the SOST (upper cycle in semester-based form), that
changes the modules' assessment from a yearly to a semester basis <cit.>.

In the NOVI, there are up to eleven elective modules that can be chosen without any pre-conditions. These eleven courses are
typically taught for two hours per week and distributed evenly
among the last two class levels in the OS (seventh and eight). That means that, in a typical week, students attend about 30 hours of
non-electives and 4 hours in modules. To facilitate scheduling, all non-electives are planned in the morning, the modules being taught
in the afternoon.

Category classification
Accoding to our category system, the proportion of electable periods can be considered to be on the lower end of the scale.
Using the typical scenario outlined before, this would amount to about one third of the total number of periods per week to be in
modules. The module election sytem is individual: there are no restrictions for students on which modules they are allowed to select.
The number of choices that a student has to make lies within the lower end of the scale (students only choose their subjects once
and this remains until the end of the upper cycle). In this system, only the last two class levels are module-oriented, i.e., from
the total of eight levels that would result in a total proportion of 25%. In a typical year, there are two semesters (fall/spring).
Regarding scheduling workflow, first the timetable is made, and after that the students can select their subjects based on the
already existing schedule. Class level overlaps are usual (students from the seventh and the eighth grade can be present) and
there are no school collaborations.

§.§ Finland

Finland has a long tradition in modular education at the upper secondary level (high school), comprising the last years levels where
students are generally between 16 and 18 years old.
High schools therefore normally encompass three years although some students have to take a fourth. All students participate in the elective
course system. Courses are not necessarily bound to class levels and therefore most courses can be elected by students in any of them.
We see around 75% elective courses in course election data, the others being mandatory.

Category classification
The choice system is individual, except for general class hours with a class teacher in one subject. The number of choices is as follows:
Students in the first two class levels choose between 30-40 courses, while students in the third and last year can select between 20-24 courses.
There are between 5-6 terms per year and courses can take place in any of them,
but there is also the possibility for students to take a certain exam so the corresponding course
has to take place in the corresponding term too.
Students first make their course choices, afterwards the timetable is created (election-first workflow).
Usually, the assignment of teachers to courses is not known at the time the student make their choices. School collaborations are
usual, especially in the context of a given municipality. High schools in the same municipality share courses that students of
other schools can attend. This results in a very high complexity when scheduling courses, since times for shared courses need
to be taken into account.

§.§ Germany

In Germany, the responsibility for the school system lies with the 16 federal states.
Consequently, significant differences between them exist.
As in Austria, secondary education is distributed among different school types.
Regarding modular education, school types which lead to the
general qualification for university entrance (Abitur) are the most relevant.
These are of the types Gymnasium, Oberschule, or Gesamtschule.
In particular in the two or three highest class levels (upper cycle)
electives can be chosen by students with a high degree of freedom.

In the following subsections,
we present the situations in specific federal states.
We conducted five interviews with seven experts for course timetabling.
These interviews cover schools in 10 of the 16 federal states of Germany:
Two experts for Baden-Württemberg, one expert for Bavaria,
three experts for Rhineland-Palatinate,
and one expert covering seven states
(Brandenburg, Bremen, Lower Saxony, Mecklenburg-Vorpommern, Saxony, Saxony-Anhalt, Thuringia)
at the same time.

§.§.§ Baden-Württemberg

In Baden-Württemberg, there are two different school types in secondary education.
One is the Allgemeinbildendes Gymnasium which has an elective system
that allows many individual electives for students.
The other is the Berufliches Gymnasium where
more periods per week (about 12 to 14) take place within a class context
and a profile based election system is used.
In both school types, a course-based system is used in the final two year levels.
In Baden-Württemberg, there are either 12 or 13 years levels for each student since primary school.
So, depending on this, the course-based system is used
in year levels eleven and twelve, or twelve and thirteen.

Category classification
As Allgemeinbildende Gymnasien (AGY) and Berufliche Gymnasien (BGY)
are quite different, we classify them in separate categories.
The proportion of electable periods is medium (BGY) or high (AGY).
All periods take place in modules (AGY) or roughly half of the periods (BGY).
The module election sytem is individual (AGY) or profile based (BGY).
The remaining category classification is identical for both school types.
Students make their choices once, right before they enter the class levels of the upper cycle.
So, the number of elections is low.
In this system, only the last two class levels are module-oriented, i.e.,
from the total of eight (or nine) levels that would result in a total proportion of 25% (low).
Timetables can be different in each term (half-year).
An election-first scheduling workflow is used.
Students first make their course choices, after that the timetable is created.
The assignment of teachers to courses is not known at the time the student make their choices.
Class level overlaps can be planned for lessons which are chosen by only few students.
This happens rarely (low).
For the same reason, some schools in this state do collaborate to offer common courses.

§.§.§ Bavaria

In the federal state of Bavaria, modular education is mainly present at two school types: the
Fachoberschule (FOS) and the Berufsoberschule (BOS). The main difference lies in the
practical orientation: while the FOS can be attended by all students with a middle school diploma,
the BOS is intended for students with some professional experience that aim at deepening their
training in that area <cit.>.
Both types of schools lead to the general qualification for university entrance. The FOS comprises
three class levels (11, 12 and 13), while the BOS encompasses only two (12 and 13). Students choose
electives in the eleventh class level, having more choices in the BOS than the FOS. In general,
besides general subjects like math, history and ethics, students can choose one out of seven different
profiles, each with their own profile subjects (e.g. environmental sciences, health sciences,
technical subjects, etc.). Furthermore, and based on the chosen profile, students can choose up to two
additional elective courses that aim at deepening the knowledge of the student in a particular direction
(for instance, diverse language courses, biotechnology, arts and music, etc.). In total, around 20 hours
per week are dedicated to general subjects, 10 for profile subjects and 4 hours for freely electable

Category classification
The proportion of electable periods can be considered medium (about 50% of the time is spent in
either profile or electable courses). Therefore, the module election system is a mixture of profile-based and
individual system. Students typically choose once their profile and electives (in the eleventh class level in the FOS or during
their practical training in the BOS), and these elections remain constant until their graduation. All class
levels except the eleventh (FOS) are modular, and there are in general no distinction between semesters.
The scheduling workflow is election-first: students choose their profiles and electives first, and then the
timetable is made with the goal of fulfilling all the student elections. Class level overlaps are possible,
and in general there are no school collaborations.

§.§.§ Rhineland-Palatinate

Modular education in Rhineland-Palatinate is mainly applied in the last three years of the Gymnasium,
which can be either the 10th, 11th and 12th grades in 8-year schools (G8), or the 11th, 12th and 13th grade
in 9-year schools (G9). Across all class levels, students take between 32 and 35 hours per week of courses,
which are divided into basic courses (which are taught for 3 hours per week) and advanced level courses
(which are taught 4 or 5 hours per week). In general, a student will choose 3 advanced courses,
the rest being basic courses on subjects not considered central regarding the profile of the student or the
school itself. In practice, resources are bundled together in some cases by defining advanced courses as
basic courses with additional hours where more advanced material is taught.

The course election process is normally coordinated by a single person, whereas another person is in charge
of scheduling the courses in the timetable. On each year, students are asked to elect courses until March, and
then groups of courses that can be scheduled together are clustered. Later on, the timetable is made
according to those clusters. If possible without creating any disadvantage for other students, elected courses can be
changed until the next autumm.

Category classification
The Gymnasium upper cycle in Rhineland-Palatinate can be considered as a medium-level modular system based
on individual student elections. The core of this system is given by the election of the
advanced courses. Since those courses are taught for either 4 or 5 hours per week, that results in between 12 and
20 hours per week spent on advanced courses, which roughtly amounts to half the weekly lesson load for a typical student.
Only class levels in the upper cycle are modular, resulting in about 1/3 of modular class levels in the Gymnasium,
and also here there is no distinction between semesters. The
scheduling process here is, as typical in Germany, also election-first. Class level overlaps are usual, and
some schools may collaborate with others by bundling educational resources.

§.§.§ Brandenburg, Bremen, Lower Saxony, Mecklenburg-Vorpommern, Saxony, Saxony-Anhalt, Thuringia

Given that one of our interview partners is an expert on the educational systems of these federal states, and since
these are quite similar, we proceed to report on all of them in this section. In general, we can distinguish between
profile-based (e.g. in Bremen) and individual-election systems (e.g. Lower Saxony). In the former case, a high portion of the courses
students attend are fixed by their profiles, whereas in the latter, students choose their courses individually.
Depending on the specific federal state, the Gymnasium is divided into 9 class leves (G9), mostly in Bremen and
Lower Saxony, or 8 levels in the rest (G8). Similarly as in Rhineland-Palatinate, only typically the last three levels
are modular. While in the 11th grade a typical student spents about half of their time in modular courses, the 12th
and the 13th grade (where appropriate) is completely modular, so students are allowed to elect all of their courses. Typically,
students will choose in the 11th class their courses, and once again in the 12th.

Category classification
In this case, we can regard these federal states as having highly modular educational systems, since the average amount
of hours spent on modular courses by the average student is clearly higher than 50%. There is a mixture of profile-based and
individual election systems, although individual systems are more common. Like in Rhineland-Palatinate, about a third of all
class levels in the Gymnasium can be regarded as modular. The
scheduling process is election-first, with frequent class-level overlaps and the possibility of school collaborations (mostly
when these schools are located in the same city).

§.§ Luxembourg

The secondary school system in Luxembourg starts with 12 year old students and is divided into the following variations: classical seconday education (ESC),
general secondary education (ESG), European education, International English curriculum, British education and
German-Luxembourgish education. The high school education cycle in all cases always comprises
seven class levels <cit.>. Since both interviewees E9 and E10
work at European schools, we will focus on this variant in the following discussion. In the European system,
the 7-year cycle (S1-S7) is itself subdivided into three sub-cycles S1-S3, S4-S5 and S6-S7. In general,
the degree of modularity increases with each sub-cycle. As part of the individual educational approach of each
school (school autonomy), schools may introduce additional subjects or classes tailored to the particular approach
of that school.

Category classification

The proportion of electable periods starts in the first sub-cycle S1-S3 with approximately 30% of periods
in modular courses (including language courses) and increases to 50% in S4-S5 until about 90% in the last two years. The election system
used is based on individual choices (no profiles are given). Students make course selections a total
of three times, one per sub-cycle. All seven class levels of the secondary education system can be considered
as modular, therefore the proportion of modular class level is highest. There is no special distinction between
different terms in the course of a regular school year. The scheduling workflow used is a election-first type of
workflow were students select their courses first, and then the timetable is scheduled according to the students
choices. In general, students from different sections and class levels can be mixed into individual courses,
like languages and natural sciences. School collaborations are not usual, since some schools are already
divided into different sites and this would overly complicate the scheduling process.

§.§ Netherlands

The secondary education system in the Netherlands is divided into pre-vocational (VMBO), pre-university (VWO) and senior general
secondary education (HAVO) <cit.>. The VMBO is profile-oriented.
Once students choose a profile (an occupational sector), a predefined set of
courses is automatically assigned. In general, students need to attend between 3 and 4 mandatory courses that make up a total
of about 15 hours peer week for a typical student. In the HAVO and the VWO, students attend a pre-defined curriculum for the first
three years. In the upper cycle, this common part of the curriculum gets reduced to core subjects like Dutch, English and
social studies. Students then choose one among four different profiles (technology, health, economics and culture). However, students
are allowed to choose up to two additional subjects related to the profile, and one additional elective, which might be
unrelated to the profile. Regarding the timetable, schools try to assign students to courses so that the students stay most
of the time in the same group, and avoid mixing students from different class levels (which is usual in other countries like
in Germany). On the one side, this facilitates scheduling the different courses to a high degree, and
on the other side helps students keep their social bonds during the time they spend in secondary school.

Category classification
The degree of modularity of the different secondary education branches is slightly different for VMBO, VWO and HAVO, but in
general one can consider the system to be medium modular. In all types of secondary education there are core subjects and optional
subjects, which are always pre-determined by the choice of a profile. Therefore, secondary education in the Netherlands can be
regarded as profile-based. The number of choices that the pupils make is either only once (in fully profile-based variants
like VMBO) or up to twice (like in the VWO). All class levels contain electives to some degree, and in general there is no
distinction between fall and spring semesters. The schedule is made in an election-first manner, and if possible no students from
different class levels are mixed in individual courses. School collaborations are not usual, since secondary schools in the
Netherlands tend to be already quite large.

§.§ Switzerland

For Switzerland, we conducted two interviews: one for the French-speaking cantons, and one for the German-speaking cantons.
We present the results in separate sections, as there are considerable differences between both approaches.

§.§.§ German-speaking cantons

In the German-speaking cantons of Switzerland,
modular education is mainly present at community schools (Gemeindeschulen).
Most of the schools in these cantons are of this type,
overall the number of such schools is around 1000.
Although Gymnasiums also exist in these cantons, they almost don't offer any modular education,
therfore we don't consider them further in this paper. In the community schools, and
all schools that implement the compulsory part of the education system,
modular education is concerned basically with the last class level (that is the third
level of the lower secondary cycle). However, there is no general obligation for schools
to offer elective courses <cit.>.
When they do, choices are made by students in spring before the timetabling takes place in summer.
Students choose specific courses without specifying alternatives.
In general, there is no collaboration between schools to offer shared courses.
For the timetablers, it is very important that idle periods
are avoided for students in their timetables.

Category classification
The proportion of electable periods is highly variable, but in general, the system can be considered to be of
low modularity.
The module election sytem is individual.
In general, students choose only once (at the last year of their compulsory education).
The proportion of module-oriented class levels is therefore in general limited to one class level out of nine.
Timetables can be different in each term (half-year).
An election-first scheduling workflow is used.
Since in general only one class level is involved, there is no class level overlap in the elective courses.
As mentioned above, in general there are no school collaborations for shared courses.

§.§.§ French-speaking cantons

There are in total eight French-speaking cantons in Switzerland. In general, secondary education is divided into a
lower and an upper cycle. The lower cycle is common for all of Switzerland, and lets students
choose among three predefined profiles. However, the upper cycle (which involves students
of ages between 15 and 19 years) can be tailored to specific cantons reflecting the diversity of approaches. In our interview,
we focused on the Geneva, Fribourg, and Jura cantons as they stands out for their high degree of modularization. Before entering the upper cycle,
students are asked to select a basic set of courses, including two languages and a main optional subject
(students can specify alternatives in case the elected course is full or not available for some other reason). Students might
also request to attend a course at another school, which in general is possible if they stay in the same canton. The mandatory
subjects (French, geography, history and mathematics) account for about 30% of the total lesson time for a typical student.
Students are asked to choose again courses in their third year (in the upper cycle), but the scope of this electives is much
more reduced than in the first election. Scheduling is done by first finding a good placement for all the courses and then assigning
the students to courses.

Category classification
We can consider the upper secondary education system in the above mentioned cantons to be modular
to a high degree (i.e. about 70% of the lesson time for a student is spent in elective courses). Students choose subjects twice during
the upper cycle, once at the very beginning and once again in the third year. While students are mostly free to choose their subjects,
it results in practice into a large number of profiles (i.e. possible combinations of electives). However, our interview partner
confirmed that from about 250 students, the number of resulting profiles can be as high as 200 or above. Therefore, for the purpose
of this study we consider this system to be individually oriented, rather than profile-oriented. The proportion of modular class levels
is 100%, since both the lower and the upper cycle are designed in a modular way. There is no distinction between terms and the
scheduling workflow is timetable-first (seemingly for historical reasons). Students from different class levels can be mixed in
principle, and collaborations between schools are possible (e.g. a student attending courses in another school of the same

§ DISCUSSION

As can be seen in the interviews, the approaches to modular secondary education are very heterogeneous. However,
some common aspects can be identified. For example, all of the aforementioned educational systems use modular education as
a means of fostering individualization in students curricula. On the one side, individually-oriented election systems
(like Germany or Finland) give more weight to students to follow their interest and deepen their understanding of core
subjects. These electives might be relevant in their career after leaving secondary education, but professional usefulness alone does not provide
the main rationale for the system. On the other side, profile-based systems (like in the Netherlands) are more usually focused on vocational
education, and profiles are crafted in such a way that students learn to know which professions might be relevant
in their professional life. In between, there are many different approaches to modular education as represented for
instance in the case of Austria. In Germany, there are plans to harmonize the modular education system in the
Gymnasium upper cycle to focus more on the advanced courses (as interview partner E7 mentioned) rather than basic courses,
stressing the focus of the system as enabler to deepen students' understanding of core subjects. How successful these plans
turn out to be depends on future developments. As can also be seen in the case of Switzerland, countries with a highly federal
structure tend to fragment their educational systems, making harmonization difficult in the long run.

Figure <ref> shows graphically the results of the classification of all educational systems investigated
in this work. For this purpose we use radar charts, which depict the different categories as axes where
higher values (i.e. modularity-increasing) are represented as points with higher distance from the center.
For example, the higher the modularity regarding the PEP (proportion of electable periods, see Table <ref>)
parameter, the higher the distance to the center of each chart. The resulting shape (delineated using
red lines) represents geometrically the degree of modularity of each educational system taking all
the parameters into account. Ideally, the larger this shape, the more modular that particular educational
system is according to our categories. Note that we use a minimum of one unit for each axis to improve
readability. According to this representation, the most modular educational system
is definitely Finland (Figure <ref>), followed by French-speaking Switzerland in Figure <ref>
(particularly, the Geneva canton), with Lower Saxony and related German federal states (Figure <ref>), Bremen (Figure <ref>)
and Rhineland-Palatinate (Figure <ref>) thereafter. Finland scores the maximum scores in all
categories investigated.
In general, highly-modular sytems have in common a high degree of electable periods
(medium in case of Rhineland-Palatinate) and individually-oriented election systems, with frequent class-level
overlaps. Interestingly, they also share a election-first approach to scheduling. Other systems like Austria
(Figure <ref>) follow a more conservative approach with previously determined slots in the timetable
for electives and a smaller proportion of electable courses. It can also be remarked that during our
interview, expert E1 mentioned not believing that a election-first approach could be feasible, given the
sheer amount of different possibilities to consider. However, such an approach has been practiced successfully since
at least the 90s in other parts of Europe, notably in Germany. We therefore need to stress here the important role
of automated timetabling tools in delivering support for complex modular educational systems. It is also
important for experts to know what automated timetabling tools can do in this area.

Visual comparison using radar charts from the educational systems studied in this paper.

§.§ Consequences for scheduling

The interviews show that there are various challenges when trying to create a schedule that satisfies all the needs of students,
teachers and schools. The central problem shared by all modular educational systems studied is how to assign courses to students
in such a way that students can attend all the courses they have elected. For instance, there might not be enough teachers for
courses where too many students registered, or courses might need to be canceled when not enough students decide to enroll. In these
cases, it will be necessary to relocate students to other courses. Additionally, course occupation needs to be balanced as well. E.g.
if there are two advanced math courses that are equivalent (i.e. parallel courses), it should be avoided that the number
of students that attend each course is very different.

Another aspect that came up frequently in the interviews was the necessity to minimize the number of
idle periods for students (and, secondarily, for teachers as well). In class-based systems, since students attend lessons
together, the timetabler can easily ensure that core times are always assigned a lesson, resulting in no idle times
for the entire class. However, this can be significantly more challenging in modular systems, since every student has their own timetable.
As a result, some timetablers (mainly in Germany) use a two-step method for building the schedule: First, they cluster courses
in such a way that these courses can be scheduled simultaneously (no teacher or student clashes). Second, they maximize the amount
of students in every cluster, which means that when a cluster is scheduled in a given time slot, no student will have idle time then.
If these clusters can completely fill a set of core time slots, it can be guaranteed that no idle periods are produced. However,
this task can be extremely challenging and automated tools are needed. In some systems (e.g. the Netherlands), timetablers try to
avoid class level overlaps to make this problem easier to solve to some extent. Even then, it might be impossible to avoid idle times at all.
How difficult these problems turn out to be is largely determined by the PEP (proportion of electable periods) and ES (election system)
categories in our framework. In general, the higher the PEP, the more possibilities need to be considered when building the timetable.
The more individualized an election system, the more difficult it is to take all student choices into consideration.

Lastly, the room situation and teacher availability needs to be considered as well. If too many courses are scheduled at the
same time that need the same type of room (e.g. chemistry lab, projectors, etc), the timetable might be unfeasible.
Similarly, teachers working at more
than one school need to be considered separately since they might not be available at certain days or times. Modular systems with
school collaborations face this type of problem when building timetables (e.g. in Finland).

In general, the higher the modularity as holistically estimated by our framework, the more
difficult building a timetable becomes. The problem of creating a timetable that satisfies a given set of requirements is not new and has been studied for more than 50 years <cit.>.
Throughout the years the problem of educational timetabling has evolved into three subproblems that are often treated as independent: High school timetabling, course timetabling and examination timetabling <cit.>.

In high school timetabling the focus lies in creating a weekly schedule for the various lessons of classes in a way that gives both students and teachers a compact schedule according to their availabilites while also paying attention to room assignments and other organizational constraints.

Course timetabling centers around the assignment of students to classes that are then scheduled in a timetable where each week of the term is scheduled individually.
Again many different organizational constraints like assigning rooms and paying attention to the availabilities of teachers apply but the main focus lies in scheduling the lessons in a way such that every student can attend their desired courses.
This makes it a good fit for creating schedules for universities.

Finally, in examination timetabling the goal is to assign exams to examination periods in a way that every student can take the exams they signed up for.
This problem differs from the others since examinations are usually singular events without patterns that extend over several weeks or months.
However, many of the constraints from other educational timetabling problems, like room requirements and distributing events, still apply.

From the interviews we have conducted, we can conclude that none of the three mentioned categories completely
cover the requirements for the regions in which we investigated.
For instance, course timetabling focuses on the assignment of students to classes, usually not considering other aspects like
compactness or pedagogical considerations like scheduling lesson in double periods. Both student assignments and pedagogical
considerations are relevant in all educational systems studied.
The problem definition seems to lie somewhere between high school timetabling and course timetabling.
However, combining those two disciplines is no easy task since each on its own already is difficult enough to inspire decades of research that still results in non-optimal schedules.
Nevertheless, we want to move the research in a direction that focuses on more modern school systems with modular course choices for students.
To achieve this, this study represents the first step in a series of papers where we will propose new techniques for improving automatic scheduling software.
We hope that developing such automatic timetabling software that supports the requirements outlined in this paper will make it easier for schools to transition to modular education
which in turn will give students many more opportunities to follow their interests and prepare for their future careers through individualized choices.

§ CONCLUSION

In this paper, we presented a selection of modular educational systems in Europe and a novel category system for classifying
them according to a well-defined set of characteristics. To the best of our knowledge, this is the first effort of this kind
in the literature to date. This study lays the groundwork for analyizing the needs and requirements of timetabling in different
regions when modular courses are present, paving the way for a detailed investigation into how to automate this requirements
to build specially tailored tools that support realizing the promise of modular education in a way that improves its quality
for all stakeholders involved, including students, teachers, school administration and policy makers.

For this investigation, we had access to interview partners covering a wide range of educational systems. However, the studied regions
by far don't cover the whole of secondary education in Europe. We expect the selection presented in this paper to be representative
of the main trends in modern modular education, but prominent examples (like the United Kingdom) are missing. We plan to fill this gap
in future work.

Additionally, automatic timetabling methods that comply with the requirements investigated in this paper will be developed to
support educational systems across Europe to provide and extend modular education at the secondary level.

§ ACKNOWLEDGEMENTS

The authors acknowledge financial support from the Agency for Research Promotion of Lower Austria (GFF) under Project
Course scheduling in modular educational systems.