Smoothed Online Learning for Prediction in Piecewise Affine Systems
Authors: Adam Block
Max Simchowitz
Russ Tedrake
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Smoothed Online Learning
Piecewise Affine Prediction
Learning Dynamics
TL;DR: In this paper, we provide the first provably oracle-efficient, no-regret algorithm for prediction in piecewise affine systems

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.

Smoothed Online Learning for Prediction in Piecewise Affine Systems
Adam Block
Max Simchowitz
Department of Mathematics
CSAIL
MIT ablock@mit.cm edu
MIT
msimchow@ccail.miis mit.saaii.mmttee....... edu
Russ Tedrake
CSAIL MIT
Abstract
The problem of piecewise affine (PWA) regression and planning is of foundational importance 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 impos- sible and practical algorithms are forced resort heuristic approaches. This paper builds 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 weak smoothness assumption; moreover, our algorithms are efficient the number of calls to an optimization oracle. We further apply 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, develop several technical tools of more general interest.
Introduction
A central problem in the fields of online learning, control, and robotics is how to efficiently plan through piccewise-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, consider the related problem of learning to make predictions in PWA systems when the dynamics are unknown. While recent years have considerable progress around 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 simplified way of modeling rich phenomena that arise in numerous robotic manipulation and locomotion tasks [41, 64, 40], such modeling dynamics involving contact. In addition, deep neural networks with ReLU activation [24] are PWA systems, providing further motiviation for their study. Already, there is computational challenge simply in optimizing 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, as is common in online learning [29, 9, 28). Uniformly accurate learning of the dynamics across all pieces is typically impossible
objective over these systems, which is the subject
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

