* Huang and Kim, (2014) Huang, Z. and Kim, A. (2014).  Welfare maximization with production costs: A primal dual approach.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 59–72. SIAM.
  * Huber, (1964) Huber, P. J. (1964).  Robust estimation of a location parameter.  The Annals of Mathematical Statistics, 35(1):73–101.
  * Huber, (1967) Huber, P. J. (1967).  Under nonstandard conditions.  In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability: Weather modification, volume 5, page 221. Univ of California Press.
  * Jasin, (2015) Jasin, S. (2015).  Performance of an lp-based control for revenue management with unknown demand parameters.  Operations Research, 63(4):909–915.
  * Jasin and Kumar, (2012) Jasin, S. and Kumar, S. (2012).  A re-solving heuristic with bounded revenue loss for network revenue management with customer choice.  Mathematics of Operations Research, 37(2):313–345.
  * Jenatton et al., (2016) Jenatton, R., Huang, J., and Archambeau, C. (2016).  Adaptive algorithms for online convex optimization with long-term constraints.  In International Conference on Machine Learning, pages 402–411. PMLR.
  * Kakade et al., (2009) Kakade, S., Shalev-Shwartz, S., Tewari, A., et al. (2009).  On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization.  Unpublished Manuscript, http://ttic. uchicago. edu/shai/papers/KakadeShalevTewari09. pdf, 2(1):35.
  * Kim et al., (2015) Kim, S., Pasupathy, R., and Henderson, S. G. (2015).  A guide to sample average approximation.  Handbook of simulation optimization, pages 207–243.
  * Kleinberg, (2005) Kleinberg, R. (2005).  A multiple-choice secretary algorithm with applications to online auctions.  In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 630–631. Citeseer.
  * Kleywegt et al., (2002) Kleywegt, A. J., Shapiro, A., and Homem-de Mello, T. (2002).  The sample average approximation method for stochastic discrete optimization.  SIAM Journal on Optimization, 12(2):479–502.
  * Lee et al., (2013) Lee, K.-C., Jalali, A., and Dasdan, A. (2013).  Real time bid optimization with smooth budget delivery in online advertising.  In Proceedings of the seventh international workshop on data mining for online advertising, pages 1–9.
  * Li and Ye, (2021) Li, X. and Ye, Y. (2021).  Online linear programming: Dual convergence, new algorithms, and regret bounds.  Operations Research.
  * Lobos et al., (2021) Lobos, A., Grigas, P., and Wen, Z. (2021).  Joint online learning and decision-making via dual mirror descent.  In International Conference on Machine Learning, pages 7080–7089. PMLR.
  * Mahdavi et al., (2012) Mahdavi, M., Jin, R., and Yang, T. (2012).  Trading regret for efficiency: online convex optimization with long term constraints.  The Journal of Machine Learning Research, 13(1):2503–2528.
  * McMahan, (2011) McMahan, B. (2011).  Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization.  In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 525–533. JMLR Workshop and Conference Proceedings.
  * McMahan, (2017) McMahan, H. B. (2017).  A survey of algorithms and analysis for adaptive online learning.  The Journal of Machine Learning Research, 18(1):3117–3166.
  * Mehta, (2013) Mehta, A. (2013).  Online matching and ad allocation.  Foundations and Trends® in Theoretical Computer Science, 8(4):265–368.
  * Mehta et al., (2007) Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. (2007).  Adwords and generalized online matching.  Journal of the ACM (JACM), 54(5):22–es.
  * Molinaro and Ravi, (2014) Molinaro, M. and Ravi, R. (2014).  The geometry of online packing linear programs.  Mathematics of Operations Research, 39(1):46–59.
  * Nash, (1950) Nash, J. F. (1950).  The bargaining problem.  Econometrica, 18(2):155–162.
  * Nesterov, (2009) Nesterov, Y. (2009).  Primal-dual subgradient methods for convex problems.  Mathematical programming, 120(1):221–259.
  * Rakhlin et al., (2012) Rakhlin, A., Shamir, O., and Sridharan, K. (2012).  Making gradient descent optimal for strongly convex stochastic optimization.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571–1578.
  * Reiman and Wang, (2008) Reiman, M. I. and Wang, Q. (2008).  An asymptotically optimal policy for a quantity-based network revenue management problem.  Mathematics of Operations Research, 33(2):257–282.
  * Rost et al., (2017) Rost, P., Mannweiler, C., Michalopoulos, D. S., Sartori, C., Sciancalepore, V., Sastry, N., Holland, O., Tayade, S., Han, B., Bega, D., et al. (2017).  Network slicing to enable scalability and flexibility in 5g mobile networks.  IEEE Communications magazine, 55(5):72–79.
  * Ruszczyński and Shapiro, (2003) Ruszczyński, A. and Shapiro, A. (2003).  Stochastic programming models.  Handbooks in operations research and management science, 10:1–64.
  * Shapiro et al., (2009) Shapiro, A., Dentcheva, D., and Ruszczynski, A. (2009).  Lectures on stochastic programming: modeling and theory.  SIAM.
  * Talluri et al., (2004) Talluri, K. T., Van Ryzin, G., and Van Ryzin, G. (2004).  The theory and practice of revenue management, volume 1.  Springer.
  * Tan et al., (2020) Tan, X., Leon-Garcia, A., Wu, Y., and Tsang, D. H. K. (2020).  Online combinatorial auctions for resource allocation with supply costs and capacity limits.  IEEE Journal on Selected Areas in Communications, 38(4):655–668.
  * Vazirani et al., (2005) Vazirani, U., Vazirani, V., Mehta, A., and Saberi, A. (2005).  Adwords and generalized on-line matching.  In Proceedings of FOCS.
  * Wu et al., (2015) Wu, H., Srikant, R., Liu, X., and Jiang, C. (2015).  Algorithms with logarithmic or sublinear regret for constrained contextual bandits.  Advances in Neural Information Processing Systems, 28.
  * Xiao, (2010) Xiao, L. (2010).  Dual averaging methods for regularized stochastic learning and online optimization.  Journal of Machine Learning Research, 11:2543–2596.
  * Yu et al., (2017) Yu, H., Neely, M., and Wei, X. (2017).  Online convex optimization with stochastic constraints.  Advances in Neural Information Processing Systems, 30.
  * Yuan and Lamperski, (2018) Yuan, J. and Lamperski, A. (2018).  Online convex optimization for cumulative constraints.  Advances in Neural Information Processing Systems, 31.
  * Zinkevich, (2003) Zinkevich, M. (2003).  Online convex programming and generalized infinitesimal gradient ascent.  In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936.

Supplement to “ Optimal Regularized Online Convex Allocation by Adaptive Re-
Solving ”

##  Appendix A Proofs of Main Results

###  A.1 Proof of Lemma 1

We prove the bound of the deterministic optimal solution. Consider
$\Omega^{\prime}_{\mu}=\left\\{-\nabla r(a)\middle|a\in\mathcal{Z}\right\\}$ .
The bounded subgradient in Assumption 2.1 suggests that the dual variable
region $\Omega_{\mu}^{\prime}$ we defined is bounded by $G$. We explain this
definition by the optimal conditions of stochasic programming. Note that for
problem (2.8), $\mu$ is unconstrained. The optimal condition suggests that

$\nabla r^{*}(-\mu^{*})=\mathbb{E}b_{t}\nabla
f^{*}_{t}(b_{t}^{\top}(\lambda^{*}+\mu^{*}))$

if we assume fubini theorem holds. Then by the Fenchel conjugate, we have
$\mu^{*}\in-\nabla r(\mathbb{E}b_{t}\tilde{x}_{t})$. This shows that by
defining $\Omega^{\prime}_{\mu}$ we indeed define the possible region that
contains optimal solution $\mu^{*}$, i.e., $\mu^{*}\in\Omega_{\mu}$. Thus we
have $\left\lVert\mu\right\rVert_{\infty}\leq G$.

For the second bound of $\left\lVert\lambda^{*}\right\rVert_{\infty}$, we only
need to check that $d^{\top}\lambda^{*}\leq 2(\bar{f}+\bar{r})$ always holds.
Otherwise if $d^{\top}\lambda^{*}>2(\bar{f}+\bar{r})$, we have

$\displaystyle D(\boldsymbol{\lambda}^{*},d)$
$\displaystyle=\mathbb{E}\sup_{x}\\{f_{t}(x)-(\lambda^{*}+\mu^{*})^{\top}b_{t}x_{t}\\}+\sup_{a}\\{r(a)+a^{\top}\mu^{*}\\}+d^{\top}\lambda^{*}\geq\mathbb{E}f_{t}(0)+r(0)+d^{\top}\lambda^{*}$
$\displaystyle>(\bar{f}+\bar{r})\geq D(\boldsymbol{0},d),$

which suggests that $\boldsymbol{\lambda}^{*}$ is not optimal. Thus we have
$d^{\top}\lambda^{*}\leq 2(\bar{f}+\bar{r})$, i.e.,
$\left\lVert\lambda^{*}\right\rVert_{\infty}\leq\frac{2(\bar{f}+\bar{r})}{\underline{d}}$.
The bound of empirical optimal solution $\boldsymbol{\lambda}^{*}_{T}$ follows
exactly the same argument.

###  A.2 Proof of Proposition 1

We consider

$\displaystyle D(\boldsymbol{\lambda},d)-D(\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})=\int_{0}^{1}\left[\nabla
D(z(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})+\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)\right]^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})dz,$

where $\nabla
D(\boldsymbol{\lambda},d)=\left[\begin{array}[]{c}\mathbb{E}b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu+\lambda))+d\\\ \mathbb{E}b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu+\lambda)-\nabla r^{*}(-\mu)\end{array}\right]$.
Then for any $z$, we have

$\displaystyle\left[\nabla
D(z(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})+\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)\right]^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})$
$\displaystyle\leq$ $\displaystyle\left\lVert\mathbb{E}b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(z(\mu+\lambda-\mu^{*}-\lambda^{*})+\mu^{*}+\lambda^{*})-\mathbb{E}b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu^{*}+\lambda^{*}))\right\rVert_{2}(\left\lVert\lambda-\lambda^{*}\right\rVert_{2}+\left\lVert\mu-\mu^{*}\right\rVert_{2})$
$\displaystyle+\left\lVert\nabla r^{*}(-\mu)-\nabla
r^{*}(-\mu^{*})\right\rVert_{2}\left\lVert\mu-\mu^{*}\right\rVert_{2}$
$\displaystyle\leq$ $\displaystyle\left\lVert
z\bar{\mathcal{L}}_{f}\bar{b}\mathbb{E}\left[b_{t}^{\top}(\mu+\lambda-\mu^{*}-\lambda^{*})\right]\right\rVert_{2}(\left\lVert\lambda-\lambda^{*}\right\rVert_{2}+\left\lVert\mu-\mu^{*}\right\rVert_{2})+\bar{\mathcal{L}}_{r}z\left\lVert\mu-\mu^{*}\right\rVert_{2}^{2}$
$\displaystyle\leq$ $\displaystyle
z\bar{\mathcal{L}}_{f}\bar{b}^{2}(\left\lVert\lambda-\lambda^{*}\right\rVert_{2}+\left\lVert\mu-\mu^{*}\right\rVert_{2})^{2}+\bar{\mathcal{L}}_{r}z\left\lVert\mu-\mu^{*}\right\rVert_{2}^{2}\leq
z(2\bar{b}^{2}\bar{\mathcal{L}}_{f}+\bar{\mathcal{L}}_{r})\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2},$

where the second inequality is by Assumption 3.1 when conditioned on $b_{t}$
and Assumption 2.3. By the integral of $z$ we have

