Smoothed Online Learning for Prediction in Piecewise Affine Systems

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.

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: * 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. * 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. * The paper is generally quite well-written and it is easy to follow the main developments.

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: * 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. Perhaps my main concern is the following: * 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 $$error^2_i \lesssim \sqrt{T} / (\textnormal{number of visits to i}) \leq 1/\sqrt{\textnormal{number of visits to i}}$$ where 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$: $$ 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}.$$ Re-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. * 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. [A] Ziemann, Ingvar, and Stephen Tu. "Learning with little mixing." Advances in Neural Information Processing Systems, 2022. **minor:** * overflow on line 723-724. *

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. * 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, and see also your own reference [48])? * 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. [B] Liang, Tengyuan, Alexander Rakhlin, and Karthik Sridharan. "Learning with square loss: Localization through offset rademacher complexity." Conference on Learning Theory. PMLR, 2015. * How reasonable is your assumption 6? It is not obvious to me how to construct/verify this condition.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above caveats about rates and assumptions.

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.

Strengths

I 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. Most importantly, the main algorithm is easy to implement and seems really promising to apply to the real problem.

Weaknesses

To further improve the paper, I have the following comments: - How does Definition 1 of directionally smooth imply that "directional smoothness ensures the system spends little time close to a boundary" ? - It is not sure if Assumption 2 is mild, given there are jumps/discontinuities in PWA. - line 216, what's the meaning of "$\Theta(\sigma_{dir}^{d})$-smoothness"? - 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? - Line 312, "a sketch of the proof of Theorem 15", I didn't see any Theorem 15 in the main text. - Typo in Equ. (3.1), $z_t$ should be $z_{t,h}$ - 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}$ - 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.

Questions

Please see my questions in the above section.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Please see my questions in the above section.

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.

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.

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?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

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.

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.

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. The 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. I 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.

Questions

Please see my comments in the previous section.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

1 poor

Contribution

2 fair

Limitations

The authors discussed many future directions at the end of the paper, and I did not see any potential negative societal impact.