Online Optimization of Piecewise-Lipschitz Functions

1. Let the parameter dimension be $p=1$, and suppose discontinuities of $u_t$ are roots of

$$\phi_\alpha(\theta)=\theta^d+\alpha_{d-1}\theta^{d-1}+\cdots+\alpha_0,$$

where $\alpha=(\alpha_{d-1},\ldots,\alpha_0)\in[-R,R]^d$ is random. For a class $\mathcal{D}$ of coefficient distributions, define

$$C_{\mathcal D}:= \sup_{\mu\in\mathcal D} \sup_{\substack{I\subseteq\Theta\text{ interval}\\ |I|>0}} \frac{\Pr_{\alpha\sim\mu}(\exists\theta\in I:\phi_\alpha(\theta)=0)}{|I|}.$$

Under what natural necessary and sufficient conditions on $\mathcal D$ is $C_{\mathcal D}$ finite? Under what conditions is it polynomial in $d$ and $R$? Partial progress includes sufficient conditions that yield improved or new regret bounds for applications of online data-driven algorithm design.

1. Let $J$ be a one-dimensional parameter interval and let

$$\phi_\alpha(\theta)=\sum_{i=1}^{N}\alpha_iF_i(\theta) =\langle\alpha,F(\theta)\rangle,$$

where $F=(F_1,\ldots,F_N)$ is a vector of Pfaffian functions on $J$, and $\alpha\in[-R,R]^N$ is drawn from a distribution with bounded joint density. What normalization condition on $F$, analogous to fixing the leading coefficient of a polynomial, guarantees that

$$C^{\mathrm{Pf}}_{\mathcal D}:= \sup_{\mu\in\mathcal D} \sup_{\substack{I\subseteq J\text{ interval}\\ |I|>0}} \frac{\Pr_{\alpha\sim\mu}(\exists\theta\in I: \langle\alpha,F(\theta)\rangle=0)}{|I|}$$

is finite? If every $F_i$ is a polynomial, the condition should recover the known polynomial bound.

One candidate for the second question is a bound on the Lipschitz constant of the normalized function $F(\theta)/\|F(\theta)\|_2$, provided that this constant is itself polynomially bounded in the relevant instance-complexity parameters.