$D(\boldsymbol{\lambda},d)-D(\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})\leq(\bar{b}^{2}\bar{\mathcal{L}}_{f}+\bar{\mathcal{L}}_{r}/2)\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}.$

For the next direction we have

$\displaystyle\left[\nabla
D(z(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})+\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)\right]^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\langle\nabla{f^{*}_{t}}(b_{t}^{\top}(z(\mu+\lambda-\mu^{*}-\lambda^{*})+\mu^{*}+\lambda^{*}))-\nabla{f^{*}_{t}}(b_{t}^{\top}(\mu^{*}+\lambda^{*})),b_{t}^{\top}(\mu+\lambda-\mu^{*}-\lambda^{*})\rangle\right]\middle|b_{t}\right]$
$\displaystyle+\langle\nabla r^{*}(-(z(\mu-\mu^{*})+\mu^{*}))-\nabla
r^{*}(-\mu^{*}),\mu^{*}-\mu\rangle$ $\displaystyle\geq$ $\displaystyle
z\underline{\mathcal{L}}_{f}\mathbb{E}\left\lVert
b_{t}^{\top}(\mu+\lambda-\mu^{*}-\lambda^{*})\right\rVert_{2}^{2}+z\underline{\mathcal{L}}_{r}\left\lVert\mu-\mu^{*}\right\rVert_{2}^{2}\geq
z\underline{\mathcal{L}}_{f}\sigma_{\min}\left\lVert\mu+\lambda-\mu^{*}-\lambda^{*}\right\rVert_{2}^{2}+z\underline{\mathcal{L}}_{r}\left\lVert\mu-\mu^{*}\right\rVert_{2}^{2}.$

Here the first inequality is by Assumption 3.1 when conditioned on $b_{t}$ and
Assumption 2.2. With the inequality $\left\lVert
a+b\right\rVert^{2}=\left\lVert a\right\rVert^{2}+\left\lVert
b\right\rVert^{2}+2\langle a,b\rangle\geq\left\lVert
a\right\rVert^{2}+\left\lVert b\right\rVert^{2}-(1+\delta)\left\lVert
a\right\rVert^{2}-\frac{1}{1+\delta}\left\lVert
b\right\rVert^{2}=-\delta\left\lVert
a\right\rVert^{2}+\frac{\delta}{1+\delta}\left\lVert b\right\rVert^{2}$ for
any positive $\delta$, we choose
$\delta=\frac{\underline{\mathcal{L}}_{r}}{2\underline{\mathcal{L}}_{f}\sigma_{\min}}$
and $a=\mu-\mu^{*}$, $b=\lambda-\lambda^{*}$. Then we have

$\displaystyle\left[\nabla
D(z(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})+\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)\right]^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})\geq$
$\displaystyle
z\left(\frac{\underline{\mathcal{L}}_{r}}{\underline{\mathcal{L}}_{r}+2\underline{\mathcal{L}}_{f}\sigma_{\min}}\left\lVert\lambda-\lambda^{*}\right\rVert_{2}^{2}+\frac{\underline{\mathcal{L}}_{r}}{2}\left\lVert\mu-\mu^{*}\right\rVert_{2}^{2}\right)$
$\displaystyle\geq$ $\displaystyle
z(\frac{\underline{\mathcal{L}}_{r}}{2}\wedge\frac{\underline{\mathcal{L}}_{r}}{\underline{\mathcal{L}}_{r}+2\underline{\mathcal{L}}_{f}\sigma_{\min}})\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}.$

By the integral of $z$ we can get the corresponding lower bound of the growth
of $D(\boldsymbol{\lambda},d)$. Thus we have

$\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}\leq
D(\boldsymbol{\lambda},d)-D(\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)^{\top}(\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*})\leq\bar{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2},$

where the constant
$\underline{\mathcal{L}}_{D}=\frac{\underline{\mathcal{L}}_{r}}{4}\wedge\frac{1}{2}\frac{\underline{\mathcal{L}}_{r}}{\underline{\mathcal{L}}_{r}+2\underline{\mathcal{L}}_{f}\sigma_{\min}}$,
$\bar{\mathcal{L}}_{D}=\bar{b}^{2}\bar{\mathcal{L}}_{f}+\bar{\mathcal{L}}_{r}/2$.

###  A.3 Proof of Lemma 2

Since
$\phi_{t}(\boldsymbol{\lambda}^{*},d)=\left[\begin{array}[]{c}b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu^{*}+\lambda^{*}))+d\\\ b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu^{*}+\lambda^{*})-\nabla
r^{*}(-\mu^{*})\end{array}\right]=\left[\begin{array}[]{c}\partial_{\lambda}D_{t}(\boldsymbol{\lambda}^{*},d)\\\
\partial_{\mu}D_{t}(\boldsymbol{\lambda}^{*},d)\end{array}\right]$, we
consider the partial gradient of $\lambda,\ \mu$ separately.

For any dimension $i\in[m]$,
$|(\partial_{\lambda}D_{t}(\boldsymbol{\lambda}^{*},d))_{i}-d_{i}|=|(b_{t}\nabla
f_{t}^{*}(b_{t}^{\top}(\mu^{*}+\lambda^{*})))_{i}|\leq\sqrt{n}\bar{b}D$, then

$\left\lvert(\partial_{\lambda}D_{t}(\boldsymbol{\lambda}^{*},d))_{i}\right\rvert\leq\sqrt{n}\bar{b}D+\bar{d};$

we also have

$\left\lvert(\partial_{\mu}D_{t}(\boldsymbol{\lambda}^{*},d))_{i}\right\rvert\leq\sqrt{n}\bar{b}D+G,$

According to Hoeffding’s inequality, we have

$\displaystyle\mathop{{}\mathbb{P}}(\left\lvert\left(\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d)\right)_{i}-\left(\nabla
D(\boldsymbol{\lambda}^{*},d)\right)_{i}\right\rvert>\varepsilon/\sqrt{2m})\leq
2\exp(-\frac{T\varepsilon^{2}}{4mc_{3}})$

for $\forall i\in[2m]$.

Combining all $2m$ dimensions together we conclude that

$\mathop{{}\mathbb{P}}(\left\lVert\frac{1}{T}\sum_{t=1}^{T}\phi_{t}(\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)\right\rVert>\varepsilon)\leq 2m\cdot
2\exp(-\frac{T\varepsilon^{2}}{4mc_{1}})=4m\exp(-\frac{T\varepsilon^{2}}{4mc_{1}}).$

###  A.4 Proof of Proposition 2

For any given $\varepsilon>0$, we define the neighbourhood of
$\boldsymbol{\lambda}^{*}$ for given $\varepsilon$ as 3.4. We then construct a
good event $\mathcal{E}(\varepsilon)$ that only depends on $\varepsilon$ to
guarantee that under this good event, the convex function
$\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)$
is larger than a quadratic function in
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$, which serves as a lower bound of
dual function. The construction of this good event $\mathcal{E}(\varepsilon)$
is based on the following splitting scheme and concentration of objective
function:

  1. 1.

Firstly we confine the first order term so that
$\bar{\phi}_{T}(\boldsymbol{\lambda},d)=\frac{1}{T}\sum_{t=1}^{T}\phi_{t}(\boldsymbol{\lambda},d)$
will not vary too much. This can be guaranteed by the concentration inequality
Lemma 2.

  2. 2.

Then we split $\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ into multiple cubes
layer by layer and in each single cube, we control the difference of second
order terms between all the $\boldsymbol{\lambda}$ in the cube and the central
point of the cube.

  3. 3.

Finally we uniformly control the deviation of second order terms for all
central points.

For the first order term, denote event
$\mathcal{E}_{0}(\varepsilon)=\\{\left\lVert\bar{\phi}_{T}(\boldsymbol{\lambda},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)\right\rVert_{2}>\varepsilon\\}$. Then by Lemma
2, we have $\mathop{{}\mathbb{P}}(\mathcal{E}_{0}(\varepsilon))\leq
4m\exp(-\frac{T\varepsilon^{2}}{4mc_{1}})$. Under event
$\mathcal{E}_{0}^{c}(\varepsilon)$, we have

$\left\langle\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle\geq\left\langle\nabla
D(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle-\varepsilon\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq-\varepsilon\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}.$
(A.1)

We now discuss the second order term of $\bar{D}_{T}(\boldsymbol{\lambda},d)$.
Define the second order term

$\displaystyle
s_{t}(\boldsymbol{\lambda},d)=D_{t}(\boldsymbol{\lambda},d)-D_{t}(\boldsymbol{\lambda}^{*},d)-\left\langle\phi_{t}(\boldsymbol{\lambda}^{*}d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle$
$\displaystyle\bar{s}_{T}(\boldsymbol{\lambda},d)=\frac{1}{T}\sum_{t=1}^{T}s_{t}(\boldsymbol{\lambda},d).$

To derive an uniform lower bound of $\bar{s}_{T}(\boldsymbol{\lambda},d)$, we
do the following split on $\Omega_{\boldsymbol{\lambda}}(\varepsilon)$
according to Huber, (1967).

Define set
$\Omega^{k}_{\boldsymbol{\lambda}}(\varepsilon)=\left\\{(\lambda,\mu)|\left\lVert\lambda-\lambda^{*}\right\rVert_{\infty}\leq
q^{k}4H\varepsilon,\left\lVert\mu-\mu^{*}\right\rVert_{\infty}\leq
q^{k}4H\varepsilon\right\\},0\leq k\leq N$, where $q\in(0,1)$ and
$N\in\mathbb{N}_{+}$ will be identified later. This split divides
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ into $N$ layers
$\\{\Omega^{k-1}_{\boldsymbol{\lambda}}(\varepsilon)\backslash\Omega^{k}_{\boldsymbol{\lambda}}(\varepsilon)\\}_{k=1}^{N}$
and a center cube $\Omega^{N}_{\boldsymbol{\lambda}}(\varepsilon)$. We then
split each layer into disjoint cubes
$\\{\bar{\Omega}^{kl}(\varepsilon)\\}_{l=1}^{l_{k}}$ with edges of length
$(1-q)q^{k-1}4H\varepsilon$, and denote the center cube by
$\bar{\Omega}^{N1}(\varepsilon)$. Huber, (1967) shows that there are at most
$(2N)^{2m}$ cubes. This split is not unique to get the desired convergence
order but it makes our result tighter. The center of each cube
$\bar{\Omega}^{kl}(\varepsilon)$ is
$\boldsymbol{\lambda}_{kl}=(\lambda_{kl},\mu_{kl})$. Define
$\bar{\boldsymbol{\lambda}}_{kl}=\arg\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$,
and

$\displaystyle\Gamma^{kl}_{t}$
$\displaystyle=\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left[s_{t}(\boldsymbol{\lambda}_{kl},d)-s_{t}(\boldsymbol{\lambda},d)\right]$
(A.2)
$\displaystyle=\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left[D_{t}(\boldsymbol{\lambda}_{kl},d)-D_{t}(\boldsymbol{\lambda},d)-\left\langle\phi_{t}(\boldsymbol{\lambda}^{*}d),\boldsymbol{\lambda}_{kl}-\boldsymbol{\lambda}\right\rangle\right].$

Then for $k\in\\{0,\dots,N-1\\}$, and
$\forall\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)$, $\bar{s}_{T}$
can be decomposed as

