# Smoothed Online Learning for Prediction in Piecewise Affine Systems

Adam Block<EMAIL_ADDRESS>
MIT  Max<EMAIL_ADDRESS>
MIT  Russ<EMAIL_ADDRESS>
MIT

###### Abstract

The problem of piecewise affine (PWA) regression and planning is of
foundational importance to the study of online learning, control, and
robotics, where it provides a theoretically and empirically tractable setting
to study systems undergoing sharp changes in the dynamics. Unfortunately, due
to the discontinuities that arise when crossing into different “pieces,”
learning in general sequential settings is impossible and practical algorithms
are forced to resort to heuristic approaches. This paper builds on the
recently developed _smoothed online learning_ framework and provides the first
algorithms for prediction and simulation in PWA systems whose regret is
polynomial in all relevant problem parameters under a weak smoothness
assumption; moreover, our algorithms are efficient in the number of calls to
an optimization oracle. We further apply our results to the problems of one-
step prediction and multi-step simulation regret in piecewise affine dynamical
systems, where the learner is tasked with simulating trajectories and regret
is measured in terms of the Wasserstein distance between simulated and true
data. Along the way, we develop several technical tools of more general
interest.

###### Contents

  1. 1 Introduction
    1. 1.1 Related Work
  2. 2 Setting
  3. 3 Results
    1. 3.1 Regret for One-Step Prediction in PWA Systems
    2. 3.2 Guarantees for Simulation Regret
  4. 4 Analysis
    1. 4.1 Parameter Recovery
    2. 4.2 Mode Prediction
  5. 5 Discussion
  6. I General Tools
    1. A Notation
    2. B Lower Bounds
      1. B.1 Proof of Proposition 1
      2. B.2 A Lower Bound for Identification
    3. C Properties of Smoothness
      1. C.1 Directional Smoothness of Gaussians and Uniform Distributions
      2. C.2 Directional Smoothness Equivalent to Lebesgue Density
      3. C.3 Concatenation Preserves Directional Smoothness
      4. C.4 Smoothness of Parameters Induces Separation
  7. II Supporting Proofs
    1. D Parameter Recovery
      1. D.1 Disagreement Covers
      2. D.2 Lower Bounding the Covariance
      3. D.3 Small Ball Inequality
      4. D.4 Upper Bounding the Empirical Error
      5. D.5 Proof of Theorem 12
    2. E Modifying the Classifier and Mode Prediction
      1. E.1 Look-ahead Classification Error
      2. E.2 Bounding Permutation Disagreement and $\mathrm{Term}_{1}$
    3. F Proving Theorem 3
    4. G Application to PWA Dynamical Systems
      1. G.1 Proof of Lemma 3.1
      2. G.2 Formal Simulation Regret Setup
      3. G.3 Algorithm Modifications
      4. G.4 Formal Guarantees for Simulation Regret
      5. G.5 Extensions

###  1 Introduction

A central problem in the fields of online learning, control, and robotics is
how to efficiently plan through piecewise-affine (PWA) systems. Such systems
are described by a finite set of disjoint regions in state-space, within which
the dynamics are affine. In this paper, we consider the related problem of
learning to make predictions in PWA systems when the dynamics are unknown.
While recent years have seen considerable progress around our understanding of
linear control systems, the vast majority of dynamics encountered in practical
settings involve nonlinearities. Learning and predicting in nonlinear systems
is typically far more challenging because, unlike their linear counterparts,
the dynamics in a local region of a nonlinear system do not determine its
global dynamics.

PWA systems allow for discontinuities across the separate regions (“pieces”),
and are thus a simplified way of modeling rich phenomena that arise in
numerous robotic manipulation and locomotion tasks (Mason, 2001; Van Der
Schaft and Schumacher, 2007; Marcucci and Tedrake, 2019), with one example
among many being the modeling of dynamics involving contact. In addition, deep
neural networks with ReLU activation (Goodfellow et al., 2016) are PWA
systems, providing further motiviation for their study. Already, there is a
computational challenge simply in optimizing an objective over these systems,
which is the subject of much of the previous literature. Here, we take a
statistical perspective, assuming that we have access to effective heuristic
algorithms for this optimization task. Uniformly accurate learning of the
dynamics across all pieces may be impossible because some regions of space may
require onerous exploration to locate (see Proposition 10); thus, we instead
consider an iterative prediction setting, where at times $t=1,2,\dots,T$, the
learner predicts the subsequent system state. From this, we extend to
prediction of entire trajectories: over episodes $t=1,\dots,T$, a learner
suggests a policy $\pi_{t}$, and the learner attempts to learn the dynamics so
as to minimize prediction error along the trajectory $\pi_{\tau}$ induces.
This is motivated by iterative learning control, where our notion of error is
an upper bound on the discrepancy between the planner’s estimate of policy
performance and the ground truth.

Our iterative formulation of the learning problem is equivalent to the regret
metric favored by the online learning community, and which has seen
application to online/adaptive control and filtering problems in recent work.
Importantly, our sense of regret does not require uniform identification of
system parameters, as we observe that it may actually be impossible in certain
settings. The key pathology here is that policies can oscillate across the
boundary of two regions, accruing significant prediction error due to sharp
discontinuities of the dynamics between said regions, a problem well-known to
the online learning community (Littlestone, 1988). Moreover, this pathology is
not merely a theoretical artifact: discontinuities and non-smoothness pose
significant challenges to planning and modeling contact-rich dynamics such as
those encountered in robotic manipulation (Suh et al., 2022a, b; Posa et al.,
2014).

Our solution takes inspiration from, and establishes a connection between, two
rather different fields. Recent work in the robotics and control communities
has relied on _randomized smoothing_ to improve planning across discontinuous
and non-smooth dynamics (Suh et al., 2022a, b; Lidec et al., 2022; Pang et
al., 2022). Additionally, in recent years, the online learning community has
studied the _smoothed online learning setting_ (Rakhlin et al., 2011;
Haghtalab et al., 2021, 2022; Block et al., 2022; Block and Simchowitz, 2022),
which circumvents the threshold-effect pathologies like the one described
above. We show that, if the dynamics and the control inputs are subject to
randomized smoothing, it is indeed possible to achieve low regret. More
importantly, our proposed no-regret algorithm is _efficient_ in terms of the
number of calls to an optimization oracle, a popular notion of computational
efficiency in the online learning community (Hazan and Koren, 2016; Kalai and
Vempala, 2005; Block et al., 2022; Haghtalab et al., 2022). In our setting,
the optimization oracle required finds the _best-fit_ PWA system to a batch of
given data. Though this problem is, in general, computationally infeasible
(Amaldi and Mattavelli, 2002), there is a rich literature of popular
heuristics (Garulli et al., 2012; Paoletti et al., 2007; Ferrari-Trecate et
al., 2003). Unlike those works, this paper examines the _statistical
challenges_ of generalization to novel data given such an algorithm. We note
that the randomized smoothing approach is, in some sense, canonical in
mitigating the aforementioned pathology of policies that oscillate across the
boundaries of two regions; smoothing prohibits precisely this pathology by
ensuring that the system state is mostly far from these boundaries.

##### Contributions.

A formal description of our setting is deferred to Section 2. Informally, we
consider the problem of prediction in a PWA system over a horizon of $T$
steps, where the regions are determined by intersections of halfspaces; we
obtain prediction in PWA dynamical systems as a special case. We aim to
achieve sublinear-in-$T$ excess square-loss error (_regret_) of
$O\left(T^{1-\alpha}\right)$ with respect to the optimal predictor which knows
the system dynamics, where $\alpha>0$ is constant and the prefactor on the
regret is at most polynomial in all of the problem parameters. Our result is
derived from a general guarantee for online piecewise affine regression, which
subsumes the online PWA identification setting. We show that, when the
dynamics and the control inputs are subject to randomized smoothing satisfying
the $\sigma_{\mathrm{dir}}$-directional smoothness condition introduced by
Block and Simchowitz (2022), our regret bound is polynomial in
$\sigma_{\mathrm{dir}}$, dimension, and other natural problem parameters. We
emphasize that we have made no effort to optimize either the polynomial
dependence on the parameters or the exponent on the horizon; the goal of this
work is to demonstrate that smoothness allows for oracle-efficient algorithms
that achieve this polynomial dependence in the difficult setting of PWA
systems. We further note that if we care only about low regret without regard
to oracle efficiency, a simple discretization scheme coupled with a standard
learning from experts algorithm (Cesa-Bianchi and Lugosi, 2006) can achieve
low-regret; because we wish for an oracle-efficient algorithm, the problem is
significantly more challenging.

As a further application, we adapt our algorithm to make predictions, at each
time $t$, of the trajectory comprising the next $H$ steps in the evolution of
the dynamical system. We bound the _simulation regret_ , the cumulative error
in Wasserstein distance between the distribution of our proposed trajectory
and that of the actual trajectory. Assuming a Lyapunov condition, we
demonstrate that our modified algorithm achieves simulation regret
$O\left(\mathsf{poly}(H)\cdot T^{1-\alpha}\right)$, which allows for efficient
simulation.

##### Key challenges.

As noted above, vanishing regret in our setting is impossible without
directional smoothness due to discontinuity in the regressors between
different regions. The key challenge is to leverage smoothness to mitigate the
effect of these discontinuties. Note that, if the learner were to observe the
region in addition to the state, regression would be easy by decomposing the
problem into $K$ separate affine regression instances; the difficulty is in
minimicking this approach _without explicit labels indicating which points are
in which regions._ As described below, we adopt a natural, epoch-based
approach by calling the optimization oracle between epochs, estimating the
underlying system, and using this estimate to assign points to regions in the
subsequent epoch. This introduces three new challenges. First, we need to
control the performance of our oracle on the regression task, which we term
_parameter recovery_ below. Second, we must enforce consistency between
regions learned in different epochs, so that we can predict the correct
regions for subsequent covariates; doing this necessitates an intricate
analysis of how the estimated parameters evolve between epochs. Finally, we
need to modify the output of our oracle to enforce low regret with respect to
the classification problem of correctly predicting which mode we are in on as
yet unseen data. Each of these challenges requires substantial technical
effort to overcome, as summarized below.

##### Our techniques.

Our algorithm proceeds in epochs, at the end of each of which we compute a
best-fitting piecewise affine approximation to available data by calling the
Empirical Risk Minimization (ERM) oracle (defined in Assumption 1). The
analysis of this best-fit shows that we recover the parameters and decision
boundaries of the associated regions (“pieces”) frequently visited during that
epoch. By the pigeonhole principle, this ultimately covers all regions visited
at a non-neglible number of times $t$ over the horizon $T$. Here, we leverage
a careful analysis based on two modern martingale-least squares techniques:
the self-normalized concentration bound (Abbasi-Yadkori et al., 2011) for
establishing recovery in a norm induced by within-region empirical covariance
matrices, and the block-martingale small-ball method (Simchowitz et al., 2018)
to lower-bound the smallest eigenvalues of empirical covariances with high
probability. In addition, we introduce and bound a new complexity parameter,
the _disagreement cover_ , in order to make our statements uniform over the
set of possible decision boundaries.

After the estimation phase, each epoch uses this estimate to make predictions
on new data as it arrives. The key challenge is classifying the region to
which each newly observed data point belongs. Without smoothing, this can be
particularly treacherous, as points on or near to the boundary of regions can
be easily be misclassified, and the correct predictions are discontinous. To
leverage smoothing, we propose a reduction to online convex optimization on
the hinge loss with lazy updates and show, through a careful decomposition of
the loss, that our classification error can be controlled in terms of the
assumed directional smoothness. Combining this bound on the classification
error with the parameter recovery described in the preceding paragraph yields
our sublinear regret guarantee.

We instantiate one-step prediction as a special case of the more general
online linear regression problem, showing that the approach described above
immediately applies to the first problem under consideration. Finally, in
order to simulate trajectories, we use the learned parameters in the epoch to
predict the next $H$ steps of the evolution. We then use the fact that our
main algorithm recovers the parameters defining the PWA system to show that
simulation regret is bounded, which solves the second main problem and allows
for simulation in such systems.

####  1.1 Related Work

##### System Identification.

System-identification refers to the estimation of the governing equations of a
dynamical system. The special case of linear dynamical systems has been
studied for decades (Ljung, 1999; Ljung and Wahlberg, 1992; Deistler et al.,
1995), and more recent work has provided finite-sample statistical analyses in
various regimes of interest (Simchowitz et al., 2018; Dean et al., 2020; Oymak
and Ozay, 2019; Tsiamis and Pappas, 2019; Tsiamis et al., 2022). Estimation
for non-linear systems has proven more challenging, and has been studied most
in the setting where the dynamics involve a known and smooth nonlinearity
(Mania et al., 2020; Sattar and Oymak, 2022; Foster et al., 2020), or where
only the observation model is nonlinear (Dean and Recht, 2021; Mhammedi et
al., 2020). Sattar et al. (2021) study _Markov jump systems_ , where the
system dynamics alternate between one of a finite number of linear systems
(“modes”), and switches between modes are governed by a (discrete) Markov
chain. PWA systems are thus an attractive intermediate step between the too
simple linear setting and the intractably complex general case. To our
knowledge, we are the first work to tackle piecewise affine dynamics in full
generality, where the system mode is determined by the system state.

##### Heuristics for PWA System Identification.

Despite its worst-case computational intractability (Amaldi and Mattavelli,
2002), there is a rich literature of heuristic algorithms for computing the
best-fit PWA system to data; see the surveys Garulli et al. (2012) and
Paoletti et al. (2007), which compare various approaches, notably the
clustering method due to Ferrari-Trecate et al. (2003). These references focus
strictly on the _algorithmic_ facets of computing a best-fit given an existing
data set. We instead abstract the computation of a best-fit into an ERM oracle
in order to focus on the _statistical_ considerations.

##### Online Learning and Smoothing.

The study of online learning is now classical, with a small sample of early
works including Littlestone (1988); Freund and Schapire (1999b, a). More
recently, a general theory of online learning matching that which we have in
the statistical learning setting was built up in Rakhlin et al. (2011);
Rakhlin and Sridharan (2013); Rakhlin et al. (2015); Block et al. (2021), with
Rakhlin and Sridharan (2014) characterizing the minimax regret of online
regression. Due to the robustness and generality of this adversarial model,
many problems that are trivial to learn in the statistical setting become
impossible in the adversarial regime. Thus, some work (Rakhlin et al., 2011;
Haghtalab et al., 2021, 2022; Block et al., 2022) has sought to constrain the
adversary to be _smooth_ , in the sense that the adversary is unable to
concentrate its actions on worst-case points. Of these, most relevant to the
current work is Block and Simchowitz (2022), which introduces the notion of
directional smoothness to control the regret in a realizable, online
classification problem.

##### Online Learning for Control.

In addition to the recent advances in finite-sample system identification, a
vast body of work has studied control tasks from the perspective of regret
[see, e.g. Abbasi-Yadkori and Szepesvári (2011); Agarwal et al. (2019);
Simchowitz et al. (2020); Simchowitz and Foster (2020); Cohen et al. (2018)].
While we do not consider a control objective in this work, we share with these
works the performance metric of regret. Our work is more similar in spirit to
online prediction in control settings (Hazan et al., 2017; Tsiamis et al.,
2020), in that we also consider the task of next-step predictions under a
system subject to control inputs.

##### Smoothing in RL and Control.

One interpretation of the online smooth learning setting is that well-
conditioned random noise is injected into the adversary’s decisions. Thus,
one’s predictions (or in the control setting, estimates) converge attain zero
regret under these noise-smoothed dynamics. It is well known that such noise
injection can be viewed as a form of regularization (Duchi et al., 2012), and
recent recent work in the robotics literature has shown that randomized
smoothing improves the landscape in various robotic planning and control tasks
(Suh et al., 2022a, b; Lidec et al., 2022; Pang et al., 2022). More broadly,
randomization has been popular for computation of zeroth-order estimates of
gradients, notably via the acclaimed policy-gradient computation Williams
(1992).

###  2 Setting

In this section, we formally describe the problem setting of online PWA
regression. We suppose there is a ground truth classifier
$g_{\star}:\mathbb{R}^{d}\to[K]$ and matrices
$\left\\{\mathbf{\Theta}^{\star}_{i}\mid i\in[K]\text{ and
}\mathbf{\Theta}^{\star}_{i}\in\mathbb{R}^{m\times(d+1)}\right\\}$ such that

$\displaystyle\mathbf{y}_{t}=\mathbf{\Theta}^{\star}_{i_{t}}\cdot\bar{\mathbf{x}}_{t}+\mathbf{e}_{t}+\bm{\delta}_{t},\quad
i_{t}=g^{\star}(\bar{\mathbf{x}}_{t}),\quad\bar{\mathbf{x}}_{t}=[\mathbf{x}_{t}^{\top}|1]^{\top},\quad\left|\left|\bm{\delta}_{t}\right|\right|\leq\varepsilon_{\mathrm{crp}},$
(2.1)

where $\mathbf{x}_{t}\in\mathbb{R}^{d}$ are covariates,
$\mathbf{y}_{t}\in\mathbb{R}^{m}$ are responses,
$\mathbf{e}_{t}\in\mathbb{R}^{m}$ are zero-mean noise vectors in
$\mathbb{R}^{m}$, $\bm{\delta}_{t}$ are (small) non-stochastic corruptions
with norm at most $\varepsilon_{\mathrm{crp}}\ll 1$, and $i_{t}\in[K]$ are the
regression modes, which depend on the covariates $\mathbf{x}_{t}$. The
extension to $\bar{\mathbf{x}}_{t}$ accomodates affine regressors. We suppose
that the learner has access to pairs $(\mathbf{x}_{t},\mathbf{y}_{t})$ but,
critically, does not know the regression modes $i_{t}$. We do however suppose
that $g_{\star}$ is an _affine classifer_ ; that is

$g^{\star}\in\mathcal{G}=\left\\{\mathbf{x}\mapsto\operatorname*{arg\,max}_{1\leq
i\leq
K}\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle+b_{i}|\mathbf{w}_{i}\in
S^{d-1},b_{i}\in[-C,C]\right\\},$ (2.2)

where $S^{d-1}$ is the unit sphere. It can be shown that many natural physical
systems are indeed modeled as PWA with affine boundaries (Marcucci and
Tedrake, 2019), and the closed loop dynamics for model-predictive control
(MPC) in these cases is also a PWA system (Borrelli et al., 2017). We will
assume throughout access to an empirical risk minimization oracle, ErmOracle,
which satisfies the following guarantee:

######  Assumption 1 (ErmOracle guarantee).

Given data $(\bar{\mathbf{x}}_{1:s},\mathbf{y}_{1:s})$, ErmOracle returns
$\left\\{\widehat{\mathbf{\Theta}}_{i}|i\in[K]\right\\},\widehat{g}$
satisfying

$\sum_{t=1}^{s}\left|\left|\widehat{\mathbf{\Theta}}_{\widehat{g}(\mathbf{x}_{t})}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\inf_{g\in\mathcal{G},\,\left\\{\mathbf{\Theta}_{i}|i\in[K]\right\\}}\sum_{t=1}^{s}\left|\left|\mathbf{\Theta}_{g(\mathbf{x}_{t})}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}\leq\varepsilon_{\mathrm{orac}}.$
(2.3)

As noted, while such an oracle is necessarily not computationally efficient in
the worst case (Amaldi and Mattavelli, 2002), there are many popular
heuristics that are used in practical situations (see e.g. Ferrari-Trecate et
al. (2003), or (Garulli et al., 2012) and references therein). The learner
aims to construct an algorithm, efficient with respect to the above oracle,
that at each time step $t$ produces $\mathbf{\widehat{y}}_{t}$ such that

$\operatorname{Reg}_{T}:=\sum_{t=1}^{T}\left\|\mathbf{\widehat{y}}_{t}-\mathbf{\Theta}^{\star}_{g_{\star}(\bar{\mathbf{x}}_{t})}\bar{\mathbf{x}}_{t}\right\|^{2}=o(T).$
(2.4)

This notion of regret is standard in the online learning community and, as we
shall see, immediately leads to bounds on prediction error.

##### Directional Smoothness.

As previously mentioned, without further restriction, sublinear regret is
infeasible, as formalized in the following proposition:

######  Proposition 1.

In the above setting, there exists an adversary with $m=d=1$, K=2, that
chooses $\mathbf{\Theta}^{\star}$ and $g_{\star}$, as well as
$\mathbf{x}_{1},\dots,\mathbf{x}_{T}$ such that any learner experiences

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\geq\frac{T}{2}.$

Proposition 1 follows from a construction of a system where there is a
discontinuity across a linear boundary, across which the states
$\mathbf{x}_{t}$ oscillate. The bound is then a consequence of the classical
fact that online classification with linear thresholds suffers linear regret;
see Section B.1 for a formal proof, included for the sake of completeness.
Crucially, a discontinuity in the dynamics necessitates an $\Omega(1)$
contribution to regret each time the decision boundary is incorrectly
determined. To avoid this pathology, we suppose that the contexts are smooth;
however, because standard smoothness (Haghtalab et al., 2020) leads to regret
that is exponential in dimension (Block and Simchowitz, 2022), we instead
consider a related condition, “directional smoothness,” proposed by Block and
Simchowitz (2022).

######  Definition 2 (Definition 52 from Block and Simchowitz (2022)).

Given a scalar $\sigma_{\mathrm{dir}}>0$, a random vector $\mathbf{x}$ is
called $\sigma_{\mathrm{dir}}$-directionally smooth if for all $\mathbf{w}\in
S^{d-1}:=\\{w\in\mathbb{R}^{d}:\|w\|<1\\}$, $c\in\mathbb{R}$, and $\delta>0$,
it holds that

$\mathbb{P}\left(\left|\left\langle\mathbf{w},\mathbf{x}\right\rangle-c\right|\leq\delta\right)\leq\frac{\delta}{\sigma_{\mathrm{dir}}}.$
(2.5)

For a comparison between directional and standard smoothness, consult Block
and Simchowitz (2022). As an example, for any vector $\mathbf{z}_{t}$, if
$\mathbf{w}_{t}\sim\mathcal{N}(0,\sigma_{\mathrm{dir}}^{2}\mathbf{I})$, then
$\mathbf{z}_{t}+\mathbf{w}_{t}$ is
$\frac{\sigma_{\mathrm{dir}}}{\sqrt{2\pi}}$-directionally smooth; see Section
C.1 for a proof and examples of directional smoothness for other noise
distributions. Crucially, directional smoothness is _dimension-independent_ ,
in contradistinction to standard smoothness, where we would only have
$\Theta\left(\sigma_{\mathrm{dir}}^{d}\right)$-smoothness (in the standard
sense) in the previous example. Like prior work on smoothed online learning,
we require our smoothness condition to hold conditionally:

######  Assumption 2.

Let $\mathscr{F}_{t}$ denote the filtration generated by
$\mathbf{x}_{1},\dots,\mathbf{x}_{t}$. For all times $t$, $\mathbf{x}_{t}$
conditional on $\mathscr{F}_{t-1}$ is $\sigma_{\mathrm{dir}}$-directionally
smooth.

##### Further Assumptions.

Next, we make two standard assumption for sequential regression, one
controlling the tail of the noise and the other the magnitude of the
parameters.

######  Assumption 3.

Let $\mathscr{F}^{y}_{t}$ denote the filtration generated by $\mathscr{F}_{t}$
and $\mathbf{e}_{1},\dots,\mathbf{e}_{t-1}$ (equivalently, by
$\mathscr{F}_{t}$ and $\mathbf{y}_{t},\dots,\mathbf{y}_{t-1}$). For all $t$,
it holds that $\mathbf{e}_{t}$ is $\nu^{2}$-sub-Gaussian conditioned on
$\mathscr{F}^{y}_{t}$; in particular, $\mathbf{e}_{t}$ is conditionally zero
mean.

######  Assumption 4.

We suppose that for all $1\leq t\leq T$,
$\left|\left|\bar{\mathbf{x}}_{t}\right|\right|\leq B$ and, furthermore,
$\|\mathbf{\Theta}^{\star}_{i}\|_{\mathrm{F}}\leq R$ for all $i$. We will
further assume that ErmOracle always returns $\widehat{\mathbf{\Theta}}_{i}$
such that $\|\widehat{\mathbf{\Theta}}_{i}\|_{\mathrm{F}}\leq R$.

Finally, we assume that the true affine parameters are well-separated:

######  Assumption 5.

There is some $\Delta_{\mathrm{sep}}>0$ such that for all $1\leq i<j\leq K$,
it holds that

$\|\mathbf{\Theta}^{\star}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}\geq\Delta_{\mathrm{sep}}.$
(2.6)

We remark that Assumption 5 is, in some sense, generic. Indeed, in the
original smoothed analysis of algorithms (Spielman and Teng, 2004), it was
assumed that the parameter matrices were smoothed by Gaussian noise; if, in
addition to smoothness in contexts $\mathbf{x}_{t}$ we assume that the
$\mathbf{\Theta}^{\star}_{i}$ are drawn from a directionally smooth
distribution, then Proposition 11 below implies that with probability at least
$1-T^{-1}$, it holds that $\Delta_{\mathrm{sep}}\gtrsim
md\left(\frac{\sigma_{\mathrm{dir}}}{K^{2}T}\right)^{\frac{1}{md}}$.
Furthermore, one reason why removing the gap assumption is difficult in our
framework is that, computationally speaking, agnostically learning halfspaces
is hard (Guruswami and Raghavendra, 2009). Without Assumption 5, ErmOracle
cannot reliably separate modes and thus the postprocessing steps our main
algorithm (Algorithm 1) used to stabilize the predictions must also
agnostically learn the modes; together with the previous observation on the
difficulty of learning halfspaces, this suggests that if ErmOracle is unable
to separate modes, there is significant technical difficulty in achieving a
oracle-efficient, no-regret algorithm. We defer the formal setting of one-step
prediction and simulation regret to Sections 3.1 and 3.2.

###  3 Results

1:Initialize  Epoch length $E$, Classifiers
$\mathbf{w}_{1:K}^{0}=(\mathbf{0},\dots,\mathbf{0})$, margin parameter
$\gamma>0$, learning rate $\eta>0$

2:for $\tau=1,2,\dots,T/E$ do (% iterate over epochs)

3: $\left\\{(\widehat{\mathbf{\Theta}}_{\tau,i})_{1\leq i\leq
K},\,\widehat{g}_{\tau}\right\\}\leftarrow\textsc{ErmOracle}((\bar{\mathbf{x}}_{1:\tau
E},\mathbf{y}_{1:\tau E}))$

4:
$\widehat{g}_{\tau}\leftarrow\mathbf{\mathsf{Reorder}}\left(\widehat{g}_{\tau},\left(\widehat{\mathbf{\Theta}}_{\tau,i}\right)_{1\leq
i\leq K},\left(\widehat{\mathbf{\Theta}}_{\tau-1,i}\right)_{1\leq i\leq
K}\right)$

5: $\mathbf{w}_{1:K}^{\tau
E}\leftarrow\textsc{Ogd}(\mathbf{w}_{1:K}^{(\tau-1)E},\bar{\mathbf{x}}_{(\tau-1)E:\tau
E};\widehat{g}_{\tau},\gamma,\eta)$

6: Let $\tilde{g}_{\tau}(\bar{\mathbf{x}})=\operatorname*{arg\,max}_{1\leq
i\leq K}\left\langle\mathbf{w}_{i}^{\tau E},\bar{\mathbf{x}}\right\rangle$
denote classifier induced by $\mathbf{w}_{1:K}^{\tau E}$.

7: for $t=\tau E,\dots,(\tau+1)E-1$ do

8: Receive  $\bar{\mathbf{x}}_{t}$, and predict
$\mathbf{\hat{y}}_{t}=\widehat{\mathbf{\Theta}}_{\tau,\tilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}\cdot\bar{\mathbf{x}}_{t}$

9: Receive  $\mathbf{y}_{t}$

Algorithm 1 Main Algorithm

We propose Algorithm 1, an oracle-efficient protocol with provably sublinear
regret and polynomial dependence on all problem parameters. Algorithm 1 runs
in epochs: at the beginning of epoch $\tau$, the learner calls ErmOracle on
the past data to produce $\widehat{g}_{\tau}$ and the set of matrices
$\widehat{\mathbf{\Theta}}_{\tau,i}$. A major challenge is identifying the
same affine regions between epochs. To this end, the learner then adjusts
$\widehat{g}_{\tau}$ to preserve consistency in labels across epochs, as
explained informally in Section 4.2 and in greater detail in Appendix E.

The learner then runs online gradient descent (Algorithm 2) on the hinge loss
to produce a modified classifier $\widetilde{g}_{\tau}$; finally, throughout
the epoch, the learner uses $\widehat{\mathbf{\Theta}}_{\tau,i}$ and
$\widetilde{g}_{\tau}$ to predict $\mathbf{\widehat{y}}_{t}$ before repeating
the process in the next epoch. The reason for using a secondary algorithm to
transform $\widehat{g}_{\tau}$ into $\widetilde{g}_{\tau}$ is to enforce
stability of the predictor across epochs, which is necessary to bound the
regret. Again, we suppose that Assumption 1 holds throughout.

We have the following result:.

######  Theorem 3 (Regret Bound).

Suppose we are in the setting of online PWA regression (2.1) and Assumptions
2-5 hold. Then, if the parameters $E,\gamma,\eta$ are set as in (F.6), it
holds that with probability at least $1-\delta$,

$\operatorname{Reg}_{T}\leq\mathsf{poly}\left(d,\frac{1}{\sigma_{\mathrm{dir}}},m,B,R,K,\nu,\frac{1}{\Delta_{\mathrm{sep}}},\log(1/\delta)\right)\cdot
T^{1-\Omega(1)}+\varepsilon_{\mathrm{orac}}\cdot
T+K^{2}\cdot\sum_{t=1}^{T}\left|\left|\bm{\delta}_{t}\right|\right|,$ (3.1)

where the polynomial dependence is given in (F.7).

######  Remark 1.

While Theorem 3 requires that we are correctly setting the parameters of the
algorithm, aggregation algorithms allow us to tune these parameters in an
online fashion (see, e.g. Hazan and Seshadhri (2009)).

######  Remark 2.

We observe that the misspecification errors $\bm{\delta}_{t}$ could also be
viewed as indicators corresponding to the $\bar{\mathbf{x}}_{t}$ being in
small, rarely visited regions; thus, we could run an underspecified ErmOracle,
with $K^{\prime}\ll K$ modes and recover a regret bound depending only on
“large” modes.

Observe that in the simple setting where
$\varepsilon_{\mathrm{crp}}=\varepsilon_{\mathrm{orac}}=0$, we obtain exactly
the polynomial, no-regret rates promised in the introduction. Along the way to
proving our regret bound, we establish that ErmOracle correctly recovers the
linear parameters within the modes, assuming sufficiently many examples from
that mode have been observed.

######  Theorem 4 (Parameter Recovery).

Suppose that Assumptions 2-4 hold and let
$\left\\{\widehat{\mathbf{\Theta}}_{i}|i\in[K]\right\\},\widehat{g}$ denote
the output of $\textsc{ErmOracle}(\bar{\mathbf{x}}_{1:T},\mathbf{y}_{1:T})$
and $I_{ij}(\widehat{g})$ denote the set of times $t$ such that
$\widehat{g}(\bar{\mathbf{x}}_{t})=i$ and $g_{\star}(\bar{\mathbf{x}}_{t})=j$.
Then with probability at least $1-\delta$, for all $1\leq i,j\leq K$ such that

$\displaystyle\left|I_{ij}(\widehat{g})\right|\geq\mathrm{poly}\left(K,B,\frac{1}{\sigma_{\mathrm{dir}}},\log\left(\frac{1}{\delta}\right)\right)\cdot
T^{1-\Omega(1)},$

it holds that

$\displaystyle\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}^{2}\leq\frac{\sqrt{T}}{\left|I_{ij}(\widehat{g})\right|}\cdot\mathrm{poly}\left(K,B,\frac{1}{\sigma_{\mathrm{dir}}},R,d,m,\nu,\log\left(\frac{1}{\delta}\right)\right).$

Above we have given the result with the assumption that
$\varepsilon_{\mathrm{crp}}=\varepsilon_{\mathrm{orac}}=0$ for the sake of
presentation; in the formal statement, the fully general case is stated.
Theorem 4 implies that directional smoothness is sufficient to guarantee
parameter recovery at a parametric rate, in marked distinction to most
adversarial learning regimes. Note that this recovery result also implies mode
recovery up to a permutation, due to separation. Before providing more detail
on the algorithm and its analysis in Section 4, we discuss our two main
applications.

####  3.1 Regret for One-Step Prediction in PWA Systems

A direct application of our main result is online prediction in piecewise
affine systems. Consider the following dynamical system with state
$\mathbf{z}_{t}\in\mathbb{R}^{d_{z}}$ and input
$\mathbf{u}_{t}\in\mathbb{R}^{d_{u}}$:

$\mathbf{z}_{t+1}=\mathbf{A}^{\star}_{i_{t}}\mathbf{z}_{t}+\mathbf{B}^{\star}_{i_{t}}\mathbf{u}_{t}+\mathbf{m}^{\star}_{i_{t}}+\mathbf{e}_{t},\quad
i_{t}=g^{\star}(\mathbf{z}_{t},\mathbf{u}_{t}).$ (3.2)

Substitute
$\mathbf{\Theta}^{\star}_{i}:=[\mathbf{A}_{i}\mid\mathbf{B}_{i}\mid\mathbf{m}_{i}]$
and define the concatenations
$\mathbf{x}_{t}=[\mathbf{z}_{t}\mid\mathbf{u}_{t}]$ and
$\bar{\mathbf{x}}_{t}=[\mathbf{x}_{t}\mid 1]$. The following lemma, proven in
Section G.1, gives sufficient conditions on the system noise $\mathbf{e}_{t}$
and structure of the control inputs $\mathbf{u}_{t}$ under which
$\mathbf{x}_{t}$ is directionally smooth.

######  Lemma 3.1.

Let $\mathcal{F}_{t}$ denote the filtration generated by
$\mathbf{x}_{t}=[\mathbf{z}_{t}\mid\mathbf{u}_{t}]$. Suppose that
$\mathbf{e}_{t-1}\mid\mathcal{F}_{t-1}$ is $\sigma_{\mathrm{dir}}$ smooth, and
that in addition,
$\mathbf{u}_{t}=\bar{}\mathbf{K}_{t}\mathbf{x}_{t}+\bar{\mathbf{u}}_{t}+\bar{\mathbf{e}}_{t}$,
where $\bar{}\mathbf{K}_{t}$ and $\bar{\mathbf{u}}_{t}$ are
$\mathcal{F}_{t-1}$-measurable444This permits, for example, that
$\bar{}\mathbf{K}_{t}$ is chosen based on the previous mode $i_{t-1}$, or any
estimate thereof that does not use $\mathbf{x}_{t}$. , and
$\bar{\mathbf{e}}_{t}\mid\mathcal{F}_{t-1},\mathbf{e}_{t}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth. Then,
$\mathbf{x}_{t}\mid\mathcal{F}_{t-1}$ is
$\sigma_{\mathrm{dir}}/\sqrt{(1+\|\mathbf{K}_{t}\|_{\mathrm{op}})^{2}+1}$\-
directionally smooth.

Directionally smooth noise distributions, such as Gaussians, are common in the
study of online control (Dean et al., 2020; Simchowitz et al., 2020), and the
smoothing condition on the input can be achieved by adding fractionally small
noise, as is common in many reinforcement learning domains, such as to compute
gradients in policy learning (Sutton et al., 1999) or for Model Predictive
Path Integral (MPPI) Control (Williams et al., 2015).

Throughout, we keep the notation for compactly representing our parameters by
letting
$\mathbf{\Theta}^{\star}_{i}=[\mathbf{A}^{\star}_{i}\mid\mathbf{B}^{\star}_{i}\mid\mathbf{m}^{\star}_{i}]$,
the estimate at time $t$ be
$\widehat{\mathbf{\Theta}}_{t,i}=[\hat{\mathbf{A}}_{t,i}\mid\hat{\mathbf{B}}_{t,i}\mid\hat{\mathbf{m}}_{t,i}]$,
and covariates $\mathbf{x}_{t}=(\mathbf{z}_{t},\mathbf{u}_{t})$. We let
$\mathscr{F}_{t}$ denote the filtration generated by $\mathbf{x}_{1:t}$, and
note that $\mathbf{e}_{t}$ is $\mathscr{F}_{t+1}$-measurable.

######  Assumption 6 (Boundedness).

The covariates and parameters, as defined above, satisfy Assumption 4.

######  Assumption 7 (SubGaussianity and Smoothness so as to satisfy Lemma
3.1).