because some regions of space require onerous exploration to locate; thus, we instead consider an iterative prediction setting, where at each time the learner predicts the subsequent system state. From this, we extend to prediction of entire trajectories: over episodes L = 1,..., T, learner suggests a policy Tr, and the learner attempts to learn the dynamics so as to minimize prediction error along the trajectory TT, 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. Critically, regret does not require uniform identification of system parameters, which is typically impossible. The key pathology 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, problem well-known to the online learning community [36]. 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 [58, 59, 46].
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 [58, 59, 35, 44]. Additionally, the online learning community has studied smoothed online learning [49, 27, 28, 9, 7, 6], which circumvents the threshold-effed pathologies described above. We show that, if the dynamics and the control inputs are subject to randomized smoothing. low regret becomes achievable. 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 this pathology by ensuring that the system is generally far from these boundaries. 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 [29, 34, 9, 28]. In our setting, the optimization oracle required finds the best-fit PWA system to a batch of given data. Though this problem is intractable [5]. there is rich literature of popular heuristics [23, 45, 19]. Unlike those works, we examine the statistical challenge of generalization to novel data given such an oracle. We remark that in many practical cases, our smoothness assumption comes for free, in the sense that the Gaussian noise used to smooth gradients in Suh et al. [58] is already sufficient for our results to hold.
Contributions. A formal description of our setting is deferred to Section 2. Informally, we consider the problem of prediction in PWA system over 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 (T!-a) with respect to the optimal predictor which knows the system dynamics, where a > 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 dai-direcii smoothness condition introduced by [7], our regret bound is polynomial in dir- dimension, and other natural problem parameters. While the exact dependence on horizon may be far from optimal, we emphasize that our algorithm is the first to achieve regret even polynomial in all parameters in the difficult setting of PWA systems. Moreover, our work provides the first regret bound with polynomial dependence in dimension for oracle-efficies smoothed online learning in the sense of Hazan and Koren [29] of noncontinuous function class without a realizability assumption and allowing for process noise. As 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 Lyapunov condition, we demonstrate that our modified algorithm achieves simulation regret O (Poly(H) T')a), which allows for efficient simulation.
Key challenges. As noted above, vanishing regret 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. We remark that were we to care only about low regret without regard to efficiency, simple discretization scheme of size exponential in dimension coupled with a standard learning from experts algorithm [12] can achieve low regret; realizing an oracle-efficient algorithm is significantly more challenging.
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, each of which requires substantial technical effort to overcome. 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.
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. 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 non-neglible number of times & over the horizon T. Here, we leverage careful analysis based on two modern martingale-least squares techniques: the self-normalized concentration bound [2] for establishing recovery in a norm induced by within- region empirical covariance matrices, and the block-martingale small-ball method [54] to lower-bound the smallest cigenvalues 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 easily be misclassified and the correct predictions are discontinous. To leverage smoothing, we propose 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 paramcter recovery described in the preceding paragraph yields our sublincar 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
iesttmmidentificationn refers to estimating the governing equations of a dynamical system. The special case of linear dynamical systems is classical [37, 38, 16), and more recent work has provided finite-sample statistical analyses in many regimes of interest [54, 15, 43, 61, 63]. Estimation for non-linear systems has proven challenging, and has been studied most in the setting where the dynamics involve a known and smooth nonlincarity [39, 51, 20], or where only the observation model is nonlinear [14, 42]. [52] study Markov jump systems, where the system dynamics alternate between one a finite number of linear systems ("modes"), with switches between modes governed by Markov chain. PWA systems are thus an attractive intermediate step between the simple linear setting and the intractable general case. To our knowledge, ours is the first work to tackle piecewise affine dynamics in full generality, where the system mode is determined by the system state.
System Identification.
jump
Despite its worst-case computational intractability [5], there is rich literature of heuristic algorithms for computing the best-fit PWA system to data; see the surveys [23] and [45], which compare various approaches, notably the clustering method due to [19]. These references focus strictly on
3

---

the algorithmic facets of computing a best-fit given an existing data set. We instead abstract the computation of 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 [36], Freund and Schapire [22, 21J. 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. [49], Rakhlin and Sridharan [47], Rakhlin et al. [50], Block et al. [8], with Rakhlin and Sridharan [48] 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 the adversarial regime. Thus, some work [49, 27, 28, 9, 6] 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. In addition, Block and Simehowitz [7], which introduces the notion of directional smoothness to control the regret in realizable, online classification problem; realizability, here, means that there is no process noise in the sense that there exists some piecewise affine function that perfectly predicts all targets given the covariates. We also note that the algorithm in that paper is highly tailored to this realizable setting and thus is not at all robust to the noise considered in the present paper. Of partieular note is the concurrent work of Block et al. [10], which solves a similar problem with a stronger oracle. Note that in that paper, the oracle assumption is strong enough break the lower bound of Hazan and Koren [29], while in this work we use the much weaker oracle assumption found in Hazan and Koren [29]. Haghtalab et al. [28], Block et al. [9]. This distinction is important because even in the standard (fully adversarial) online learning setting, there is a computational separation between these two oracle models in general, as per Agarwal et al. [4]; thus the fact that this separation does not apply to PWA systems given smoothness may be of independent interest.
Online Learning for Control. In addition to the recent advances in finite-sample system identifica- tion, a vast body of work has studied control tasks from the perspective of regret [1, 3, 56, 53, 13]. 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 online prediction in control settings [31, 62], 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 smooth online learning setting is that well-conditioned random noise is injected into the adversary's 's decisions. It is well known that such noise injection can be viewed as a form of regularization [17], and recent recent work in the robotics literature has shown that randomized smoothing improves the landscape in various robotic planning and control tasks [58, 59, 35, 44]. More broadly, randomization has been popular for computation of policy-gradient zeroth-order estimates of gradients, notably via the acclaimed policy- gradient computation [66].
2 Setting
In this section, we formally describe the problem setting of online PWA regression. We suppose there is ground truth classifier g. Rd [K] and matrices {θ; i E [K] and 0; (d-1)) such that
y: = O x; + e + 8,,, i, = (x.), x; [x])1 || S Earps
(2.1)
where, x, Rdd are covariates, y, E T are responses, C, E RTT are zero-mean noise vectors in RmM 8, are (small) non-stochastic corruptions with norm at most Sorp < 1, and i, E [K] are the regression modes, which depend on the covariates X,- The extension to x; accomodates affine regressors. We suppose that the learner has access to pairs (x,, but, critically, does not know the regression modes i,. We do however suppose that g. is an affine classifer; that is g" E 9 = {x arg m (W. + b, J. where w, S is the unit sphere and 6, E B, B]. It can be shown that many natural physical systems are indeed modeled as PWA with affine boundaries [40], and the closed loop dynamics for model- preeiitpre control (MPC) in these cases is also PWA system [11]. We will assume throughout access to an empirical risk minimization oracle, ERMORACLE, which satisfies the following guarantee:

---

Assumption 1 (ERMORACLE guarantee), @ E [ 7 satisfying
Given data (1:s), ERMORACLE returns
Σ
inf + 0(x,) - -xil gES. [e])E(]]]
Σ 1 s(x,) - S Eorac.
(2.2)
While such an oracle is not computationally efficient in the worst case [5], there are many popular heuristics used in practical situations [19, 23]. The learner aims to construct an algorithm, efficient with respect to the above oracle, that at each time step produces Yt such that
Regr = Ei= 18+ e (s.) x 1| oT)).
(2.3)
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 = = 1, K=2, that chooses O' and 9a, as well as x1. Xy such that any learner experiences E [Regr] 2"
T
Proposition 1 follows from a construction of a system where there is a discontinuity across linear boundary, across which the states x2 oscillate. The bound is then consequence of the classical fact that online classification with linear thresholds suffers linear regret; see Appendix B.1 for a formal proof, included for the sake of completeness. Crucially, discontinuity in the dynamics necessitates an (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 [26] leads to regret that is exponential in dimension [7], we instead consider a related condition, "directional smoothness.""
Definition 2 (Definition 52 from Block and Simchowitz [7]). Given a scalar ddir > 0. random vector called dair- -irrecttcti smooth if for all w E 5d-1 = {w E Rdd ||l]|| = 1}, e E IR, and 8 > 0, it holds that TP (Iww, x) cl < 8) S 8/Oair-
As an example, for any vector z,, if w. N(O, o I). then z, ww, is Gaiz direccionally smooth; see /2T Appendix C.1 for proof and examples of directional smoothness for other noise distributions. Cru- cially, directional smoothness is dinension-indeeeeeee independent, in contradistinction standard smoothness, where we would only have (o)))) -smoothness (in the standard sense) in the previous example. We remark that directional smoothness is weak condition that holds in many natural settings. Indeed, whenever noise is injected into the dynamics, directional smoothness will come for free. Such noise injection can occur when there is uncertainty in position, as common in robotic applications; in this case, we can interpret this uncertainty itself as stochastic, which was the original motivation for smoothed analysis of algorithms [57]. Further, note that while directional smoothness ensures the system spends little time close to a boundary, due to the discreteness in time, there is no restriction on the number of mode switches, which can be ( in general.
We defer further discussion of the assumption to Appendix C.I. We require our smoothness condition to hold conditionally:
Assumption 2. Let F, denote the filtration generated by Xi,..., X1. For all times t, X2 conditional on Fi-1 d direeciccll 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 Fe denote the filtration generated by Ft and ei,..., e:-1 (equivalently, by Ft and yt... Yt-1) For all I, it holds that e v²-sub Subb-Gaussian conditioned on F²;; in particular, is conditionally zero mean.
Assumption 4. We suppose that for all 1 S T. | I B and, furthermore, | 11 S foror all
i. We will further assume that ERMORACLE always returns θ such that |0O1|P S R.
For comparison between directional and standard smoothness, consult [7].
5

---

Algorithm Main Algorithm
1: Initialize Epoch length E, Classifiers wi.k - (O....,,) ....,,)) margin parameter 7 > 0, learning
rate >>
2: for r =,,,, T/E do (x iterate over epochs)
3:
(o,,)IsiK, Ir + ERMORACLE(R1
4:
Ør - Reorder ( (O,,))s)ssssn (6r-1.)ssis)
5:
Wi:k + OGD(GW (w 1:K
(T-1)E [(r (- 1i::EEE:::::- "/:
6: Let 9r (x) arg I EiEK (w7e. x) denote classifier induced by wi:k.
7: for / .....,, (T - 1)E - do
8: Receive X,, and predict ÿ: ① (8.)
9: Receive Y:
Finally, we assume that the true affine parameters are well-separated:
Assumption 5. There is some Asop > O such that for all Si<js K, it holds that |0;-0] Asep-
Note that Assumption 5 is, a sense, generic, as explained in Remark We defer the formal setting of one-step prediction and simulation regret to Appendix G.1 and section 3.1.
3 Algorithm and Guarantees
We propose Algorithm I, an oracle-efficient protocol with provably sublinear regret and polynomial dependence all problem parameters. Algorithm 1 runs in epochs: at the beginning of epoch the learner calls ERMOR ACIE on the past data to produce a linear classifier G, and estimates of the regression matrices in each mode, ,, A major challenge is identifying the same affine regions between epochs. To this end, the learner permutes the labels of Gr 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) the hinge loss produce modified classifier П-; finally, throughout the epoch, the learner uses θ,,, and g- predict yt before repeating the process in the next epoch. The reason for using a secondary algorithm to transform 9r into 9. is enforce stability of the predictor across epochs, which is necessary bound the regret. Again, we suppose that Assumption holds throughout.
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, N. 77 are set as in (F.6), it holds that with probability at least 1 - 8, Regr < poly (par, log(1/5)) T35/36 + Eorsc T + K2 ET= 1e for par max(d. d. m. dir A B, R, K,v), v}, 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. [30]).
The misspecification errors ò can be indicators corresponding the X, being in small, rarely visited regions; thus, we could run an underspecified ERMORACLE, with K' < modes and recover regret bound depending only on frequently visited modes.
Remark 2.
When Cerp Corac = 0, we obtain exactly the polynomial, no-regret rates promised in the introduc- tion. Along the way to proving regret bound, we establish that ERMORACLE correctly recovers the linear parameters within frequently visited modes.
Theorem 4 (Parameter Recovery). Suppose that Assumptions 2-4 hold and let { @ E [K] 9
denote the oulput ofEEOOOAALEEEII Yı.)) and Tığ (g) denote the of times & such that 7(x;)
and g- (X+) = Then with probability at least - 8, for all S i.j S K such that [T. ( 2
poly (par, log (1)) -1(()) holds that | θ ||2 is bounded by [T,
/T
poly (par, log (1)).
Above we have given the result with the assumption that Eerp = Corac = for the sake of presentation; in the formal statement, the general case is stated. Theorem 4 implics that directional smoothness

---

is sufficient to guarantee parameter recovery at a parametric rate, in marked distinction to most adversarial learning regimes. Before providing more detail on the algorithm and its analysis in Section 4, we discuss an application to H-step prediction. An application to one-step prediction with learner-rrovided controls can found Appendix G.1
3.1 Guarantees for Simulation Regret
We now describe an application of our results to H-step prediction; more formal description is detailed in Appendix G.3. The learning process occurs in episodes t = 1, .... T, consisting of steps h = .. H. simplicity, we assume that ne (u.,...... Hz is open loop (state-independent) and stochastic, minimicking situations such as model predictive control; extensions are mentioned in Appendix G.6. With each episode. the true dynamies are given by
In each episode, an external planner provides the learner a policy For
2t A Zt B U + M + CLAb 4thh = 9" (Zt,h; Ur,h)
(3.1)
We assume that the process noise e are independently drawn from known distribution D, and that 2t.1 is sampled from an arbitrary -mooth distribution. At the start of episode 6, the learner then produces estimates A,, Be, 9t. and simulates the plan Te using the plug in estimate of the dynamics,
ie., 2 = À A,,,, 2,,,, Ze, + Br,.. 4t, + m,,,, êc, de,1 = ge (Zz,n, k,,,,, where êt, i.idd D, and Úr, are an i.i.d. draw from the stochastic, open-loop policy consider the following notion of error, which measures the distance betwen the two distributions induced by the dynamics, opposed to the regret, which measure the distance between the realizations thereof. We choose the Wasserstein metric W2, as upper bounds the difference in expected value of any Lipschitz reward function between the true and simulated trajectories (see Appendix G.3 for formal definition and more explanation).
Because the simulated and true
processes use different noise sequence,
Definition 5 (Simulation Regret). Let W2(1.)) denote the La- Wasserstein distance, define the con- catenations Xt = (,,,,) and &e, = (2, (,,,)), and let F. be the filtration generated by (XaAk We define the Trepisode, H- step simulation regret as SimRegr,tt == EL W2 (X,,1.1, 1
Our goal is to achieve SimRegr,, /! S HH) T7))()) but polynomial-in- dependence may be challenging for arbitrary open-loop policies and unstable dynamics of the pieces. Thus, 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 6. There exists a known, positive definite Lyapunov matrix P E Rddxxds that satisfies P( P for all modes E [K].
Using minor modification of Algorithm 1, detailed in Algorithm 4, show that can get vanishing simulation regret, summarized in the following result:
Theorem 6. Suppose that we are in the setting of (3.1) and that Assumptions 2-5 and 6 hold. If we run variant of Algorithm 1 (see Algorithum 4 in Appendix G.4), then with probability at least 1 8, it holds that SimRegr, S poly (par, H) - 35/6
The proof of Theorem 6 with the exact polynomial dependence on the parameters can be found in Appendix G.3 and rests lemma showing that under Assumption 6, simulation regret at given time & can be bounded as poly ()) multiplied by the maximum one-step prediction error for times t, + ...., + H. which is bounded in Theorem 3. We provide an exact recovery guarantee in the case H = 1 and without requiring Assumption 6 in Appendix G.I.
Analysis
In this section, we present a sketch the proof of Theorem 15. There are two primary sources of regret: that which is due to poorly estimating the linear parameters within mode and that which due to misclassification of the mode. We analyze each source separately, beginning with the parameter recovery result of Theorem 4.
7

---

Algorithm 2 Online Gradient Descent (Single Epoch)
1: Initialize Data &I.E, clasifiers wi.k- margin parameter 7 > 0, learning rate 17 > O, classifier
Ø: X [K]
2: for s == =,,,,..... do x i defined in (4.1)
3: Receive x; and update wi.k f- [op--11x (witk - vyV (.
4: Return Wi:k
4.1 Proof Sketch of Theorem 4
We break the proof into three parts: first, we show that the regret of 9 and the Q; when restricted to
times t E 13 (9), is small; second, we relate the prediction error Qi (T) Eier, I 0 )x,1?
to the regret on Lig (g); third, demonstrate that Σij (g) ()) xxx; has minimal eigenvalue bounded below by some constant with high probability. If all three of these claims hold, then, noting p < [[
that I e
Eeet, ||( ( -,)88111
we conclude. Each of these claims requires significant technical effort in its own right. We introduce disagreement covers, stronger analogue of e-nets adapted our problem and allowing to turn statements proven for a single E 9 into ones uniform over S. The first step is to bound the size of disagreement covers for the class 9 of interest; then prove each of the three claims for some fixed E 9 and lift the result to apply to the data-dependent ğ. This is done in Appendix D.I.
We now turn to our three claims. For the first, proved in Lemma D.15, we introduce the excess risk (g θ) ELEr,,(o) || 1 yrll2-1le: l/e, 5,11² for each pair (i,j), and note that the cumulative empirical excess risk Σv, Ryg [g, Q of predicting using f and θ returned by the ERM oracle is bounded by Eorac because R2y (g.: O.) 0 due to Equation (2.1). Thus, showing that R2y (g. θ) is small can be done by showing that for no i' ,', is R (ū, θ) << O. This can be accomplished by a concentration argument for single g, On coupled with a covering argument using our notion of disagreement covers to boost the result to one uniform 9.
For the second claim, i.e., that 2ig (g) controlled by Riy (g. θ), we provide a proof Lemma D.14.
For a fixed g 9. we decompose Rr, (g. + into Q.y(0 (g) and an error term. We then use generaliza- tion of the self-normalized martingale inequality from Yadkori et al. [2] to control the error in terms of 2iy (g), providing a self- bolf-bounded inequality. Finally, we rearrange this inequality and apply a union bound on disagreement cover to boost the result to one uniform in 9 and O.
To prove the third claim, that Ei (g) has singular values uniformly bounded from below, we split our argument into two parts. First, in Appendix D.2, we assume the following sliced-small ball condition on the data, i.e., for some S.P P 0, holds that P((x,, w)² 2 c C-<3,. t Ig)( 2 c p. Given the above condition, we establish high probability lower bound on Egy(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 disagreement cover to lift this result to be uniform in G. Finally, in Appendix D.3, we provide bounds on Ç, p using directional smoothness and Markov's 's inequality.
4.2 Mode Prediction
In this section, we address the second source of error, mode misclassification. The primary challenge that directional smoothness, as opposed to independent data, is insufficiently strong to guarantee that Ôr generalizes well to unseen data in epoch - + 1. We take inspiration from online learning and stabilize our algorithm across epochs by modifying the classifier 9-. There are two challenges in ensuring 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 enforce consistency of labelling accross epochs. This task is made more difficult by the fact that different modes may be combined or split up across epochs due to the black box nature of ERMORACII ACLE. We solve this by appealing to subroutine, Reorder, described in Algorithm 3 in Appendix E, which combines modes that are sufficiently large and have sufficiently similar parameters and then relabels the modes that similar nominal clusters persist accross epochs.
8

---

The second challenge is enforcing stability of our online classifier. We do this by introducing a surrogate loss L.,.gg. the multi-class hinge loss with parameter y > 0 Formally, let Wi:K (W1....; wx) for w, E Bá-1, and for g E 9, define the (1/7)-Lipschitz and convex surrogate loss:
lg (W1:K) = max (0. max (+9(
(1 (1- (WOCR)) (1 wy.x.)) ))
(4.1)
In OGD (see Algorithm 2), we modify the output of ERMORACLE to construct a classifier gr by running lazy online gradient descent on this surrogate loss, using the reordered labels given by the output of ERMÖRACLE 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 7 (Mode Prediction, Informal Statement of Theorem 13). Suppose that Assumptions 2-5 hold and let Epode be the event that the learner, invoking Algorithm I with correctly tuned parameters, misclassifies the mode of Xt. Then, with probability al least - 6, it holds that Et= 1[grodde S poly (par, (1) -T1-2(3)
Proof Sketch. We begin by addressing the lack of identifiability of the modes. For the pur- poses of analysis, for each epoch т, introduce the function TT [K] - [K] such that T (i) argminggjgk | θjll.. In words, T. (i) is the mode j according to the ground truth whose parameters are closest to those estimated by ERMORACLE, We let gmode denote the event of misclassifying the mode, i.e. the event that x (x- # (xx). We can then decom- pose the misclassification as Emoode C I (Rx)) * g. (8.)) U { (T- (&.)) & I (ār().)) (8+)) 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: ( (gr (R)) + 9. (x,)] C (T++1(0r+1
* (xx) U [ō+ (Xx) * ( Controlling the first of these events is proved as corollary of the bound the permutation disagreement error and we defer its discussion for the sake of simplicity. To bound the probability of the second event,
upper bound the indicator loss by E7,13.+1 and apply standard online learning techniques to show that regret of OGD on the (1/y)-Liph) //issh-ipscchtz and convex surrogate loss is small. 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 comparator experiencing zero loss due to the well well-specified nature of 9.. Thus, putting everything together, this provides bound on the look-ahead classification error, with full details presented in Appendix 1.
Bounding the permutation disagreement error is what necessitates the gap assumption. We show that if there are sufficiently many data points that Ir assigns to a given mode, with the threshold defined in terms of sep and other parameters of the problem, then with high probability the cluster becomes stable in the sense that +,, O This result is proved using the fact that if [+=) is large enough, then the parameter recovery results from the previous section tell us that ||: - @ l| is small. Using the triangle inequality and the fact that || e ||: > Asep for j' # j ensures that
is unique in satisfying @ - 07 IF < 1. A similar argument applies to epoch 7 + 1, and thus we can identify θ,.: with some ,,+1,' 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 Appendix F.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-affing but forced to be continuous on their boundaries, is there an oracle efficient algorithm which suffers low regret without assuming directional
We use the hinge loss because it is convex, Lipschitz, and its relationship to the indicator loss is particularly convenient under directional smoothness. Other convex, Lipschitz surrogates provide similar guarantees.

---

smoothness? Can learning in piecewise affine systems be obtained under partial observation of the system state? Can the dependence of regret on horizon be improved? We hope that our work initiates investigation of the above as the field continues to expand its understanding beyond the linear regime.
Acknowledgments and Disclosure of Funding
AB acknowledges support from the National Science Foundation Graduate Research Fellowship under Grant No. 1 1122374 well support from ONR under grant N00014-20- 1-2336 and DOE under grant DE-SC0022199, MS acknowledges support from Amazon.com com Services LLC grant; PO# 2D-06610236. We also acknowledge Zak Mhammedi, Terry H.J. Suh and Tao Pang for their helpful comments.
References
[1] Y. Abbasi- Yadkori and C. Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference Learning Theory, pages 1-26. JMLR Workshop and Conference Proceedings, 2011.
Abbasi-Yadkori
[2] Y. Abbasi Yadkori, D. Pál, and Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[3] N. Agarwal, B. Bullins, E. Hazan, S. Kakade, and K. Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111-119, PMLR, 2019.
[4] N. Agarwal, A. Gonen, and E. Hazan. Learning in non-convex games with optimization oracle. Conference on Learning Theory, pages 18-29, PMLR, 2019.
[5] E. Amaldi and M. Mattavelli. The min pfs problem and piecewise linear model estimation. Discrete Applied Mathematics, 1
2002.
[6] A. Block and Y. Polyanskiy. The sample complexity of approximate rejection sampling with applications to smoothed online learning. arXiv preprint vrXiv:2302.0465: 2023.
[7] A. Block and M. Simchowitz. Efficient and near-optimal smoothed online learning for general- ized linear functions. arXiv preprint arXiv:2205. 13056, 2022.
[8] A. Block, Y. Dagan, and A. Rakhlin. Majorizing measures, sequential complexities, and online learning. In Conference on Learning Theory, pages 587-590. PMLR, 2021.
[9] A. Block, Y. Dagan, N. Golowich, and A. Rakhlin. Smoothed online learning is as easy as statistical learning, arXiv preprint arXiv:2202. 2202222004400,. 2022.
[10] A. Block, A. Rakhlin, and M. Simchowitz. Oracle-efficient smoothed online learning for piecewise continuous decision making. arXiv preprint 0rXW:22302.05400, 2023.
[11] Borrelli, A. Bemporad, and M. Morari. Predictive control for linear and hybrid systems. Cambridge University Press, 2017.
[12] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[13] A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y. Mansour, and K. Talwar. Online linear quadratic control. In International Conference on Machine Learning, pages 1029-1038. PMLR, 2018.
[14] Dean and B. Recht. Certainty equivalent perception- control. In Learning for Dynamics and Control, pages 399-417 PMLR, 2021.
[15] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4)6633-679, 2020.
[16] M. Deistler, K. Peternell, and W. Scherrer. Consistency and relative efficiency of subspace methods. Automatica, 31(12): ((12):1865-1875 865-1875, 1995.
[17] C. Duchi, P. L. Bartlett, and M. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22 2012.
[18) H. Federer. Geometric measure theory. Springer, 2014.
[19] G. Ferrari-Trecate, M. Muselli, Liberati, and M. Morari. clustering technique for the identification of piccewise affine systems. Automatica, 39(2):005-217, 2003.
10

---

[20] D. Foster, T. Sarkar, and A. Rakhlin. Learning nonlinear dynamical systems from a single trajectory. In Learning for Dynamics and Control, pages 851-861. PMLR, 2020.
[21] Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
[22] Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine learning. 37(3) 1999.
[23] A. Garulli, S. Paoletti, and A. Vicino. A survey switched and piecewise affine system identification. IFAC Proceedings Volumes, 45(16))344-355, 2012.
[24] I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. MIT press, 2016.
[25] V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 39(2):742-765. 2009.
[26] N. Haghtalab, Roughgarden, and A. Shetty. Smoothed analysis of online and differentially private learning. arXiv preprint arXiv:2006. 2020.
[27] N. Haghtalab, T. Roughgarden, and A. Shetty, Smoothed analysis with adaptive adversaries. arXiv preprint arXiv:2102.em 08446, 2021.
[28] N. Haghtalab, Y. Han, A. Shetty, and K. Yang. Oracle-efficent online learning for beyond worst-case adversaries. arXiv preprint vrXiv:2202.08549 2022.
[29] E. Hazan and T. Koren. The computational power of optimization in online learning. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 128- 141, 2016.
[30] E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th annual international conference on machine learning, pages 393-400, 2009.
[31] E. Hazan, K. Singh, and C. Zhang. Learning linear dynamical systems via spectral filtering. Advances in Neural Information Processing Systems, 30, 2017.
[32] E. Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325 2016.
[33] C. N. Jones and M. Morari. Approximate explicit mpc using bilevel optimization. In 2009 European control conference (ECC). pages 2396-2401. IEFF, 2009.
[34] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences. 71(3):291-3077 2005.
[35] Q. L. Lidec, L. Montaut, C. Schmid, I. Laptev, and J. Carpentier. Leveraging randomized smooth- ing for optimal control of nonsmooth dynamical systems. arXiv preprint arXiv:2203.0324 2022.
[36] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4):285-318, 1988.
[37] L. Ljung, System identification: Theory for the users," prentice hall, new jersey, 1999.
[38] L. Ljung and B. Wahlberg. Asymptotic properties of the least-squares method for estimating transfer functions and disturbance spectra. Advances in Applied Probability, 24(2):412-440) 1992.
[39] H. Mania, M. Jordan, and B. Recht. Active learning for nonlinear system identification with guarantees. arXiv preprint (rXiv:2006.10277 2020.
[40] T. Marcucci and R. 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.
[41] M. T. Mason. Mechanics of robotic manipulation. MIT press, 2001.
[42] Z. Mhammedi, D. J. Foster, M. Simchowitz, D. Misra, W. Sun, A. Krishnamurthy, A. Rakhlin, and J. Langford. Learning the linear quadratic regulator from nonlinear observations. Advances in Neural Information Processing Systems, 33: 13532-114454, 2020.
[43] Oymak and Oray. Non-asymptotic identification of Iti systems from a single trajectory. In 2019 American control conference (ACC), pages 5655-5661. IEEE, 2019.

---

[44] T. Pang, H. Suh, L. Yang, and R. Tedrake. Global planning for contact-rich manipulation via local smoothing of quasi-dynamic contact models. arXiv preprint vrXiv:2266.10887, 2022.
[45] S. Paoletti, A. L. Juloski, G. Ferrari-Trecate, and R. Vidal. Identification of hybrid systems tutorial. European journaal of control, 13(2-3):242-260, 2007.
[46] M. Posa, C. Cantu, and R. Tedrake. A direct method for trajectory optimization of rigid bodies through contact. The International Journal of Robotics Research, 33(1):69-81) 2014.
[47] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, PMLR, 2013.
[48] A. Rakhlin and K. Sridharan. Online non-parametric regression. In Conference on Learning Theory, pages 1232-1264. PMLR, 2014.
[49] A. Rakhlin, K. Sridharan, and A. Tewari. Online learning:
Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 14:177441777 1772, 2011.
[50] A. Rakhlin, K. Sridharan, and A. Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1):111-15) 2015.
[51] Y. Sattar and S. Oymak. Non-asymptotic and accurate learning of nonlinear dynamical systems. Journal of Machine Learning Research, 23(140): 2022.
[52] Y. Sattar, Z. Du, D. A. Tarzanagh, L. Balzano, N. Ozay, and S. Oymak. Identification and adaptive control of markov jump systems: Sample complexity and regret bounds. arXiv preprint arXiv:2111.07018, 2021.
[53] M. Simchowitz and D. Foster. Naive exploration optimal for online lqr. In International Conference Machine Learning, pages 8937-8948. PMLR, 2020.
[54] M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht. Learning without mixing: Towards a sharp analysis of linear system identification. In Conference On Learning Theory, pages 439-473. PMLR, 2018.
[55] M. Simchowitz, R. Boczar, and B. Recht. Learning linear dynamical systems with semi- parametric least squares. In Conference on Learning Theory, pages 2714-2802. PMLR, 2019.
[56) M. Simchowitz, K. Singh, and E. Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMI.R, 2020.
[57] D. A. Spielman and S.-H. Teng, Nearly-linee -ineer 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.
[58] H. J. Suh, M. Simehowitz, K. Zhang, and R. Tedrake. Do differentiable simulators give better policy gradients? In International Conference on Machine Learning, pages 20668-20696. PMLR, 2022.
[59] H. J. T. Suh, T. Pang, and R. Tedrake. Bundled gradients through contact via randomized smoothing. IEEE Robotics and Automation Letters, 7(2)4400-4007, 2022.
[60] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforce- ment learning with function approximation. Advances in neural information processing systems,
12, 1999.
[61] A. Tsiamis and G. J. Pappas. Finite sample analysis of stochastic system identification. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 3648-3654. IEFE, 2019.
[62] A. Tsiamis. N. Matni, and G. Pappas. Sample complexity of kalman filtering for unknown systems. In Learning for Dynamics and Control, pages 435-444, PMLR, 2020.
[63] A. Tsiamis, I. Ziemann, N. Matni, and G. J. Pappas. Statistical learning theory for control: A finite sample perspective. arXiv preprint arXiv:2209.054223 2022.
[64] A. J. Van Der Schaft and H. Schumacher. An introduction hybrid dynamical systems, volume
251. springer, 2007.
[65] G. Williams, A. Aldrich, and E. Thcodorou. Model predictive path integral control using covariance variable importance sampling, arXiv preprint 1009::150000014::. 2015.
[66] R. J. Williams. Simple statistical gralient- algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-254) 1992.
12


Reviews:
[{"review_id": "enyVdzwdeY", "reviewer": "Reviewer_7mVW", "summary": "This paper studies the problem of prediction in piecewise affine systems over a finite horizon. The main results are a linear regret bound and a sublinear regret bound under the proposed metric of simulation regret. To obtain the regret bounds, the authors made many assumptions and assume the access to an empirical risk minimization oracle.", "questions": "Please see my comments in the previous section.", "limitations": "The authors discussed many future directions at the end of the paper, and I did not see any potential negative societal impact.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "There is a good motivation to study piecewise-affine systems as an intermediate step between linear and nonlinear systems. This paper also presents many theoretical results.", "weaknesses": "It is hard for me to follow the paper from the problem setting of piece-wise affine regression. There are too many mathematical expressions without an appropriate amount of context and motivating examples. And many key definitions and explanations are deferred to the appendix.\n\nThe setting is confusing because some assumptions are not stated formally as assumptions. For example, in line 185, the authors assume $g_*$ to be an affine classifier, but they did not explain the implication or motivation of this assumption. It seems that taking argmax only contains a small subset of piece-wise affine systems. Besides, it is also unclear where the non-stochastic corruption $\\delta_t$ comes from and if it is oblivious.\n\nI also have some concern about whether the assumptions made to obtain the regret bound are too strong, especially for Assumption 1. I conjecture that the upper bound $\\varepsilon_{orac}$ on the right hand side will increase with the horizon $s$ in practice if we want to solve this problem efficiently with unknown parameters. Assumption 6 also seems very strong and I feel it is almost equivalent to knowing the exact dynamics under each mode.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We will be sure to provide more concrete examples and motivation for our setting in our revision. While we deferred several explanations to the appendix for the sake of space, we will better clarify the intuition for the mathematical expressions. \n\nWe agree that there may be more settings for the boundaries that are not covered by the theory. For example, our bounds are poly in the the number of argmax regions $K$, whereas a classifier that, for example, parameterizes $K’$ hyperplanes can induce $2^{K’}$ regions. We will clarify this limitation in the revision; it is essentially for simplicity.   Specifically, the properties of the mode classifier we need are (1) it has a bounded disagreement cover and (2) the form of the classifier is amenable to online multi-class classification. We can envision several more general classifiers with this property, and will remark this when we revise.  It should be noted that one-vs-all classification is extremely common in classification and the problem is already very nontrivial in this case.\n\nRegarding the strength of the other assumptions, we note that Assumption 1 (i.e. that we have access to an optimization oracle over the function class) is the accepted standard in the online learning literature, as we discuss in the paragraph starting in line 145 in the related work.  \nMoreover, one of the surprising implications of our result is that the general computational lower bounds of Hazan & Koren 2016, Block et al 2022, and Haghtalab et al 2022, cited in our paper, do not hold PWA functions in the smoothed online learning setting, paving the way for future analysis of computational tractability for function classes of practical interest.  While online learning is possible with stronger oracles (e.g. the FTPL oracle in Agarwal, Gonen, Hazan), we show that the standard ERM oracle suffices. Furthermore, we discuss in lines 57-64 the practicality of this oracle in the context under consideration; informally, this oracle should be viewed as “the best available heuristic”, which can be replaced with better algorithms as they are developed.\n\nRe:f Assumption 6, we acknowledge in line 298 that this is a strong assumption; this section is just a first application of our main results, emphasizing that the barrier to go from prediction regret to simulation regret is stability of the system (and the predictions), rather than long horizons per se."}, {"review_id": "NobCvPgHtn", "reviewer": "Reviewer_QtL6", "summary": "This paper presents an algorithm for learning policies for piecewise affine systems, with both parameter-accuracy and regret bound guarantees, by using a kind of randomized smoothing of the boundaries of the affine regions. It identifies an anticoncentration property (\"directional smoothness\") that was previously proposed, along with some more standard assumptions on the noise distribution and separation of parameters in the affine regions that enable efficient identification; the problem was known to be inherently hard in the absence of such assumptions.", "questions": "What avenues do you see for potentially improving the algorithm or its analysis? What would you conjecture the correct order of dependence on the time horizon to be?", "limitations": "I think this is fine. Although it isn't clear whether or not the algorithm is practical, the work is positioned as being a first work to meet basic theoretical desiderata, and the assumptions used seem to be well motivated.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The problem tackled in this work is natural and was known to be quite challenging. Although the basic idea of randomized smoothing to avoid the accumulation of error around the boundaries of affine regions is quite clear, actually executing this plan required quite a bit of technical sophistication. The paper itself gives a decent sketch of the approach and where these difficulties lay. ", "weaknesses": "The only weakness is that the bounds, while meeting the requirements of being polynomial, sublinear, etc. are a bit extravagant. I don't know if this is a practical algorithm, and I hope this work isn't the last word on this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.  Regarding the regret bound, we agree that the resulting oracle complexity is likely suboptimal.  Note that if one is happy with computationally inefficient algorithms, then running exponential weights on an exponentially large cover will attain optimal regret scaling like the square root of the horizon, so the more challenging question is what the oracle complexity of achieving average regret bounded by some epsilon is.  The primary cause for the poor regret is in our parameter recovery proof, specifically coming from our lower bound on the empirical covariance matrix of data on each mode, described in lines 339-345.  While the analysis is already fairly sophisticated in the proof of this result, one may hope that tighter bounds are possible, which would then translate into a significantly better regret bound.  We emphasize that it is already somewhat surprising that an oracle complexity that is polynomial in all parameters is possible in light of the general lower bound of Hazan & Koren (2016) cited in the paper.\n\nWhile we conjecture that an optimal algorithm should not argue directly through parameter recovery, an advantage of our analysis is that it exposes the various components and challenges in addressing our setting. Moreover, by ensuring parameter recovery, we obtain guarantees for simulation regret which may be of independent interest. \n"}, {"review_id": "gPqMY4KYOC", "reviewer": "Reviewer_MA9v", "summary": "This paper develops the theory to show that the online smoothed learning of piecewise affine model (PWA), under mild assumption, can achieve sublinear regret in dynamics prediction, and also the regret bound is polynomial in system parameters.\n\n", "questions": "Please see my questions in the above section.", "limitations": "Please see my questions in the above section.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "\nI think the results of this paper are of great importance both to robotics community, where the online learning of PWA models can be used to represent non-smooth physical contact systems, and to online learning community, where some new results, e.g., the sublinear regret is polynomial instead of exponential in system dimension, is developed. \n\nMost importantly, the main algorithm is easy to implement and seems really promising to apply to the real problem.\n", "weaknesses": "\nTo further improve the paper, I have the following comments:\n- How does Definition 1 of directionally smooth imply that  \"directional smoothness ensures the system spends little time close to a boundary\" ?\n- It is not sure if Assumption 2 is mild, given there are jumps/discontinuities in PWA.\n- line 216, what's the meaning of \"$\\Theta(\\sigma_{dir}^{d})$-smoothness\"?\n- In Algorithm 1, the re-labeling step (Algorithm 3)  needs to check each pair of labels between the new and old partitions. How is the Algorithm scalable with large number of partitions?\n- Line 312, \"a sketch of the proof of Theorem 15\", I didn't see any Theorem 15 in the main text.\n- Typo in Equ. (3.1), $z_t$ should be $z_{t,h}$\n- Typo in the text right below Euq. (3.1), $\\hat{m}_{t,\\hat{i}_{t,h}}\\hat{e}_{t,h}$ should be $\\hat{m}_{t,\\hat{i}_{t,h}}+\\hat{e}_{t,h}$\n- Since the paper is partially motivated by the recent progress in random smoothing in physical contact systems, the authors may need to discuss the promise or limitation of the proposed algorithm when it is applied to that domain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.  We will address each question below:\n1. Directional smoothness means that for any direction, the random variable projected onto this direction is anti-concentrated in any interval.  Because the boundaries are determined by affine sets, for the system to be near to the boundary, its projection onto the direction defining the boundary must lie in a small interval, which is unlikely to happen by directional smoothness.  We will clarify this in the revision.\n2. Note that smoothness in Assumption 2 refers to the distribution in a directional sense, not a function and thus whether or not it holds is not determined by the discontinuities in the system.  Indeed, randomized smoothing added for the purposes of optimization already ensures that Assumption 2 holds.\n3. By standard smoothness we mean the original notion that there exists a uniform bound on the density of some random variable, which is studied in the earlier works on smoothed analysis we cite in lines 145-165.  The distinction is included in order to emphasize why directional smoothness is so important as opposed to this previous notion.  We will add this formal definition in the revision.\n4. This is a good question and we will add some more discussion of practical considerations in the revision.  Note that a natural way to scale the algorithm to a large number of modes would be to only keep track of modes already visited and update this set accordingly between epochs.  Unfortunately, scaling polynomially with the number of modes is unavoidable in general.\n5. Thank you for catching this typo; we meant theorem 3.\n6. Thank you for catching these typos.\n7. We think that one of the most significant advantages of our algorithm is demonstrating that there are no fundamental learning-theoretic barriers to obtaining low-regret in smoothed piecewise affine prediction in an oracle efficient manner.\n"}, {"review_id": "OFvQoivht5", "reviewer": "Reviewer_Zpmv", "summary": "The authors consider a smoothed nonlinear regression problem with time-series data in which the hypothesis class is decomposed into the product of (i)  affine classes across polyhedral components and (ii) an indicator/classifier \"choosing\" the component. They first show that parameter recovery for the affine component of the class is possible at a slow rate and then proceed to control a notion of simulation regret for the prediction error at a (marginally) sublinear rate. They establish a few more results on similar lines along the way.", "questions": "* Is assumption 4 really consistent with the use of the self-normalized inequality of de la Pena et al/Abbasi-Yadkori et al? It looks like this restricts the ERM to search over bounded regions in Euclidean space. \n\n* relating to the above weakness about parametric rates: is Lemma D.13 really anywhere near sharp? Why is there a factor $\\sqrt{T}$ on the RHS? Assuming realizability ($\\delta=0$) I would expect this to be  $\\tilde O(\\textnormal{complexity hyp class})$. Could this perhaps be removed by using an offset style of analysis as in [B] (which is for iid data, but see also [A] above for the dynamic (martingale) case, \nand see also your own reference [48])?\n\n* Is your claim that you have provided an \"efficient algorithm\" (line 399) really motivated without further nuance? Certainly, no claim to statistical efficiency can be made based on your analysis. See also my comments about your rates above.\n\n[B] Liang, Tengyuan, Alexander Rakhlin, and Karthik Sridharan. \"Learning with square loss: Localization through offset rademacher complexity.\" Conference on Learning Theory. PMLR, 2015.\n\n* How reasonable is your assumption 6? It is not obvious to me how to construct/verify this condition.\n", "limitations": "See above caveats about rates and assumptions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this is an interesting theory paper contributing to the growing field of learning in dynamical/control systems and I recommend it to be accepted contingent on a few of my minor concerns being addressed (after which I will gladly raise my score to 7 or higher). It is relatively original in terms of formulation and the quality of writing is good. The technical details also appear sound to me, although I did not check them all beyond quick \"sanity checks\". Details:\n\n* The directional smoothness concept taken from [7] and its use here are interesting. Overcoming the curse of dimensionality in learning nonlinear systems is a nontrivial matter and this is an interesting contribution applying this concept.\n\n* The problem is well-chosen and relatively well-motivated in terms of control applications (MPC). The claim to being foundational is perhaps a bit over the top but otherwise I quite liked the formulation.\n\n* The paper is generally quite well-written and it is easy to follow the main developments. \n\n", "weaknesses": "Overall, as I state above, I quite liked the paper and found the techniques/results to be interesting. However, it does feel a little unfinished for the reasons I outline below:\n\n* The regret bound is quite weak (which is basically just $o(T)$). While I appreciate that this perhaps is more to be seen as a \"proof of concept\" I cannot help but wonder whether some more effort should have been put into proving a more palatable rate before submission.\n\nPerhaps my main concern is the following: \n\n* I also wonder whether the parameter recovery bound could have been improved, which as it stands, appears to be at a slow rate. I did not really appreciate this being passed of as a \"parametric rate\" (line 270). The authors prove in Theorem 4 that \n$$error^2_i \\lesssim \\sqrt{T} / (\\textnormal{number of visits to i}) \\leq 1/\\sqrt{\\textnormal{number of visits to i}}$$  \nwhere I have omitted dimensional and complexity factors. Normally, the error in square norm for parameter recovery occurs at a fast rate (i.e. removing the square-root in the RHS above). If I squint I can also see how this could be obtained by controlling the $L^2$ prediction error of the hypothesis class as in [A] below. Heuristically I would expect by lower isomorphism in $L^2$:\n$$ error^2_i (L^2) \\times \\textnormal{occupancy rate}_i \\lesssim error^2(L^2) \\lesssim  error^2(\\textnormal{empirical }L^2) \\lesssim \\textnormal{self-normalized term}.$$\nRe-arranging this should in principle give a fast rate for parameter recovery. I am sure the predictor $\\hat g$ complicates matters, but the additional complexity should be controllable in terms of the number of regions. While it would be appreciated, let me also say that I do not expect the authors to  entirely \"fix\" this for the final submission but I think it at least deserves comment.\n\n* While on the topic of [A], this reference should be added to the related work section on nonlinear system identification for (stochastically) stable systems. The ideas therein may also be useful for answering parts of the discussion in Section 5.\n\n[A] Ziemann, Ingvar, and Stephen Tu. \"Learning with little mixing.\" Advances in Neural Information Processing Systems, 2022.\n\n\n**minor:**\n\n* overflow on line 723-724. \n\n* ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Regret Bound\n\nThank you for your review.  Regarding the regret bound, we agree that the resulting oracle complexity is likely suboptimal.  Note that if one is happy with computationally inefficient algorithms, then running exponential weights on an exponentially large cover will attain optimal regret scaling like the square root of the horizon, so the more challenging question is what the oracle complexity of achieving average regret bounded by some epsilon is.  The primary cause for the poor regret is in our parameter recovery proof, specifically coming from our lower bound on the empirical covariance matrix of data on each mode, described in lines 339-345.  While the analysis is already fairly sophisticated in the proof of this result, one may hope that tighter bounds are possible, which would then translate into a significantly better regret bound.  We emphasize that it is already somewhat surprising that an oracle complexity that is polynomial in all parameters is possible in light of the general lower bound of Hazan & Koren (2016) cited in the paper.  While we conjecture that an optimal algorithm should not argue directly through parameter recovery, an advantage of our analysis is that it exposes the various components and challenges in addressing our setting. Moreover, by ensuring parameter recovery, we obtain guarantees for simulation regret which may be of independent interest. \n\n# Fast vs Slow Rate\nRegarding the fast vs slow rates of the parameter recovery in Theorem 4, we will clarify this point better in the revision and remove the reference to a parametric rate.  Note that minor changes to our analysis do *not* yield fast rates in the manner that is being suggested precisely because of the dependence on the classifier.  The “slow” square root only comes in through Lemma D.15 with the core issue being that while we have control over the *total* excess risk summed over all pairs of modes (i,j), in order for our parameter recovery to hold, we need the excess risk on each *individual* pair to also be small.  Due to the stochasticity of the perturbations, some of these excess risks can be negative and the size of the fluctuations is on the order of the square root of the number of points for Gaussian perturbations.  Thus, fast rates *cannot* be obtained without modifying the definition of excess risk.  One might hope for some improvement by changing the definition of the excess risk and considering perturbations around the empirically optimal predictor on the data, as opposed to the ground truth, but this would add substantial technical difficulty to an already highly intricate proof; furthermore, it is not clear that this method would help because, again, we need to control the lower tail of excess risk on individual pairs of modes, whereas most fast rate analyses follow by careful control of the upper tail.  To summarize, because the fundamental difficulty is in translating a bound on the sum of many different terms (some of which can be negative) into a bound that holds uniformly over each term, we pay for the largest excess risk on a given term, which may be substantially larger than one might initially expect; thus, in order to improve this rate, we suspect that a substantially different analysis would be needed.\n\n# Questions\n\n1. Note that we use the self-normalized bounds not because we are concerned that our numerators are too large, but rather because the denominators might be too small; indeed, their main utility is in easily allowing us to specialize bounds to apply only to time steps that fall into a given mode.  We suspect that a similar analysis without self-normalization but with more involved conditioning would also hold.  Meanwhile, the compactness assumption is necessary for us to bound the size of the disagreement cover. \n2. See the above discussion on these bounds.  In particular, the slow rate comes only from Lemma D.15, with all other parts of the proof having the desired dependence on horizon.\n3. What we mean by “efficient” is that all dependences are polynomial in all problem parameters, in contrast to something like exponential weights on a cover of the function class, whose computational complexity suffers an unavoidable exponential-in-dimension dependence.  This is also in contrast to naively applying the algorithms of Block et al (2022) and Haghtalab et al (2022) from the smoothed online learning community, which also suffer this exponential dependence.  We agree that the polynomials in our bounds are not small; we consider the mere fact that they are polynomial as opposed to exponential surprising in light of computational lower bounds in Hazan & Koren (2016), Block et al (2022), and Haghtalab (2022), which is where the word “efficient” is coming from.\n4. Assumption 6 was the simplest (albeit strong) assumption that we needed to ensure simulation regret. Its purpose is to show that possible instability of the predicted system, rather than horizon per se, is the main obstacle for PWA simulation. In some sense, stability is necessary for multi-step prediction problems (as has been studied in the setting of imitation learning (see e.g. https://arxiv.org/abs/2205.14812). We could replace Assumption 6 with the weaker assumption that the Lypaunov matrix P* is unknown, and instead propose to synthesize this common Lyapunov function from data (certifying a Lyapunov equation is an SDP and hence can be certified for many matrices simultaneously). Because simulation regret is intended as an application of our result, we did not go down this route."}]

Author rebuttal:

Meta-review: This work proposes an algorithm for prediction under PWA systems with sublinear regret that depends polynomially on system parameters. The general PWA setting is known to be difficult, and this work gives reasonable conditions under which good regret is achievable. This is a very interesting theoretical result, and even though it’s unclear if the bounds are optimal, this result is still significant for achieving vanishing regret and oracle efficiency. I recommend acceptance.
Decision: Accept (spotlight)