$\displaystyle\bar{s}_{T}(\boldsymbol{\lambda},d)=$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}s_{t}(\boldsymbol{\lambda},d)-\frac{1}{T}\sum_{t=1}^{T}s_{t}(\boldsymbol{\lambda}_{kl},d)+\frac{1}{T}\sum_{t=1}^{T}s_{t}(\boldsymbol{\lambda}_{kl},d)$
(A.3) $\displaystyle\geq$
$\displaystyle\underbrace{\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)-\mathbb{E}\Gamma^{kl}_{t}}_{\ref{eq:sec_decomp}.1}+\underbrace{-\frac{1}{T}\sum_{t=1}^{T}\Gamma^{kl}_{t}+\mathbb{E}\Gamma^{kl}_{t}}_{\ref{eq:sec_decomp}.2}+\underbrace{\frac{1}{T}\sum_{t=1}^{T}s_{t}(\boldsymbol{\lambda}_{kl},d)-\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)}_{\ref{eq:sec_decomp}.3}$

We study lower bounds of these 3 terms in (A.3) respectively.

Lower bound of A.3.1:

$\displaystyle\mathbb{E}\Gamma^{kl}_{t}=$
$\displaystyle\mathbb{E}\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left[f_{t}^{*}(b_{t}^{\top}(\lambda_{kl}+\mu_{kl}))+r^{*}(-\mu_{kl})-f_{t}^{*}(b_{t}^{\top}(\lambda+\mu))-r^{*}(-\mu)\right.$
(A.4) $\displaystyle\left.-\nabla
f_{t}^{*}(\lambda^{*}+\mu^{*})^{\top}b_{t}^{\top}(\lambda_{kl}+\mu_{kl}-\lambda-\mu)+\nabla
r^{*}(-\mu^{*})^{\top}(\mu_{kl}-\mu)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left[\int_{0}^{1}v_{1}^{\top}(\boldsymbol{\lambda})\left[\nabla
f_{t}^{*}(b_{t}^{\top}(\lambda+\mu)+v_{1}\cdot z)-\nabla
f_{t}^{*}(b_{t}^{\top}(\lambda^{*}+\mu^{*}))\right]dz\right.$
$\displaystyle\left.+\int_{0}^{1}(\mu_{kl}-\mu)^{\top}\left[-\nabla
r^{*}(-\mu-(\mu_{kl}-\mu)\cdot z)+\nabla r^{*}(-\mu^{*})\right]\right]dz$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\int_{0}^{1}v_{1}^{\top}(\tilde{\lambda},\tilde{\mu})\left[\nabla
f_{t}^{*}(b_{t}^{\top}(\tilde{\lambda}+\tilde{\mu})+v_{1}\cdot z)-\nabla
f_{t}^{*}(b_{t}^{\top}(\lambda^{*}+\mu^{*})))\right]dz\right.$
$\displaystyle\left.+\int_{0}^{1}(\mu_{kl}-\tilde{\mu})^{\top}\left[-\nabla
r^{*}(-\tilde{\mu}-(\mu_{kl}-\tilde{\mu})\cdot z)+\nabla
r^{*}(-\mu^{*})\right]\right]dz\ \text{for some
$(\tilde{\lambda},\tilde{\mu})\in\sigma(f_{t},b_{t})$}$ $\displaystyle\leq$
$\displaystyle\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert
v_{1}\right\rVert_{2}\cdot\sqrt{L_{2}}\bar{b}\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\lambda+\mu-\lambda^{*}-\mu^{*}\right\rVert_{2}+\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\mu_{kl}-\mu\right\rVert_{2}\cdot\bar{\mathcal{L}}_{r}\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\mu-\mu^{*}\right\rVert_{2}$
$\displaystyle\leq$
$\displaystyle\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}\cdot(\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\lambda_{kl}-\lambda\right\rVert_{2}+\left\lVert\mu_{kl}-\mu\right\rVert_{2})\cdot(\left\lVert\bar{\lambda}_{kl}-\lambda^{*}\right\rVert_{2}+\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2})$

where
$v_{1}(\boldsymbol{\lambda})=b_{t}^{\top}(\lambda_{kl}+\mu_{kl}-\lambda-\mu)$
is the direction vector, and the first inequality is obtained by Assumption 2
and Assumption 4.

According to Proposition 1, we have

$\displaystyle\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)=$ $\displaystyle
D(\boldsymbol{\lambda}_{kl},d)-D(\boldsymbol{\lambda}^{*},d)-\nabla
D(\boldsymbol{\lambda}^{*},d)^{\top}\left[\begin{array}[]{c}\lambda_{kl}-\lambda^{*}\\\
\mu_{kl}-\mu^{*}\end{array}\right]$
$\displaystyle\geq\underline{\mathcal{L}}_{D}(\left\lVert\mu_{kl}-\mu^{*}\right\rVert_{2}^{2}+\left\lVert\lambda_{kl}-\lambda^{*}\right\rVert_{2}^{2})$

So for the first term we have

$\displaystyle-\mathbb{E}\Gamma^{kl}_{t}+\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)$
(A.5)
$\displaystyle\geq\underline{\mathcal{L}}_{D}(\left\lVert\mu_{kl}-\mu^{*}\right\rVert_{2}^{2}+\left\lVert\lambda_{kl}-\lambda^{*}\right\rVert_{2}^{2})$
$\displaystyle-\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}\cdot(\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\lambda_{kl}-\lambda\right\rVert_{2}+\left\lVert\mu_{kl}-\mu\right\rVert_{2})\cdot(\left\lVert\bar{\lambda}_{kl}-\lambda^{*}\right\rVert_{2}+\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2})$

Lower bound of A.3.2: Since the gradients $\left\lVert\nabla
f_{t}^{*}\right\rVert_{\infty}$, $\left\lVert\nabla
r^{*}\right\rVert_{\infty}$ are bounded by $D$ and $G$, by the integral form
of $\Gamma_{kl}$ in the second equality of A.4, we also have:

$\displaystyle\left\lVert\Gamma^{kl}_{t}\right\rVert_{2}\leq$ $\displaystyle
2\sqrt{n}\bar{b}D\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\mu+\lambda-\mu_{kl}-\lambda_{kl}\right\rVert+2\sqrt{m}G\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\mu-\mu_{kl}\right\rVert_{2}$
$\displaystyle\leq$ $\displaystyle
2(\sqrt{n}\bar{b}D+\sqrt{m}G)(\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\lambda-\lambda_{kl}\right\rVert_{2}+\left\lVert\mu-\mu_{kl}\right\rVert_{2}),$

for any $t\in[T]$.

Define event

$\mathcal{E}_{kl,1}(\varepsilon)=\left\\{-\frac{1}{T}\sum_{t=1}^{T}\Gamma^{kl}_{t}+\mathbb{E}\Gamma^{kl}_{t}<-2\varepsilon(\sqrt{n}\bar{b}D+\sqrt{m}G)(\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\lambda-\lambda_{kl}\right\rVert_{2}+\left\lVert\mu-\mu_{kl}\right\rVert_{2})\right\\}.$
(A.6)

Then according to Hoeffding’s inequality,
$\mathop{{}\mathbb{P}}(\mathcal{E}_{kl,1}(\varepsilon))\leq\exp(-\frac{T\varepsilon^{2}}{2})$

Lower bound of A.3.3: We calculate the norm of each
$s_{t}(\boldsymbol{\lambda}_{kl},d)$:

$\displaystyle\left\lVert s_{t}(\boldsymbol{\lambda}_{kl},d)\right\rVert_{2}=$
$\displaystyle\left\|\left[\int_{0}^{1}v_{2}^{\top}\left[\nabla
f_{t}^{*}(b_{t}(\lambda^{*}+\mu^{*})+v_{2}\cdot z)-\nabla
f_{t}^{*}(\lambda^{*}+\mu^{*})\right]dz\right.\right.$ (A.7)
$\displaystyle\left.\left.+\int_{0}^{1}(\mu_{kl}-\mu^{*})^{\top}\left[-\nabla
r^{*}(-\mu^{*}-(\mu_{kl}-\mu^{*})\cdot z)+\nabla
r^{*}(-\mu^{*})\right]\right]dz\right\|_{2}$ $\displaystyle\leq$
$\displaystyle
2\sqrt{n}\bar{b}D(\left\lVert\bar{\lambda}_{kl}-\lambda^{*}\right\rVert_{2}+\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2})+2\sqrt{m}G\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2}$
$\displaystyle\leq$ $\displaystyle
2(\sqrt{n}\bar{b}D+\sqrt{m}G)(\left\lVert\bar{\lambda}_{kl}-\lambda^{*}\right\rVert_{2}+\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2}),$

for any $t\in[T]$, where
$v_{2}=b_{t}^{\top}(\lambda_{kl}+\mu_{kl}-\lambda^{*}-\mu^{*})$ is the
direction vector.

Define event

$\mathcal{E}_{kl,2}=\left\\{\frac{1}{T}\sum_{t=1}^{T}s_{t}(\boldsymbol{\lambda}_{kl},d)-\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)<-2\varepsilon(\sqrt{n}\bar{b}D+\sqrt{m}G)(\left\lVert\bar{\lambda}_{kl}-\lambda^{*}\right\rVert_{2}+\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2})\right\\}.$
(A.8)

Then we have
$\mathop{{}\mathbb{P}}(\mathcal{E}_{kl,2})\leq\exp(-\frac{T\varepsilon^{2}}{2})$
by Hoeffding’s inequality.

Now we would like to make all the quantities in the lower bound uniform by
leveraging the splitting scheme. From the split, we have

$\displaystyle\max_{\lambda\in\bar{\Omega}^{kl}(\varepsilon)}\left\|\lambda-\lambda_{kl}\right\|_{2}$
$\displaystyle=\sqrt{m}(1-q)q^{k-1}4H\varepsilon,$
$\displaystyle\max_{\mu\in\bar{\Omega}^{kl}(\varepsilon)}\left\|\mu-\mu_{kl}\right\|_{2}$
$\displaystyle=\sqrt{m}(1-q)q^{k-1}4H\varepsilon,$
$\displaystyle\left\|\lambda^{*}-\lambda_{kl}\right\|_{2}$ $\displaystyle\geq
q^{k}4H\varepsilon,$ $\displaystyle\left\|\mu^{*}-\mu_{kl}\right\|_{2}$
$\displaystyle\geq q^{k}4H\varepsilon.$

And also

$\displaystyle\left\|\lambda^{*}-\bar{\lambda}_{kl}\right\|_{2}$
$\displaystyle\leq\left\|\lambda^{*}-\lambda_{kl}\right\|_{2}+\max_{\bar{\Omega}^{kl}(\varepsilon)}\left\|\lambda-\lambda_{kl}\right\|_{2}$
$\displaystyle\leq\left(1+\frac{\sqrt{m}(1-q)}{q}\right)\left\|\lambda-\lambda_{kl}\right\|_{2},$
$\displaystyle\left\|\mu^{*}-\bar{\mu}_{kl}\right\|_{2}$
$\displaystyle\leq\left(1+\frac{\sqrt{m}(1-q)}{q}\right)\left\|\mu-\mu_{kl}\right\|_{2},$
$\displaystyle\max_{\lambda\in\bar{\Omega}^{kl}(\varepsilon)}\left\|\lambda-\lambda_{kl}\right\|_{2}$
$\displaystyle\leq\frac{\sqrt{m}(1-q)}{q}\left\lVert\lambda^{*}-\lambda_{kl}\right\rVert_{2}\leq\frac{\sqrt{m}(1-q)}{q}\left\lVert\lambda^{*}-\bar{\lambda}_{kl}\right\rVert_{2}\
\text{(so as $\mu$)}.$

Thus we have the following result for the A.3.1 term in (A.5).