We assume that

  * •

$\mathbf{e}_{t}\mid\mathscr{F}_{t}$ is $\sigma_{\mathrm{dir}}$-directionally
smooth

  * •

$\mathbf{u}_{t}=\bar{}\mathbf{K}_{t}\mathbf{x}_{t}+\bar{\mathbf{u}}_{t}+\bar{\mathbf{e}}_{t}$,
where $\bar{}\mathbf{K}_{t}$ and $\bar{\mathbf{u}}_{t}$ are
$\mathcal{F}_{t-1}$-measurable and
$\bar{\mathbf{e}}_{t}\mid\mathcal{F}_{t-1},\mathbf{e}_{t}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth.

Further, we assume that $\mathbf{e}_{t}\mid\mathscr{F}_{t}$ is
$\nu^{2}$-subGaussian.

Under these assumptions, we can apply our main result, Theorem 3, to bound the
one-step prediction error in PWA systems. In particular, we have the
following:

######  Theorem 5 (One-Step Regret in PWA Systems).

Suppose that $\mathbf{z}_{t},\mathbf{u}_{t}$ evolve as in (3.2) with the
attendant notation defined therein. Suppose further that Assumptions 5, 6, and
7 hold and that at each time $t$, the learner predicts
$\widehat{\mathbf{z}}_{t+1}$ with the aim of minimizing the cumulative square
loss with respect to the correct $\mathbf{z}_{t+1}$. If the learner applies
Algorithm 1 to this setting, then with probability at least $1-\delta$, the
learner experiences regret at most

$\displaystyle\sum_{t=0}^{T-1}\left|\left|\mathbf{z}_{t+1}-\widehat{\mathbf{z}}_{t+1}\right|\right|^{2}\leq
T\nu^{2}+\mathsf{poly}\left(d,\frac{\sqrt{1+(1+\max_{1\leq t\leq
T}\left|\left|\mathbf{K}_{t}\right|\right|_{\mathrm{op}})^{2}}}{\sigma_{\mathrm{dir}}},m,B,R,K,\nu,\log\left(\frac{1}{\delta}\right)\right)\cdot
T^{1-\Omega(1)}$

where the exact polynomial dependence is given in Theorem 16.

###### Proof.

The result follows from applying Lemma 3.1 to demonstrate directional
smoothness and using Assumptions 7 and 6 and smoothness to apply Theorem 3. ∎

####  3.2 Guarantees for Simulation Regret

We now describe an extension of the one-step prediction desideratum to a
notion of $H$-step prediction; more formal description is detailed in Section
G.2. The learning process occurs in _episodes_ $t=1,2,\dots,T$, consisting of
steps $h=1,2,\dots,H$. In each episode, an external planner provides the
learner a policy $\pi_{t}$. For simplicity, we assume that
$\pi_{t}=(\mathbf{u}_{t,1},\dots,\mathbf{u}_{t,H})$ is _open loop_ (state-
independent) and stochastic, minimicking situations such as model predictive
control; extensions are mentioned in Section G.5. With each episode, the true
dynamics are given by

$\displaystyle\mathbf{z}_{t,h+1}$
$\displaystyle=\mathbf{A}^{\star}_{i_{t,h}}\mathbf{z}_{t}+\mathbf{B}^{\star}_{i_{t,h}}\mathbf{u}_{t,h}+\mathbf{m}^{\star}_{i_{t,h}}+\mathbf{e}_{t,h}$
(3.3) $\displaystyle i_{t,h}$
$\displaystyle=g^{\star}(\mathbf{z}_{t,h},\mathbf{u}_{t,h}).$

We assume that the process noise $\mathbf{e}_{t,h}$ are independently drawn
from a known distribution $\mathcal{D}$, and that $\mathbf{z}_{t,1}$ is
sampled from an arbitrary $\sigma_{\mathrm{dir}}$-smooth distribution. At the
start of episode $t$, the learner then produces estimates
$\hat{}\mathbf{A}_{t},\hat{}\mathbf{B}_{t},\hat{g}_{t}$ and simulates the plan
$\pi_{t}$ using the plug in estimate of the dynamics, i.e.,

$\displaystyle\hat{\mathbf{z}}_{t;h+1}$
$\displaystyle=\hat{\mathbf{A}}_{t,\hat{i}_{t,h}}\hat{}\mathbf{z}_{t,h}+\hat{\mathbf{B}}_{t,\hat{i}_{t,h}}\mathbf{u}_{t,h}+\hat{\mathbf{m}}_{t,\hat{i}_{t,h}}\hat{\mathbf{e}}_{t,h},$
$\displaystyle\hat{i}_{t,h}$
$\displaystyle=\widehat{g}_{t}(\hat{\mathbf{z}}_{t,h},\hat{\mathbf{u}}_{t,h}),$

where $\hat{\mathbf{e}}_{t,h}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{D}$, and
$\hat{\mathbf{u}}_{t,h}$ are an i.i.d. draw from the stochastic, open-loop
policy $\pi_{t}$. Because the simulated and true processes use a different
noise sequence, we consider the following notion of error, which measures the
distance betwen the two _distributions_ induced by the dynamics, as opposed to
the regret, which measure the distance between the realizations thereof. We
choose the Wasserstein metric $\mathcal{W}_{2}$, as it upper bounds the
difference in expected value of any Lipschitz reward function between the true
and simulated trajectories (see Section G.2 for a formal definition and more
explanation).

######  Definition 6 (Simulation Regret).

Let $\mathcal{W}_{2}(\cdot,\cdot)$ denote the $L_{2}$-Wasserstein distance,
define the concatenations
$\mathbf{x}_{t,h}=(\mathbf{z}_{t,h},\mathbf{u}_{t,h})$ and
$\hat{}\mathbf{x}_{t,h}=(\hat{}\mathbf{z}_{t,h},\hat{}\mathbf{u}_{t,h})$, and
let $\bar{\mathscr{F}}_{t}$ be the filtration generated by
$\\{\mathbf{x}_{s,h}\\}_{1\leq s\leq t,1\leq h\leq H}$. We define the
$T$-episode, $H$-step simulation regret as

$\displaystyle\mathrm{SimReg}_{T,H}$
$\displaystyle:=\sum_{t=1}^{T}\mathcal{W}_{2}\left(\mathbf{x}_{t,1:H},\hat{\mathbf{x}}_{t,1:H}\mid\bar{\mathscr{F}}_{t-1}\right)^{2}.$

Our goal is to achieve $\mathrm{SimReg}_{T,H}\lesssim\mathrm{poly}(H)\cdot
T^{1-\Omega(1)}$, but polynomial-in-$H$ dependence may be challenging for
arbitrary open-loop policies and unstable dynamics of the pieces. Thus, in the
interest of simplicity, we decouple the problems of linear stability from the
challenge of error compounding due to discontinuity of the dynamics by
adopting the following strong assumption.

######  Assumption 8.

There exists a _known_ , positive definite Lyapunov matrix
$\mathbf{P}\in\mathbb{R}^{d_{z}\times d_{z}}$ that satisfies
$(\mathbf{A}^{\star}_{i})^{\top}\mathbf{P}(\mathbf{A}^{\star})_{i}\preceq\mathbf{P}$
for all modes $i\in[K]$.

Extensions are described in Section G.5. Using a minor modification of
Algorithm 1, detailed in Algorithm 4, we show that we can get vanishing
simulation regret, summarized in the following result:

######  Theorem 7.

Suppose that we are in the setting of (3.3) and that Assumptions 2-5 and 8
hold. If we run a variant of Algorithm 1 (see Algorithm 4 in Section G.3),
then with probability at least $1-\delta$, it holds that

$\displaystyle\mathrm{SimReg}_{T,H}\leq\mathsf{poly}\left(H,d,\frac{1}{\sigma_{\mathrm{dir}}},m,B,R,K,\nu,\frac{1}{\Delta_{\mathrm{sep}}}\right)\cdot
T^{1-\Omega(1)}.$

The proof of Theorem 7 with the exact polynomial dependence on the parameters
can be found in Section G.2 and rests on a lemma showing that under Assumption
8, simulation regret at a given time $t$ can be bounded as $\mathsf{poly}(H)$
multiplied by the maximum one-step prediction error for times
$t,t+1,\dots,t+H$, which is bounded in Theorem 3.

###  4 Analysis

In this section, we present a sketch of the proof of Theorem 16 by breaking
the analysis into two parts and stating informal versions of two key
intermediate theorems. There are two primary sources of regret: that which is
due to poorly estimating the linear parameters within a mode and that which is
due to misclassification of the mode. The first of these sources can be
controlled by our first theorem, which we term parameter recovery, while the
second can be controlled by our second theorem on mode prediction.

####  4.1 Parameter Recovery

We now describe how we control the regret that arises due to error in
estimating the linear parameter in each mode. In particular, we sketch a proof
of Theorem 4, stated above, which says that if we have seen many examples of
$\bar{\mathbf{x}}_{t}$ such that $g_{\star}(\bar{\mathbf{x}}_{t})=i$ and
$\widehat{g}(\bar{\mathbf{x}}_{t})=j$, then our estimated parameter
$\widehat{\mathbf{\Theta}}_{j}$ for this mode is close to
$\mathbf{\Theta}^{\star}_{i}$. The theorem was stated in terms of a recovery
guarantee given $T$ observations, but we ultimately apply it only to times
within a given epoch. The full proof is given in Appendix D.

###### Proof sketch of Theorem 4.

We break the proof into three parts: first, we show that the regret of
$\widehat{g}$ and the $\widehat{\mathbf{\Theta}}_{i}$, when restricted to
times $t\in I_{ij}(\widehat{g})$, is small; second, we relate the prediction
error

$\displaystyle\mathcal{Q}_{ij}(\widehat{g})=\sum_{t\in
I_{ij}(\widehat{g})}\left|\left|(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})\bar{\mathbf{x}}_{t}\right|\right|^{2}$

to the regret on $I_{ij}(\widehat{g})$; third, demonstrate that
$\Sigma_{ij}(\widehat{g})=\sum_{t\in
I_{ij}(\widehat{g})}\bar{\mathbf{x}}_{t}\bar{\mathbf{x}}_{t}^{T}$ has minimal
eigenvalue bounded below by some constant with high probability. If all three
of these claims hold, then, noting that

$\displaystyle\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}^{2}\leq\left|\left|\Sigma_{ij}(\widehat{g})^{-1}\right|\right|_{\mathrm{op}}\cdot\sum_{t\in
I_{ij}(\widehat{g})}\left|\left|(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})\bar{\mathbf{x}}_{t}\right|\right|^{2},$

we conclude. Each of these claims requires significant technical effort in its
own right. We introduce the notion of _disagreement covers_ , a stronger
analogue of the traditional $\varepsilon$-net that is adapted to our problem
and allows us to turn statements proven for a single $g\in\mathcal{G}$ into
ones uniform over $\mathcal{G}$. The first step is to bound the size of
disagreement covers for the class $\mathcal{G}$ of interest; we then prove
each of the three claims for some fixed $g\in\mathcal{G}$ and lift the result
to apply to the data-dependent $\widehat{g}$. This step is accomplished in
Section D.1.

We now turn to our three claims555Note that the presentation in this sketch is
not in the order of that in the section below due to the natural structure of
certain logical dependencies in the proof structure.. For the first, proved in
Lemma D.15, we introduce the _excess risk_ on each pair $(i,j)$,

$\displaystyle\mathcal{R}_{ij}(g,\mathbf{\Theta})=\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{\Theta}_{i}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\left|\left|\mathbf{e}_{t}+\bm{\delta}_{t}\right|\right|^{2}$

and note that the cumulative empirical excess risk
$\sum_{i,j}\mathcal{R}_{ij}(\widehat{g},\widehat{\mathbf{\Theta}})$ of
predicting using $\widehat{g}$ and $\widehat{\mathbf{\Theta}}$ returned by the
ERM oracle is bounded by $\varepsilon_{\mathrm{orac}}$, which can be checked
by the fact that $\mathcal{R}_{ij}(g_{\star},\mathbf{\Theta}_{\star})=0$ due
to Equation 2.1. Thus, showing that
$\mathcal{R}_{ij}(\widehat{g},\widehat{\mathbf{\Theta}})$ is small can be done
by showing that for no $i^{\prime},j^{\prime}$ is
$\mathcal{R}_{i^{\prime}j^{\prime}}(\widehat{g},\widehat{\mathbf{\Theta}})\ll
0$. This can be accomplished by a concentration argument for a single
$g,\mathbf{\Theta}_{0}$, coupled with a covering argument using our notion of
disagreement covers to boost the result to one uniform in $\mathcal{G}$, and
thus applying to $\widehat{g},\widehat{\mathbf{\Theta}}$.

For the second claim, i.e., that $\mathcal{Q}_{ij}(\widehat{g})$ is controlled
by $\mathcal{R}_{ij}(\widehat{g},\widehat{\mathbf{\Theta}})$, we provide a
proof in Lemma D.14. For a fixed $g\in\mathcal{G}$, we decompose
$\mathcal{R}_{ij}(g,\widehat{\mathbf{\Theta}})$ into $\mathcal{Q}_{ij}(g)$ and
an error term. We then use a generalization of the self-normalized martingale
inequality from Abbasi-Yadkori et al. (2011) to control the error in terms of
$\mathcal{Q}_{ij}(g)$, providing a self-bounded inequality. Finally, we
rearrange this inequality and apply a union bound on a disagreement cover to
boost the result to one uniform in $\mathcal{G}$ and $\mathbf{\Theta}$.

To prove the third claim, that $\Sigma_{ij}(\widehat{g})$ has singular values
uniformly bounded from below, we split our argument into two parts. First, in
Section D.2, we assume the following sliced-small ball condition on the data,
i.e., for some $\zeta,\rho>0$, it holds that

$\mathbb{P}\left(\left\langle\bar{\mathbf{x}}_{t},\mathbf{w}\right\rangle^{2}\geq
c\cdot\zeta^{2}|\mathscr{F}_{t},\,t\in I_{ij}(\widehat{g})\right)\geq
c\cdot\rho.$

Given the above condition, we establish a high probability lower bound on
$\Sigma_{ij}(g)$ for fixed $g$ using a self-normalized martingale inequality,
using analysis that may be of independent interest. We then again apply a
union bound on a disagreement cover to lift this result to be uniform in
$\mathcal{G}$. Finally, in Section D.3, we provide bounds on $\zeta,\rho$
using directional smoothness and Markov’s inequality. ∎

While we do not expand on this point here, we remark in passing that our
method for bounding the size of a disagreement cover can be applied to
significantly simplify the proofs of many of the results found in Block and
Simchowitz (2022).

####  4.2 Mode Prediction

1:Initialize  Data $\bar{\mathbf{x}}_{1:E}$, clasifiers
$\mathbf{w}_{1:K}^{0}$, margin parameter $\gamma>0$, learning rate $\eta>0$,
classifier $\widehat{g}:\mathcal{X}\to[K]$

2:for $s=1,2,\dots,E$ do

3: Receive  $\bar{\mathbf{x}}_{i}$ and update
$\mathbf{w}_{1:K}^{s}\leftarrow\Pi_{({\mathcal{B}}^{d-1})^{\times
K}}\left(\mathbf{w}_{1:K}^{{s}-1}-\eta\nabla\widetilde{\ell}_{\gamma,i,\widehat{g}}(\mathbf{w}^{{s}-1})\right)$
(% Gradient step and project so
$\left|\left|{\mathbf{w}}_{i}\right|\right|{\leq}1$)

4: % $\widetilde{\ell}_{\gamma,i,\widehat{g}}$ defined in Equation 4.1

5: Return  $\mathbf{w}_{1:K}^{m}$

Algorithm 2 Online Gradient Descent (Single Epoch)

As mentioned earlier, there are two sources of regret; (1) misspecification of
the parameters defining the linear functions on each mode and (2) error in
estimating the modes $i_{t}$. The previous section described how we control
this first source, while this section addresses the second source. Algorithm 1
proceeds in epochs, which allows us to apply our parameter recovery results
per-epoch, thereby ensuring that, when we correctly classify our modes, we are
incurring low regret. The primary challenge is that directional smoothness, as
opposed to independence, is insufficiently strong an assumption to guarantee
that a learned classifier $\widehat{g}_{\tau}$ at each epoch $\tau$
generalizes well to unseen data in the next epoch. In order to ensure such
generalization, we take inspiration from online learning and enforce stability
of our algorithm across epochs by modifying the classifier
$\widehat{g}_{\tau}$.

There are two problems to solve before we can ensure good performance of our
online classifier. First, the dynamics described in (2.1) are only
identifiable up to a permutation of the labels. Thus, in order to enforce
stability across epochs, we need to ensure that we label the same modes in the
same way. This task is made more difficult by the fact that different modes
may be combined or split up across different epochs due to the black box
nature of ErmOracle. We solve this by appealing to a subroutine,
$\mathbf{\mathsf{Reorder}}$, described in Algorithm 3 in Appendix E, which
combines modes that are both sufficiently large and have sufficiently similar
parameters and then relabels the modes so that similar nominal clusters
persist accross epochs.

The next issue is how to enforce stability of our online classifier. We do
this by introducing a surrogate loss
$\widetilde{\ell}_{\gamma,t,\widehat{g}}$, the multi-class hinge loss with
parameter $\gamma>0$. Formally, let
$\mathbf{w}_{1:K}=(\mathbf{w}_{1},\dots,\mathbf{w}_{K})$ for
$\mathbf{w}_{i}\in\mathcal{B}^{d-1}$, and for $g\in\mathcal{G}$, define the
$(1/\gamma)$-Lipschitz and convex surrogate loss:

$\widetilde{\ell}_{\gamma,t,g}(\mathbf{w}_{1:K})=\max\left(0,\max_{j\neq
g(\bar{\mathbf{x}}_{t})}\left(1-\frac{\left\langle\mathbf{w}_{g(\bar{\mathbf{x}}_{t})}-\mathbf{w}_{j},\bar{\mathbf{x}}_{t}\right\rangle}{\gamma}\right)\right).$
(4.1)

In Ogd (see Algorithm 2), we modify the output of ErmOracle to construct a
classifier $\widetilde{g}_{\tau}$ by running lazy online gradient descent on
this surrogate loss, using the reordered labels given by the output of
ErmOracle evaluated on the previous epoch. By invoking Ogd, we show that our
mode classifier is sufficiently stable to ensure low regret, as stated
informally in the following result.