$\displaystyle-\mathbb{E}\Gamma^{kl}_{t}+\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)\geq$
$\displaystyle\underline{\mathcal{L}}_{D}(\left\lVert\mu_{kl}-\mu^{*}\right\rVert_{2}^{2}+\left\lVert\lambda_{kl}-\lambda^{*}\right\rVert_{2}^{2})$
$\displaystyle-\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}\cdot(\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\lambda_{kl}-\lambda\right\rVert_{2}+\left\lVert\mu_{kl}-\mu\right\rVert_{2})\cdot(\left\lVert\bar{\lambda}_{kl}-\lambda^{*}\right\rVert_{2}+\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2})$
$\displaystyle\geq$
$\displaystyle\frac{\underline{\mathcal{L}}_{D}}{\left(1+\frac{\sqrt{m}(1-q)}{q}\right)^{2}}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}-2\frac{\sqrt{m}(1-q)}{q}\cdot\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}$

So there exists
$\underline{q}=\frac{\sqrt{m}}{\sqrt{m}+1\wedge\frac{\underline{\mathcal{L}}_{D}}{8\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}}}$
such that when $q\geq\underline{q}$, $\frac{\sqrt{m}(1-q)}{q}\leq
1\wedge\frac{\underline{\mathcal{L}}_{D}}{8\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}}$,
and

$\frac{\underline{\mathcal{L}}_{D}}{(1+\frac{\sqrt{m}(1-q)}{q})^{2}}-2\frac{\sqrt{m}(1-q)}{q}\cdot\sqrt{L_{2}}\bar{b}^{2}\vee\bar{\mathcal{L}}_{r}\geq\underline{\mathcal{L}}_{D}/2.$

Choose $q=\underline{q}\vee\frac{1}{2}$. Then for the A.3.1 term in (A.5) we
have

$-\mathbb{E}\Gamma^{kl}_{t}+\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)\geq\frac{\underline{\mathcal{L}}_{D}}{2}(\left\lVert\bar{\mu}_{kl}-\mu^{*}\right\rVert_{2}^{2}+\left\lVert\bar{\lambda}_{kl}-\lambda^{*}\right\rVert_{2}^{2})=\frac{\underline{\mathcal{L}}_{D}}{2}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}.$
(A.9)

For A.3.2, under event $\mathcal{E}_{kl,1}^{c}(\varepsilon)$ in (A.6) we have

$\displaystyle-\frac{1}{T}\sum_{t=1}^{T}\Gamma^{kl}_{t}+\mathbb{E}\Gamma^{kl}_{t}$
$\displaystyle\geq-2\varepsilon(\sqrt{n}\bar{b}D+\sqrt{m}G)(\max_{\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)}\left\lVert\lambda-\lambda_{kl}\right\rVert_{2}+\left\lVert\mu-\mu_{kl}\right\rVert_{2})$
(A.10)
$\displaystyle\geq-2\sqrt{2}\varepsilon(\sqrt{n}\bar{b}D+\sqrt{m}G)\frac{\sqrt{m}(1-q)}{q}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}.$

For A.3.3, under event $\mathcal{E}_{kl,2}^{c}(\varepsilon)$ in (A.8) we have

$\frac{1}{T}\sum_{t=1}^{T}s_{t}(\boldsymbol{\lambda}_{kl},d)-\mathbb{E}s_{t}(\boldsymbol{\lambda}_{kl},d)\geq-2\sqrt{2}\varepsilon(\sqrt{n}\bar{b}D+\sqrt{m}G)\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}.$
(A.11)

Now we combine first order lower bound in (A.1) and second order lower bound
in (A.9), (A.10), (A.11) together under the desired good event

$\displaystyle\mathcal{E}(\varepsilon)=\mathcal{E}_{0}^{c}(\varepsilon)\cap_{k=1}^{N}\cap_{l}(\mathcal{E}_{kl,1}^{c}(\varepsilon)\cap\mathcal{E}^{c}_{kl,2}(\varepsilon)),$

where we choose $N$ by setting the radius of $\bar{\Omega}^{N1}(\varepsilon)$:
$\sqrt{2m}q^{N}4H\varepsilon\leq 2H\varepsilon$, i.e.,
$N=\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil$. Under
$\mathcal{E}(\varepsilon)$, for any
$\boldsymbol{\lambda}\in\Omega_{\boldsymbol{\lambda}}(\varepsilon)$ satisfying
$\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}>2H\varepsilon$,
there exists $k=\\{0,\dots,N-1\\}$ and $l$ such that
$\boldsymbol{\lambda}\in\bar{\Omega}^{kl}(\varepsilon)$, and

$\displaystyle\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)=$
$\displaystyle\left\langle\bar{\phi}_{T}(\boldsymbol{\lambda}^{*},d),\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rangle+\bar{s}_{T}(\boldsymbol{\lambda},d)$
$\displaystyle\geq$
$\displaystyle\frac{\underline{\mathcal{L}}_{D}}{2}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}-2\sqrt{2}\varepsilon(\sqrt{n}\bar{b}D+\sqrt{m}G)\frac{\sqrt{m}(1-q)}{q}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$
$\displaystyle-2\sqrt{2}\varepsilon(\sqrt{n}\bar{b}D+\sqrt{m}G)\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}-\varepsilon\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$
$\displaystyle=$
$\displaystyle\frac{\underline{\mathcal{L}}_{D}}{2}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}-H\varepsilon\cdot\underline{\mathcal{L}}_{D}\left\lVert\bar{\boldsymbol{\lambda}}_{kl}-\boldsymbol{\lambda}^{*}\right\rVert_{2}$

where
$H=\left(1+2\sqrt{2}(\sqrt{n}\bar{b}D+\sqrt{m}G)(1+\frac{\sqrt{m}(1-q)}{q})\right)/\underline{\mathcal{L}}_{D}$.

Compute the probability of $\mathcal{E}(\varepsilon)$ we can show that

$\displaystyle\mathop{{}\mathbb{P}}(\mathcal{E}(\varepsilon))\geq$
$\displaystyle
1-\mathop{{}\mathbb{P}}(\mathcal{E}_{0}(\varepsilon))-\sum_{0\leq k\leq N-1,\
l}\left(\mathop{{}\mathbb{P}}(\mathcal{E}_{kl,1}(\varepsilon))+\mathop{{}\mathbb{P}}(\mathcal{E}_{kl,2}(\varepsilon))\right)$
$\displaystyle\geq$ $\displaystyle
1-4m\exp(-\frac{T\varepsilon^{2}}{4mc_{1}})-2(2\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil)^{2m}\exp(-\frac{T\varepsilon^{2}}{2})$

###  A.5 Proof of Corollary 1

Recall the proof of Theorem 2 that when $\varepsilon$ satisfying
$\epsilon<4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$, with high
probability the deterministic $\epsilon$-optimal solution must be in
$\Omega_{\boldsymbol{\lambda}}(\varepsilon)$. Similarly, for the stochastic
$\epsilon$-optimal solution, we try to confine it in a larger region so that
with high probability
$\mathbb{E}\left[\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}_{T}^{*}\right\rVert_{2}^{2}\middle|\bar{D}_{T}\right]$
can still be bounded by $\varepsilon$. Notice that, although our Proposition 2
only focus on $\Omega_{\boldsymbol{\lambda}}(\varepsilon)$, it also bring us
information outside $\Omega_{\boldsymbol{\lambda}}(\varepsilon)$. For any
$\varepsilon$ and $\epsilon$, under the event when Proposition 2 holds, for
any $\bar{D}_{T}$ we have:

  1. 1.

If
$\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{\epsilon},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\leq
4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$, then
$\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}_{T}^{*}\right\rVert_{2}\leq
4H\varepsilon$.

  2. 2.

If
$\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{\epsilon},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)>4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$,
then we have
$\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}_{T}^{*}\right\rVert_{2}\leq\frac{1}{H\varepsilon\underline{\mathcal{L}}_{D}}(\bar{D}_{T}(\boldsymbol{\lambda}_{T}^{\epsilon},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d))$.
Because the convex function
$\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)=0$
when $\boldsymbol{\lambda}=\boldsymbol{\lambda}^{*}$, and
$\bar{D}_{T}(\boldsymbol{\lambda},d)-\bar{D}_{T}(\boldsymbol{\lambda}^{*},d)\geq
4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$ when
$\left\lVert\boldsymbol{\lambda}-\boldsymbol{\lambda}^{*}\right\rVert_{2}=4H\varepsilon$.

We conclude that under the event when Proposition 2 holds, for any
$\epsilon<4H^{2}\varepsilon^{2}\underline{\mathcal{L}}_{D}$,

$\mathbb{E}_{\mathcal{B}}\left[\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}\middle|\bar{D}_{T}\right]\leq
16H^{2}\varepsilon^{2}+\frac{2\sqrt{m\left(2\frac{\bar{f}+\bar{r}}{\underline{d}}+G\right)}}{H\varepsilon\underline{\mathcal{L}}_{D}}\cdot\epsilon$

because
$\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}^{*}\right\rVert_{2}\leq
2\sqrt{m\left(2\frac{\bar{f}+\bar{r}}{\underline{d}}+G\right)}$. The RHS term
has a minimum value

$z_{0}=3\cdot
2^{\frac{4}{3}}\epsilon^{\frac{2}{3}}\left(m\left(2\frac{\bar{f}+\bar{r}}{\underline{d}}+G\right)\right)^{\frac{1}{3}}/\underline{\mathcal{L}}_{D}^{\frac{2}{3}}$

when
$\varepsilon_{0}=\epsilon^{\frac{1}{3}}\left(m\left(2\frac{\bar{f}+\bar{r}}{\underline{d}}+G\right)\right)^{\frac{1}{6}}/(2^{\frac{4}{3}}H\underline{\mathcal{L}}_{D}^{\frac{1}{3}})$.
When the RHS term is larger than is minimum value, we can always take the
corresponding $\varepsilon$ at the right side where
$\varepsilon>\varepsilon_{0}$ and it follows that

$z=16H^{2}\varepsilon^{2}+\frac{2\sqrt{m\left(2\frac{\bar{f}+\bar{r}}{\underline{d}}+G\right)}}{H\varepsilon\underline{\mathcal{L}}_{D}}\cdot\epsilon\leq
48H^{2}\varepsilon^{2}.$

Then by the tail expectation formula we have

$\displaystyle\mathbb{E}_{\mathcal{B},\mathcal{P}}\left\lVert\boldsymbol{\lambda}^{\epsilon}_{T}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}$
$\displaystyle=\int_{0}^{z_{0}}\mathop{{}\mathbb{P}}(\mathbb{E}_{\mathcal{B}}\left[\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}\middle|\bar{D}_{T}\right]\geq
z)dz+\int_{z_{0}}^{\infty}\mathop{{}\mathbb{P}}(\mathbb{E}_{\mathcal{B}}\left[\left\lVert\boldsymbol{\lambda}_{T}^{\epsilon}-\boldsymbol{\lambda}^{*}\right\rVert_{2}^{2}\middle|\bar{D}_{T}\right]\geq
z)dz$ $\displaystyle\leq
z_{0}+\int_{z_{0}}^{\infty}\left[4m\exp(-\frac{T\frac{z}{48H^{2}}}{4mc_{1}})+2(2\lceil\log_{q}(\frac{1}{2\sqrt{2m}})\rceil)^{2m}\exp(-\frac{T\frac{z}{48H^{2}}}{2})\right]dz.$
$\displaystyle\leq z_{0}+12\frac{C_{1}}{T}.$

###  A.6 Proof of Proposition 3

By Fenchel conjugate, the definition of $\hat{\mu}_{T}$ implies