######  Theorem 8 (Mode Prediction, Informal Statement of Theorem 14).

Suppose that Assumptions 2-5 hold and let $\mathcal{E}_{t}^{\mathrm{mode}}$ be
the event that the learner, invoking Algorithm 1 with correctly tuned
parameters, misclassifies the mode of $\bar{\mathbf{x}}_{t}$. Then, with
probability at least $1-\delta$, it holds that

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\\{\mathcal{E}_{t}^{\mathrm{mode}}\\}\leq\mathrm{poly}\left(K,B,\frac{1}{\sigma_{\mathrm{dir}}},R,d,m,\nu,\frac{1}{\Delta_{\mathrm{sep}}},\log\left(\frac{1}{\delta}\right)\right)\cdot
T^{1-\Omega(1)}.$

###### Proof Sketch.

As mentioned above, the first problem that needs to be solved is the lack of
identifiability of the modes. To address this, for the purposes of analysis,
for each epoch $\tau$, we introduce the function $\pi_{\tau}:[K]\to[K]$ such
that

$\displaystyle\pi_{\tau}(i)=\operatorname*{argmin}_{1\leq j\leq
K}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}.$

In words, $\pi_{\tau}(i)$ is the mode $j$ according to the ground truth whose
parameters are closest to those estimated by ErmOracle. We let
$\mathcal{E}_{t}^{\mathrm{mode}}$ denote the event of misclassifying the mode,
i.e. the event that
$\pi_{\tau}(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})$. We can then decompose the misclassification
as

$\displaystyle\mathcal{E}_{t}^{\mathrm{mode}}\subset\left\\{\pi_{\tau+1}(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right\\}\cup\left\\{\pi_{\tau}(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t}))\neq\pi_{\tau+1}(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t}))\right\\}.$

We call the first event look-ahead classification error and the second
permutation disagreement error. To bound the first of these, we further
decompose the look-ahead classification error event:

$\displaystyle\left\\{\pi_{\tau+1}(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right\\}\subset\left\\{\pi_{\tau+1}(\widehat{g}_{\tau+1}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right\\}\cup\left\\{\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\neq\widehat{g}_{\tau+1}(\bar{\mathbf{x}}_{t})\right\\}.$

Controlling the first of these events is proved as a corollary of the bound on
the permutation disagreement error and we defer its discussion for the sake of
simplicity. To bound the indicator loss of the second event, we use the fact
that indicator loss is upper bounded by
$\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}$ and apply standard online
learning techniques to show that the regret on the $(1/\gamma)$-Lipschitz and
convex surrogate loss can be controlled using online gradient descent. We then
use smoothness to show that the optimal comparator with respect to the
surrogate loss does not experience large regret with respect to the indicator
loss, which in turn has a comparator experiencing zero loss due to the well-
specified nature of $g_{\star}$. Thus, putting everything together, this
provides bound on the look-ahead classification error, with full details
presented in Section E.1.

Bounding the permutation disagreement error is what necessitates the gap
assumption. We show that if there are sufficiently many data points that
$\widehat{g}_{\tau}$ assigns to a given mode, with the threshold defined in
terms of $\Delta_{\mathrm{sep}}$ and other parameters of the problem, then
with high probability the cluster becomes stable in the sense that
$\widehat{\mathbf{\Theta}}_{\tau,i}\approx\widehat{\mathbf{\Theta}}_{\tau+1,i}$.
This result is proved using the fact that if
$\left|I_{i,j}(\widehat{g}_{\tau})\right|$ is large enough, then the parameter
recovery results from the previous section tell us that
$\|\widehat{\mathbf{\Theta}}_{i}-\widehat{\mathbf{\Theta}}_{j}\|_{\mathrm{F}}$
is small. Using the triangle inequality and the fact that
$\|\mathbf{\Theta}^{\star}_{j}-\mathbf{\Theta}^{\star}_{j^{\prime}}\|_{\mathrm{F}}>\Delta_{\mathrm{sep}}$
for $j^{\prime}\neq j$ ensures that $j$ is unique in satisfying
$\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}$
is small. A similar argument applies to epoch $\tau+1$, and thus we can
identify $\widehat{\mathbf{\Theta}}_{\tau,i}$ with some
$\widehat{\mathbf{\Theta}}_{\tau+1,i^{\prime}}$ by these matrices being
sufficiently close in Frobenius norm. Algorithm 3 takes advantage of exactly
this property and permutes the labels across epochs in order to maintain
consistency and control the permutation disagreement error; full details can
be found in Section E.2. Combining this argument with the bound on the look-
ahead classification error suffices to control the online classification
component of the regret. ∎

###  5 Discussion

We have given an efficient online learning algorithm for prediction in
piecewise affine (PWA) systems. Our results are the first foray into the study
of such systems, and a number of outstanding questions remain:

  * •

Does directional smoothness facilliate low regret for planning and control, in
addition to for simulation and prediction?

  * •

If the systems are piecewise-affine but forced to be continuous on their
boundaries, is there an oracle efficient algorithm which suffers low regret
without assuming directional smoothness? Note that exponential weights on a
suitable discretization suffices for an information-theoretic bound.

  * •

Can learning in piecewise affine systems be obtained under _partial
observation_ of the system state?

  * •

What guarantees are possible if the underlying system can be approximated by a
PWA system with many pieces, even if it is not exactly described by one? Note
that this may require algorithms which overcome the separation condition,
Assumption 5.

  * •

What other class of systems, like Linear Complementarity systems, studied in
(Jin et al., 2022), are amenable to oracle-efficient online learning?

We hope that our work initiates investigation of the above as the field
continues to expand its understanding beyond the linear regime.

### Acknowledgements

AB acknowledges support from the National Science Foundation Graduate Research
Fellowship under Grant No. 1122374 as well as support from ONR under grant
N00014-20-1-2336 and DOE under grant DE-SC0022199. MS acknowledges support
from Amazon.com Services LLC grant; PO# 2D-06310236. We also acknowledge Zak
Mhammedi, Terry H.J. Suh and Tao Pang for their helpful comments.

### References

  * Abbasi-Yadkori and Szepesvári [2011] Yasin Abbasi-Yadkori and Csaba Szepesvári.  Regret bounds for the adaptive control of linear quadratic systems.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pages 1–26. JMLR Workshop and Conference Proceedings, 2011.
  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Agarwal et al. [2019] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh.  Online control with adversarial disturbances.  In _International Conference on Machine Learning_ , pages 111–119. PMLR, 2019.
  * Amaldi and Mattavelli [2002] Edoardo Amaldi and Marco Mattavelli.  The min pfs problem and piecewise linear model estimation.  _Discrete Applied Mathematics_ , 118(1-2):115–143, 2002.
  * Block and Simchowitz [2022] Adam Block and Max Simchowitz.  Efficient and near-optimal smoothed online learning for generalized linear functions.  _arXiv preprint arXiv:2205.13056_ , 2022.
  * Block et al. [2021] Adam Block, Yuval Dagan, and Alexander Rakhlin.  Majorizing measures, sequential complexities, and online learning.  In _Conference on Learning Theory_ , pages 587–590. PMLR, 2021.
  * Block et al. [2022] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin.  Smoothed online learning is as easy as statistical learning.  _arXiv preprint arXiv:2202.04690_ , 2022.
  * Borrelli et al. [2017] Francesco Borrelli, Alberto Bemporad, and Manfred Morari.  _Predictive control for linear and hybrid systems_.  Cambridge University Press, 2017.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Cohen et al. [2018] Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar.  Online linear quadratic control.  In _International Conference on Machine Learning_ , pages 1029–1038. PMLR, 2018.
  * Dean and Recht [2021] Sarah Dean and Benjamin Recht.  Certainty equivalent perception-based control.  In _Learning for Dynamics and Control_ , pages 399–411. PMLR, 2021\.
  * Dean et al. [2020] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu.  On the sample complexity of the linear quadratic regulator.  _Foundations of Computational Mathematics_ , 20(4):633–679, 2020.
  * Deistler et al. [1995] Manfred Deistler, K Peternell, and Wolfgang Scherrer.  Consistency and relative efficiency of subspace methods.  _Automatica_ , 31(12):1865–1875, 1995.
  * Duchi et al. [2012] John C Duchi, Peter L Bartlett, and Martin J Wainwright.  Randomized smoothing for stochastic optimization.  _SIAM Journal on Optimization_ , 22(2):674–701, 2012.
  * Federer [2014] Herbert Federer.  _Geometric measure theory_.  Springer, 2014.
  * Ferrari-Trecate et al. [2003] Giancarlo Ferrari-Trecate, Marco Muselli, Diego Liberati, and Manfred Morari.  A clustering technique for the identification of piecewise affine systems.  _Automatica_ , 39(2):205–217, 2003.
  * Foster et al. [2020] Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin.  Learning nonlinear dynamical systems from a single trajectory.  In _Learning for Dynamics and Control_ , pages 851–861. PMLR, 2020\.
  * Freund and Schapire [1999a] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  _Games and Economic Behavior_ , 29(1-2):79–103, 1999a.
  * Freund and Schapire [1999b] Yoav Freund and Robert E Schapire.  Large margin classification using the perceptron algorithm.  _Machine learning_ , 37(3):277–296, 1999b.
  * Garulli et al. [2012] Andrea Garulli, Simone Paoletti, and Antonio Vicino.  A survey on switched and piecewise affine system identification.  _IFAC Proceedings Volumes_ , 45(16):344–355, 2012\.
  * Goodfellow et al. [2016] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep learning_.  MIT press, 2016.
  * Guruswami and Raghavendra [2009] Venkatesan Guruswami and Prasad Raghavendra.  Hardness of learning halfspaces with noise.  _SIAM Journal on Computing_ , 39(2):742–765, 2009\.
  * Haghtalab et al. [2020] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis of online and differentially private learning.  _arXiv preprint arXiv:2006.10129_ , 2020.
  * Haghtalab et al. [2021] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis with adaptive adversaries.  _arXiv preprint arXiv:2102.08446_ , 2021.
  * Haghtalab et al. [2022] Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang.  Oracle-efficient online learning for beyond worst-case adversaries.  _arXiv preprint arXiv:2202.08549_ , 2022.
  * Hazan and Koren [2016] Elad Hazan and Tomer Koren.  The computational power of optimization in online learning.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , pages 128–141, 2016.
  * Hazan and Seshadhri [2009] Elad Hazan and Comandur Seshadhri.  Efficient learning algorithms for changing environments.  In _Proceedings of the 26th annual international conference on machine learning_ , pages 393–400, 2009.
  * Hazan et al. [2017] Elad Hazan, Karan Singh, and Cyril Zhang.  Learning linear dynamical systems via spectral filtering.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Hazan et al. [2016] Elad Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Jin et al. [2022] Wanxin Jin, Alp Aydinoglu, Mathew Halm, and Michael Posa.  Learning linear complementarity systems.  In _Learning for Dynamics and Control Conference_ , pages 1137–1149. PMLR, 2022.
  * Jones and Morari [2009] Colin N Jones and Manfred Morari.  Approximate explicit mpc using bilevel optimization.  In _2009 European control conference (ECC)_ , pages 2396–2401. IEEE, 2009.
  * Kalai and Vempala [2005] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Lidec et al. [2022] Quentin Le Lidec, Louis Montaut, Cordelia Schmid, Ivan Laptev, and Justin Carpentier.  Leveraging randomized smoothing for optimal control of nonsmooth dynamical systems.  _arXiv preprint arXiv:2203.03986_ , 2022.
  * Littlestone [1988] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine learning_ , 2(4):285–318, 1988.
  * Ljung [1999] Lennart Ljung.  System identification: Theory for the users," prentice hall, new jersey, 1999.
  * Ljung and Wahlberg [1992] Lennart Ljung and Bo Wahlberg.  Asymptotic properties of the least-squares method for estimating transfer functions and disturbance spectra.  _Advances in Applied Probability_ , 24(2):412–440, 1992.
  * Mania et al. [2020] Horia Mania, Michael I Jordan, and Benjamin Recht.  Active learning for nonlinear system identification with guarantees.  _arXiv preprint arXiv:2006.10277_ , 2020.
  * Marcucci and Tedrake [2019] Tobia Marcucci and Russ Tedrake.  Mixed-integer formulations for optimal control of piecewise-affine systems.  In _Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control_ , pages 230–239, 2019.
  * Mason [2001] Matthew T Mason.  _Mechanics of robotic manipulation_.  MIT press, 2001.
  * Mhammedi et al. [2020] Zakaria Mhammedi, Dylan J Foster, Max Simchowitz, Dipendra Misra, Wen Sun, Akshay Krishnamurthy, Alexander Rakhlin, and John Langford.  Learning the linear quadratic regulator from nonlinear observations.  _Advances in Neural Information Processing Systems_ , 33:14532–14543, 2020.
  * Oymak and Ozay [2019] Samet Oymak and Necmiye Ozay.  Non-asymptotic identification of lti systems from a single trajectory.  In _2019 American control conference (ACC)_ , pages 5655–5661. IEEE, 2019.
  * Pang et al. [2022] Tao Pang, HJ Suh, Lujie Yang, and Russ Tedrake.  Global planning for contact-rich manipulation via local smoothing of quasi-dynamic contact models.  _arXiv preprint arXiv:2206.10787_ , 2022.
  * Paoletti et al. [2007] Simone Paoletti, Aleksandar Lj Juloski, Giancarlo Ferrari-Trecate, and René Vidal.  Identification of hybrid systems a tutorial.  _European journal of control_ , 13(2-3):242–260, 2007.
  * Posa et al. [2014] Michael Posa, Cecilia Cantu, and Russ Tedrake.  A direct method for trajectory optimization of rigid bodies through contact.  _The International Journal of Robotics Research_ , 33(1):69–81, 2014.
  * Rakhlin and Sridharan [2013] Alexander Rakhlin and Karthik Sridharan.  Online learning with predictable sequences.  In _Conference on Learning Theory_ , pages 993–1019. PMLR, 2013.
  * Rakhlin and Sridharan [2014] Alexander Rakhlin and Karthik Sridharan.  Online non-parametric regression.  In _Conference on Learning Theory_ , pages 1232–1264. PMLR, 2014\.
  * Rakhlin et al. [2011] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Stochastic, constrained, and smoothed adversaries.  _Advances in neural information processing systems_ , 24:1764–1772, 2011.
  * Rakhlin et al. [2015] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Sequential complexities and uniform martingale laws of large numbers.  _Probability Theory and Related Fields_ , 161(1):111–153, 2015.
  * Sattar and Oymak [2022] Yahya Sattar and Samet Oymak.  Non-asymptotic and accurate learning of nonlinear dynamical systems.  _Journal of Machine Learning Research_ , 23(140):1–49, 2022.
  * Sattar et al. [2021] Yahya Sattar, Zhe Du, Davoud Ataee Tarzanagh, Laura Balzano, Necmiye Ozay, and Samet Oymak.  Identification and adaptive control of markov jump systems: Sample complexity and regret bounds.  _arXiv preprint arXiv:2111.07018_ , 2021.
  * Simchowitz and Foster [2020] Max Simchowitz and Dylan Foster.  Naive exploration is optimal for online lqr.  In _International Conference on Machine Learning_ , pages 8937–8948. PMLR, 2020.
  * Simchowitz et al. [2018] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht.  Learning without mixing: Towards a sharp analysis of linear system identification.  In _Conference On Learning Theory_ , pages 439–473. PMLR, 2018.
  * Simchowitz et al. [2019] Max Simchowitz, Ross Boczar, and Benjamin Recht.  Learning linear dynamical systems with semi-parametric least squares.  In _Conference on Learning Theory_ , pages 2714–2802. PMLR, 2019\.
  * Simchowitz et al. [2020] Max Simchowitz, Karan Singh, and Elad Hazan.  Improper learning for non-stochastic control.  In _Conference on Learning Theory_ , pages 3320–3436. PMLR, 2020\.
  * Spielman and Teng [2004] Daniel A Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , pages 81–90, 2004.
  * Suh et al. [2022a] Hyung Ju Suh, Max Simchowitz, Kaiqing Zhang, and Russ Tedrake.  Do differentiable simulators give better policy gradients?  In _International Conference on Machine Learning_ , pages 20668–20696. PMLR, 2022a.
  * Suh et al. [2022b] Hyung Ju Terry Suh, Tao Pang, and Russ Tedrake.  Bundled gradients through contact via randomized smoothing.  _IEEE Robotics and Automation Letters_ , 7(2):4000–4007, 2022b.
  * Sutton et al. [1999] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  _Advances in neural information processing systems_ , 12, 1999.
  * Tsiamis and Pappas [2019] Anastasios Tsiamis and George J Pappas.  Finite sample analysis of stochastic system identification.  In _2019 IEEE 58th Conference on Decision and Control (CDC)_ , pages 3648–3654. IEEE, 2019.
  * Tsiamis et al. [2020] Anastasios Tsiamis, Nikolai Matni, and George Pappas.  Sample complexity of kalman filtering for unknown systems.  In _Learning for Dynamics and Control_ , pages 435–444. PMLR, 2020\.
  * Tsiamis et al. [2022] Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J Pappas.  Statistical learning theory for control: A finite sample perspective.  _arXiv preprint arXiv:2209.05423_ , 2022.
  * Van Der Schaft and Schumacher [2007] Arjan J Van Der Schaft and Hans Schumacher.  _An introduction to hybrid dynamical systems_ , volume 251.  springer, 2007.
  * Williams et al. [2015] Grady Williams, Andrew Aldrich, and Evangelos Theodorou.  Model predictive path integral control using covariance variable importance sampling.  _arXiv preprint arXiv:1509.01149_ , 2015.
  * Williams [1992] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3):229–256, 1992.

##  Part I General Tools

###  Appendix A Notation