$\displaystyle
r(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T})+\hat{\mu}_{T}^{\top}\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T}=$
$\displaystyle\max\limits_{a}r(a)+\hat{\mu}_{T}^{\top}a=r^{*}(-\hat{\mu}_{T})\geq
r(\frac{\sum_{t=1}^{T}a_{t}}{T})+\hat{\mu}_{T}^{\top}\frac{\sum_{t=1}^{T}a_{t}}{T}$
$\displaystyle\geq$
$\displaystyle\frac{\sum_{t=1}^{T}r(a_{t})}{T}+\hat{\mu}_{T}^{\top}\frac{\sum_{t=1}^{T}a_{t}}{T}.$

Combined with
$R\left(A\middle|\mathcal{P}\right)=\mathbb{E}_{A,\mathcal{P}}\left[\sum_{t=1}^{T}f_{t}(x_{t})+T\cdot
r(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T})\right]$, we have

$\displaystyle R\left(A\middle|\mathcal{P}\right)$
$\displaystyle\geq\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})+\sum_{t=1}^{T}r(a_{t})+\hat{\mu}_{T}^{\top}(\sum_{t=1}^{T}(a_{t}-b_{t}x_{t}))\right].$

The Assumption 2 suggests that

$\left\lVert\hat{\mu}_{T}\right\rVert_{2}\leq\sqrt{m}G,\text{ and }\left\lVert
a_{t}\right\rVert_{2}=\left\lVert\nabla
r^{*}(-\mu_{t})\right\rVert_{2}\leq\sqrt{n}D\bar{b}.$

Thus

$\displaystyle R\left(A\middle|\mathcal{P}\right)\geq\mathbb{E}$
$\displaystyle\left[\sum_{t=1}^{\tau}\left[f_{t}(\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1}))+r(a_{t})\right]-(\bar{f}+\bar{r}+2\sqrt{mn}GD\bar{b})(T-\tau)+\left\langle\hat{\mu}_{T},\sum_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rangle\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{t=1}^{\tau}g(\boldsymbol{\lambda}_{t-1})+\left\langle\hat{\mu}_{T}-\mu^{*},\sum_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rangle\right]$
$\displaystyle-$
$\displaystyle\mathbb{E}\left[(\bar{f}+\bar{r}+2C_{3})(T-\tau)-\left\langle\lambda^{*},\sum_{t=1}^{\tau}(d-b_{t}x_{t})\right\rangle\right]$

Combined with (5.2), we conclude the proof.

###  A.7 Proof of Lemma 4

We start with a lemma on the continuity of dual optimal solution to prove
Lemma 4.

######  Lemma 8 (Continuity of dual optimal solution (Li and Ye,, 2021)).

Under Assumption 1, 2, 3, for the stochasitc program
$\min\limits_{\mu,\lambda\succeq
0}D(\boldsymbol{\lambda},d^{\prime})=\mathbb{E}f_{t}^{*}(b_{t}^{\top}(\mu+\lambda))+r^{*}(-\mu)+{d^{\prime}}^{\top}\lambda$,
let $d^{\prime}$ be $d^{\prime}_{1},d^{\prime}_{2}\in\Omega_{d}$ separately,
then the corresponding optimal solution
$\boldsymbol{\lambda}^{*}(d^{\prime}_{1}),\boldsymbol{\lambda}^{*}(d^{\prime}_{2})$
satisfies

$\left\lVert\boldsymbol{\lambda}^{*}(d^{\prime}_{1})-\boldsymbol{\lambda}^{*}(d^{\prime}_{2})\right\rVert^{2}_{2}\leq\frac{1}{4\underline{\mathcal{L}}_{D}^{2}}\left\lVert
d^{\prime}_{1}-d^{\prime}_{2}\right\rVert^{2}_{2}.$

If further $d^{\prime}_{1},d^{\prime}_{2}$ identify the same binding/non-
binding dimensions, then

$\left\lVert\boldsymbol{\lambda}^{*}(d^{\prime}_{1})-\boldsymbol{\lambda}^{*}(d^{\prime}_{2})\right\rVert^{2}_{2}\leq\frac{1}{4\underline{\mathcal{L}}_{D}^{2}}\sum_{i\in
I_{\textsf{B}}}(d^{\prime}_{1i}-d^{\prime}_{2i})^{2},$

where the binding dimension $I_{\textsf{B}}$ is with respect to
$d_{1}^{\prime}$ and $d^{\prime}_{2}$.

######  Proof (Lemma 8).

By Proposition 1 and the uniform assumption on $d$, we have

$\displaystyle
D(\boldsymbol{\lambda}^{*}(d_{2}^{\prime}),d_{1}^{\prime})-D(\boldsymbol{\lambda}^{*}(d_{1}^{\prime}),d_{1}^{\prime})$
$\displaystyle\geq\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2}^{2}$
$\displaystyle
D(\boldsymbol{\lambda}^{*}(d_{1}^{\prime}),d_{2}^{\prime})-D(\boldsymbol{\lambda}^{*}(d_{2}^{\prime}),d_{2}^{\prime})$
$\displaystyle\geq\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}^{*}(d_{1}^{\prime})-\boldsymbol{\lambda}^{*}(d_{2}^{\prime})\right\rVert_{2}^{2}.$

Summing up two inequality we have

$\displaystyle(d_{1}^{\prime}-d_{2}^{\prime})^{\top}(\lambda^{*}(d_{2}^{\prime})-\lambda^{*}(d_{1}^{\prime}))\geq
2\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2}^{2},$
(A.12)

or equivalently, $\sum_{i\in
I_{\textsf{B}}}(d^{\prime}_{1i}-d^{\prime}_{2i})(\lambda^{*}_{i}(d_{2}^{\prime})-\lambda^{*}_{i}(d_{1}^{\prime}))\geq
2\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2}^{2}$
if further $d^{\prime}_{1},d^{\prime}_{2}$ share the same binding/non-binding
dimensions. From (A.12) we can show that

$\displaystyle
2\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2}^{2}$
$\displaystyle\leq(d_{1}^{\prime}-d_{2}^{\prime})^{\top}(\lambda^{*}(d_{2}^{\prime})-\lambda^{*}(d_{1}^{\prime}))\leq\left\lVert
d_{1}^{\prime}-d_{2}^{\prime}\right\rVert_{2}\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2}$
$\displaystyle\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2}$
$\displaystyle\leq\frac{1}{2\underline{\mathcal{L}}_{D}}\left\lVert
d_{1}^{\prime}-d_{2}^{\prime}\right\rVert_{2}.$

Thus we get the first statement. For the second statement we focus on the
binding dimensions

$\displaystyle
2\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2}^{2}$
$\displaystyle\leq\sum_{i\in
I_{\textsf{B}}}(d^{\prime}_{1i}-d^{\prime}_{2i})(\lambda^{*}_{i}(d_{2}^{\prime})-\lambda^{*}_{i}(d_{1}^{\prime}))$
$\displaystyle\leq\sqrt{\sum_{i\in
I_{\textsf{B}}}(d^{\prime}_{1i}-d^{\prime}_{2i})^{2}}\sqrt{\sum_{i\in
I_{\textsf{B}}}(\lambda^{*}_{i}(d_{2}^{\prime})-\lambda^{*}_{i}(d_{1}^{\prime}))^{2}}$
$\displaystyle\leq\sqrt{\sum_{i\in
I_{\textsf{B}}}(d^{\prime}_{1i}-d^{\prime}_{2i})^{2}}\left\lVert\boldsymbol{\lambda}^{*}(d_{2}^{\prime})-\boldsymbol{\lambda}^{*}(d_{1}^{\prime})\right\rVert_{2},$

which completes the proof of Lemma 8.

Then, we return to Lemma 4 and consider the original constraints $d$ and the
its binding/non-binding dimensions:
$I_{\textsf{B}}=\left\\{i\middle|d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}=0\right\\}$,
and
$I_{\textsf{NB}}=\left\\{i\middle|d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}>0\right\\}$.
Here we write the corresponding optimal solution to
$\min\limits_{\mu,\lambda\succeq 0}D(\boldsymbol{\lambda},d)$ as
$\boldsymbol{\lambda}^{*}$, and write $\boldsymbol{\lambda}^{*}(d^{\prime})$
if we change $d$ to $d^{\prime}$. Then if $i\in I_{\textsf{B}}$ and $i$
changes to non-binding dimensions for $d^{\prime}$, by Lemma 8 we have

$\left\lVert d-d^{\prime}\right\rVert_{2}\geq
2\underline{\mathcal{L}}_{D}\left\lVert\boldsymbol{\lambda}^{*}(d^{\prime})-\boldsymbol{\lambda}^{*}\right\rVert_{2}\geq
2\underline{\mathcal{L}}_{D}\underline{\lambda},$ (A.13)

where $\underline{\lambda}=\min\left\\{\lambda^{*}_{i}\middle|i\in
I_{\textsf{B}}\right\\}$. If on the other hand, $i\in I_{\textsf{NB}}$ and $i$
changes to binding dimensions for $d^{\prime}$, by Assumption 3.1 we have

$\displaystyle\mathbb{E}\left\lVert\boldsymbol{\lambda}^{*}(d^{\prime})-\boldsymbol{\lambda}^{*}\right\rVert_{2}$
$\displaystyle\geq\frac{1}{2\bar{b}^{2}\bar{\mathcal{L}}_{f}}\left|\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(d^{\prime}))\right)_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}\right|=\frac{1}{2\bar{b}^{2}\bar{\mathcal{L}}_{f}}\left|d^{\prime}_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}\right|$
$\displaystyle\geq\frac{1}{2\bar{b}^{2}\bar{\mathcal{L}}_{f}}\left(\left|d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}\right|-\left\lvert
d^{\prime}_{i}-d_{i}\right\rvert\right).$

Denote the minimum of remaining resources in non-binding dimensions by

$\gamma=\min_{i\in
I_{\textsf{NB}}}\left\\{d_{i}-\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right)_{i}\right\\}.$

By Lemma 8 we have

$\displaystyle\left\lVert d-d^{\prime}\right\rVert_{2}\geq
2\underline{\mathcal{L}}_{D}\mathbb{E}\left\lVert\boldsymbol{\lambda}^{*}(d^{\prime})-\boldsymbol{\lambda}^{*}\right\rVert_{2}$
$\displaystyle\geq\frac{\underline{\mathcal{L}}_{D}}{\bar{b}^{2}\bar{\mathcal{L}}_{f}}\left(\gamma-\left\lvert
d^{\prime}_{i}-d_{i}\right\rvert\right)\geq\frac{\underline{\mathcal{L}}_{D}}{\bar{b}^{2}\bar{\mathcal{L}}_{f}}\left(\gamma-\left\lVert
d-d^{\prime}\right\rVert_{2}\right),$

i.e., $\left\lVert
d-d^{\prime}\right\rVert_{2}\geq\frac{\gamma\underline{\mathcal{L}}_{D}}{\underline{\mathcal{L}}_{D}+\bar{b}^{2}\bar{\mathcal{L}}_{f}}$.
Combined with (A.13), taking
$\delta_{d}=\frac{1}{\sqrt{m}}\cdot\left(\frac{\gamma\underline{\mathcal{L}}_{D}}{\underline{\mathcal{L}}_{D}+\bar{b}^{2}\bar{\mathcal{L}}_{f}}\right)\wedge\left(2\underline{\mathcal{L}}_{D}\underline{\lambda}\right)$
we can conclude that when $\left\lvert
d_{i}-d^{\prime}_{i}\right\rvert\leq\delta_{d}$, the binding/non-binding
dimensions will never change. Moreover, enlarging the constraint in a non-
binding dimension will never change this constraint to binding dimension. So,
for the non-binding dimensions, $d_{i}^{\prime}-d_{i}$ can be any large. This
finishes the proof.