Problem Parameter | Definition
---|---
$T$ | total number of time steps
$K$ | number of modes
$d$ | dimension of $\mathbf{x}$ (general PWA)
$m$ | dimension of $y$
$\sigma_{\mathrm{dir}}$ | directional smoothness constant (Assumption 2)
$\nu$ | subGaussian constant of noise (Assumption 3)
$B$ |  magnitude bound on $\|\bar{\mathbf{x}}_{t}\|$ (Assumption 4)
$R$ | magnitude bound on $\|\mathbf{\Theta}^{\star}\|_{\mathrm{F}}$ (Assumption 4)
$\Delta_{\mathrm{sep}}$ | separation parameter (optional for sharper rates, see Assumption 5)
Algorithm Parameters | Definition
---|---
$E$ | epoch length
$\tau$ | current epoch
$\eta$ | step size (Line 4 in Algorithm 2)
$\gamma$ | hinge loss parameter
$A$ | cluster size threshold (Line 11 in Algorithm 3)
$\varepsilon_{\mathrm{crp}}$ | distance from realizability (see (2.1))
Algorithm Objects | Definition
$\widetilde{\ell}_{\gamma,t,\widehat{g}}{g}$ | hinge loss on estimated labels (see (4.1))
$\pi_{\tau}$ | stabilizing permutation (see (E.2))
$\gamma$ | hinge loss parameter
Analysis Parameters | Definition
$\delta$ | probability of error
$\xi$ | scale of disagreement cover discretization (Theorem 12)
$\Xi$ | minimum cluster size to ensure continuity (1)

###  Appendix B Lower Bounds

####  B.1 Proof of Proposition 1

We suppose that $d=m=1$ and consider the unit interval. Thus, $\mathcal{G}$ is
just the set of thresholds on the unit interval, i.e.,

$\displaystyle\mathcal{G}=\left\\{\mathbf{x}\mapsto\mathbb{I}\left\\{\mathbf{x}>\theta\right\\}|\theta\in[0,1]\right\\}.$

We suppose that

$\displaystyle\mathbf{\Theta}^{\star}_{0}=\begin{bmatrix}0&|&1\end{bmatrix}$
$\displaystyle\mathbf{\Theta}^{\star}_{1}=\begin{bmatrix}0&|&0\end{bmatrix},$

i.e., $\mathbf{y}_{t}=g_{\star}(\mathbf{x}_{t})$. We are thus in the setting
of adversarially learning thresholds with an oblivious adversary. It is well
known that this is unlearnable, but we sketch a proof here. With $T$ fixed,
let the adversary sample $\varepsilon_{1},\dots,\varepsilon_{T}$ as
independent Rademacher random variables and let

$\displaystyle\mathbf{x}_{t}=\frac{1}{2}+\sum_{s=1}^{t-1}\varepsilon_{s}2^{-s-1}$

and let $\theta^{\star}=\mathbf{x}_{T+1}$. We observe that
$\mathbf{y}_{t}=-\varepsilon_{t}$ for all $t$. To see this, note that if
$\varepsilon_{t}=1$, then $x_{s}>x_{t}$ for all $s>t$ and similarly if
$\varepsilon_{t}=-1$ then $x_{s}<x_{t}$; as $\theta^{\star}=\mathbf{x}_{T+1}$,
the claim is clear. Note that due to the independence of the
$\varepsilon_{t}$, any $\hat{y}_{t}$ chosen by the learner is independent of
$\varepsilon_{t}$ and thus is independent of $\mathbf{y}_{t}$. Thus the
expected number of mistakes the learner makes, independent of the learner’s
strategy, is $\frac{T}{2}$, concluding the proof.

####  B.2 A Lower Bound for Identification

Consider a setting where there are $K=3$ modes with state and input dimension
$d=1$. For a parameters $\alpha,\beta>0$, define the linear functions

$\displaystyle g_{1}(x;\alpha,\beta)$ $\displaystyle=0$ $\displaystyle
g_{3}(x;\alpha,\beta)$ $\displaystyle=x-(1+\alpha)$ $\displaystyle
g_{2}(x;\alpha,\beta)$ $\displaystyle=2(x-(1+\alpha))-\beta$

For our lexicographic convention in the definition of the
$\operatorname*{arg\,max}$ operator666alternatively, we can make this
unambiguous by ommiting the points $\\{1+\tau,1+2\tau\\}$, we have

$\displaystyle\operatorname*{arg\,max}_{i}g_{i}(x;\alpha,\beta)=\begin{cases}1&x\leq
1+\alpha\\\ 2&x\geq 1+\alpha+\beta\\\
3&x\in(1+\alpha,1+\alpha+\beta)\end{cases}$

That is, $x\mapsto\operatorname*{arg\,max}_{i}g_{i}(x;\alpha,\beta)$ defines
three modes, with the third mode a segment of length $\beta$ between
$1+\alpha$ and $1+\alpha+\beta$. We consider simple $3$-piece PWA systems
whose regions are defined by the above linear functions.

######  Definition 9.

Let $\mathscr{I}(\alpha,\beta,m,\mathcal{D})$ denote the problem instance with
$K=3$ pieces where where the dynamics abide by

$\displaystyle\mathbf{x}_{t+1}=\mathbf{u}_{t}+\mathbf{m}_{i_{t}}+\mathbf{w}_{t}\quad\mathbf{m}_{i}=\begin{cases}0&i=1,2\\\
m&i=3\end{cases},\quad
i_{t}=\operatorname*{arg\,max}_{i}g_{i}(\mathbf{x}_{t};\alpha,\beta),\quad\mathbf{w}_{t}\sim\mathcal{D}.$

,

The following proposition shows that, regardless of the noise distribution
$\mathcal{D}$, learning the parameter $\bm{}3$ can be make arbitrarily hard.
This is because as the $\beta$ parameter is made small, making locating region
$3$ (which is necesary to learn $\bm{}3$) arbitrarily challenging.

######  Proposition 10.

Fix any positive integer $N\in\mathbb{N}$ and any arbitrary distribution
$\mathcal{D}$ over $\mathbb{R}$. Then, any algorithm which adaptively selects
inputs $\mathbf{u}_{1},\dots,\mathbf{u}_{T}$ returns an estimate
$\hat{\mathbf{m}}_{T}$ of $\mathbf{m}_{3}$ must suffer

$\displaystyle\sup_{\iota\in\\{-1,1\\}}\sup_{j\in[2N]}\mathbb{P}_{\mathscr{I}(j/N,1/N,\iota
m,\mathcal{D})}[|\hat{\mathbf{m}}_{T}-\mathbf{m}_{3}|\geq
m]\geq\frac{1}{2}\left(1-\frac{T}{N}\right).$

As $N$ is arbitrary, this makes a constant-accuracy estimate of
$\mathbf{m}_{3}$ arbitrarily difficult.

######  Remark 3.

The lower bound of Proposition 10 can be circumvented in two cases. First, if
the dynamics are forced to be Lipschitz continuous, then deviations of the
dynamics in small regions can only lead to small differences in parameter
values. Second, if there is an assumption which stipulates that all linear
regions have “large volume”, then there is an upper bound on how large $N$ can
be in the above construction, obviating our lower bound. It turns out that
there are practical cricumstances under which PWA systems (a) are not
Lipschitz, and (b) certain regions have vanishingly small volume [Jones and
Morari, 2009]. Still, whether stronger guarantees are possible under such
conditions is an interesting direction for future work.

###### Proof of Proposition 10.

Introduce the shorthand
$\mathbb{P}_{j,\iota}[\cdot]:=\mathbb{P}_{\mathscr{I}(j/N,1/N,\iota
m)}[\cdot]$. Consider the regions $\mathcal{R}_{j}:=[1+j/4N,1+(j+1)/4N]$, and
define the event
$\mathcal{E}_{j,t}:=\\{\mathbf{u}_{j}\notin\mathcal{R}_{j}\\}$ and
$\mathcal{E}_{j}:=\bigcap_{t=1}^{T}\mathcal{E}_{j,t}$. As the learner has
information about $\mathbf{m}_{3}$ on $\mathcal{E}_{j}$, then if if
$\iota\overset{unif}{\sim}\\{-1,1\\}$, it holds that

$\displaystyle\operatorname{\mathbb{E}}_{\iota\sim\\{-1,1\\}}\mathbb{P}_{j,\iota}[|\hat{\mathbf{m}}_{T}-\mathbf{m}_{3}|\geq
m\mid\mathcal{E}_{j}]\geq\min_{\mu\in\mathbb{R}}\mathbb{P}_{\iota}[|\iota
m-\mu|\geq m]=\frac{1}{2}$

Thus,

$\displaystyle\sup_{j,\iota}\mathbb{P}_{j,\iota}[|\hat{\mathbf{m}}_{T}-\mathbf{m}_{3}|\geq
m]\geq\frac{1}{2}\sup_{j,\iota}\mathbb{P}_{j,\iota}[\mathcal{E}_{j}]$

Introduce a new measure $\mathbb{P}_{0}$ where the dynamics are given by

$\displaystyle\mathbf{x}_{t+1}=\mathbf{u}_{t}+\mathbf{w}_{t},\quad\mathbf{w}_{t}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{D}.$

We observe that on
$\mathbb{P}_{j,\iota}[\mathcal{E}_{j}]=\mathbb{P}_{0}[\mathcal{E}_{j}]$,
because on $\mathcal{E}_{j}$ the learner has never visited region $i=3$ where
$\bm{}{i_{t}}\neq 0$. Hence,

$\displaystyle\sup_{j,\iota}\mathbb{P}_{j,\iota}[|\hat{\mathbf{m}}_{T}-\mathbf{m}_{3}|\geq
m]\geq\frac{1}{2}\sup_{j}\mathbb{P}_{0}[\mathcal{E}_{j}]$
$\displaystyle=\frac{1}{2}\left(1-\min_{j}\mathbb{P}_{0}[\mathcal{E}_{j}^{c}]\right)\geq\frac{1}{2}\left(1-\min_{j}\sum_{t=1}^{T}\mathbb{P}_{0}[\mathcal{E}_{j,t}^{c}]\right).$

Observe that $\mathcal{E}_{j,t}^{c}:=\\{\mathbf{u}_{t}\in\mathbb{R}_{j}\\}$.
As $\mathcal{R}_{2\ell}\cap\mathcal{R}_{2(\ell+1)}$ are disjoint for
$\ell\in\mathbb{N}$, it holds that $\mathcal{E}_{2\ell,t}^{c}$ are disjoint
events for $\ell\in\mathbb{N}$. Upper bound bounding minimum by average on any
subset, we have

$\displaystyle\min_{j}\mathbb{P}_{0}[\mathcal{E}_{j,t}^{c}]\leq\frac{1}{N}\sum_{\ell=1}^{N}\mathbb{P}_{0}[\mathcal{E}_{2\ell+1,t}^{c}]\overset{(i)}{=}\frac{1}{N}\mathbb{P}_{0}[\bigcup_{\ell=1}^{N}\mathcal{E}_{2\ell+1,t}^{c}]\leq
1/N,$

where $(i)$ uses disjointness of the events $\mathcal{E}_{2\ell,t}$ as argued
above. Thus, continuing from the second-to-last display, we have

$\displaystyle\sup_{j,\iota}\mathbb{P}_{j,\iota}[|\hat{\mathbf{m}}_{T}-\mathbf{m}_{3}|\geq
m]\geq\frac{1}{2}\left(1-\frac{T}{N}\right).$

∎

###  Appendix C Properties of Smoothness

####  C.1 Directional Smoothness of Gaussians and Uniform Distributions

######  Lemma C.1.

Let $\mathbf{w}$ be distributed as a centred Gaussian with covariance
$\sigma^{2}\mathbf{I}$ in $\mathbb{R}^{d}$. Then for any
$\mathbf{z}\in\mathbb{R}^{d}$, if $\mathbf{w}$ is independent of $\mathbf{z}$,
it holds that $\mathbf{x}=\mathbf{z}+\mathbf{w}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth, with
$\sigma_{\mathrm{dir}}=\sqrt{2\pi}\sigma$.

###### Proof.

Fix some $\mathbf{u}\in\mathcal{S}^{d-1}$ and $c\in\mathbb{R}$. Then note that

$\displaystyle\mathbb{P}\left(\left|\left\langle\mathbf{x},\mathbf{u}\right\rangle-c\right|<\delta\right)$
$\displaystyle=\mathbb{P}\left(\left|\left\langle\mathbf{w},\mathbf{u}\right\rangle-\left(-\left\langle\mathbf{z},\mathbf{u}\right\rangle+c\right)\right|<\delta\right)$
$\displaystyle=\mathbb{P}\left(\left|\left\langle\mathbf{w},\mathbf{u}\right\rangle-c^{\prime}\right|<\delta\right)$
$\displaystyle\leq\frac{\delta}{\sqrt{2\pi}\sigma},$

where the last inequality follows by the fact that
$\left\langle\mathbf{w},\mathbf{u}\right\rangle$ is distributed as a centred
univarate Gaussian with variance $\sigma^{2}$ and the fact that such a
distribution has density upper bounded by $\frac{1}{\sqrt{2\pi}\sigma}$. The
result follows. ∎

######  Lemma C.2.

Let $\mathbf{w}$ be uniform on a centred Euclidean ball of radius $\sigma$.
Then for any $\mathbf{z}\in\mathbb{R}^{d}$, if $\mathbf{w}$ is independent of
$\mathbf{z}$, it holds that $\mathbf{x}=\mathbf{z}+\mathbf{w}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth, with
$\sigma_{\mathrm{dir}}\geq\frac{\sigma}{2}$.

###### Proof.

Let $\mathbf{v}$ denote a point sampled uniformly from the unit Euclidean ball
and note that $\mathbf{w}\stackrel{{\scriptstyle d}}{{=}}\sigma\mathbf{v}$. We
then have for any $\mathbf{u}\in\mathcal{S}^{d-1}$,

$\displaystyle\mathbb{P}\left(\left|\left\langle\mathbf{w},\mathbf{u}\right\rangle-c^{\prime}\right|<\delta\right)$
$\displaystyle=\mathbb{P}\left(\left|\left\langle\mathbf{v},\mathbf{u}\right\rangle-c\right|<\frac{\delta}{\sigma}\right).$

Let $A=\left(c-\frac{\delta}{\sigma},c+\frac{\delta}{\sigma}\right)$ and let
$\phi:\mathbb{R}^{d}\to\mathbb{R}$ be defined so that
$\phi(\mathbf{v})=\left\langle\mathbf{v},\mathbf{u}\right\rangle$. We note
that $D\phi=\mathbf{u}^{T}$ and thus $\det\left(D\phi D\phi^{T}\right)=1$
uniformly. Using the co-area formula [Federer, 2014], we see that

$\displaystyle\mathbb{P}\left(\left|\left\langle\mathbf{v},\mathbf{u}\right\rangle-c\right|<\frac{\delta}{\sigma}\right)$
$\displaystyle=\int_{\phi^{-1}(A)}d\operatorname{vol}_{d}(\mathbf{v})$
$\displaystyle=\int_{\phi^{-1}(A)}\sqrt{\det\left(D\phi(\mathbf{v})D\phi(\mathbf{v})^{T}\right)}d\operatorname{vol}_{d}(\mathbf{v})$
$\displaystyle=\int_{A}\operatorname{vol}_{d-1}\left(\phi^{-1}(y)\right)dy$
$\displaystyle\leq\left(\sup_{y\in
A}\operatorname{vol}_{d-1}\left(\phi^{-1}(y)\right)\right)\int_{c-\frac{\delta}{\sigma}}^{c+\frac{\delta}{\sigma}}dy$
$\displaystyle\leq\frac{2\delta}{\sigma}.$

The result follows. ∎

####  C.2 Directional Smoothness Equivalent to Lebesgue Density

######  Lemma C.3.

Let $\mathbf{x}\in\mathbb{R}^{d}$ be a (Borel-measurable) random vector. Then,
$\mathbf{x}$ is $\sigma_{\mathrm{dir}}$-smooth if and only if, for any
$\mathbf{w}\in\mathcal{S}^{d-1}$, $\langle\mathbf{w},\mathbf{x}\rangle$ admits
a density $p(\cdot)$ with respect to the Lebesgue measure on $\mathbb{R}$ with
$\operatorname{ess\,sup}_{v\in\mathbb{R}}p(v)\leq 2/\sigma_{\mathrm{dir}}$.

###### Proof.

The “if” direction is immediate. For the converse, let $\mu(B)$ denote the
Lebesgue measure of a Borel set $B\subset\mathbb{R}$. We observe that
$\sigma_{\mathrm{dir}}$-smoothness proves that for any interval
$I=(a,b])\subset\mathbb{R}$,
$\mathbb{P}[\langle\mathbf{w},\mathbf{x}\rangle\in
I]\leq\sigma_{\mathrm{dir}}\mu(I)/2$ (consider $c=(a+b)/2$ and
$\delta=|b-a|/2$). Since the Borel sigma-algebra is the generated by open
intervals, this implies that for any Borel subset $B$ of $\mathbb{R}$,
$\mathbb{P}[\langle\mathbf{w},\mathbf{x}\rangle\in B]\leq
2\mu(B)/\sigma_{\mathrm{dir}}$, where $\mu(\cdot)$ denotes the Lebesgue
measure. Thus we see that the law of
$\left\langle\mathbf{w},\mathbf{x}\right\rangle$ is absolutely continuous with
respect to the Lebesgue measure and, by definition of the Radon-Nikodym
derivative, there exists some $p$ such that for all Borel $B$, it holds that

$\displaystyle\mathbb{P}\left(\left\langle\mathbf{w},\mathbf{x}\right\rangle\in
B\right)=\int_{B}p(a)da.$

Now, let

$\displaystyle B=\left\\{a|p(a)>\frac{2}{\sigma_{\mathrm{dir}}}\right\\}$

and note that

$\displaystyle\mathbb{P}\left(\left\langle\mathbf{w},\mathbf{x}\right\rangle\in
B\right)$
$\displaystyle=\int_{B}p(a)da>\frac{2}{\sigma_{\mathrm{dir}}}\cdot\mu(B).$

Combining this with the fact that
$\mathbb{P}\left(\left\langle\mathbf{w},\mathbf{x}\right\rangle\in
B\right)\leq\frac{2\mu(B)}{\sigma_{\mathrm{dir}}}$, we see that $\mu(B)=0$ and
the result holds. ∎

####  C.3 Concatenation Preserves Directional Smoothness

######  Lemma C.4.

Let $\mathbf{x}_{1}\in\mathbb{R}^{d_{1}}$ and
$\mathbf{x}_{2}\in\mathbb{R}^{d_{2}}$ be two random vectors such that
$\mathbf{x}_{1}\mid\mathbf{x}_{2}$ and $\mathbf{x}_{2}\mid\mathbf{x}_{1}$ are
both $\sigma_{\mathrm{dir}}$-directionally smooth. Then, the concatenated
vector $\tilde{\mathbf{x}}=(\mathbf{x}_{1},\mathbf{x}_{2})$ is
$\frac{\sigma_{\mathrm{dir}}}{\sqrt{2}}$-directionally smooth.

###### Proof.

Fix
$\tilde{\mathbf{w}}=(\mathbf{w}_{1},\mathbf{w}_{2})\in\mathbb{R}^{d_{1}+d_{2}}$
with $\|\tilde{\mathbf{w}}\|=1$. Set $\alpha_{1}:=\|\mathbf{w}_{1}\|$ and
$\alpha_{2}=\|\mathbf{w}_{2}\|$. Assume without loss of generality that
$\alpha_{1}\geq\alpha_{2}$, so then necessarily $\alpha_{1}\geq 1/\sqrt{2}$.
Then,

$\displaystyle\mathbb{P}[|\langle\tilde{}\mathbf{w},\tilde{}\mathbf{x}\rangle-c|<\delta]$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathbf{w}_{2}}\mathbb{P}[|\langle\tilde{}\mathbf{w},\tilde{}\mathbf{x}\rangle-c|<\delta\mid\mathbf{w}_{2}]$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathbf{w}_{2}}\mathbb{P}\left[\left|\langle\mathbf{w}_{1},\mathbf{x}_{1}\rangle-(c-\langle\mathbf{w}_{2},\mathbf{x}_{2}\rangle)\right|<\delta\mid\mathbf{w}_{2}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathbf{w}_{2}}\mathbb{P}\left[\left|\langle\frac{1}{\alpha_{1}}\mathbf{w}_{1},\mathbf{x}_{1}\rangle-\frac{1}{\alpha_{1}}(c-\langle\mathbf{w}_{2},\mathbf{x}_{2}\rangle)\right|<\frac{\delta}{\alpha_{1}}\mid\mathbf{w}_{2}\right]\leq\frac{\delta}{\sigma_{\mathrm{dir}}\alpha_{1}}\leq\frac{\sqrt{2}\delta}{\sigma_{\mathrm{dir}}}.$

The bound follows. ∎

######  Lemma C.5.

Let $\mathbf{z}\in\mathbb{R}^{d_{1}}$ and
$\mathbf{u},\mathbf{v}\in\mathbb{R}^{d_{2}}$ be random vectors such that
$\mathbf{z}\mid\mathbf{v}$ is $\sigma_{\mathrm{dir}}$-directionally smooth,
$\mathbf{v}\mid\mathbf{z}$ is $\sigma_{\mathrm{dir}}$-directionally smooth,
and $\mathbf{u}=\mathbf{K}\mathbf{z}+\mathbf{v}$. Then, the concatenated
vector $\mathbf{x}=(\mathbf{z},\mathbf{u})$ is
$\sigma_{\mathrm{dir}}/\sqrt{(1+\|\mathbf{K}\|_{\mathrm{op}})^{2}+1}$-smooth.

###### Proof.

Fix
$\bar{\mathbf{w}}=(\mathbf{w}_{1},\mathbf{w}_{2})\in\mathbb{R}^{d_{1}+d_{2}}$
such that $\|\bar{\mathbf{w}}\|=1$. Then,

$\displaystyle\langle\bar{\mathbf{w}},\mathbf{x}\rangle$
$\displaystyle=\langle\mathbf{w}_{1},\mathbf{z}\rangle+\langle\mathbf{w}_{2},\mathbf{K}\mathbf{z}\rangle+\langle\mathbf{w}_{2},\mathbf{v}\rangle$
$\displaystyle=\langle\mathbf{w}_{1}+\mathbf{K}^{\top}\mathbf{w}_{2},\mathbf{z}\rangle+\langle\mathbf{w}_{2},\mathbf{v}\rangle.$

Define $\alpha_{1}:=\|\mathbf{w}_{1}+\mathbf{K}^{\top}\mathbf{w}_{2}\|$,
$\alpha_{2}:=\|\mathbf{w}_{2}\|$, and
$X_{1}:=\langle\mathbf{w}_{1}+\mathbf{K}^{\top}\mathbf{w}_{2},\mathbf{z}\rangle$
and $X_{2}:=\langle\mathbf{w}_{2},\mathbf{v}\rangle$. $\mathbf{X}_{1}$
dependends only on $z$ and $\mathbf{X}_{2}$ only on $v$. Hence, $X_{1}\mid
X_{2}$ is $\alpha_{1}\sigma_{\mathrm{dir}}$ smooth and $X_{2}\mid X_{1}$ is
$\alpha_{2}\sigma_{\mathrm{dir}}$ smooth. It follows that

$\displaystyle\mathbb{P}[|X_{1}+X_{2}-c|\leq\delta]$
$\displaystyle=\operatorname{\mathbb{E}}_{X_{1}}\mathbb{P}[|X_{1}+X_{2}-c|\leq\delta\mid
X_{1}]\leq\frac{\delta}{\sigma_{\mathrm{dir}}\alpha_{2}},$

and so my symmetry under labels $i=1,2$,

$\displaystyle\mathbb{P}[|\langle\tilde{}\mathbf{w},\mathbf{x}\rangle-c|\leq\delta]=\mathbb{P}[|X_{1}+X_{2}-c|\leq\delta]\leq\min\left\\{\frac{1}{\alpha_{1}},\frac{1}{\alpha_{2}}\right\\}\frac{\delta}{\sigma_{\mathrm{dir}}}=\frac{1}{\max\\{\alpha_{1},\alpha_{2}\\}}\cdot\frac{\delta}{\sigma_{\mathrm{dir}}}.$

We continue by bounding

$\displaystyle\max\\{\alpha_{1},\alpha_{2}\\}$
$\displaystyle=\max\\{\|\mathbf{w}_{1}+\mathbf{K}^{\top}\mathbf{w}_{2}\|,\|\mathbf{w}_{2}\|\\}$
$\displaystyle\geq\max\\{\|\mathbf{w}\|_{1}-\|\mathbf{K}\|_{\mathrm{op}}\|\mathbf{w}_{2}\|,\|\mathbf{w}_{2}\|\\}$
$\displaystyle=\min_{\alpha\in[0,1]}\max\\{\sqrt{1-\alpha^{2}}-\|\mathbf{K}\|_{\mathrm{op}}\alpha,\,\alpha\\}.$
($\|\mathbf{w}_{1}\|^{2}+\|\mathbf{w}_{2}\|^{2}=1$)

The above is minimized when
$\sqrt{1-\alpha^{2}}-\|\mathbf{K}\|_{\mathrm{op}}\alpha=\alpha$, so that
$\alpha^{2}(1+\|\mathbf{K}\|_{\mathrm{op}})^{2}=1-\alpha^{2}$, yielding
$\alpha=1/\sqrt{(1+\|\mathbf{K}\|_{\mathrm{op}})^{2}+1}$. Hence,
$\max\\{\alpha_{1},\alpha_{2}\\}\geq
1/\sqrt{(1+\|\mathbf{K}\|_{\mathrm{op}})^{2}+1}$. The bound follows.

∎

####  C.4 Smoothness of Parameters Induces Separation

In this section, we show that if the true parameters
$\mathbf{\Theta}^{\star}_{i}$ are taken from a smooth distribution, then with
high probability Assumption 5 is satisfied with $\Delta_{\mathrm{sep}}$ not
too small. In particular, we have the following result:

######  Proposition 11.

Suppose that $(\mathbf{\Theta}^{\star}_{1},\dots,\mathbf{\Theta}^{\star}_{K})$
are sampled from a joint distribution on the $K$-fold product of the
Frobenius-norm ball of radius $R$ in $\mathbb{R}^{m\times d}$. Suppose that
the distribution of
$(\mathbf{\Theta}^{\star}_{1},\dots,\mathbf{\Theta}^{\star}_{K})$ is such that
for all $1\leq i<j\leq K$, the distribution of $\mathbf{\Theta}^{\star}_{j}$
conditioned on the value of $\mathbf{\Theta}^{\star}_{i}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth. Then, with probability at least
$1-\delta$, Assumption 5 is satisfied with

$\displaystyle\Delta_{\mathrm{sep}}\geq\frac{md}{4\sqrt{\pi}}\cdot\left(\frac{\sigma_{\mathrm{dir}}\delta}{K^{2}}\right)^{\frac{1}{md}}.$

###### Proof.

By a union bound, we have

$\displaystyle\mathbb{P}\left(\min_{1\leq i<j\leq
K}\|\mathbf{\Theta}^{\star}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}<\Delta_{\mathrm{sep}}\right)$
$\displaystyle\leq K^{2}\max_{1\leq i<j\leq
K}\mathbb{P}\left(\|\mathbf{\Theta}^{\star}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}<\Delta_{\mathrm{sep}}\right)$
$\displaystyle=K^{2}\max_{1\leq i<j\leq
K}\mathbb{E}_{\mathbf{\Theta}^{\star}_{i}}\left[\mathbb{P}\left(\|\widehat{\mathbf{\Theta}}_{i}-\widehat{\mathbf{\Theta}}_{j}\|_{\mathrm{F}}<\Delta_{\mathrm{sep}}|\mathbf{\Theta}^{\star}_{i}\right)\right]$
$\displaystyle\leq
K^{2}\sup_{\mathbf{\Theta}^{\star}_{i}\in\mathbb{R}^{m\times
d}}\mathbb{P}\left(\|\mathbf{\Theta}^{\star}_{j}-\mathbf{\Theta}^{\star}_{i}\|_{\mathrm{F}}<\Delta_{\mathrm{sep}}|\mathbf{\Theta}^{\star}_{i}\right)$
$\displaystyle\leq
K^{2}\cdot\frac{\operatorname{vol}\left(\mathcal{B}_{\Delta_{\mathrm{sep}}}^{md}\right)}{\sigma_{\mathrm{dir}}},$

where $\mathcal{B}_{\Delta_{\mathrm{sep}}}^{md}$ denotes the Euclidean ball in
$\mathbb{R}^{m\times d}$ of radius $\Delta_{\mathrm{sep}}$ and the last
inequality follows by the smoothness assumption. Note that

$\displaystyle\operatorname{vol}\left(\mathcal{B}_{\Delta_{\mathrm{sep}}}^{md}\right)=\frac{\pi^{\frac{md}{2}}}{\Gamma\left(\frac{md}{2}+1\right)}\cdot\Delta_{\mathrm{sep}}^{md}$

and thus

$\displaystyle\mathbb{P}\left(\min_{1\leq i<j\leq
K}\|\mathbf{\Theta}^{\star}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}<\Delta_{\mathrm{sep}}\right)\leq\frac{K^{2}\pi^{\frac{md}{2}}\Delta_{\mathrm{sep}}^{md}}{\sigma_{\mathrm{dir}}\cdot\Gamma\left(\frac{md}{2}+1\right)}.$

Noting that $\Gamma\left(\frac{md}{2}+1\right)^{\frac{1}{md}}\geq\frac{md}{4}$
concludes the proof. ∎

##  Part II Supporting Proofs

###  Appendix D Parameter Recovery

In this section, we fix $\tau$ and let
$\left\\{\widehat{\mathbf{\Theta}}_{i}|i\in[K]\right\\},\widehat{g}$ denote
the output of $\textsc{ErmOracle}(\bar{\mathbf{x}}_{1:\tau
E},\mathbf{y}_{1:\tau E})$. For any $g\in\mathcal{G}$ and $i,j\in[K]$, we
denote

$I_{ij}(g)=\left\\{1\leq t\leq\tau E|g(\bar{\mathbf{x}}_{t})=i\text{ and
}g_{\star}(\bar{\mathbf{x}}_{t})=j\right\\}.$ (D.1)

We will show the following result:

######  Theorem 12 (Parameter Recovery).

Suppose that Assumptions 2-4 hold. Then there is a universal constant $C$ such
that for any tunable parameter $\xi\in(0,1)$ (which appears in the analysis
but not in the algorithm), with probability at least $1-\delta$, it holds for
all $1\leq i,j\leq K$ satisfying

$\displaystyle\left|I_{ij}(\widehat{g})\right|\geq
CK^{2}T\xi+C\frac{B^{8}Kd}{\sigma_{\mathrm{dir}}^{8}\xi^{8}}\log\left(\frac{BKT}{\sigma_{\mathrm{dir}}\xi\delta}\right),$

it holds that

$\displaystyle\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}^{2}\leq
C\frac{B^{2}}{\sigma_{\mathrm{dir}}^{2}\xi^{2}\left|I_{ij}(\widehat{g})\right|}\left(\varepsilon_{\mathrm{orac}}+1+K^{3}B^{2}R^{2}d^{2}m\nu^{2}\sqrt{T}\log\left(\frac{TRBmdK}{\delta}\right)\right)+4BRK^{2}\frac{1}{\left|I_{ij}(g)\right|}\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|$

We refer the reader to the notation table in Appendix A for a reminder about
the parameters. We begin by defining for any $i,j\in[K]$ and
$g\in\mathcal{G}$,

$\Sigma_{ij}(g)=\sum_{\begin{subarray}{c}1\leq t\leq\tau E\\\ t\in
I_{ij}(g)\end{subarray}}\bar{\mathbf{x}}_{t}\bar{\mathbf{x}}_{t}^{T},$

the empirical covariance matrix on those $t\in I_{ij}(g)$. We will first show
that for a fixed $g$, $\Sigma_{ij}(g)\succeq cI$ for a sufficiently small $c$
depending on problem parameters. We will then introduce a complexity notion we
call a disagreement cover that will allow us to lift this statement to one
uniform in $\mathcal{G}$, which will imply that
$\Sigma_{ij}(\widehat{g})\succeq cI$. We will then use the definition of
ErmOracle to show that
$\sum_{t}\|(\widehat{\mathbf{\Theta}}_{\widehat{g}(\bar{\mathbf{x}}_{t})}-\mathbf{\Theta}^{\star}_{g_{\star}(\bar{\mathbf{x}}_{t})})\bar{\mathbf{x}}_{t}\|_{\mathrm{F}}^{2}$
is small and the theorem will follow.

For the entirety of the proof and without loss of generality, we will assume
that $T/E\in\mathbb{Z}$. Indeed, if $T$ is not a multiple of $E$ then we
suffer regret at most $O(E)$ on the last episode, which we will see does not
adversely affect our rates.

####  D.1 Disagreement Covers

We begin by introducing a notion of complexity we call a disagreement cover;
in contrast to standard $\varepsilon$-nets, we show below that the
disagreement cover provides more uniform notion of coverage. Moreover, we then
show that the size of a disagreement cover of $\mathcal{G}$ can be controlled
under the assumption of directional smoothness.

######  Definition 13.

Let
$\mathscr{D}=\left\\{\left(g_{i},\mathscr{D}_{i}\right)|g_{i}\in\mathcal{G}\text{
and }\mathscr{D}_{i}\subset\mathbb{R}^{d}\right\\}$. We say that $\mathscr{D}$
is an _$\varepsilon$ -disagrement cover_ if the following two properties hold:

  1. 1.

For every $g\in\mathcal{G}$, there exists some $i$ such that
$(g_{i},\mathscr{D}_{i})\in\mathscr{D}$ and
$\left\\{\mathbf{x}\in\mathbb{R}^{d}|g_{i}(\mathbf{x})\neq
g(\mathbf{x})\right\\}\subset\mathscr{D}_{i}$.

  2. 2.

For all $i$ and $t$, it holds that
$\mathbb{P}\left(\mathbf{x}_{t}\in\mathscr{D}_{i}\mid\mathscr{F}_{t-1}\right)\leq\varepsilon$

We will denote by $\textsc{DN}(\mathcal{G},\varepsilon)$ (or
$\textsc{DN}(\varepsilon)$ when $\mathcal{G}$ is clear from context) the
minimal size of an $\varepsilon$-disagreement cover of $\mathcal{G}$.

We remark that a disagreement cover is stronger than the more classical notion
of an $\varepsilon$-net because the sets of points where multiple different
functions $g$ disagree with a single element of the cover $g_{i}$ has to be
contained in a single set. With an $\varepsilon$-net, there is nothing
stopping the existence of an $i$ such that the set of points on which at least
one $g$ satisfying $\mathbb{P}(g_{i}\neq g)\leq\varepsilon$ is the entire
space. The reason that this uniformity is necessary is to provide the
following bound:

######  Lemma D.1.

Let $\mathscr{D}$ be an $\varepsilon$-disagreement cover for $\mathcal{G}$.
Then, with probability at least $1-\delta$, it holds that

$\displaystyle\sup_{g\in\mathcal{G}}\min_{(g_{i},\mathscr{D}_{i})\in\mathscr{D}}\sum_{t=1}^{T}\mathbb{I}\left[g(\mathbf{x}_{t})\neq
g_{i}(\mathbf{x}_{t})\right]\leq
2T\varepsilon+6\log\left(\frac{\left|\mathscr{D}\right|}{\delta}\right).$

###### Proof.

Note that by the definition of a disagreement cover, it holds that

$\displaystyle\sup_{g\in\mathcal{G}}\min_{(g_{i},\mathscr{D}_{i})\in\mathscr{D}}\sum_{t=1}^{T}\mathbb{I}\left[g(\mathbf{x}_{t})\neq
g_{i}(\mathbf{x}_{t})\right]\leq\max_{(g_{i},\mathscr{D}_{i})\in\mathscr{D}}\sum_{t=1}^{T}\mathbb{I}\left[\mathbf{x}_{t}\in\mathscr{D}_{i}\right].$

Note that for any fixed $i$, it holds that
$\mathbb{P}\left(\mathbf{x}_{t}\in\mathscr{D}_{i}|\mathscr{F}_{t-1}\right)\leq\varepsilon$,
also by construction. Applying a Chernoff bound (Lemma D.2), we see that

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}\mathbb{I}\left[\mathbf{x}_{t}\in\mathscr{D}_{i}\right]\geq
2T\varepsilon+6\log\left(\frac{1}{\delta}\right)\right)$
$\displaystyle\leq\delta.$

Taking a union bound over $\mathscr{D}_{i}\in\mathscr{D}$ concludes the proof.
∎

For the sake of completeness, we state and prove the standard Chernoff Bound
with dependent data used in the previous argument:

######  Lemma D.2 (Chernoff Bound).

Suppose that $X_{1},\dots,X_{T}$ are random variables such that
$X_{t}\in\left\\{0,1\right\\}$ for all $1\leq t\leq T$. Suppose that there
exist $p_{t}$ such that $\mathbb{P}\left(X_{t}=1|\mathscr{F}_{t-1}\right)\leq
p_{t}$ almost surely, where $\mathscr{F}_{t-1}$ is the $\sigma$-algebra
generated by $X_{1},\dots,X_{t-1}$. Then

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}X_{t}>2\sum_{t=1}^{T}p_{t}+\frac{1}{2}\log\left(\frac{1}{\delta}\right)\right)\leq\delta$