###  A.8 Proof of lemma 5

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\right]\leq
2\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}(d_{t-1})\right\rVert^{2}_{2}+\left\lVert\boldsymbol{\lambda}^{*}(d_{t-1})-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\right]$

By the definition of stopping time $\tau$ and Condition 1, the first term in
the RHS has

$\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}(d_{t-1})\right\rVert^{2}_{2}\right]\leq\sum_{t=1}^{T}2C_{2}\frac{1}{t}\text{
or }C_{2}\frac{1}{T-t+1}\\\ \leq 2C_{2}(\log T+1)$

For the second term, we apply lemma 8 to it.

$\displaystyle
2\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}^{*}(d_{t-1})-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\right]\leq\frac{1}{2\underline{\mathcal{L}}_{D}^{2}}\mathbb{E}\left[\sum_{t=1}^{\tau}\sum_{i\in
I_{\textsf{B}}}(d_{it}-d_{i})^{2}\right].$

Thus we transform the perturbation of $\boldsymbol{\lambda}^{*}(d_{t})$ into
the derivation of $d_{t}$ in the binding dimensions.

To ease our analysis, we define a new sequence $d_{t}^{\prime}$

$d_{t}^{\prime}=\begin{cases}d_{t},&\text{ if }t\leq\tau\\\ d_{t-1},&\text{ if
}t>\tau\end{cases}$

which shares the same stopping time with $d_{t}$ and define
$\tau_{i}=\min\limits_{t}\\{T-\left\lceil\frac{m\bar{b}}{\underline{d}}\right\rceil\\}\cup\\{t|d_{it}^{\prime}\notin\mathcal{D}_{i}\\}$
for $i\in[m]$ as the stopping time on each dimension with
$\tau=\min\\{\tau_{1},...,\tau_{m}\\}$.

We first consider the binding dimensions. For any $i\in I_{\textsf{B}}$, we
follow a similar procedure in Li and Ye, (2021) to derive:

$\displaystyle d_{i,t+1}^{\prime}$
$\displaystyle=d_{it}^{\prime}+\frac{d_{it}^{\prime}-\left(b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}_{t})\right)_{i}}{T-t-1}\mathbb{I}(\tau>t)$
$\displaystyle\mathbb{E}\left(d_{i,t+1}^{\prime}-d_{i}\right)^{2}$
$\displaystyle=\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}+\underbrace{\mathbb{E}\frac{\left(d_{it}^{\prime}-\left(b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}_{t-1})\right)_{i}\right)^{2}}{(T-t-1)^{2}}\mathbb{I}(\tau>t)}_{A^{\prime}}$
$\displaystyle+\underbrace{2\mathbb{E}\frac{\left(d_{it}^{\prime}-d_{i}\right)\left(d_{it}^{\prime}-\left(b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}^{*}(d_{t}))\right)_{i}\right)}{T-t-1}\mathbb{I}(\tau>t)}_{B^{\prime}}$
$\displaystyle+\underbrace{2\mathbb{E}\frac{\left(d_{it}^{\prime}-d_{i}\right)\left(\left(b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}^{*}(d_{t}))-b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}_{t})\right)_{i}\right)}{T-t-1}\mathbb{I}(\tau>t)}_{C^{\prime}}$

For the term $A^{\prime}$ we have
$A^{\prime}\leq\frac{\left(\bar{d}+\sqrt{n}D\bar{b}\right)^{2}}{(T-t-1)^{2}}$.
For the term $B^{\prime}$, since $i\in I_{\textsf{B}}$ and
$d_{t}\in\sigma(\mathcal{H}_{t})$, conditioned on past history
$\mathcal{H}_{t}$, we always have
$\mathbb{E}\left[\left(d_{it}^{\prime}-d_{i}\right)\left(d_{it}^{\prime}-\left(b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}^{*}(d_{t}))\right)_{i}\right)\mathbb{I}(\tau>t)\middle|\mathcal{H}_{t}\right]=0$,
thus $B^{\prime}=0$. For the term $C^{\prime}$, we apply Assumption 4 and
Condition 1:

$\displaystyle C^{\prime}$
$\displaystyle\leq\frac{2\sqrt{\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}}\sqrt{\mathbb{E}\left\lVert
b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}^{*}(d_{t}))-b_{t+1}\tilde{x}_{t+1}(\boldsymbol{\lambda}_{t})\right\rVert_{2}^{2}}}{T-t-1}$
$\displaystyle\leq\frac{2\sqrt{\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}}\sqrt{2\bar{b}^{4}L_{2}\mathbb{E}\left\lVert\boldsymbol{\lambda}_{t}-\boldsymbol{\lambda}^{*}(d_{t})\right\rVert_{2}^{2}}}{T-t-1}\leq\frac{2\sqrt{2C_{2}L_{2}}\bar{b}^{2}\sqrt{\frac{1}{t+1}+\frac{1}{T-t}}\sqrt{\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}}}{T-t-1}.$

Here the second inequality is because of Assumption 4, and the third
inequality is from Condition 1. Here in the derivation, we can treat
$\\{\boldsymbol{\lambda}_{t}\\}$ as a new sequence generated by
$\\{d_{t}^{\prime}\\}$, which has the same value with the original one when
$t\leq\tau$, and takes
$\boldsymbol{\lambda}_{t}=\mathcal{B}_{t}(\mathcal{H}_{t},d_{t}^{\prime})$
when $t>\tau$. We then get the recurrence relation of $d_{it}^{\prime}-d_{i}$:

$\displaystyle\mathbb{E}\left(d_{i,t+1}^{\prime}-d_{i}\right)^{2}\leq$
$\displaystyle\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}+\frac{\left(\bar{d}+\sqrt{n}D\bar{b}\right)^{2}}{(T-t-1)^{2}}+\frac{2\sqrt{2C_{2}L_{2}}\bar{b}^{2}\sqrt{\frac{1}{t+1}+\frac{1}{T-t}}\sqrt{\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}}}{T-t-1}.$

Since $d_{0}=d$, by induction we have
$\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}\leq
C_{3}\frac{t+1}{(T+1)(T-t)}$, where

$C_{3}=\left(2\cdot\left(\bar{d}+\sqrt{n}D\bar{b}\right)^{2}\vee\left(2\sqrt{2C_{2}L_{2}}\bar{b}^{2}\right)+1\right)^{2}.$

So, we have

$\displaystyle
2\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}^{*}(d_{t-1})-\boldsymbol{\lambda}^{*}\right\rVert^{2}\right]\leq$
$\displaystyle 2\mathbb{E}\left[\sum_{t=1}^{\tau}\sum_{i\in
I_{\textsf{B}}}(d_{i,{t-1}}-d_{i})^{2}\right]$ $\displaystyle\leq$
$\displaystyle
2m\mathbb{E}\sum_{t=1}^{T}\left[\left(d_{i,t+1}^{\prime}-d_{i}\right)^{2}\right]\leq
2mC_{3}\log T,\text{ and }$
$\displaystyle\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\right]\leq$
$\displaystyle\left(2C_{2}+\frac{mC_{3}}{\underline{\mathcal{L}}_{D}^{2}}\right)\log
T+2C_{2},$

which completes the proof.

###  A.9 Proof of lemma 6

Since $\tau=\min\\{\tau_{1},...,\tau_{m}\\}$, we only need to show
$\mathbb{E}(T-\tau_{i})\leq C\log T$ for any $i$ in binding dimensions and
non-binding dimensions.

For the binding dimensions, applying Chebyshev’s inequality, we have

$\displaystyle\mathbb{E}(T-\tau_{i})\leq\sum_{i=1}^{T}P\left(\tau_{i}\leq
t\right)\leq$ $\displaystyle
1+\frac{\sqrt{n}D\bar{b}}{\underline{d}}+\sum_{i=1}^{T}P\left(|d_{it}^{\prime}-d_{i}|\leq\delta_{d}\right)$
(A.14) $\displaystyle\leq$ $\displaystyle
1+\frac{\sqrt{n}D\bar{b}}{\underline{d}}+\sum_{t=1}^{T}\frac{\mathbb{E}\left(d_{it}^{\prime}-d_{i}\right)^{2}}{\delta_{d}^{2}}$
$\displaystyle\leq$ $\displaystyle
1+\frac{\sqrt{n}D\bar{b}}{\underline{d}}+\frac{C_{3}}{\delta_{d}^{2}}\log T$

For the non-binding dimensions, $\mathcal{D}$ ensures that binding/non-binding
dimensions remain unchanged when $d^{\prime}\in\mathcal{D}$. Then for
$d^{\prime}\in\mathcal{D}$, we define

$\tilde{d}^{\prime}_{i}=\begin{cases}d_{i}^{\prime},&\text{ if }i\in
I_{\textsf{B}}\\\ d_{i}-\delta_{d},&\text{ if }i\in
I_{\textsf{NB}}\end{cases}$

We know that
$\boldsymbol{\lambda}^{*}(d^{\prime})=\boldsymbol{\lambda}^{*}(\tilde{d}^{\prime})$
because the non-binding constraints are loose, then

$\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(d^{\prime}))\right)_{i}=\mathbb{E}\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(\tilde{d}^{\prime}))\right)_{i}<d_{i}-\delta_{d}$

Recall that $\tilde{x}_{t}(\cdot)\perp\\!\\!\\!\perp\mathcal{H}_{t-1}$, thus
$\mathbb{E}\left[\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(d_{t-1})\right)_{i}\middle|\mathcal{H}_{t-1}\right]<d_{i}-\delta_{d}$
for $i\in I_{\textsf{NB}}$ and $d_{t-1}\in\mathcal{D}$. This implies that

$\displaystyle\mathop{{}\mathbb{P}}\left(\tau_{i}\leq t\right)$
$\displaystyle=\mathop{{}\mathbb{P}}\left(\sum_{j=1}^{t^{\prime}}(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}\geq
t^{\prime}\left(d_{i}-\delta_{d}\right)+T\delta_{d}\text{ for some }1\leq
t^{\prime}\leq t\right)$
$\displaystyle\leq\mathop{{}\mathbb{P}}\left(\sum_{j=1}^{t^{\prime}}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}-\mathbb{E}\left[\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(d_{j-1})\right)_{i}\middle|\mathcal{H}_{j-1}\right]\right]\geq
T\delta_{d}\text{ for some }1\leq t^{\prime}\leq t\right)$
$\displaystyle\leq\mathop{{}\mathbb{P}}\left(\sum_{j=1}^{t^{\prime}}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}-\mathbb{E}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}|\mathcal{H}_{j-1}\right]\right]+\right.$
$\displaystyle\left.\sum_{j=1}^{t^{\prime}}\left\lvert\mathbb{E}\left[\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(d_{j-1})\right)_{i}\middle|\mathcal{H}_{t-1}\right]-\mathbb{E}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}|\mathcal{H}_{j-1}\right]\right\rvert\geq
T\delta_{d}\text{ for some }1\leq t^{\prime}\leq t\right)$
$\displaystyle\leq\mathop{{}\mathbb{P}}\left(\sum_{j=1}^{t^{\prime}}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}-\mathbb{E}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}|\mathcal{H}_{j-1}\right]\right]\geq\frac{T\delta_{d}}{2}\text{
for some }1\leq t^{\prime}\leq t\right)$
$\displaystyle+\mathop{{}\mathbb{P}}\left(\sum_{j=1}^{t^{\prime}}\left\lvert\mathbb{E}\left[\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(d_{j-1})\right)_{i}\middle|\mathcal{H}_{j-1}\right]-\mathbb{E}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}|\mathcal{H}_{j-1}\right]\right\rvert\geq\frac{T\delta_{d}}{2}\text{
for some }1\leq t^{\prime}\leq t\right)$

Since sequences in the last two lines are martingales/sub-martingales, we use
Doob’s martingale inequality and get the following derivation:

$\displaystyle\mathop{{}\mathbb{P}}\left(\tau_{i}\leq t\right)\leq$
$\displaystyle\frac{4}{T^{2}\delta_{d}^{2}}\sum_{j=1}^{t}\mathbb{E}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}-\mathbb{E}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}|\mathcal{H}_{t-1}\right]\right]^{2}$
$\displaystyle+\frac{4}{T^{2}\delta_{d}^{2}}\mathbb{E}\left[\sum_{j=1}^{t}\left\lvert\mathbb{E}\left[\left(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}(d_{j-1})\right)_{i}\middle|\mathcal{H}_{j-1}\right]-\mathbb{E}\left[(b_{j}\tilde{x}_{j}\left(\boldsymbol{\lambda}_{j-1}\right))_{i}|\mathcal{H}_{j-1}\right]\right\rvert\right]^{2}$
$\displaystyle\leq$
$\displaystyle\frac{16n\bar{b}^{2}D^{2}t}{T^{2}\delta_{d}^{2}}+\frac{8\bar{\mathcal{L}}_{f}^{2}\bar{b}^{4}t}{T^{2}\delta_{d}^{2}}\sum_{j=1}^{t}\mathbb{E}\left\lVert\boldsymbol{\lambda}_{j-1}-\boldsymbol{\lambda}^{*}(d_{j-1})\right\rVert_{2}^{2}\text{
(by Assumption \ref{asm:nondegeneracy})}$ $\displaystyle\leq$
$\displaystyle\frac{16n\bar{b}^{2}D^{2}t}{T^{2}\delta_{d}^{2}}+\frac{16n\bar{b}^{2}D^{2}C_{2}t}{T^{2}\delta_{d}^{2}}(\log
t+\log T-\log(T-t+1)+2)$

We now go back to calculate the $\mathbb{E}(T-\tau_{i})$:

$\displaystyle\mathbb{E}(T-\tau_{i})$ $\displaystyle\leq
1+\frac{\sqrt{n}D\bar{b}}{\underline{d}}+\sum_{i=1}^{T}P\left(\tau_{i}\leq
t\right)\leq\sum_{t=1}^{T}\frac{16n\bar{b}^{2}D^{2}t}{T^{2}\delta_{d}^{2}}+\frac{16n\bar{b}^{2}D^{2}C_{2}t}{T^{2}\delta_{d}^{2}}(\log
t+\log T+2)$ (A.15) $\displaystyle\leq
1+\frac{\sqrt{n}D\bar{b}}{\underline{d}}+\frac{8n\bar{b}^{2}D^{2}(1+2C_{2})}{\delta_{d}^{2}}+\frac{16n\bar{b}^{2}D^{2}\log
T}{\delta_{d}^{2}}$

Putting together (A.14) and (A.15) we conclude the proof of lemma 6.

###  A.10 Proof of Lemma 7

For the $\mathbb{E}\left\lVert\hat{\mu}_{T}-\mu^{*}\right\rVert^{2}_{2}$, the
optimality of $\mu^{*}$ implies
$\tilde{a}(\mu^{*})=\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})$,
thus by conjugate we have

$\displaystyle\mathbb{E}\left\lVert\hat{\mu}_{T}-\mu^{*}\right\rVert^{2}_{2}=$
$\displaystyle\mathbb{E}\left\lVert\nabla r(\tilde{a}(\mu^{*}))-\nabla
r(\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T})\right\rVert^{2}_{2}\leq\mathbb{E}(\frac{1}{\underline{\mathcal{L}}_{r}})^{2}\left\lVert\tilde{a}(\mu^{*})-\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T}\right\rVert^{2}_{2}$
$\displaystyle=$
$\displaystyle(\frac{1}{\underline{\mathcal{L}}_{r}})^{2}\mathbb{E}\left\lVert\frac{\sum_{t=1}^{T}b_{t}x_{t}}{T}-\frac{\sum_{t=1}^{T}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}+\frac{\sum_{t=1}^{T}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}-\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}$
$\displaystyle\leq$
$\displaystyle\frac{3}{\underline{\mathcal{L}}_{r}^{2}}\left.\mathbb{E}\left\lVert\frac{\sum_{t=1}^{\tau}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}\right\rVert^{2}_{2}\right.\text{(part
\ref{sec:proof_c_s}.1)}$
$\displaystyle+\frac{3}{\underline{\mathcal{L}}_{r}^{2}}\left.\mathbb{E}\left\lVert\frac{\sum_{t=1}^{T}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})-T\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}\right\rVert^{2}_{2}\right.\text{(part
\ref{sec:proof_c_s}.2)}$
$\displaystyle+\frac{3}{\underline{\mathcal{L}}_{r}^{2}}\left.\mathbb{E}\left\lVert\frac{\sum_{t=\tau+1}^{T}b_{t}x_{t}-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}\right\rVert^{2}_{2}\right.\text{(part
\ref{sec:proof_c_s}.3)}.$

For the part A.10.1, applying Assumption 4 we can yield

$\displaystyle\mathbb{E}$
$\displaystyle\left\lVert\frac{\sum_{t=1}^{\tau}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}\right\rVert^{2}_{2}\leq\mathbb{E}\frac{\tau\sum_{t=1}^{\tau}\left\lVert
b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}}{T^{2}}$
$\displaystyle\leq\frac{\mathbb{E}\sum_{t=1}^{\tau}\left\lVert
b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}}{T}=\frac{\mathbb{E}\sum_{t=1}^{T}\left\lVert
b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}\mathbb{I}(t\leq\tau)}{T}$
$\displaystyle=\frac{\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{E}\left[\left\lVert
b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}_{t-1})-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}\middle|\mathcal{H}_{t-1},b_{t}\right]\mathbb{I}(t\leq\tau)\right]}{T}$
$\displaystyle\stackrel{{\scriptstyle\text{ (a)
}}}{{\leq}}L_{2}\bar{b}^{2}\frac{\sum_{t=1}^{T}\mathbb{E}\left[\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\mathbb{I}(t\leq\tau)\right]}{T}=L_{2}\bar{b}^{2}\frac{\mathbb{E}\left[\sum_{t=1}^{\tau}\left\lVert\boldsymbol{\lambda}_{t-1}-\boldsymbol{\lambda}^{*}\right\rVert^{2}_{2}\right]}{T}$
$\displaystyle\stackrel{{\scriptstyle\text{ (b) }}}{{\leq}}O(\frac{\log
T}{T}).$

(a) is by Assumption 4 and the fact
$\\{t\leq\tau\\}\in\sigma(\mathcal{H}_{t-1})$, and
$\tilde{x}_{t}(\cdot)\perp\\!\\!\\!\perp\boldsymbol{\lambda}_{t-1}$. (b) is by
Lemma 5.

For the part A.10.2, since $b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})$ is
bounded by
$\left\lvert(b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*}))_{i}\right\rvert\leq\sqrt{n}D\bar{b}$,
using Hoeffding’s inequality on each dimension we have

$\displaystyle
P\left(\left\lVert\frac{\sum_{t=1}^{T}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}-\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert_{2}>\varepsilon\right)\leq
m\exp\left(-\frac{2\varepsilon^{2}T}{mnD^{2}\bar{b}^{2}}\right).$

Thus

$\displaystyle\mathbb{E}\left\lVert\frac{\sum_{t=1}^{T}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}-\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}=$
$\displaystyle\int_{0}^{\infty}\mathop{{}\mathbb{P}}\left(\left\lVert\frac{\sum_{t=1}^{T}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}-\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}>\varepsilon\right)d\varepsilon$
$\displaystyle\leq$
$\displaystyle\int_{0}^{\infty}m\exp\left(-\frac{2\varepsilon
T}{mnD^{2}\bar{b}^{2}}\right)d\varepsilon\leq\frac{m^{2}nD^{2}\bar{b}^{2}}{2T}.$

For the part A.10.3, since $\left\lVert
b_{t}x_{t}-\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}_{2}\leq
nD^{2}\bar{b}^{2}$, by Lemma 6, we have

$\displaystyle\mathbb{E}\left\lVert\frac{\sum_{t=\tau+1}^{T}b_{t}x_{t}-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})}{T}\right\rVert^{2}_{2}\leq$
$\displaystyle\frac{\mathbb{E}\left[(T-\tau)\sum_{t=\tau+1}^{T}\left\lVert
b_{t}x_{t}-b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})\right\rVert^{2}\right]}{T^{2}}$
$\displaystyle\leq$ $\displaystyle
nD^{2}\bar{b}^{2}\frac{\mathbb{E}(T-\tau)}{T}\leq O(\frac{\log T}{T})$

We then go back to control the next term
$\mathbb{E}\left\lVert\sum\limits_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rVert^{2}_{2}$.

$\displaystyle\mathbb{E}\left\lVert\sum_{t=1}^{\tau}(a_{t}-b_{t}x_{t})\right\rVert^{2}_{2}=$
$\displaystyle\mathbb{E}\left\lVert\sum_{t=1}^{\tau}\left(a_{t}-\tilde{a}(\mu^{*})+\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})-b_{t}x_{t}\right)\right\rVert^{2}$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}\left\lVert\sum_{t=1}^{\tau}(a_{t}-a(\mu^{*}))\right\rVert^{2}_{2}+2\mathbb{E}\left\lVert\sum_{t=1}^{\tau}(\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})-b_{t}x_{t})\right\rVert^{2}_{2}$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}\tau\sum_{t=1}^{\tau}\bar{\mathcal{L}}_{r}\left\lVert\mu_{t}-\mu^{*}\right\rVert^{2}_{2}+2T^{2}\mathbb{E}\left\lVert\frac{1}{T^{2}}\sum_{t=1}^{\tau}(\mathbb{E}b_{t}\tilde{x}_{t}(\boldsymbol{\lambda}^{*})-b_{t}x_{t})\right\rVert^{2}_{2}$

From the argument above, we show that the first term is controlled by $O(T\log
T)$, and the second term can also be controlled by $O(T\log T)$ (this proof
follows previous derivation of part A.10.1-3). Thus we finish the proof.

###  A.11 Proof of Theorem 4 and 5

We specify a non-regularized case where
$f_{t}(x)=-\frac{1}{4}(x-2\xi_{t})^{2}+\xi_{t}^{2}$, with fixed cost
$b_{t}=1$, average resource capacity $d=\frac{1}{2}D$, and $\xi_{t}$ following
two-point distribution
$\mathop{{}\mathbb{P}}(\xi_{t}=\frac{1}{2}D)=\mathop{{}\mathbb{P}}(\xi_{t}=\frac{3}{4}D)=\frac{1}{2}$.
Then the dual problem is

$D_{t}(\lambda)=\begin{cases}\frac{1}{2}D\lambda&\text{ if }\lambda>\xi_{t}\\\
-\frac{1}{4}D+\xi_{t}-\frac{1}{2}D\lambda&\text{ if
}\lambda<\xi_{t}-\frac{1}{2}D\\\
\lambda^{2}-2(\xi_{t}-\frac{1}{4}D)\lambda+\xi_{t}^{2}&\text{ if
}\xi_{t}-\frac{1}{2}D\leq\lambda\leq\xi_{t}.\end{cases}$

Suppose $\lambda^{*}$ is the optimal solution to the deterministic problem
$\min_{\lambda\geq 0}D(\lambda)=\mathbb{E}D_{t}(\lambda)$. Without loss of
generality, we assume that our dual variable $\lambda$ is taken within
$\left[\frac{1}{4}D,\frac{1}{2}D\right]$ since we know that
$\lambda^{*}=\mathbb{E}\xi_{t}-\frac{1}{4}D=\frac{3}{8}D\in\left[\frac{1}{4}D,\frac{1}{2}D\right]$.

$D_{t}(\lambda)=f^{*}_{t}(\lambda)+d^{\top}\lambda=\lambda^{2}-2(\xi_{t}-\frac{1}{4}D)\lambda+\xi_{t}^{2}.$

For the dual-based police $\left\\{\lambda_{t}\right\\}_{t=0}^{T-1}$, the
corresponding primal variable is
$x_{t}=\tilde{x}_{t}(\lambda_{t-1})=2\xi_{t}-2\lambda_{t-1}$ or void if the
resource is depleted. We have the following regret:

$\displaystyle\operatorname{Regret}(A)=$ $\displaystyle
R^{*}(\mathcal{P})-R\left(A\middle|\mathcal{P}\right)$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\max_{x_{t}\in[0,D]}\left\\{\sum_{t=1}^{T}f_{t}(x_{t})\text{
s.t.
}\sum_{t=1}^{T}x_{t}\leq\frac{1}{2}DT\right\\}\right]-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$
$\displaystyle=$ $\displaystyle\mathbb{E}\left[\min_{\lambda\geq
0}\left\\{\sum_{t=1}^{T}D_{t}(\lambda)\right\\}\right]-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}D_{t}(\lambda^{*}_{T})\right]-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$

Define the corresponding

$g(\lambda)=\mathbb{E}\left[f_{t}(\tilde{x}_{t}(\lambda))+\langle
d-b_{t}\tilde{x}_{t}(\lambda),\lambda^{*}\rangle\right]=D(\lambda)-\langle\nabla
D(\lambda),\lambda-\lambda^{*}\rangle$

We have $g(\lambda^{*})=D(\lambda^{*})$ and
$g(\lambda^{*})-g(\lambda)=(\lambda^{*}-\lambda)^{2}$. For the quadratic
function $D_{t}$, we always have $D_{t}(\lambda_{1})-D_{t}(\lambda_{2})=\nabla
D_{t}(\lambda_{2})(\lambda_{1}-\lambda_{2})+(\lambda_{1}-\lambda_{2})^{2}$.
Thus it follows that

$\displaystyle\operatorname{Regret}(A)$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}D_{t}(\lambda^{*}_{T})\right]-TD(\lambda^{*})+TD(\lambda^{*})-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}D_{t}(\lambda^{*}_{T})-D_{t}(\lambda^{*})\right]+Tg(\lambda^{*})-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$
$\displaystyle=-\mathbb{E}\left[\sum_{t=1}^{T}\left[\nabla
D_{t}(\lambda^{*}_{T})(\lambda^{*}-\lambda^{*}_{T})\right]+T(\lambda^{*}-\lambda^{*}_{T})^{2}\right]+Tg(\lambda^{*})-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$
$\displaystyle=-T\mathbb{E}(\lambda^{*}-\lambda^{*}_{T})^{2}+Tg(\lambda^{*})-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right].$

By the dual convergence in Theorem 1, we know that the first term
$T\mathbb{E}(\lambda^{*}-\lambda^{*}_{T})^{2}$ can be bounded by a constant.
Now we handle the second term by controlling the stopping time. Define the
stopping time
$\tau_{0}=\min\left\\{t\in[T]\middle|\sum_{i=1}^{t}x_{t}\geq\frac{1}{2}DT-D\right\\}\cup\\{T\\}$.
Then when $t\leq\tau_{0}$, we always have
$x_{t}=\tilde{x}_{t}(\lambda_{t-1})=2\xi_{t}-2\lambda_{t-1}$, and
$0\leq\sum_{t=\tau_{0}+1}^{T}x_{t}\leq D$ for $t>\tau$. Then we have

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{\tau_{0}}f_{t}(\tilde{x}_{t}(\lambda_{t-1}))+\langle\frac{1}{2}D-\tilde{x}_{t}(\lambda_{t-1}),\lambda^{*}\rangle\right]+\mathbb{E}\left[\sum_{t=\tau_{0}+1}^{T}f_{t}(x_{t})+\langle\frac{1}{2}D-x_{t}(\lambda),\lambda^{*}\rangle\right]$
$\displaystyle\leq\mathbb{E}\sum_{t=1}^{\tau}g(\lambda_{t-1})+\mathbb{E}\left[\sum_{t=\tau_{0}+1}^{T}\frac{3}{4}Dx_{t}+\frac{1}{2}D\lambda^{*}\right]$
$\displaystyle\leq\mathbb{E}\sum_{t=1}^{\tau}g(\lambda_{t-1})+\frac{3}{16}D^{2}\mathbb{E}[T-\tau_{0}]+\frac{3}{4}D^{2}.$

The first inequality is because of the resource constraint, and the second one
is because $f_{t}(x)\leq f_{t}^{\prime}(0)(x-0)\leq\frac{3}{4}Dx$. If we
specify $\lambda_{t-1}=\xi_{t}$ when the resource constraints are violated, we
also have
$\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]\leq\mathbb{E}\sum_{t=1}^{T}g(\lambda_{t-1})$.
Then

$\displaystyle
Tg(\lambda^{*})-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]$
$\displaystyle\geq\mathbb{E}\left[\sum_{t=1}^{\tau_{0}}g(\lambda^{*})-g(\lambda_{t-1})\right]+\mathbb{E}(g(\lambda^{*})-\frac{3}{16}D^{2})\mathbb{E}[T-\tau_{0}]-\frac{3}{4}D^{2}$
(A.16)
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{\tau_{0}}(\lambda^{*}-\lambda_{t-1})^{2}\right]+\frac{5}{64}D^{2}\mathbb{E}[T-\tau_{0}]-\frac{3}{4}D^{2},$

or
$Tg(\lambda^{*})-\mathbb{E}\left[\sum_{t=1}^{T}f_{t}(x_{t})\right]\geq\mathbb{E}\left[\sum_{t=1}^{T}(\lambda^{*}-\lambda_{t-1})^{2}\right]$
. Applying van Trees inequality to the estimation of $\lambda^{*}$ (Li and
Ye,, 2021), we can prove the Theorem 4. To prove the Theorem 5, we only need
to show the stopping time $\mathbb{E}[T-\tau_{0}]\geq\Omega(\sqrt{T})$ given
the convergence condition. This proof is inspired by Arlotto and Gurvich,
(2019). Denote $t^{\prime}=\lfloor T-\sqrt{T}\rfloor$. We show that
$\mathop{{}\mathbb{P}}(\tau_{0}\leq t^{\prime})$ is larger that a constant $c$
so that $\mathbb{E}\tau_{0}\leq(1-c)T+c(T-\sqrt{T})\leq T-c\sqrt{T}$.

$\displaystyle\mathop{{}\mathbb{P}}(\tau_{0}\leq t^{\prime})$
$\displaystyle=\mathop{{}\mathbb{P}}\left(\sum_{t=1}^{t^{\prime}}2(\xi_{t}-\lambda_{t-1})\geq\frac{DT}{2}-D\right)$
$\displaystyle\geq\mathop{{}\mathbb{P}}\left(\left\\{\sum_{t=1}^{t^{\prime}}2(\xi_{t}-\lambda^{*})\geq\frac{DT}{2}-D+\varepsilon
D\sqrt{t^{\prime}}\right\\}\cap\left\\{\sum_{t=1}^{t^{\prime}}|\lambda_{t-1}-\lambda^{*}|<\varepsilon
D\sqrt{t^{\prime}}\right\\}\right)$
$\displaystyle\geq\mathop{{}\mathbb{P}}\left(\left\\{\sum_{t=1}^{t^{\prime}}2(\xi_{t}-\lambda^{*})\geq\frac{DT}{2}-D+\varepsilon
D\sqrt{t^{\prime}}\right\\}\right)-\mathop{{}\mathbb{P}}\left(\sum_{t=1}^{t^{\prime}}|\lambda_{t-1}-\lambda^{*}|\geq\varepsilon
D\sqrt{t^{\prime}}\right)$

With the condition $\mathbb{E}|\lambda_{t}-\lambda^{*}|\leq
c_{2}D/\sqrt{t+1}$, we have
$\mathop{{}\mathbb{P}}\left(\sum_{t=1}^{t^{\prime}}|\lambda_{t-1}-\lambda^{*}|\geq\varepsilon
D\sqrt{t^{\prime}}\right)\leq\frac{2c_{2}}{\varepsilon}$ by Chebyshev’s
inequality. Then it holds that

$\displaystyle\mathop{{}\mathbb{P}}(\tau_{0}\leq t^{\prime})$
$\displaystyle\geq\mathop{{}\mathbb{P}}\left(\left\\{\sum_{t=1}^{t^{\prime}}2(\xi_{t}-\lambda^{*})\geq\frac{DT}{2}-D+\varepsilon
D\sqrt{t^{\prime}}\right\\}\right)-\frac{2c_{2}}{\varepsilon}$
$\displaystyle=\mathop{{}\mathbb{P}}\left(\left\\{\sum_{t=1}^{t^{\prime}}\frac{4}{D}(\xi_{t}-\frac{D}{2})\geq\frac{t^{\prime}}{2}+(T-t^{\prime})-2+2\varepsilon\sqrt{t^{\prime}}\right\\}\right)-\frac{2c_{2}}{\varepsilon}$
$\displaystyle\geq\mathop{{}\mathbb{P}}\left(\left\\{\sum_{t=1}^{t^{\prime}}\frac{4}{D}(\xi_{t}-\frac{D}{2})\geq\frac{t^{\prime}}{2}+(1+2\varepsilon)\sqrt{t^{\prime}}\right\\}\right)-\frac{2c_{2}}{\varepsilon},$

where $\sum_{t=1}^{t^{\prime}}\frac{4}{D}(\xi_{t}-\frac{D}{2})$ follows the
binomial distribution $B(t^{\prime},\frac{1}{2})$, with mean
$\mu=\frac{t^{\prime}}{2}$ and standard deviation
$\sigma=\frac{\sqrt{t^{\prime}}}{2}$. The second inequality is because
$T-t^{\prime}\leq\sqrt{T}+1$ and
$\sqrt{T}-\sqrt{t^{\prime}}\leq\sqrt{T}-\sqrt{T-\sqrt{T}}=\frac{\sqrt{T}}{\sqrt{T-\sqrt{T}}+\sqrt{T}}\leq
1$. For the binomial distribution, $\mathop{{}\mathbb{P}}(X\geq\mu+x\sigma)$
converge to $\Phi(-x)$ for any $x$ with known $O(\frac{1}{\sqrt{n}})$ speed by
Berry-Esseen CLT where $\Phi(x)$ is the distribution function of standard
normal distribution. We let
$c_{2}=\sup_{\varepsilon>0}\varepsilon\Phi(-2-4\varepsilon)/{4}$. Then there
exists $\varepsilon_{0}>0$ such that when $T$ is large enough,
$\mathop{{}\mathbb{P}}\left(\left\\{\sum_{t=1}^{t^{\prime}}\frac{4}{D}(\xi_{t}-\frac{D}{2})\geq\frac{t^{\prime}}{2}+(1+2\varepsilon_{0})\sqrt{t^{\prime}}\right\\}\right)\geq\frac{3c_{2}}{\varepsilon_{0}}$,
which indicates that $\mathop{{}\mathbb{P}}(\tau_{0}\leq
t^{\prime})\geq\frac{c_{2}}{\varepsilon_{0}}$. This makes our proof complete.