###### Proof.

We use the standard Laplace transform trick:

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}X_{t}>2\sum_{t=1}^{T}p_{t}+u\right)$
$\displaystyle=\mathbb{P}\left(e^{\lambda\sum_{t=1}^{T}X_{t}}>e^{2\lambda
u+2\lambda\sum_{t=1}^{T}p_{t}}\right)$ $\displaystyle\leq e^{-2\lambda
u-2\lambda\sum_{t=1}^{T}p_{t}}\cdot\mathbb{E}\left[\prod_{t=1}^{T}e^{\lambda
X_{t}}\right]$ $\displaystyle=e^{-2\lambda
u-2\lambda\sum_{t=1}^{T}p_{t}}\cdot\mathbb{E}\left[\prod_{t=1}^{T}\mathbb{E}\left[e^{\lambda
X_{t}}|\mathscr{F}_{t-1}\right]\right]$ $\displaystyle\leq e^{-2\lambda
u-2\lambda\sum_{t=1}^{T}p_{t}}\cdot\mathbb{E}\left[\prod_{t=1}^{T}e^{\lambda}\mathbb{P}\left(X_{t}=1|\mathscr{F}_{t-1}\right)+(1-\mathbb{P}\left(X_{t}=1|\mathscr{F}_{t-1}\right))\right]$
$\displaystyle\leq e^{-2\lambda
u-2\lambda\sum_{t=1}^{T}p_{t}}\cdot\prod_{t=1}^{T}e^{\left(e^{\lambda}-1\right)p_{t}}.$

Thus we see that

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}X_{t}>2\sum_{t=1}^{T}p_{t}+u\right)$
$\displaystyle\leq e^{-2\lambda
u+\left(e^{\lambda}-1-2\lambda\right)\sum_{t=1}^{T}p_{t}}.$

Setting $\lambda=1$ and noting that $\sum_{t=1}^{T}p_{t}>0$ tells us that

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}X_{t}>2\sum_{t=1}^{T}p_{t}+u\right)\leq
e^{-2u}$

and the result follows. ∎

Returning to the main thread, we see that Lemma D.1 allows us to uniformly
bound the approximation error of considering a disagreement cover. Before we
can apply the result, however, we need to show that this complexity notion is
small for the relevant class, $\mathcal{G}$. We have the following result:

######  Lemma D.3.

Let $\mathcal{G}$ be the set of classifiers considered above. Then it holds
that

$\displaystyle\log\left(\textsc{DN}(\mathcal{G},\varepsilon)\right)\leq
K(d+1)\log\left(\frac{3BK}{\varepsilon}\right)$

We prove the result in two parts. For the first part, we show that any
function class that is constructed by aggregating $K$ simpler classes has a
disagreement cover whose size is controlled by that of the $K$ classes:

######  Lemma D.4.

Let $\mathcal{G}_{1},\dots,\mathcal{G}_{K}$ be function classes mapping
$\mathcal{X}\to\mathcal{Y}$. Let $h:\mathcal{Y}^{\times K}\to\mathbb{R}$ be
some aggregating function and define

$\mathcal{G}=\left\\{\mathbf{x}\mapsto
h(g_{1}(\mathbf{x}),\dots,g_{K}(\mathbf{x}))\mid
g_{1}\in\mathcal{G}_{1},\dots,g_{K}\in\mathcal{G}_{K}\right\\}$

Let $\textsc{DN}(\mathcal{G}_{i},\varepsilon)$ be the minimal size of an
$\varepsilon$-disagreement cover of $\mathcal{G}_{i}$. Then

$\textsc{DN}(\mathcal{G},\varepsilon)\leq\prod_{i=1}^{K}\textsc{DN}\left(\mathcal{G}_{i},\frac{\varepsilon}{K}\right)$

###### Proof.

Suppose that $\mathscr{D}_{i}$ are
$\left(\frac{\varepsilon}{K}\right)$-disagreement covers for $\mathcal{G}_{i}$
and for any $g_{i}\in\mathcal{G}_{i}$ denote by
$(\pi(g_{i}),\mathscr{D}_{i}(g_{i}))$ the pair of functions and disagreement
sets satisfying the definition of a disagreement cover. Then we claim that

$\mathscr{D}=\left\\{\left(h(g_{1},\dots,g_{K}),\bigcup_{i}\mathscr{D}_{i}\right)|(g_{i},\mathscr{D}_{i})\in\mathscr{D}_{i}\right\\}$

is an $\varepsilon$-disagreement cover for $\mathcal{G}$. Note that
$\left|\mathscr{D}\right|$ is clearly bounded by the desired quantity so this
claim suffices to prove the result.

To prove the claim, we first note that a union bound ensures that
$\mathbb{P}(\mathbf{x}_{t}\in\bigcup_{i}\mathscr{D}_{i}\mid\mathscr{F}_{t-1})\leq\varepsilon$.
We further note that if $g=h(g_{1},\dots,g_{K})$ then

$\displaystyle\left\\{\mathbf{x}\mid g(\mathbf{x})\neq
h(\pi(g_{1}(\mathbf{x})),\dots,\pi(g_{K}(\mathbf{x})))\right\\}$
$\displaystyle\subset\bigcup_{1\leq i\leq K}\left\\{\mathbf{x}\mid
g_{i}(\mathbf{x})\neq\pi(g_{i}(\mathbf{x}))\right\\}\subset\bigcup_{1\leq
i\leq K}\mathscr{D}_{i}(g_{i}).$

The result follows. ∎

We now prove that the class of linear threshold functions has bounded
disagreement cover:

######  Lemma D.5.

Let $\mathcal{H}:\mathbb{R}^{d}\to\left\\{\pm 1\right\\}$ be the class of
affine thresholds given by
$\mathbf{x}\mapsto\operatorname{sign}(\left\langle\mathbf{w},\mathbf{x}\right\rangle+b)$
for some $\mathbf{w}\in B^{d}$ and some $b\in[-B,B]$. Then

$\displaystyle\log\textsc{DN}(\mathcal{H},\varepsilon)\leq(d+1)\log\left(\frac{3B}{\varepsilon}\right).$

###### Proof.

We first let $\mathcal{N}:=\\{(\mathbf{w}_{i},b_{i})\\}$ denote an
$\varepsilon$-net on $\mathcal{B}^{d}\times[-B,B]$. Associate each
$(\mathbf{w}_{i},b_{i})$ to its corresponding classifier
$h_{i}(\mathbf{x})\operatorname{sign}(\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle+b_{i})$.
We claim that for each $h_{i}$, there is a region
$\mathscr{D}_{i}\subset\mathbb{R}^{d}$ such that
$\\{(h_{i},\mathscr{D}_{i})\\}$ is an $\varepsilon$-disagreement cover. To see
this, consider some $h$ with parameters $(\mathbf{w},b)$, and let $h_{i}$ with
parameters $(\mathbf{w}_{i},b_{i})$ ensure
$\left|\left|\mathbf{w}_{i}-\mathbf{w}\right|\right|+\left|b_{i}-b\right|\leq\sigma_{\mathrm{dir}}\varepsilon/B$.
Consider any $\mathbf{x}$ such that

$\displaystyle\operatorname{sign}\left(\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle+b_{i}\right)\neq\operatorname{sign}\left(\left\langle\mathbf{w},\mathbf{x}\right\rangle+b\right)$

By the continuity of affine functions, there is some $\lambda\in(0,1)$ such
that if $\mathbf{w}_{\lambda}=(1-\lambda)\mathbf{w}_{i}+\lambda\mathbf{w}$ and
$b_{\lambda}=(1-\lambda)b_{i}+\lambda b$ then

$\displaystyle\left\langle\mathbf{w}_{\lambda},\mathbf{x}\right\rangle+b_{\lambda}=0$

Note however that

$\displaystyle\left|\left\langle\mathbf{w}_{\lambda},\mathbf{x}\right\rangle+b_{\lambda}-\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle-
b_{i}\right|$
$\displaystyle\leq\lambda\left|\left\langle\mathbf{w}-\mathbf{w}_{i},\mathbf{x}\right\rangle\right|+\lambda\left|b_{i}-b\right|\leq
B\left(\frac{\sigma_{\mathrm{dir}}\varepsilon}{B}\right)\leq\sigma_{\mathrm{dir}}\varepsilon$

by the definition of our $\varepsilon$-net. Thus, let

$\mathscr{D}_{i}=\left\\{\mathbf{x}\mid\left|\left\langle\mathbf{w}_{i},\mathbf{x}\right\rangle+b\right|\leq\frac{\sigma_{\mathrm{dir}}\varepsilon}{B}\right\\}$

and note that the above computation tells us that if
$\mathbf{x}\not\in\mathscr{D}_{i}$ then $h_{i}$ must agree with
$h=(\mathbf{w},b)$ for all $h$ that are mapped to $h_{i}$ by the projection
onto the $\varepsilon$-net. Thus for all such $h$, it holds that

$\displaystyle\mathbb{P}\left(h(\mathbf{x}_{t})\neq
h_{i}(\mathbf{x}_{t})|\mathscr{F}_{t-1}\right)\leq\mathbb{P}\left(\left|\left\langle\mathbf{w}_{i},\mathbf{x}_{t}\right\rangle+b\right|\leq\frac{\sigma_{\mathrm{dir}}\varepsilon}{B}|\mathscr{F}_{t-1}\right)\leq\varepsilon.$

Thus the claim holds and we have constructed an $\varepsilon$-disagreement
cover. By noting that there are at most
$\left(\frac{3}{\varepsilon}\right)^{d}\cdot\frac{B}{\varepsilon}$ members of
this cover by a volume argument we conclude the proof. ∎

By combining Lemma D.4 and Lemma D.5, we prove Lemma D.3. In the next section,
we will apply Lemma D.3 and Lemma D.1 to lower bound
$\Sigma_{ij}(\widehat{g})$.

####  D.2 Lower Bounding the Covariance

We continue by lower bounding $\Sigma_{ij}(\widehat{g})$. Before we begin, we
introduce some notation. For any $g\in\mathcal{G}$, we will let

$\displaystyle Z_{t;ij}(g)=\mathbb{I}\left[g(\bar{\mathbf{x}}_{t})=i\text{ and
}g_{\star}(\bar{\mathbf{x}}_{t})=j\right]$
$\displaystyle\bar{Z}_{t;ij}(g)=\mathbb{E}\left[Z_{t;ij}(g)|\mathscr{F}_{t-1}\right]$

or, in words, $Z_{t;ij}(g)$ is the indicator of the event that a classifier
predicts label $i$ when $g_{\star}$ predicts $j$ and $\bar{Z}_{t;ij}(g)$ is
probability of this event conditioned on the $\mathbf{x}$-history. We will
work under the small-ball assumption that there exist constants $c_{0},c_{1}$
as well as $\zeta_{t},\rho_{t}$ such that for any
$\mathbf{w}\in\mathcal{S}^{d}$, it holds for all $g\in\mathcal{G}$ that

$\mathbb{P}\left(\left\langle\bar{\mathbf{x}}_{t},\mathbf{w}\right\rangle^{2}\geq
c_{0}\zeta_{t}^{2}\mid\mathscr{F}_{t},Z_{t;ij}(g)=1\right)\geq c_{1}\rho_{t}$
(D.2)

We will show that (D.2) holds and defer control of the values of
$\zeta_{t},\rho_{t}$ to Section D.3, but, for the sake of clarity, we take
these constants as given for now. We proceed to show that for a single
function $g$, that for all $i,j$ such that $I_{ij}(g)$ is big, it holds that
$\Sigma_{ij}(g)$ is also large. We will then apply our results in the previous
section to lift this statement to one uniform in $\mathcal{G}$. We have the
following result:

######  Lemma D.6.

Let $\rho=\min_{t}\rho_{t}$ and let $\zeta=\min_{t}\zeta_{t}$, where
$\rho_{t},\zeta_{t}$ are from (D.2). Then with probability at least
$1-\delta$, for all $1\leq i,j\leq K$ and all $g\in\mathcal{G}$ such that

$\displaystyle\left|I_{ij}(g)\right|\geq\max\left(\frac{2}{\rho^{2}}\left(\log\left(\frac{2T}{\delta}\right)+\frac{d}{2}\log\left(C\frac{B\zeta^{2}}{\rho}\right)+\log\left(K^{2}\textsc{DN}(\varepsilon)\right)\right),C\frac{B^{2}}{\zeta^{2}}\left(2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right)\right)$

it holds that

$\Sigma_{ij}(g)\succeq\frac{c_{0}\zeta^{2}}{8}\left|I_{ij}(g)\right|$

We will prove Lemma D.6 by first fixing $g\in\mathcal{G}$ and showing the
statement for the fixed $g$ and then using the results of Section D.3 to make
the statements uniform in $\mathcal{G}$. To prove the statement for a fixed
$g$, we require the following self-normalized martingale inequality:

######  Lemma D.7.

Let $\mathscr{F}_{t}$ be a filtration with $A_{t}\in\mathscr{F}_{t}$ and
$B_{t}\in\mathscr{F}_{t-1}$ for all $t$. Let

$\displaystyle
p_{A_{t}}=\mathbb{P}\left(A_{t}\mid\mathscr{F}_{t-1},\,B_{t}\right)$
$\displaystyle p_{B_{t}}=\mathbb{P}\left(B_{t}\mid\mathscr{F}_{t-1}\right)$

and suppose that $p_{A_{t}}\geq\rho$ for all $t$. Then, with probability at
least $1-\delta$,

$\sum_{t=1}^{T}\mathbb{I}[A_{t}]\mathbb{I}[B_{t}]\geq\rho\sum_{t=1}^{T}\mathbb{I}[B_{t}]-\frac{1}{2}\sqrt{2\left(\sum_{t=1}^{T}\mathbb{I}[B_{t}]\right)\log\left(\frac{2T}{\delta}\right)}$

In particular with probability at least $1-\delta$, if

$\sum_{t=1}^{T}\mathbb{I}[B_{t}]\geq\frac{2}{\rho^{2}}\log\left(\frac{2T}{\delta}\right)$

then

$\sum_{t=1}^{T}\mathbb{I}[A_{t}]\mathbb{I}[B_{t}]\geq\frac{\rho}{2}\sum_{t=1}^{T}\mathbb{I}[B_{t}]$

In order to prove Lemma D.7, we will require the following general result:

######  Lemma D.8 (Theorem 1 from Abbasi-Yadkori et al. [2011]).

Let $(u_{t})$ be predictable with respect to a filtration $(\mathscr{G}_{t})$,
and let $(e_{t})$ be such that $e_{t}\mid\mathscr{G}_{t}$ is
$\nu^{2}$-subGaussian. Then, for any fixed parameter $\lambda>0$, with
probability $1-\delta$,

$\displaystyle\left(\sum_{t=1}^{T}u_{t}e_{t}\right)^{2}\leq
2\nu^{2}\left(\lambda+\sum_{t=1}^{T}u_{t}^{2}\right)\log\frac{(1+\lambda^{-1}\sum_{t=1}^{T}u_{t}^{2})^{1/2}}{\delta}$

We now present the proof of Lemma D.7:

###### Proof of Lemma D.7.

We apply Lemma D.8 with $u_{t}=\mathbb{I}[B_{t}]$,
$e_{t}=\mathbb{I}[A_{t}]-p_{A_{t}}$, and $\mathscr{G}_{t}=\mathscr{F}_{t}$.
Noting that the latter is $\frac{1}{8}$-subGaussian because it is
conditionally mean zero and bounded in absolute value by $1$, we have with
probability at least $1-\delta$,

$\displaystyle\left|\sum_{t=1}^{T}(\mathbb{I}[A_{t}]-p_{A_{t}})\mathbb{I}[B_{t}]\right|\leq\frac{1}{2}\sqrt{\left(\lambda+\sum_{t=1}^{T}\mathbb{I}[B_{t}]\right)\log\left(\frac{\sqrt{1+\frac{\sum_{t=1}^{T}\mathbb{I}[B_{t}]}{\lambda}}}{\delta}\right)}$

Taking a union bound over $\lambda\in[T]$ and noting that
$\sum_{t=1}^{T}\mathbb{I}[B_{t}]\in[T]$ almost surely, we recover the result.
∎

We now proceed to apply Lemma D.7 to prove a version of Lemma D.6 with the
function $g\in\mathcal{G}$ fixed:

######  Lemma D.9.

Suppose that (D.2) holds and that $\rho=\min_{t}\rho_{t}$ as well as
$\zeta=\min_{t}\zeta_{t}$. For fixed $1\leq i,j\leq K$ and $g\in\mathcal{G}$,
it holds with probability at least $1-\delta$ that if

$\displaystyle\left|I_{ij}(g)\right|\geq\frac{2}{\rho^{2}}\log\left(\frac{2T}{\delta}\right)+\frac{d}{\rho^{2}}\log\left(C\frac{B\zeta^{2}}{\rho}\right)$

then

$\displaystyle\Sigma_{ij}(g)\succeq\frac{c_{0}\zeta^{2}}{4}\left|I_{ij}(g)\right|$

###### Proof.

Note that for any fixed unit vector $\mathbf{u}\in\mathcal{S}^{d-1}$, the
following holds:

$\displaystyle\mathbb{P}\left(\mathbf{u}^{T}\Sigma_{ij}(g)\mathbf{u}\leq\frac{c_{0}\rho\zeta^{2}\left|I_{ij}(g)\right|}{2}\right)\leq\mathbb{P}\left(\sum_{t=1}^{T}\mathbb{I}\left[\mathbf{u}^{T}\mathbf{x}_{t}\mathbf{x}_{t}^{T}\mathbf{u}\leq
c_{0}\zeta^{2}\right]Z_{t;ij}\leq\frac{\rho\left|I_{ij}(g)\right|}{2}\right)$

Now let $A_{t}$ denote the event that
$\left(\left\langle\mathbf{u},\mathbf{x}_{t}\right\rangle\right)^{2}\geq
c_{0}\zeta^{2}$ and let $B_{t}$ denote the event that $Z_{t;ij}=1$. Noting
that $\mathbb{P}(A_{t}|B_{t})\geq\rho$ by (D.2), we may apply Lemma D.7 and
note that $\left|I_{ij}(g)\right|$ is just the sum of the $B_{t}$ to show that
if $I_{ij}(g)$ satisfies the assumed lower bound, then

$\mathbb{P}\left(\sum_{t=1}^{T}\mathbb{I}\left[\mathbf{u}^{T}\mathbf{x}_{t}\mathbf{x}_{t}^{T}\mathbf{u}\leq
c_{0}\zeta^{2}\right]Z_{t;ij}\leq\frac{\rho\left|I_{ij}(g)\right|}{2}\right)\leq
1-\delta\exp\left(-\frac{d}{2}\log\left(C\frac{R\zeta^{2}}{\rho}\right)\right).$

Taking a union bound over an appropriately sized $\varepsilon$-net on
$\mathcal{S}^{d-1}$ to approximate $\mathbf{u}$, and applying Block and
Simchowitz [2022, Lemma 45] concludes the proof. ∎

We are now ready to prove the main result in this section, i.e., a lower bound
on $\Sigma_{ij}(\widehat{g})$:

###### Proof of Lemma D.6.

Fix $\mathscr{D}=\left\\{(g_{i},\mathscr{D}_{i})\right\\}$ an
$\varepsilon$-disagreement cover of $\mathcal{G}$ of size
$\textsc{DN}(\varepsilon)$. Taking a union bound over all $g_{i}$ in
$\mathscr{D}$ and then applying Lemma D.9 tells us that with probability at
least $1-\frac{\delta}{2}$, it holds for all $1\leq i,j\leq K$ and all
$g_{k}\in\mathscr{D}$ such that

$\displaystyle\left|I_{ij}(g)\right|\geq\frac{4}{\rho^{2}}\log\left(\frac{2TK\textsc{DN}(\varepsilon)}{\delta}\right)+\frac{d}{\rho^{2}}\log\left(C\frac{B\zeta^{2}}{\rho}\right)$

we have

$\displaystyle\Sigma_{ij}(g_{k})\succeq\frac{c_{0}\zeta^{2}}{4}\left|I_{ij}(g)\right|.$
(D.3)

Applying Lemma D.1, we see that with probability at least
$1-\frac{\delta}{2}$,

$\sup_{g\in\mathcal{G}}\min_{g_{k}\in\mathscr{D}}\sum_{t=1}^{T}\mathbb{I}\left[g(\mathbf{x}_{t})\neq
g_{k}(\mathbf{x}_{t})\right]\leq
2T\varepsilon+12\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right).$

Noting that by assumption,
$\left|\left|\mathbf{x}_{t}\mathbf{x}_{t}^{T}\right|\right|\leq B^{2}$, we see
that for any $g\in\mathcal{G}$, there is some $g_{k}\in\mathscr{D}$ such that

$\displaystyle\Sigma_{ij}(g)\succeq\Sigma_{ij}(g_{k})-B^{2}\left(4T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right).$

Thus, applying the above lower bound on $\Sigma_{ij}(g_{k})$ concludes the
proof. ∎

Lemma D.6 has provided a lower bound on the empirical covariance matrices
under the assumption that (D.2) holds; in the next section we show that this
assumption is valid.

####  D.3 Small Ball Inequality

Introduce the shorthand
$\mathbb{P}_{t}\left(\cdot\right):=\mathbb{P}\left(\cdot\mid\mathscr{F}_{t-1}\right)$
and
$\operatorname{\mathbb{E}}_{t}\left[\cdot\right]:=\operatorname{\mathbb{E}}\left[\cdot\mid\mathscr{F}_{t-1}\right]$.
Recall from the previous section that we assumed that there are constants
$c_{0},c_{1}$ and $\zeta_{t},\rho_{t}$ such that for any
$\bar{\mathbf{w}}\in\mathcal{S}^{d}$, and any $g\in\mathcal{G}$, it holds that

$\displaystyle\mathbb{P}_{t}\left(\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}\geq
c_{0}\zeta_{t}^{2}\mid Z_{t;ij}(g)=1\right)\geq c_{1}\rho_{t}.$ (D.4)

In this section, we will show that smoothness and an assumption on
$Z_{t;ij}(g)$ suffice to guarantee that this holds. We will show the following
result:

######  Lemma D.10.

Suppose that Assumptions 4 and 2 hold. Fix a $g\in\mathcal{G}$ and $1\leq
i,j\leq K$ and suppose that

$\displaystyle\mathbb{P}_{t}\left(Z_{t;ij}(g)\right)\geq\xi.$

For all $\bar{\mathbf{w}}\in\mathcal{S}^{d}$, it holds that, for universal
constants $c_{0}$ and $c_{1}$,

$\displaystyle\mathbb{P}_{t}\left(\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}\geq
c_{0}\frac{\sigma_{\mathrm{dir}}^{2}\xi^{2}}{B^{2}}\mid
Z_{t;ij}(g)=1\right)\geq c_{1}\frac{\sigma_{\mathrm{dir}}^{4}\xi^{4}}{B^{4}}.$

We begin by defining some notation. First, we let
$\mathbb{V}_{\mathbf{x}_{t}}$ denote variance with respect to
$\mathbf{x}_{t}$, conditioned on the $\mathbf{x}$-history and $Z_{t;ij}(g)$.
That is, for some function $f$ of $\mathbf{x}_{t}$, we let

$\displaystyle\mathbb{V}_{\mathbf{x}_{t}}\left[f\right]=\mathbb{E}_{t}\left[f(\mathbf{x}_{t})^{2}\mid
Z_{t;ij}(g)\right]-\mathbb{E}_{t}\left[f(\mathbf{x}_{t})\mid
Z_{t;ij}(g)\right]^{2}.$ (D.5)

For a fixed $\bar{\mathbf{w}}\in\mathcal{S}^{d}$, denote by $\mathbf{w}$ the
first $d$ coordinates. For fixed $g\in\mathcal{G}$, and $1\leq i,j\leq K$, we
will denote:

$\displaystyle\rho_{t}(g,\bar{\mathbf{w}})$
$\displaystyle=\left(\frac{\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]}{\left|\left|\mathbf{w}\right|\right|^{2}\vee\left(\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]\right)}\right)^{2}\cdot\frac{1}{32\left(1+\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{4}\mid
Z_{t;ij}(g)=1\right]\right)}$ $\displaystyle\zeta_{t}^{2}(g,\bar{\mathbf{w}})$
$\displaystyle=\frac{\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]}{\left|\left|\mathbf{w}\right|\right|^{2}\vee\left(\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]\right)}.$

We will now show the following result:

######  Lemma D.11.

It holds for any fixed $1\leq i,j\leq K$ and $g\in\mathcal{G}$ that

$\displaystyle\mathbb{P}_{t}\left(\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}\geq
c_{0}\zeta_{t}^{2}(g,\bar{\mathbf{w}})Z_{t;ij}(g)=1\right)\geq
c_{1}\rho_{t}(g,\bar{\mathbf{w}})$

After proving Lemma D.11, we will provide lower bounds on $\zeta_{t}$ and
$\rho_{t}$ under the assumptions of Lemma D.10, which will allow us to prove
the main result. To begin the proof of Lemma D.11, we will begin by showing
that $\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}$ is
lower bounded in expectation in the following result:

######  Lemma D.12.

Suppose that Assumptions refass:dirsmooth and 4 hold. Then for any fixed
$1\leq i,j\leq K$ and $g\in\mathcal{G}$, it holds for all
$\mathbf{w}\in\mathcal{S}^{d}$ that

$\displaystyle\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}\mid
Z_{t;ij}(g)\right]\geq\zeta_{t}^{2}(g,\bar{\mathbf{w}})$

###### Proof.

We prove two distinct lower bounds and then combine them. Fix $i,j,g$, and
$\bar{\mathbf{w}}$. Recall that $\mathbf{w}$ is $\bar{\mathbf{w}}$ without its
last coordinate and let $w_{0}$ denote the last coordinate of
$\bar{\mathbf{w}}$. We compute:

$\displaystyle\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]$
$\displaystyle=\mathbb{E}_{t}\left[\left(w_{0}+\left\langle\mathbf{x}_{t},\mathbf{w}_{t}\right\rangle\right)^{2}\mid
Z_{t;ij}(g)=1\right]$
$\displaystyle\geq\mathbb{V}_{\mathbf{x}_{t}}\left[w_{0}+\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]$

where the equality comes from noting that the last coordinate of
$\bar{\mathbf{x}}_{t}$ is 1 by construction, the inequality is trivial. This
is our first lower bound. For our second lower bound, we compute:

$\displaystyle\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]$
$\displaystyle=\mathbb{E}_{t}\left[\left(w_{0}+\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right)^{2}\mid
Z_{t;ij}(g)=1\right]$
$\displaystyle\geq\frac{w_{0}^{2}}{2}-\mathbb{E}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]$

where the inequality follows from applying the numerical inequality
$2(x+y)^{2}\geq x^{2}-2y^{2}$. This is our second lwoer bound. To ease
notation, denote

$\displaystyle\alpha=\frac{\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{2}|Z_{t;ij}(g)=1\right]}{\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]}\geq
1.$

Combining the two previous lower bounds, we see that

$\displaystyle\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]$
$\displaystyle\geq\max\left(\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right],\frac{w_{0}^{2}}{2}-2\alpha\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]\right)$
$\displaystyle\geq\max_{0\leq\lambda\leq
1}\left\\{(1-\lambda)\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]+\lambda\frac{w_{0}^{2}}{2}-2\lambda\alpha\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]\right\\}$
$\displaystyle=\max_{0\leq\lambda\leq
1}\left\\{\left(1-\lambda-2\alpha\lambda\right)\mathbb{V}_{\mathbf{u}_{t}}\left[\left\langle\mathbf{u}_{t},\mathbf{w}\right\rangle\right]+\lambda\frac{w_{0}^{2}}{2}\right\\}$
$\displaystyle\geq\max_{0\leq\alpha\leq
1}\left\\{(1-3\alpha\lambda)\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]+\lambda\frac{w_{0}^{2}}{2}\right\\}$
$\displaystyle\geq\left(1-\frac{3\alpha}{6\alpha}\right)\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]+\frac{1}{12\alpha}w_{0}^{2}$
$\displaystyle=\frac{1}{2}\left|\left|\mathbf{w}\right|\right|^{2}\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\frac{\mathbf{w}}{\left|\left|\mathbf{w}\right|\right|}\right\rangle\right]+\frac{w_{0}^{2}}{2}\cdot\frac{1}{6\alpha}$
$\displaystyle\geq\frac{1}{2}\left(\left|\left|\mathbf{w}\right|\right|^{2}+w_{0}^{2}\right)\min\left(\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\frac{\mathbf{w}}{\left|\left|\mathbf{w}\right|\right|}\right\rangle\right],\frac{1}{6\alpha}\right)$
$\displaystyle=\frac{1}{2}\min\left(\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\frac{\mathbf{w}}{\left|\left|\mathbf{w}\right|\right|}\right\rangle\right],\frac{\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]}{6\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]}\right),$

where the third inequality follows because $\alpha\geq 1$ and the last
equality follows because
$1=\left|\left|\bar{\mathbf{w}}\right|\right|^{2}=\left|\left|\mathbf{w}\right|\right|^{2}+w_{0}^{2}$.
The result follows. ∎

We now are prepared to use the Paley-Zygmund inequality to prove the lower
bound depending on $\rho_{t}$ and $\zeta_{t}$:

###### Proof of Lemma D.11.

We apply the Paley-Zygmund inequality and note that

$\displaystyle\mathbb{P}_{t}\left(\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{2}\geq\frac{\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]}{2}\mid Z_{t;ij}(g)=1\right)$
$\displaystyle\geq\frac{\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]^{2}}{4\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{4}\mid
Z_{t;ij}(g)=1\right]}$
$\displaystyle\geq\frac{\zeta_{t}(g,\bar{\mathbf{w}})^{4}}{4\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{4}\mid
Z_{t;ij}(g)=1\right]}$

where the second inequality follows from Lemma D.12. Applying the bound in
Claim D.2, proved in a computation below for clarity, it holds that the last
line above is lower bounded by:

$\displaystyle\left(\frac{\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]}{\left|\left|\mathbf{w}\right|\right|^{2}\vee\left(\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{2}\mid
Z_{t;ij}(g)=1\right]\right)}\right)^{2}\cdot\frac{1}{32\left(1+\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{4}\mid
Z_{t;ij}(g)=1\right]\right)}.$

The result follows by the definition of $\rho_{t}(g,\bar{\mathbf{w}})$. ∎

We defer the more technical computation to the end of this section. We now
have our desired small ball result, modulo the fact that we need to lower
bound $\zeta_{t}$ and $\rho_{t}$. To do this, we have the following key result
that lower bounds the conditional variance:

######  Claim D.1.

Suppose that Assumptions 2 and 4 holds and that

$\displaystyle\mathbb{P}\left(Z_{t;ij}(g)\mid\mathscr{F}_{t-1}\right)\geq\xi.$

Then it holds for any $\mathbf{w}\in\mathcal{B}^{d}$ that

$\displaystyle\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]\geq\frac{\sigma_{\mathrm{dir}}^{2}\xi^{2}\left|\left|\mathbf{w}\right|\right|^{2}}{4}.$

In particular, it holds that

$\displaystyle\rho_{t}(g,\mathbf{w})\geq\frac{\sigma_{\mathrm{dir}}^{4}\xi^{4}}{128B^{4}},\quad\zeta_{t}(g,\mathbf{w})^{2}\geq\frac{\sigma_{\mathrm{dir}}^{2}\xi^{2}}{4B^{2}}.$

###### Proof.

We begin by noting that by Markov’s inequality, for any $\lambda>0$, it holds
that

$\displaystyle\mathbb{P}_{t}\left(\left|\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle-\mathbb{E}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\mid
Z_{t;ij}(g)=1\right]\right|>\lambda\mid
Z_{t;ij}(g)=1\right)\leq\frac{\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]}{\lambda^{2}}.$

Rearranging, we see that

$\displaystyle\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]\geq\sup_{\lambda>0}\lambda^{2}\cdot\mathbb{P}_{t}\left(\left|\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle-\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\mid
Z_{t;ij}(g)=1\right]\right|>\lambda\mid Z_{t;ij}(g)=1\right).$

Now we compute by Bayes’ theorem,

$\mathbb{P}_{t}\left(\left|\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle-\mathbb{E}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\mid
Z_{t;ij}(g)=1\right]\right|\leq\lambda\mid Z_{t;ij}(g)=1\right)\\\
\leq\frac{\mathbb{P}_{t}\left(\left|\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle-\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\mid
Z_{t;ij}(g)=1\right]\right|\leq\lambda\mid\right)}{\xi}$

and note that

$\displaystyle\mathbb{P}_{t}\left(\left|\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle-\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle~{}\mid
Z_{t;ij}(g)=1\right]\right|\leq\lambda\right)$
$\displaystyle\quad\leq\sup_{\mathbf{w},c}\mathbb{P}_{t}\left(\left|\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle-c\right|\leq\lambda\right)$
$\displaystyle\quad\leq\sup_{\mathbf{w},c}\mathbb{P}_{t}\left(\left|\left\langle\mathbf{x}_{t},\frac{\mathbf{w}}{\left|\left|\mathbf{w}\right|\right|}\right\rangle-c\right|\leq\frac{\lambda}{\left|\left|\mathbf{w}\right|\right|}\right)\leq\frac{\lambda}{\left|\left|\mathbf{w}\right|\right|\sigma_{\mathrm{dir}}},$

by Assumption 2. Thus we have

$\displaystyle\mathbb{V}_{\mathbf{x}_{t}}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right]\geq\sup_{\lambda>0}\lambda^{2}\left(1-\frac{\lambda}{\xi\sigma_{\mathrm{dir}}\left|\left|\mathbf{w}\right|\right|}\right).$

Setting
$\lambda=\frac{1}{2}\cdot\xi\sigma_{\mathrm{dir}}\left|\left|\mathbf{w}\right|\right|$
concludes the proof of the first statement. The second statements follow by
Assumption 4. ∎

Combining the lower bound in Claim D.1 with the small ball estimate of Lemma
D.11 concludes the proof of Lemma D.10. We now prove the technical results
required in previous proofs above.

######  Claim D.2.

Suppose we are in the situation of Lemma D.12. Then it holds that

$\displaystyle\mathbb{E}_{t}\left[\left\langle\bar{\mathbf{x}}_{t},\mathbf{w}\right\rangle^{4}\mid
Z_{t;ij}(g)=1\right]\leq
8+8\mathbb{E}_{t}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{4}\mid
Z_{t;ij}(g)=1\right]$

###### Proof.

Continuing to use notation from the proof of Lemma D.12, we compute:

$\displaystyle\mathbb{E}\left[\left\langle\bar{\mathbf{x}}_{t},\bar{\mathbf{w}}\right\rangle^{4}|\mathscr{F}_{t-1},Z_{t;ij}(g)=1\right]$
$\displaystyle=\mathbb{E}\left[\left(w_{0}+\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle\right)^{4}\mid\mathscr{F}_{t-1},Z_{t;ij}(g)=1\right]$
$\displaystyle\leq
8w_{0}^{4}+8\mathbb{E}\left[\left\langle\mathbf{x}_{t},\mathbf{w}\right\rangle^{4}\mid\mathscr{F}_{t-1},Z_{t;ij}(g)=1\right].$

The result follows by noting that $w_{0}^{2}\leq
w_{0}^{2}+\left|\left|\mathbf{w}\right|\right|^{2}=\left|\left|\bar{\mathbf{w}}\right|\right|^{2}=1$.
∎

With the covariance matrices lower bounded, we proceed to upper bound the
regret.

####  D.4 Upper Bounding the Empirical Error

In this section, we will show that for $1\leq i,j\leq K$ such that
$\left|I_{ij}(\widehat{g})\right|$ is sufficiently large, the fact that
$\widehat{\mathbf{\Theta}}$ is formed by minimizing the empirical risk will
force

$\mathcal{Q}_{ij}(\widehat{g})=\sum_{t\in
I_{ij}(\widehat{g})}\left|\left|\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}$

to be small. In the end, we will combine this bound with our lower bound on
$\Sigma_{ij}(\widehat{g})$ proved above to conclude the proof of the theorem.
We will begin by introducing some notation. For fixed $1\leq i,j\leq K$ and a
fixed $g\in\mathcal{G}$, we define:

$\displaystyle\mathcal{R}_{ij}(g)=\sum_{t\in
I_{ij}(g)}\left|\left|\widehat{\mathbf{\Theta}}_{i}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\left|\left|\mathbf{\Theta}^{\star}_{j}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}.$

The main result of this section is as follows: