text:
\section{Introduction}

Many design problems in engineering and science are inherently combinatorial. A typical goal in these problems is to select a subset of indices from a larger candidate set, by maximizing or minimizing an objective subject to certain constraints. In resource allocation, for instance, a goal may be to assign tasks to different actors to ensure their expedited and efficient completion.
In the climate sciences, a goal might be to create the most informative network of monitoring stations by identifying a set of locations from a larger list of plausible candidate sites.

Problems such as these can be formulated as the optimization of set functions. They have a rich mathematical structure and have been studied extensively \cite{Wolsey_Nemhauser_book,lovasz_book,Schrijver_book,Papadimitriou_Steiglitz_book}. Often the set functions exhibit properties such as \emph{submodularity} (\Cref{def:submodularity_using_firt_order_diff}), which allow for efficient optimization solutions \cite{fujishige2005}. The optimization of submodular functions has been a topic of intense research in the past decade owing to these functions' significance for many problems in  machine learning. The maximization and minimization of such functions under very general matroid constraints has been a focus of several studies \cite{Vondrak_2008,Vondrak_Chekuri_Zenklusen_2011,Jegelka_Bilmes_2011,Horel_Singer_2016,Sviridenko_etal_2017,Khanna_etal_2017_a}. For a catalog of historical efforts, as well as more recent investigations on these topics, we refer to the monographs \cite{Bach2013,Krause_Golovin_2014}.

While submodularity naturally arises in many problems, there are important problems where the objective lacks this property. Our interest is one such case, where the core task is to maximize a non-submodular but non-decreasing objective. Such objectives are ubiquitous in \emph{optimal experimental design} (OED), a fundamental problem in statistics which involves the specification of all aspects of an experiment. The mathematical foundations of experimental design have a history spanning almost a century \cite{Fisher_1936,Wald_1943}. Methods developed in this field are relevant to engineering, the social and medical sciences, and econometrics. In broad terms, a typical goal is to seek a design that provides the best ``return'' (suitably defined) for the least amount of experimental effort.

More specifically, we will consider optimal experimental design under cardinality constraints in the Bayesian setting, with an objective that reflects an end goal of parameter inference.
For a classical overview of experimental design, we refer the reader to \cite{Pukelsheim_oed_book,Fedorov_oed_book}, and for a perspective on Bayesian optimal experimental design, we highlight the review in \cite{Chaloner_etal_1995}.

When maximizing a submodular function under cardinality constraints, the greedy heuristic of successively picking the best candidate performs remarkably well despite its simplicity \cite{Nemhauser1978,Nemhauser1978b}.
The same technique works well in many cases with a non-submodular objective \cite{Das_Kempe_2011,Bian_etal_2017,Khanna_etal_2017_b,Elenberg_etal_2018,Qian_Singer_2019}.
Yet the repeated function evaluations necessary to update the incremental gains (see \Cref{def:incremental_gain}) at every step
may comprise

a staggering computational cost if each function evaluation is computationally intensive.
It is natural, then, to ask if there are favorable properties of the function that circumvent the need to repeatedly update the incremental gains. To what extent do such properties hold for a given function, and how can we exploit them? And how does the worst case bound suffer if the incremental gains are only periodically updated?

Motivated by these questions, we propose and analyze a variant of the greedy heuristic for non-submodular functions which we refer to as \emph{batch greedy}. We also analyze distributed and stochastic versions of this batch greedy approach.
Every step in these algorithms selects a batch of indices, thus reducing the overall number of function evaluations. In many practical problems---for instance Bayesian optimal experimental design---this heuristic still yields excellent solutions, as we shall demonstrate.

The solution index set of the greedy algorithm results from a sequence of locally optimal choices.  The choice in every step is determined  by the incremental gains associated with each index, or---in the batch greedy setting---by the \emph{sum} of incremental gains corresponding to a fixed-size subset of indices. The sum of incremental gains is simply a modular function (\Cref{def:modular_function}) and the individual incremental gains define a subgradient  (\Cref{def:sub_grad_diff_SM}).
Analogous to results in the convex analysis for the optimization of continuous functions, the performance of the greedy algorithm can be tied to properties of the subgradient.
The choice of subgradient is not unique for any real valued continuous function, and the same is true for set functions. This observation motivates us to recast sequential greedy algorithms in a more abstract framework using minorize--maximize (MM) optimization principles. Using this framework, we propose several alternative modular bounds
and use them to develop novel techniques for linear Bayesian optimal experimental design.

\subsection{Outline and summary of key contributions}

Much of the manuscript is written with Bayesian optimal experimental design as a motivation.
Yet our theoretical results are rather general: applicable to any monotone set function.

In describing these results (\Cref{sec:batch_greedy} and \Cref{subsec:greedy_as_mm}), we have favored a more abstract notation to help reach a broader readership. These sections can be read more or less independently of the rest of the paper.  With the same intention, we disperse much of the relevant literature survey into the sections that follow.
\begin{itemize}
\item In \Cref{sec:preliminaries_notation} we introduce some notation and background on set functions, and give an overview of the Bayesian experimental design problem. We formulate the design objectives we study, and comment on some of their set theoretic properties.

\item In \Cref{sec:batch_greedy} we discuss our primary results. We provide approximation guarantees for the batch greedy heuristic in the context of maximizing monotone but non-submodular objectives.
We analyze the standard batch greedy paradigm (\Cref{thm:batch_std_greedy}), along with distributed batch greedy (\Cref{thm:parallel_batch_std_greedy}) and stochastic batch greedy (\Cref{thm:stochastic_batch_std_greedy}) variants.

Our results portray the joint expressive power of the submodularity and supermodularity ratios. These two parameters quantify how much a function deviates from submodularity and supermodularity, respectively. We then bound these parameters for the information theoretic objective in linear Bayesian experimental design.

\item  Viewing the sub/super-modularity ratios as parameters that define tight modular bounds, we argue in \Cref{sec:mm_alg} that the classical greedy heuristic can be viewed as one instance of optimization based on the MM principle. Building on that insight, we put forth a general framework for optimizing monotone set functions using any modular bound (\Cref{thm:greedy_ascent}).

\item In \Cref{sec:mm_alg_lbip}, for the problem of linear Bayesian experimental design, we explicitly discuss one such MM-based optimization approach exploiting modular bounds on the mutual information objectives. These modular bounds are constructed using standard inequalities but, as we show, they have surprising connections to notions in polyhedral combinatorics.

\item In \Cref{sec:num_results} we investigate the performance of our algorithms on random instances of structured inverse problems, and on the problem of designing sensor networks for improving climate models. We end with a broader discussion of future directions in \Cref{sec:conclusions}.

\item \Cref{appendix:def} contains some background to help with the reading, and all the technical results are collected in \Cref{appendix:techResults}.
In \Cref{appendix:extra_discussion_and_num_results} we provide some supplementary numerical results and more discussion that helps contextualize the core ideas explored in this work.

\end{itemize}


TITLE: Step missing in the proof of $\mathbb{R}$ being uncountable.
QUESTION [3 upvotes]: Today I saw the proof of the uncountability of $\mathbb{R}$, where given  a list of all elements of $\mathbb{R}$, we produce an element not in the list by requiring that its $n$-th digit is different from the $n$-th digit of the $n$-th element of the list. Since it has different decimal expansion from every element in the list, it can't be on the list. I think this last statement is actually wrong since in $\mathbb{R}$ one number can have more than one decimal expansion. So even if the decimal expansion of the newly generated element differs from those of the elements on the list, this doesn't mean that the element is not in the list.
Am I right? and if so, how can the argument be fixed?

REPLY [0 votes]: you are right, but it's not enough to invalidate the proof and it is fixable.
The only real numbers with two different decimal expansions are those that can be written with an infinite number of $9$s at the end or those that can be written with an infinite number of $0$s at the end.  (All give an argument why at the end of this post).
So creating the element that will not be on the list replace the $n$ digit of the $n$ item with a different digit.  But a different digit that is not a $9$ or a $0$.
Alternatively we could insist that when we express a number in decimal, if it has two representations we always use the one with infinite $0$s. And we replaces $0$s with  $1$s and we won't have the issue.
=======
Okay, why are infinite $0$s at the end or infinite $9$s the only two cases where a real number has two decimal extensions?
The way we figure out decimal expansions is that we have a real $x$ and we have calculated $x'$ which is $x$ up to $k$ decimal spaces.  Now there is a $d \in \{0,1,2,3,4....,9\}$ so that $d\cdot \frac 1{10^k} \le x-x' \le d+1 \cdot \frac 1{10^k}$
The idea is that we pick our $k$th decimal as $d$ and let $x" = x' + d\times 1{10^k}$ and then continue along by figuring what digit we have $d_{k+1} \cdot \frac 1{10^{k+1}} \le x-x" \le d_{k+1}\times \frac 1{10^{k+1}}$ and we do that forever....
Now if $d\cdot \frac 1{10^k} < x-x' < d+1 \cdot \frac 1{10^k}$ we have no choice but to select $d$ as our $k$ decimal digit.
But if $x-x' = m\times \frac 1{10^k}$ exactly for an integer we will have $(m-1)\cdot \frac 1{10^k} \le (m\cdot \frac 1{10^k}= x-x') \le (m+1)\cdot \frac 1{10^k}$ and we have two choices for our $k$th decimal digit: We could pick $m$ (and that's the reasonable choice) or we could pick $m-1$ (a weird choice but a legal one).
If we pick $m$ as our $k$th decimal, then  $x" = x' + m\times \frac 1{10^k} = x$ and $x-x" = 0$ and we will get $0$ for all the rest of the digits.
If we pick $m-1$ as our $k$th decimal, then $x" = x' + (m-1)\times \frac 1{10^k} = x-\frac 1{10^k}$ and $x-x" = \frac 1{10^k}$ and when we do $d_{k+1}\times 10^{k+1}\le x-x" \le (d_{k+1}+1)\times \frac 1{10^{k+1}}$ and $d_{k+1} = 0,1,2,3,...,9$ we will have no choice but $d_{k+1} =9$ and we will get $9$s for the rest of the digits.
And those are the only ambiguities and the only way we get two decimal representations.
.....
Post script:
If we start with a real number $x$ and try to construct a decimal expansion from  a real number via rounding down then every real number will only have one decimal expansion and we will never get a decimal expansion with infinite $9$s at the end.
The only reason we have to worry about decimal expansions with infinite $9$s at the end, is that if we start with a decimal expansion first, and try to calculate which real number it is from the decimal expansion we could be given an expansion with an infinite number of $9$s at the end.  We could be given that and we have to figure what then?
But if that happens we discover that this is just the same as if we had taken the very last non-$9$ and added one to it and then continued with an infinite number of $0$.


TITLE: Proving bijectivity after restriction on codomain
QUESTION [0 upvotes]: While I get this intuitively, I'm not sure how to go about solving it...

Let $X, Y \ne \emptyset$, and let $f:X \to Y$ be bijective. Let $\emptyset \ne A \subseteq X$ and $B := f\restriction_A(A) = \{f(a) : a \in A\}$.

Let $f' : A → B; x \rightarrow f(x)$, i.e., $f' = f\restriction_A$, the codomain $Y$ has shruken to $B$.
Prove that $f'$ is bijective.

REPLY [0 votes]: I would write the following:
In order to prove that $f'$ is bijective, it's sufficient to prove that (i) $f'$ is injective (ii) $f'$ is surjective.
For injectivity of $f'$: suppose $f(a)=f(b)$, then $a=b$ by injectivity of $f$.
For surjectivity of $f'$: let $b\in B$, then by definition of $B$, there exists $a\in A$ such that $f(a)=b$. Then $f'(a)=b$.

I can think of another method: to point out an inverse of $f'$: since $f$ is bijective, there exists an inverse $g$. To be proven: $g|_B$ is the inverse of $f'$.


TITLE: Reducing to regular cardinals in c.c.c. implies same cardinals and cofinalities
QUESTION [1 upvotes]: In Chapter 14 of Jech's Set Theory, he asserts the following:

Definition 14.33. A forcing notion $P$ satisfies the countable chain condition (c.c.c.) if every antichain in $P$ is at most countable.

Theorem 14.34. If $P$ satisfies the countable chain condition then $V$ and $V[G]$ have the same cardinals and cofinalities.

The proof begins with

It suffices to show that if $\kappa$ is a regular cardinal then $\kappa$ remains regular in $V[G]$.

The proof continues, but my main point of confusion lies at the very beginning. Why is it sufficient to prove that regular cardinals remain regular? How does it follow from this that all cardinals and cofinalities are preserved?

REPLY [1 votes]: If $\mu$ has cofinality $\kappa<\mu$, and we changed the cofinality of $\mu$, then we had to have changed the cofinality of $\kappa$ as well, since the new cofinal sequence will define a cofinal sequence in $\kappa$.
This means that $\kappa$ is no longer a regular cardinal, as it was in the ground model, being the cofinality of $\mu$. And quite often, it might be that $\kappa$ is not a cardinal at all in $V[G]$.
So if a forcing preserves regularity, then it preserves cofinalities as well.


TITLE: Function estimation
QUESTION [0 upvotes]: I have a list of chest measures and I need to find the size that fits as many measures that it can. If I need to find 1 size it's easy as I can minimize the function $(x−a)^2$ with $x$ as size estimated and $a$ as chest measure. And I will have the average as a result.
I need to estimate 2 sizes that if $a$ fits better than $b$ I only get value from $a$ size and of course, get as many fitted measures. I want to solve it with Solver so I can't use IF function. If you recommend another program I will take a loot at it.
I don't know if I need to explain myself better

REPLY [0 votes]: Since you have multiple groups you're trying to match against, you need to optimize
$$
min((x - a)^2, (x - b)^2)
$$
for the values of a and b.


TITLE: Atomic number of $\rm CO_2$?
QUESTION [0 upvotes]: I have to calculate the Bethe-Bloch equation for a $\rm CO_2$ absorber, I know this is a stupid question, but is Atomic number additive? Or do I need to do something a little more complex?
I was think Z = 22 since C has 6 protons and O has 8, is that correct?

REPLY [1 votes]: The relevant term is the electron number density.  So you can safely treat $\rm CO_2$ as "a thing" with $Z=22, A=44,$, mass 44 grams/mole (with more significant digits from a reference, if you like).


TITLE: Convergence in $L^\infty$ norm and continuous function
QUESTION [0 upvotes]: Let $\mathcal{C}(T)$ be the set of continuous functions on $T$, which is a metric space under the norm $\left\|f\right\|_{\infty}=\sup_{t\in T}\left|f(t)\right|$. Suppose $\{X_{n}\}$ and $X$ take their values in $\mathcal{C}(T)$ and that you have shown that $X_{n}\stackrel{L}{\longrightarrow} X$ in $L^{\infty}(T)$. Show this implies $X_{n}\stackrel{L}{\longrightarrow}X$ in $\mathcal{C}(T)$ as well.

REPLY [5 votes]: $X_n\rightarrow X$ in $L^\infty(T)$ means $\|X_n-X\|_\infty\rightarrow 0$. But this also means $X_n\rightarrow X$ in $C(T)$ the only difference being that the $\sup$ in the definition of $L^\infty$ is an essential supremum, i.e. allowing for exceptional sets of measure zero. For continuous functions however, the essential supremum equals the  ordinary supremum.


TITLE: Oscillations Near Equilibrium (With Linear Differential Equations)
QUESTION [1 upvotes]: Case I: The force acting on an object of mass m is $F(x) = F_o(1-e^{\alpha x})$
Case II: The force acting on an object of mass m is $F(x) = F_o(1-e^{-\alpha x})$
where $F_o$ and $\alpha$ are positive constants. In which case can the object oscillate
near the equilibrium and what is the oscillation frequency?
SOLVING FOR CASE I
The total force on the object is: $$ F(x, x', t) = -kx +  F_o(1-e^{\alpha x})$$
and can be rewritten as: $$ x'' + w^2 x =  F_o(1-e^{\alpha x})$$
where $w^2 = -k/m$
This is an inhomogeneous linear differential equation. I first solve for the complementary solution, $x_c$, for $x'' + w^2x = 0$. This gives me: $$x_c = Ae^{0x} + Be^{-w^2x} = A + Be^{-w^2x}$$
I can then determine the particular solution, $x_p$ for:
$$ 1)x'' + w^2 x =  F_o$$
$$ x_{p1} = \frac{F_o}{w^2} $$
$$2) x'' + w^2 x =  -F_oe^{\alpha x}$$
$$ x_{p2} = \frac{-F_oe^{\alpha x}}{\alpha ^2 + 1}$$
For a general solution of:
$$ x = A + Be^{-w^2 x} + \frac{F_o}{w^2} + \frac{-F_oe^{\alpha x}}{\alpha ^2 + 1}$$
This raises two questions:
1 - Is this solution correct?
2- Once I solve for $F(x) = F_o(1-e^{-\alpha x})$, how do I determine the case in which the object oscillates near the equilibrium? I suppose I would need to minimize the amplitude? I'm not sure how to approach this.

REPLY [0 votes]: An object that oscillates near equilibrium will essentially follow the harmonic motion F = -kx, and at equilibrium x = 0. I take the derivatives for a) and b) and solve for frequency, where $ w = \sqrt{k/m}$:
a) $ (F_o - F_o e^{\alpha x})\frac{d}{dx} = {-kx}\frac{d}{dx} $
$ -F_o \alpha e^{\alpha x} = -k $
$k = F_o \alpha e^{\alpha x}$, and for x = 0 we have:
$$ w = \sqrt{\frac{F_o \alpha}{m}} $$
b) $ (F_o - F_o e^{-\alpha x})\frac{d}{dx} = {-kx}\frac{d}{dx} $
$ F_o \alpha e^{\alpha x} = -k $
$k = -F_o \alpha e^{\alpha x}$, and for x = 0 we have:
$$ w = \sqrt{\frac{-F_o \alpha}{m}} $$
which results in an imaginary number, so it doesn't work given the question at hand. Therefore, the object can only oscillate near the equilibrium position and a), and the frequency w is given as $$ w = \sqrt{\frac{F_o \alpha}{m}} $$


TITLE: Volume bounded by the three cylinders and the two tangent planes
QUESTION [0 upvotes]: Three identical cylinders of radius $R$ meters, with $0 < R < 1$, are placed so that their axes form an equilateral triangle of side $2$ meters. Calculate the volume bounded by the three cylinders and the two tangent planes to the three cylinders.

REPLY [0 votes]: If we consider $A$ as the origin of coordinates, the cylinder $C_1$, which has its axis $\overline{AB}$ on the $x$-axis, is defined as:
$C_1 = \displaystyle \left\{ (x, y, z) \in R^3 \ \ \left( y^2+z^2=R^2 \right) \wedge \left( 0 \leq x \leq 2\sqrt{3} \right) \right\}$
The parametric equations of $C_1$ are:
$C_1 \equiv \begin{cases}
x &= t \\
y &= R\cos(\alpha) \\
z &= R\sin(\alpha) \\
\end{cases} \quad \left( 0 \leq t \leq 2\sqrt{3} \right) \wedge (0 \leq \alpha < 2\pi)$...(1)
The axis $\overline{AC}$ of the cylinder $C_2$ is contained in the line with equation $y= \displaystyle \tan \left( \frac{\pi}{3} \right) x= \sqrt{3}x$.
$C_2$ cylinder is the result of the rotation of $\displaystyle \frac{\pi}{3}$ radians around the $Z$ axis of the $C_1$ cylinder:
$C_2 \equiv \begin{cases}
x &= \frac{t}{2}-\frac{\sqrt{3}}{2} R \cos(\alpha)  \\
y &= \frac{\sqrt{3}t}{2}+\frac{R}{2}\cos(\alpha) \\
z &= R\sin(\alpha) \\
\end{cases} \quad \left( 0 \leq t \leq 2\sqrt{3} \right) \wedge (0 \leq \alpha < 2\pi)$...(2)
Clearing $\alpha$ from (2), we obtain that the implicit equation of $C_2$ is: $3x^2+y^2+4z^2-2\sqrt{3}xy-4R^2=0$.
The slice produced at $C_1$ by the plane $z=z$ turns out to be:
$y^2=R^2-z^2 \implies \left( y = \sqrt{R^2-z^2} \right) \vee \left( y = -\sqrt{R^2-z^2} \right)$
The slice produced at $C_2$ by the plane $z=z$ turns out to be:
$\begin{array}{ll}
& 3x^2+y^2-2\sqrt{3}xy-4(R-z)^2=0 \implies \\
& \left( y = \sqrt{3}x+2(R-z) \right) \vee \left( y = \sqrt{3}x+2(z-R) \right)
\end{array}$
Let $A_t(z)$ be the area of trapezoid $A^{\prime}B^{\prime}EF$ :
$\begin{array}{lll}
A_t(z) &=& \displaystyle \frac{\lvert \overline{A^{\prime}B^{\prime}} \rvert + \lvert \overline{EF} \rvert}{2} \cdot y \\
&=& \displaystyle \frac{2}{2} \left( \sqrt{3}-\frac{\sqrt{R^2-z^2}+2(R-z)}{\sqrt{3}}+\sqrt{3}-\frac{2(R-z)}{\sqrt{3}} \right) \sqrt{R^2-z^2} \\
&=& \displaystyle \left( 2\sqrt{3} - \frac{\sqrt{R^2-z^2}+4R}{\sqrt{3}} \right) \sqrt{R^2-z^2}
\end{array}$
Let $H$ be the triangular prism defined by the two tangent planes to the $3$ cylinders and with a triangular base $\triangle ABC$. The volume $V_{1t}$ of the part of cylinder $C_1$ between the intersections with $C_2$ y $C_3$ within the triangular prism is:
$
\begin{array}{lll}
V_{1t} &=& \displaystyle \int_{-R}^R A_t(z) \mathrm{d}z \\
&=& \displaystyle \int_{-R}^R \left( 2\sqrt{3} - \frac{4R}{\sqrt{3}} \right) \sqrt{R^2-z^2} \mathrm{d}z - \int_{-R}^R \frac{\sqrt{R^2-z^2}}{\sqrt{3}} \sqrt{R^2-z^2} \mathrm{d}z \\
&=& \displaystyle \sqrt{3} \pi R^2 -\frac{2\sqrt{3}\pi R^3}{3} - \frac{4R^3}{3} = \sqrt{3} \pi R^2 - \frac{(2\sqrt{3}\pi+4)R^3}{3}
\end{array}$

The area $A_p(z)$ of the parallelogram $ADA'E$ is:
$\begin{array}{lll}
A_p(z) &=& \displaystyle \lvert \overline{AE} \rvert \cdot y = \left( \frac{\sqrt{R^2-z^2}+2(R-z)}{\sqrt{3}} \right) \sqrt{R^2-z^2} \\
&=& \displaystyle \frac{2\sqrt{3}}{3}(R-z) \sqrt{R^2-z^2} + \frac{\sqrt{3}}{3}(R^2-z^2)
\end{array}$
The volume $V_{12}$ of the intersections of the cylinders $C_1$ and $C_2$ within the triangular prism $H$ is:
$\begin{array}{lll}
V_{12} &=& \displaystyle \int_{-R}^R A_p(z) \mathrm{d}z \\
&=& \displaystyle \int_{-R}^R \left( \frac{2\sqrt{3}}{3}(R-z) \sqrt{R^2-z^2} + \frac{\sqrt{3}}{3}(R^2-z^2) \right) \mathrm{d}z \\
&=& \displaystyle \frac{\sqrt{3}R^3 \pi }{3} + \frac{4\sqrt{3}}{9} R^3 = \frac{\sqrt{3}(3\pi+4)}{9}R^3
\end{array}$
The volume $V_p$ of the triangular prism defined between the two tangent planes to the 3 cylinders with triangular base  $\triangle ABC$ is:
$V_p = \displaystyle [ABC] \cdot 2R = \frac{\sqrt{3}}{4} \left( 2\sqrt{3} \right)^2 \cdot 2R = \displaystyle \frac{4 \cdot 3 \cdot 2 \cdot \sqrt{3}}{4}R =  6 \sqrt{3}R$
By symetry, the volume $V(R)$ we are looking for is:
$\begin{array}{lll}
V(R) &=& Vp-3 \left( V_{12} + V_{1t} \right) \\
&=& \displaystyle 6 \sqrt{3}R - 3 \left( \frac{\sqrt{3}(3\pi+4)}{9}R^3 + \sqrt{3} \pi R^2 - \frac{(2\sqrt{3}\pi+4)R^3}{3} \right) \\
&=& 6 \sqrt{3}R +\sqrt{3}\pi(R-3)R^2-\frac{4}{3} \left( \sqrt{3} - 3 \right)R^3
\end{array}$


TITLE: Dualty is Sobolev spaces
QUESTION [1 upvotes]: I have a question about duality in Sobolev spaces .Let $\Omega $ be an open of $R$,Suppose that u$\in H_{0}^{2}(\Omega )\cap H^{3}(\Omega )$ and $v\in H_{0}^{2}(\Omega ).$ Is that this expression make a sens ?  $\int\limits_\Omega  {\partial _x^4u.vdx} $. Can i make a integration by part to get  $\int\limits_\Omega  {\partial _x^2u\partial _x^2vdx} $ ?
Thank you ?

REPLY [1 votes]: $$u \in H_{0}^{2}(\Omega )\cap H^{3}(\Omega ),v\in H_{0}^{2}(\Omega )$$
As you said by integration by parts we get
$$\int_\Omega  {\partial _x^4u ~v~\text{d}x} =\underbrace{\big[\partial_x^3 u~ v\big]_{\partial \Omega}}_{=0, ~v\in H_0^2} – \int_\Omega \partial_x^3 u~ \partial_x v ~\text{d}x=-\underbrace{\big[\partial_x^2 u~ \partial_x v\big]_{\partial \Omega}}_{=0, ~v\in H_0^2}+\int_\Omega \partial_x^2 u~ \partial_x^2 v ~\text{d}x$$
and using Cauchy-Schwarz we get that this integral exists
$$\int_\Omega \partial_x^2 u~ \partial_x^2 v ~\text{d}x \leq ||u''||_2 ||v''||_2<\infty$$
since $u \in H^2$ and $v \in H^2$ and therefore by definition $u'' \in L^2(\Omega)$ and $v'' \in L^2(\Omega)$. The integral in between also exists since we can bound it by $||u'''||_2 ||v'||_2$.
But as you mentioned does the first integral really make sense? Only implicitly by the equality to the integral on the right hand side. But just by the assumption we can't say that the fourth weak derivative of $u$ exists.


TITLE: Show that the hitting time of a closed set is stopping time
QUESTION [0 upvotes]: Let $(E,d)$ be a metric space and $B\subseteq E$ be closed, let $x:[0,\infty)\to E$, $I:=\{t\ge0:x(t)\in B\}$ and $\tau:=\inf I$. If $I$ is nonempty and $\tau\in I$, then we easily see that $$\tau\le t\Leftrightarrow\exists s\in I:s\le t\tag1$$ for all $t\ge0$. Moreover, if $I$ is nonempty and $x$ is right-continuous, then $\tau\in I$.
Now let $(X_t)_{t\ge0}$ be a right-continuous $E$-valued process on a probability space $(\Omega,\mathcal A,\operatorname P)$ and replace $I$ by $I:=\{t\ge0:X_t\in B\}$.
If $\omega\in\Omega$, by the aforementioned facts, either $I(\omega)=\emptyset$ (and hence $\tau(\omega)=\infty$) or $\tau(\omega)\in I(\omega)$ and hence $$\tau(\omega)\le t\Leftrightarrow\exists s\in I(\omega):s\le t\tag2.$$
From $(2)$ we see that $$\{\tau\le t\}=\bigcup_{s\in[0,\:t]}\{X_s\in B\}\tag3$$ for all $t\ge0$.

How can we show that $$\{\tau\le t\}=\bigcup_{\substack{s\in\mathbb Q\\0\le s\le t}}\{X_s\in B\}\tag4$$ for all $t\ge00$?

By $(3)$ we only need to show that if $(\omega,s)\in\Omega\times[0,t]$, there is a $\tilde s\in\mathbb Q$ with $0\le\tilde s\le t$ and $X_{\tilde s}\in B$.
How can we do that? Clearly, if we fix $\varepsilon>0$, we can use that $\mathbb Q$ is dense in $\mathbb R$ to find $\tilde s\in\mathbb Q$ with $|\tilde s-s|<\varepsilon$.
Now we somehow need to use that $X$ is right-continuous and a suitable characterization of closedness of $B$ ...
EDIT
I've found the following proof in Kallenberg:

Our case is item (ii). While he is only claiming that $\tau_B$ is a weakly stopping time (i.e. $\{\tau_B<t\}\in\mathcal F_t$), his proof claims $\{\tau_B\le t\}\in\mathcal F_t$? Is this a typo? Would be somehow strange, since I've taken this from the third edition of the book ...

REPLY [0 votes]: You need rigth continuity of the filtration for this. Instead of (4) use the following:
$$(\{\tau> t\})=\bigcup_{r\in\mathbb Q,t+\epsilon> r>t}\bigcap_{s<r} (\{X_s \in B^{c})$$ which belongs to $\mathcal F_{t+\epsilon}$.


TITLE: Proving whether an argument is valid or not when the truth value of a proposition just can't be found.
QUESTION [0 upvotes]: The question I must solve is the following:
Given Problem: Use the rules of inference, show that the given argument is valid or not. The domain is all persons.
“You are listening, and I am speaking. If you are listening, then it is not silence. If music system is off then it is
silence. If music system is not off then we are in happy mood, imply the conclusion that we are in happy mood and
we are good friends.”.
Give a reason for each step of proof.
My attempt at a Solution:
I begin solving it by first creating some propositions as follows:
p = "You are listening"
q = "I am speaking"
r = "It is silence"
s = "Music system is off"
t = "We are in a happy mood"
u = "We are friends"
Now I rewrite the given arguments as follows:

$p \land q$
$p \rightarrow \lnot r$
$s \rightarrow r$
$(\lnot s \rightarrow t) \rightarrow (t \land u)$

Using these premises I do:
$$p\land q \tag{Premise}\\$$
$$p \tag{Simplification}$$
$$p \rightarrow \lnot r \tag{Premise}$$
$$\lnot r \tag{Modus Ponens}$$
$$s\rightarrow r \tag{Premise}$$
$$\lnot s \tag{Modus Tollens}$$
$$\lnot s \rightarrow t \tag{Premise}$$
$$t \tag{Modus Ponens}$$
$$t \land u \tag{Premise}$$
Now I don't know the truth value of u, if I did I could derive it and I think that would prove that the argument is valid.
Question: Is the argument invalid since there is no way for me to derive anything further? Or is there a flaw in my reasoning here?

REPLY [1 votes]: It is obvious that you cannot derive that 'we are good friends', and so this argument is invalid.
But, you cannot show the argument to be invalud using rules of inference. Using rules of inference you can only show arguments to be valid.
So .. I have no idea how you are supposed to do what you are asked to do.
What a terrible problem!  Please let me know what book this is from so I can be sure never to get it.


text:
\begin{document}

\baselineskip24pt

\maketitle

\begin{abstract}
    The regret bound of {\it dynamic} online learning algorithms is often expressed in terms of the variation in the function sequence ($V_T$) and/or the path-length of the minimizer sequence after $T$ rounds. For strongly convex and smooth functions, \citet{zhang2017improved} establish the squared path-length of the minimizer sequence ($C^*_{2,T}$) as a lower bound on regret. They also show that online gradient descent (OGD) achieves this lower bound using multiple gradient queries per round. In this paper, we focus on unconstrained online optimization. We first show that a preconditioned variant of OGD achieves $O(C^*_{2,T})$ with one gradient query per round. We then propose online optimistic Newton (OON) method for the case when the first and second order information of the function sequence is {\it predictable}. The regret bound of OON is captured via the quartic path-length of the minimizer sequence ($C^*_{4,T}$), which can be much smaller than $C^*_{2,T}$. We finally show that by using multiple gradients for OGD, we can achieve an upper bound of $O(\min\{C^*_{2,T},V_T\})$ on regret.
\end{abstract}

\section{Introduction}
Online optimization is modeled as a repeated game between a learner and an adversary \citep{hazan2016introduction}. At the $t$-th round, $t\in [T]\triangleq\{1,\ldots,T\}$, the learner selects an action $\xb_t$ from a convex set $\Xc \subseteq \mathrm{R}^n$ based on the information from previous rounds. Then, the adversary reveals a convex function $f_t:\Xc\to\mathrm{R}$ to the learner that incurs the loss $f_t(\xb_t)$. The goal of online learning is to minimize the \emph{regret}, which is the difference between the cumulative loss of the learner and that of a comparator sequence in hindsight. Depending on the comparator sequence, the regret can be either static or dynamic. The static regret is defined with respect to a fixed comparator as follows
\begin{align}\label{eq:static}
\mathbf{Reg}^s_T \triangleq \sum^T_{t=1}f_t(\xb_t)-\min_{\xb\in\Xc}\sum^T_{t=1}f_t(\xb).
\end{align}

Static regret is well-studied in the literature of online optimization. \citet{zinkevich2003online} shows that online gradient descent (OGD) provides a $O(\sqrt{T})$ upper bound on static regret for convex functions. \citet{hazan2007logarithmic} improve this bound to $O(\log T)$ for exp-concave functions as well as strongly convex functions. These bounds turn out to be optimal given their corresponding lower bounds \citep{hazan2016introduction}.

A more stringent benchmark for regret can be defined when the comparator sequence is {\it time-varying}, introducing the notion of {\it dynamic} regret \citep{besbes2015non,jadbabaie2015online}. In this case, the learner's performance is measured against the best sequence of actions (minimizers) at each round as follows

\begin{equation}\label{eq: definition of dynamic regret}
    \mathbf{Reg}^d_T \triangleq  \sum^T_{t=1}f_t(\xb_t)-\sum^T_{t=1}f_t(\xb_t^*),
\end{equation}
where $\xb_t^*\triangleq \argmin_{\xb\in\Xc}f_t(\xb)$. More generally, dynamic regret against an arbitrary  comparator sequence $\{\ub_t\}_{t=1}^T$ is defined as \citep{zinkevich2003online},
\begin{equation}\label{eq: definition of dynamic regret general}
    \mathbf{Reg}^d_T(\ub_1,\ldots,\ub_T) \triangleq \sum^T_{t=1}f_t(\xb_t)-\sum^T_{t=1}f_t(\ub_t).
\end{equation}

It is well-known that since the function sequence can fluctuate arbitrarily, the worst-case dynamic regret scales linearly with respect to $T$. However, when the environment varies slowly, there is hope to bound dynamic regret.

In the past few years, various studies on {\it dynamic online learning} have provided regret bounds in terms of the variation in the function sequence and/or the path-length of the minimizer sequence \citep{besbes2015non,hall2015online,jadbabaie2015online}. The path-length of an arbitrary sequence $\{\ub_t\}_{t=1}^T$ is defined as \citep{zinkevich2003online},
\begin{equation}\label{eq: path length}
    C_T(\ub_1,\ldots,\ub_T)\triangleq \sum_{t=2}^T\norm{\ub_t-\ub_{t-1}}.
\end{equation}
\citet{zinkevich2003online} shows that applying OGD for convex functions results in an upper bound of $O(\sqrt{T}C_T)$ on dynamic regret. If the function sequence is assumed to be strongly convex and smooth, the upper bound can be further improved to $O(C_T^*)$ \citep{mokhtari2016online}, where
$$C_T^*\triangleq C_T(\xb_1^*,\ldots,\xb_T^*)=\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}.$$
Let us now define a new variation measure $C_{p,T}^*$ ( the path-length of order $p$) as follows
\begin{equation}\label{eq: path length order p}
     C_{p,T}^*\triangleq C_{p,T}(\xb_1^*,\ldots,\xb_T^*)= \sum_{t=2}^T\norm{\xb_t^*-\xb_{t-1}^*}^p,
\end{equation}
with the convention that $C_T^*=C_{1,T}^*$. It can be immediately seen that any bound of order $C_{p,T}^*$ implies a bound of order $C_{q,T}^*$ for $q<p$, as long as the minimizer sequence is assumed to be uniformly bounded. Recently, \citet{zhang2017improved} prove that by using multiple gradient queries in one round, the regret of OGD can be improved to $O(C_{2,T}^*)$, which can be much smaller than $C_T^*$ when the local variations are small. \citet{zhang2017improved} also prove that the bound $O(C_{2,T}^*)$ is optimal in the worst-case.

Besides the path-length, another commonly used regularity measure is $V_T$, the cumulative variation in the function sequence, defined as
 \begin{equation}\label{eq: variation in funciton values}
    V_T\triangleq \sum_{t=2}^T \sup_{\xb \in \Xc} |f_t(\xb)-f_{t-1}(\xb)|.
\end{equation}
\citet{besbes2015non} show that the dynamic regret can be bounded by $O(T^{2/3}(V_T+1)^{1/3})$ and $O(\sqrt{T(1+V_T)})$
for convex functions and strongly convex functions, respectively. Note that in general $C_T$ and $V_T$ are not directly comparable, and \citet{jadbabaie2015online} provide problem environments where $V_T$ and $C_T$ are significantly different in terms of the order.

 In this work, we focus on {\it unconstrained} online optimization for strongly convex and smooth functions and study dynamic regret in the sense of \eqref{eq: definition of dynamic regret}. Our contribution is threefold:
 \begin{itemize}
     \item We propose online preconditioned gradient descent (OPGD), where the gradient direction is re-scaled by a time-varying positive-definite matrix at each round. We show that OPGD achieves the dynamic regret bound of $O(C^*_{2,T})$ with one gradient query in each round. Beside matching the lower bound in \citep{zhang2017improved}, the result also entails that OGD and a regularized variant of online Newton method enjoy the same regret bound (Section \ref{sec:opgd}).
     \item Inspired by optimistic mirror descent \citep{rakhlin2013optimization}, where predictions of the gradient sequence are used, we propose optimistic online Newton (OON) by incorporating predictions of the Hessian and gradient to online Newton method. We prove that in this case the dynamic regret bound can be further improved to $O(C^*_{4,T})$ if the predictions are accurate enough (Section \ref{sec:newton}).
     \item We finally show that by applying multiple gradient descents, the dynamic regret is upper bounded by $O(\min \{V_T, C^*_{2,T}\})$. We also construct problem setups where $V_T$ is much larger than $C^*_{2,T}$ in order, and vice versa (Section \ref{sec:4}).
 \end{itemize}
The proofs of our results are provided in the supplementary material.

\section{Related Literature}
{
\renewcommand{\arraystretch}{1.3}
\begin{table}[h!]
\caption{Related works on dynamic online learning (single gradient query in each round)}
\centering
\begin{adjustbox}{max width=0.99\columnwidth}
\begin{tabular}{||c c c c||}
 \hline
 Reference & Regret Definition & Setup & Regret Bound\\
 \hline\hline
 \citep{zinkevich2003online} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\ub_t)$ & Convex & $O\big(\sqrt{T}(1+C_T(\ub_1,\ldots,\ub_T))\big)$ \\
 \citep{hall2015online} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\ub_t)$ & Convex & $O\big(\sqrt{T}(1+C^\prime_T(\ub_1,\ldots,\ub_T))\big)$\\
 \citep{besbes2015non} & $\sum_{t=1}^T \mathbf{E}[f_t(\xb_t)]-f_t(\xb_t^*)$ & Convex & $O\big(T^{2/3}(1+V_T)^{1/3}\big)$\\
 \citep{besbes2015non} & $\sum_{t=1}^T \mathbf{E}[f_t(\xb_t)]-f_t(\xb_t^*)$ & Strongly Convex & $O\big(\sqrt{T(1+V_T)}\big)$\\
 \citep{jadbabaie2015online} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\xb_t^*)$ & Convex & $O\big(\sqrt{D_T+1}+\min \big\{\sqrt{(D_T+1)C_T^*}, [(D_T+1)V_T T]^{1/3}\big\}\big)$\\
 \citep{mokhtari2016online} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\xb_t^*)$ & Strongly Convex and Smooth & $O\big(C_T^*\big)$\\
 \citep{zhang2018adaptive} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\ub_t)$ & Convex & $O\big(\sqrt{T(1+C_T(\ub_1,\ldots,\ub_T))}\big)$ \\
 \textbf{This work} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\xb_t^*)$ & Strongly Convex and Smooth & ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ $O\big(C_{2,T}^*\big)$ ~~~~~~~~~~~~~~ {\tt OPGD Algorithm}\\
 \textbf{This work} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\xb_t^*)$ & Strongly Convex and Smooth & ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ $O\big(C_{4,T}^* + D^\prime_T\big)$ ~~~~~ {\tt OON Algorithm}\\
 \hline
\end{tabular}
\end{adjustbox}
\label{table:Dynamic regret bounds of related works 1}
\end{table}
}

{
\renewcommand{\arraystretch}{1.3}
\begin{table}[h!]
\caption{Related works on dynamic online learning (multiple gradient queries in each round)}
\centering
\begin{adjustbox}{max width=0.99\columnwidth}
\begin{tabular}{||c c c c||}
 \hline
 Reference & Regret Definition & Setup & Regret Bound\\
 \hline\hline
 \citep{zhang2017improved} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\xb_t^*)$ & Strongly Convex and Smooth & $O\big(\min\{C^*_T,C_{2,T}^*\}\big)$\\
 \textbf{This work} & $\sum_{t=1}^T f_t(\xb_t)-f_t(\xb_t^*)$ & Strongly Convex and Smooth & $O\big(\min\{V_T,C_{2,T}^*\}\big)$\\
 \hline
\end{tabular}
\end{adjustbox}
\label{table:Dynamic regret bounds of related works 2}
\end{table}
}

In this section, we provide related literature on dynamic regret defined in \eqref{eq: definition of dynamic regret} and \eqref{eq: definition of dynamic regret general}. A summary of the results is tabulated in Tables \ref{table:Dynamic regret bounds of related works 1} and \ref{table:Dynamic regret bounds of related works 2}. In particular, Table \ref{table:Dynamic regret bounds of related works 1} summarizes results with one gradient query per round, whereas Table \ref{table:Dynamic regret bounds of related works 2} exhibits those with multiple gradient queries per round.

As previously mentioned, \citet{zinkevich2003online} shows that when the functions are convex, by applying OGD with a diminishing step size of $1/\sqrt{t}$, the dynamic regret defined in \eqref{eq: definition of dynamic regret general} can be bounded by $O(\sqrt{T}(1+C_T))$. \citet{zhang2018adaptive} combine OGD with expert advice to improve the bound to $O(\sqrt{T(1+C_T)})$. Focusing on
regret in the sense of \eqref{eq: definition of dynamic regret}, \citet{mokhtari2016online} establish a regret bound of $O(C^*_T)$ for OGD under strong convexity and smoothness of the function sequence. \citet{lesage2020second} show the same bound for online Newton method.

To further express the existing regret bounds, we need to define several other regularity measures. The first one is similar to the path-length \eqref{eq: path length} and is defined as
\begin{equation}\label{eq: path length prime}
    C^\prime_T(\ub_1,\ldots,\ub_T)\triangleq\sum_{t=2}^T\norm{\ub_t - \Phi_t(\ub_{t-1})},
\end{equation}
where $\Phi_t(\cdot)$ is a given dynamics (available to the learner).
\citet{hall2015online} propose a dynamic mirror descent algorithm that incorporates the dynamics $\{\Phi_t(\cdot)\}_{t=1}^T$ into online mirror descent and achieves a regret bound of $O(\sqrt{T}(1+C^\prime_T))$.

\citet{besbes2015non} propose a restarted OGD and analyze its performance for the case when only {\it noisy} gradients are available to the learner. They prove that the expected dynamic regret is bounded by $O(T^{2/3}(V_T+1)^{1/3})$ and $O(\sqrt{T(1+V_T)})$ for convex and strongly convex functions, respectively. The restarted OGD of \citep{besbes2015non} is designed under the assumption that $V_T$ (or an upper bound on $V_T$) is available to the learner from the outset.

 Another measure is $D_T$, the variation in gradients, which is defined as
\begin{equation}\label{eq: variation in gradients}
    D_T\triangleq \sum_{t=1}^T \norm{\nabla f_t(\xb_t)-\mb_t}^2,
\end{equation}
where $\mb_t$ is a predictable sequence computed by the learner before round $t$ \citep{rakhlin2013online, rakhlin2013optimization}. A special version of $D_T$ with $\mb_t=\nabla f_{t-1}$ is introduced by \citep{chiang2012online}, and the current definition is used by \citep{rakhlin2013online, rakhlin2013optimization} for studying optimistic mirror descent. Nevertheless, all of these works deal with static regret. Motivated by the fact that various regularity measures are not directly comparable, \citet{jadbabaie2015online} propose an adaptive version of optimistic mirror descent to bound dynamic regret \eqref{eq: definition of dynamic regret}. They establish a regret bound in terms of $C_T$, $D_T$, and $V_T$ for convex functions with the assumption that the learner can accumulate each of these measures on-the-fly. When $V_T=0$ or $C_T=0$, their bound recovers that of \citep{rakhlin2013optimization} on static regret.

 Inspired by the notion of $D_T$, we introduce in Section \ref{sec:newton} a new regularity $D^\prime_T$ defined as
\begin{equation}\label{eq: variation in Hessians and gradients}
    D^\prime_T\triangleq \sum_{t=2}^T \norm{\Mb_t^{-1}(\cdot)\mb_t(\cdot)-(\nabla^2 f_{t}(\cdot))^{-1}\nabla f_t(\cdot)}^2,
\end{equation}
where $\Mb_t(\cdot)$ and $\mb_t(\cdot)$ denote the predictions of $\nabla^2f_t(\cdot)$ and $\nabla f_t(\cdot)$, respectively. We later show that by applying OON, the dynamic regret bound is $O(D^\prime_T+C^*_{4,T})$. This is an improvement over $O(C^*_{2,T})$ only if $D^\prime_T$ is small, i.e., the predictions of the learner are accurate enough. Nevertheless, we also show that if the learner uses stale gradient/Hessian information in the form of $\mb_t=\nabla f_{t-1}$ and $\Mb_t=\nabla^2f_{t-1}$, the regret is still $O(C^*_{2,T})$.

Other related works on dynamic regret include \citep{ravier2019prediction,yuan2019trading}. \citet{ravier2019prediction} assume the function sequence has a parametrizable structure and quantify the functional difference in terms of the variation in parameters. They propose an online gradient method combined with the prediction of the function parameters and show that the dynamic regret can be bounded in terms of $C^*_T$ as well as the accumulation error in the parameters. \citet{yuan2019trading} analyze the trade-off between static and dynamic regret through studying the effect of forgetting factors for a class of online Newton algorithms.

We note that \citet{zhang2017improved} prove a $O(\min\{C^*_T, C_{2,T}^*\})$ regret bound with multiple gradient queries for OGD. We revisit the same algorithm (in an unconstrained setup) and establish a bound of $O(\min\{V_T, C_{2,T}^*\})$. The main benefit of the latter is that $V_T$ and $C_{2,T}^*$ are not comparable, whereas $C^*_{2,T}=O(C_T^*)$ as long as the minimizer sequence is bounded.

{\bf Adaptive Regret:} Beside the works related to the dynamic regret, the notion of adaptive regret \citep{hazan2007adaptive,daniely2015strongly,zhang2018dynamic, zhang2019adaptive,zhang2020minimizing} is also proposed to capture the dynamics in the environment. Adaptive regret characterizes a local version of static regret, where
 $$\mathbf{Reg}^a_T([r,s]) \triangleq \sum_{t=r}^s f_t(\xb_t)-\min_{\xb\in\Xc}\sum_{t=r}^s f_t(\xb),$$
 for each interval $[r,s]\subseteq [T]$. \citet{zhang2018dynamic} draw a connection between strongly adaptive regret and dynamic regret and propose an adaptive algorithm which can bound the dynamic regret without prior knowledge of the functional variation. \citet{zhang2020minimizing} propose a novel algorithm which can minimize the dynamic regret and the adaptive regret simultaneously.
\section{Main Results}
In this section, we present our main results. We first prove that OPGD achieves the optimal bound of $O(C_{2,T}^*)$ for dynamic regret \eqref{eq: definition of dynamic regret}, matching the lower bound of \citep{zhang2017improved}. Then, we develop a variant of online Newton method (called OON), which employs predicted first and second order information in the update. The bound on the dynamic regret of OON can be improved to $O(C_{4,T}^*)$ if the predictions are accurate.

\subsection{Preliminaries}
Since our results are on strongly convex and smooth functions, we start by their formal definitions below. Throughout, we assume that the function sequence $\{f_t\}_{t=1}^T$ is differentiable.
\begin{definition}
A function $f:\Xc\to \mathrm{R}$ is $\mu$-strongly convex ($\mu>0$) over the convex set $\Xc$ if $$f(\xb)\geq f(\yb)+\nabla f(\yb)^\top(\xb-\yb) +\frac{\mu}{2}\norm{\xb-\yb}^2,\quad \forall\xb,\yb \in \Xc.\quad.$$
\end{definition}

\begin{definition}
A function $f:\Xc\to \mathrm{R}$ is $L$-smooth ($L>0$), when its gradient is Lipschitz continuous over the convex set $\Xc$, where
$$f(\xb)\leq f(\yb)+\nabla f(\yb)^\top(\xb-\yb) +\frac{L}{2}\norm{\xb-\yb}^2,\quad \forall\xb,\yb \in \Xc.\quad$$
\end{definition}

\subsection{Dynamic Regret Bound for Online Preconditioned Gradient Descent (OPGD)}\label{sec:opgd}
When the functions are $\mu$-strongly convex and $L$-smooth,
\citet{mokhtari2016online} prove that the dynamic regret of OGD can be upper bounded by $O(C_T^*)$. \citet{zhang2017improved} show that multiple gradient descents can help improving it to $O(\min\{C_T^*, C_{2,T}^*\})$.

We observe that in the unconstrained setup (which implies $\norm{\nabla f_t(\xb_t^*)}=0$ for every $t\in [T]$), querying just one gradient in each round is enough to obtain $O(C_{2,T}^*)$. We analyze this observation for a slightly more general case where OGD is preconditioned, i.e., the gradient direction at each round is re-scaled according to a positive definite matrix. Our method, called OPGD, is summarized in Algorithm \ref{alg:OPGD}. We establish the regret bound in the following theorem, under an assumption that characterizes the relationship of the condition number of the matrices used for preconditioning to parameters $\mu$ and $L$.

\begin{theorem}\label{T: Improved OPGD dynamic bound} Suppose that for any $t\in [T]$:
\begin{enumerate}
    \item The function $f_t:\mathrm{R}^n\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth, and $\xb^*_t$ is bounded.
    \item The preconditioning matrix $\Ab_t$ satisfies $\lambda^\prime\cdot \Ib\preceq \Ab_t \preceq \lambda \cdot \Ib.$
    \item The condition number satisfies $\frac{\lambda}{\lambda\prime} < 1+\frac{\mu^2}{4L^2}.$
\end{enumerate}
If we set $\eta=\frac{\lambda^\prime\mu}{2L^2}$, the dynamic regret for the sequence of actions $\xb_t$ generated by OPGD is bounded as follows
$$\mathbf{Reg}^d_T\leq  \left(\frac{L^2}{\mu}\right)\left(\frac{4L^2\lambda-\mu^2\lambda^\prime}{\mu^2\lambda^\prime - 4L^2\lambda + 4L^2\lambda^\prime}\right)\sum_{t=2}^{T+1} \norm{\xb_t^* - \xb_{t-1}^*}^2 + \left(\frac{L^2\lambda}{\lambda^\prime\mu} - \frac{\mu}{4}\right)\norm{\xb_1 - \xb_1^*}^2.$$\\
\end{theorem}
The theorem above shows that OPGD achieves $O(C_{2,T}^*)$ regret. An immediate corollary is that OGD also achieves the same rate if we set $\Ab_t=\Ib$, which implies $\lambda=\lambda^\prime=1$.

\begin{algorithm}[tb]
   \caption{Online Preconditioned Gradient Descent (OPGD)}
   \label{alg:OPGD}
\begin{algorithmic}[1]
   \STATE {\bfseries Require:} Initial vector $\xb_1\in \mathrm{R}^n$, step size $\eta$, a sequence of positive definite matrices $\Ab_t$

   \FOR{$t=1,2,\ldots,T$}
   \STATE Play $\xb_t$
   \STATE Observe the gradient of the current action $\nabla f_t(\xb_t)$
   \STATE $\xb_{t+1} = \xb_t - \eta\Ab^{-1}_t\nabla f_t(\xb_t)$
   \ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{corollary}\label{Corollary: OGD Recovery}
Suppose that for any $t\in [T]$, the function $f_t:\mathrm{R}^n\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth, and $\xb^*_t$ is bounded. Let $\Ab_t=\Ib$,  then OPGD amounts to OGD, and it achieves a regret bound of $O(C_{2,T}^*)$.
\end{corollary}
Another corollary of Theorem \ref{T: Improved OPGD dynamic bound} is on a regularized version of online Newton method as follows.
\begin{corollary}\label{Corollary: ONS Recovery}
Suppose that for any $t\in [T]$, the function $f_t:\mathrm{R}^n\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth, and $\xb^*_t$ is bounded. Let $\Ab_t=\nabla^2 f_t(\xb_t) + \zeta\cdot\Ib$ where $\zeta > \frac{(L-\mu)4L^2}{\mu^2}-\mu$. Then, OPGD corresponds to a regularized variant of online Newton method, and it achieves a regret bound of $O(C_{2,T}^*)$.
\end{corollary}
\begin{proof}
We just need to verify the third condition in Theorem \ref{T: Improved OPGD dynamic bound} for which we require $$\frac{L+\zeta}{\mu+\zeta}<1+\frac{\mu^2}{4L^2}\Longleftrightarrow \zeta > \frac{(L-\mu)4L^2}{\mu^2}-\mu.$$
\end{proof}
Compared to the regret bound of \citep{lesage2020second} for online Newton method, Corollary \ref{Corollary: ONS Recovery} puts no constraint on the relative location of the starting point, i.e., the result is global (and not local). Moreover, the regret bound is tighter as $O(C_{2,T}^*)$ always implies $O(C_{T}^*)$ when the minimizer sequence is uniformly bounded.

\begin{algorithm}[tb]
   \caption{Optimistic Online Newton (OON)}
   \label{alg:OON}
\begin{algorithmic}[1]
   \STATE {\bfseries Require:} Initial vector $\xb_1=\hat{\xb}_0\in \mathrm{R}^n$,

   \FOR{$t=1,2,\ldots,T$}
   \STATE Play $\xb_t$
   \STATE Get the predicted second order information $\Mb_{t+1}$ and first order information $\mb_{t+1}$ of function $f_{t+1}$
   \STATE $\hat{\xb}_{t} = \hat{\xb}_{t-1} - \Hb_{t}^{-1}(\hat{\xb}_{t-1})\nabla f_{t}(\hat{\xb}_{t-1})$
   \STATE $\xb_{t+1} = \hat{\xb}_t - \Mb_{t+1}^{-1}(\hat{\xb}_t)\mb_{t+1}(\hat{\xb}_t)$
   \ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Improved Dynamic Regret Bound for Optimistic Online Newton (OON)}\label{sec:newton}
The optimal bound on static regret for convex functions is $O(\sqrt{T})$ \citep{hazan2016introduction}. However, \citet{rakhlin2013optimization} show that by using gradient predictions, the regret bound can be $O(\sqrt{D_T})$, which is tighter if the predicted gradients are close enough to the actual gradients. Essentially, by using the predicted sequence, the learner aims at taking advantage of the niceness of the adversarial sequence (if possible).

In this section, we extend this idea to the case that the learner can use first and second order information simultaneously. The resulting algorithm, called optimistic online Newton (OON), is summarized in Algorithm \ref{alg:OON}. The learner performs a Newton update based on the predicted information but corrects this update using the true information. The following theorem presents the regret bound of OON in a local sense, which has the potential to significantly outperform first-order methods. The local nature of the result is not surprising as for the classical Newton method, quadratic convergence guarantee is only local (see e.g., Theorem 1.2.5 of \citep{nesterov1998introductory}).

\begin{theorem}\label{T:Online Newton dynamic bound}
Suppose that for any $t \in [T]$:
\begin{enumerate}
    \item The function $f_t:\mathrm{R}^n\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth, and $\xb^*_t$ is bounded.
    \item $\exists L_H>0$ such that $\norm{\Hb_t(\xb) - \Hb_t(\xb_t^*)}\leq L_H\norm{\xb-\xb_t^*}$, where $\Hb_t(\xb) = \nabla^2 f_t(\xb)$.
    \item $\exists \xb_1 \in \mathrm{R}^n$ such that $\norm{\xb_1 - \xb_1^*}\leq \frac{\mu}{L_H}$.

    \item There exists a bound on local variations, where $\bar{c}\triangleq \max_{t\in\{2,\ldots,T\}}\norm{\xb_t^* - \xb_{t-1}^*} \leq \frac{\mu}{2L_H}.$
\end{enumerate}
Then, the dynamic regret for the sequence of actions $\xb_t$ by OON is bounded by
\begin{equation}\label{eq: Dynamic bound of OON.}
\begin{split}
    \mathbf{Reg}^d_T&\leq L\bigg( \frac{\norm{\hat{\xb}_1 - \xb_1^*}^2- \rho^{\prime}\norm{\hat{\xb}_T - \xb_T^*}^2}{1-\rho^{\prime}} + \frac{\rho^{\prime\prime}}{1-\rho^\prime}\sum_{t=2}^{T}\norm{\xb^*_{t}-\xb^*_{t-1}}^4\bigg)\\ &+ LD^\prime_T + L\norm{\Hb_{1}^{-1}(\hat{\xb}_{0})\nabla f_1(\hat{\xb}_{0})}^2,
\end{split}
\end{equation}
where $\rho^{\prime}\triangleq\frac{1}{16}(1+c_1)^2(1+c_2),\quad \rho^{\prime \prime}\triangleq(\frac{L_H}{2\mu})^2(1+\frac{1}{c_1})^2(1+\frac{1}{c_2})$, $c_1$ and $c_2$ are any positive constants such that $0<\rho^{\prime}<1$, and $D^\prime_T\triangleq \sum_{t=2}^T \norm{\Mb_t^{-1}(\hat{\xb}_{t-1})\mb_t(\hat{\xb}_{t-1})-\Hb_{t}^{-1}(\hat{\xb}_{t-1})\nabla f_t(\hat{\xb}_{t-1})}^2$.
\end{theorem}
The theorem indicates that when the predicted information $(\Mb_t,\mb_t)$ is close to $(\Hb_t,\nabla f_t)$, $D'_T$ would be small and the dynamic regret bound would be close to $O(C_{4,T}^*)$. On the other hand, it can also be shown that if the learner uses stale information, i.e., $\Mb_t = \Hb_{t-1}$ and $\mb_t = \nabla f_{t-1}$, the regret bound of \eqref{eq: Dynamic bound of OON.} is $O(C_{2,T}^*)$, which matches the optimal worst-case bound.

\begin{corollary}\label{Corollary: Optimistic online Newton stale information} Suppose that the assumptions of Theorem \ref{T:Online Newton dynamic bound} hold. If for $t=2,\ldots,T$, $(\Mb_t,\mb_t)=(\Hb_{t-1}, \nabla f_{t-1})$, the dynamic regret for the sequence of actions $\xb_t$ by OON is bounded by $O(C^*_{2,T})$.
\end{corollary}

\section{Dynamic Regret Bound for Online Multiple Gradient Descents (OMGD)}\label{sec:4}
In this section, we revisit the OMGD algorithm developed by \citep{zhang2017improved}, outlined in Algorithm \ref{alg:OMGD}. \citet{zhang2017improved} prove that by applying multiple gradient descents, the dynamic regret bound is $O(\min\{C^*_{T}, C^*_{2,T}\})$, which basically translates to $O(C^*_{2,T})$ as soon as the minimizers are uniformly bounded. We show that the regret bound of \citet{zhang2017improved} can be made more comprehensive by including $V_T$, the variation in the function sequence. The new bound, which takes the form of $O(\min\{V_T, C^*_{2,T}\})$, is presented below.

\begin{algorithm}[tb]
   \caption{Online Multiple Gradient Descent (OMGD) \citep{zhang2017improved}}
   \label{alg:OMGD}
\begin{algorithmic}[1]
   \STATE {\bfseries Require:} Initial vector $\xb_1\in \mathrm{R}^n$, step size $\eta$, function parameters $\mu$ and $L$.
   \FOR{$t=1,2,\ldots,T$}
   \STATE Play $\xb_t$
   \STATE Receive the information of $f_t$
   \STATE Let $\zb_{t+1}^{(0)}=\xb_t$ and $K_t=\lceil \frac{-2\log(t)}{\log(1-\frac{2\eta\mu L}{\mu+L})} \rceil$
        \FOR{$j=1,2,\ldots,K_t$}
        \STATE $\zb_{t+1}^{(j)} = \zb_{t+1}^{(j-1)} - \eta\nabla f_t(\zb_{t+1}^{(j-1)})$
        \ENDFOR
   \STATE $\xb_{t+1} = \zb_{t+1}^{(K_t)}$
   \ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{theorem}\label{T:Online multiple gradient}
Suppose that for any $t\in [T]$, the function $f_t:\mathrm{R}^n\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth, and $\xb^*_t$ is bounded.
For any $0<\eta\leq \frac{2}{\mu+L}$, the dynamic regret of OMGD is bounded as follows
\begin{equation}\label{eq: Bound of Multiple GD}
    \mathbf{Reg}^d_T\leq \min \begin{cases} (f_1(\xb_1)-f_1(\xb^*_1)) + 2V_T + \frac{\pi^2 D^2L}{12}\\
    \frac{L}{2}\big[\norm{\xb_1 - \xb^*_1}^2 + 2D^2(\frac{\pi^2}{6}) + 2C^*_{2,T}\big]
    \end{cases},
\end{equation}
where $D\triangleq \max_{t\in[T]}\norm{\xb_t-\xb^*_t}$, and $V_T$ is defined with respect to $\Xc$ being the convex hull of $\{\xb_t,\xb^*_t\}_{t=1}^T$.
\end{theorem}

\subsection{Comparison of $C^*_{2,T}$ and $V_T$}
We now show that $V_T$ and $C^*_{2,T}$ are not directly comparable to each other. Therefore, having both of them present in the regret bound can only make the bound tighter. We construct two problem environments where $C^*_{2,T} \ll V_T$ and $V_T \ll C^*_{2,T} $, respectively.

Consider the following function sequence $f_t:\mathrm{R}^n\to \mathrm{R}$
\begin{eqnarray*}
    f_t(\xb) = \begin{cases}\norm{\xb-\xb^*}^2, \text{if } t \text{ is odd}\\
    \norm{\xb-\xb^*}^2 + 1, \text{if } t \text{ is even}
    \end{cases}
\end{eqnarray*}
For this function sequence, based on the regularity definitions \eqref{eq: path length order p} and \eqref{eq: variation in funciton values}, it is clear that
\begin{eqnarray*}
    &&C^*_{2,T} = \sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2 = \sum_{t=2}^T\norm{\xb^*-\xb^*}^2 = 0.\\
    &&V_T = \sum_{t=2}^T\sup_{\xb\in\Xc}|f_t(\xb)-f_{t-1}(\xb)| = \Theta(T).
\end{eqnarray*}
In this case, we see that $V_T$ is much larger than $C^*_{2,T}$. On the other hand, consider another function sequence $f_t:\mathrm{R}^n\to \mathrm{R}$
\begin{eqnarray*}
    f_t(\xb) = \begin{cases}\frac{\norm{\xb}^2}{t}, \text{if } t \text{ is odd}\\
    \frac{\norm{\xb-\yb}^2}{t}, \text{if } t \text{ is even}
    \end{cases}
\end{eqnarray*}
We have that
\begin{eqnarray*}
    &&C^*_{2,T} = \sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2 = \sum_{t=2}^T\norm{\yb}^2 = \Theta(T).\\
    &&V_T = \sum_{t=2}^T\sup_{\xb\in\Xc}|f_t(\xb)-f_{t-1}(\xb)| = \sum_{t=2}^T\sup_{\xb\in\Xc}\bigg|\frac{2\xb^\top \yb + \yb^\top \yb}{t}\bigg|\leq O(\log T).
\end{eqnarray*}
We can see that $V_T$ is considerably smaller than $C^*_{2,T}$ in this scenario. With these two examples, it can be seen that if the regret bound only uses one regularity, it is possible that the resulting bound is not tight.

\section{Discussion for Constrained Setups}
In this section, we present that for OPGD and OMGD, if the function domain is assumed to be constrained, similar theoretical results can be achieved. From the aspect of the learning process, since the domain set is constrained, the projection step needs to be added (see algorithms \ref{alg:OPGD(constrained)} \& \ref{alg:OMGD(constrained)}). Note that $\Pi_{\Xc}(\yb) = \argmin_{\xb\in\Xc}\norm{\yb-\xb}$ and $\Pi_{\Xc}^{\Ab}(\yb) = \argmin_{\xb\in\Xc}\norm{\yb-\xb}_{\Ab}$, where $\norm{\xb}_{\Ab} = \sqrt{\xb^\top \Ab \xb}$ for a positive-definite matrix $\Ab$.

\begin{algorithm}[ht]
   \caption{Online Preconditioned Gradient Descent (OPGD) for Constrained Setups}
   \label{alg:OPGD(constrained)}
\begin{algorithmic}[1]
   \STATE {\bfseries Require:} Initial vector $\xb_1\in \Xc$, step size $\eta$, a sequence of positive definite matrices $\Ab_t$

   \FOR{$t=1,2,\ldots,T$}
   \STATE Play $\xb_t$
   \STATE Observe the gradient of the current action $\nabla f_t(\xb_t)$
   \STATE $\xb_{t+1} = \Pi_{\Xc}^{\Ab_t}\bigg(\xb_t - \eta\Ab^{-1}_t\nabla f_t(\xb_t)\bigg)$
   \ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{theorem}\label{T: Improved OPGD dynamic bound (constrained)} (The constrained version of Theorem \ref{T: Improved OPGD dynamic bound}) Suppose that for any $t\in [T]$:
\begin{enumerate}
    \item The function $f_t:\Xc\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth over $\Xc$.
    \item The preconditioning matrix $\Ab_t$ satisfies $\lambda^\prime\cdot \Ib\preceq \Ab_t \preceq \lambda \cdot \Ib.$
    \item The condition number satisfies $\frac{\lambda}{\lambda\prime} < 1+\frac{\mu^2}{4L^2}.$
\end{enumerate}
If we set $\eta=\frac{\lambda^\prime\mu}{2L^2}$, the dynamic regret for the sequence of actions $\xb_t$ generated by OPGD is bounded as follows
\begin{eqnarray*}
\mathbf{Reg}^d_T&\leq& \left(\frac{L^2}{\mu}\right)\left(\frac{4L^2\lambda-\mu^2\lambda^\prime}{\mu^2\lambda^\prime - 4L^2\lambda + 4L^2\lambda^\prime}\right)\sum_{t=2}^{T+1} \norm{\xb_t^* - \xb_{t-1}^*}^2 + \left(\frac{L^2\lambda}{\lambda^\prime\mu} - \frac{\mu}{4}\right)\norm{\xb_1 - \xb_1^*}^2\\&+&\frac{\mu D}{2L}\sum_{t=1}^T\norm{\nabla f_t(\xb^*_t)},
\end{eqnarray*}
where $D=\max_{\xb,\yb\in\Xc}\norm{\xb-\yb}$.
\end{theorem}

\begin{theorem}\label{T:Online multiple gradient (constrained)}
Suppose that for any $t\in [T]$, the function $f_t:\Xc\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth.
For any $0<\eta\leq \frac{1}{L}$, the dynamic regret of OMGD is bounded as follows
\begin{equation}\label{eq: Bound of Multiple GD (constrained)}
    \mathbf{Reg}^d_T\leq \min \begin{cases} (f_1(\xb_1)-f_1(\xb^*_1)) + 2V_T + \frac{\pi^2 D^2L}{12} + D\sum_{t=2}^T\norm{\nabla f_{t-1}(\xb^*_{t-1})}\\
    \frac{L}{2}\big[\norm{\xb_1 - \xb^*_1}^2 + 2D^2(\frac{\pi^2}{6}) + 2C^*_{2,T}\big]+ D\sum_{t=1}^T\norm{\nabla f_t (\xb^*_t)}
    \end{cases},
\end{equation}
where $D\triangleq \max_{\xb,\yb\in\Xc}\norm{\xb-\yb}$.
\end{theorem}

For Theorems \ref{T: Improved OPGD dynamic bound (constrained)} \& \ref{T:Online multiple gradient (constrained)}, if $\xb^*_t$ is located in the relative interior of $\Xc$ (i.e., $\nabla f_t(\xb^*_t)=0$) for any $t\in [T]$, the theoretical results of the unconstrained case can be recovered.

\begin{algorithm}[ht]
   \caption{Online Multiple Gradient Descent (OMGD) \citep{zhang2017improved} for Constrained Setups}
   \label{alg:OMGD(constrained)}
\begin{algorithmic}[1]
   \STATE {\bfseries Require:} Initial vector $\xb_1\in \Xc$, step size $\eta$, function parameters $\mu$ and $L$.
   \FOR{$t=1,2,\ldots,T$}
   \STATE Play $\xb_t$
   \STATE Receive the information of $f_t$
   \STATE Let $\zb_{t+1}^{(0)}=\xb_t$ and $K_t=\lceil \frac{-2\log(t)}{\log(1-\frac{2\mu}{1/\eta+\mu})} \rceil$
        \FOR{$j=1,2,\ldots,K_t$}
        \STATE $\zb_{t+1}^{(j)} = \Pi_{\Xc}\bigg(\zb_{t+1}^{(j-1)} - \eta\nabla f_t(\zb_{t+1}^{(j-1)})\bigg)$
        \ENDFOR
   \STATE $\xb_{t+1} = \zb_{t+1}^{(K_t)}$
   \ENDFOR
\end{algorithmic}
\end{algorithm}

\section{Concluding Remarks}
In this paper, we analyzed the dynamic regret for unconstrained online optimization, where the function sequence is strongly convex and smooth. We first proposed online preconditioned gradient descent (OPGD), which achieves the optimal regret bound of $O(C^*_{2,T})$ with one gradient query per round. Next, we developed optimistic online Newton (OON) method, which uses predictions of Hessians and gradients in the update process. We proved a (local) dynamic regret bound scaling as $O(D^\prime_T+C^*_{4,T})$, where $D^\prime_T$ measures the dissimilarity between the predicted information and the true information. If $D^\prime_T$ is small, this algorithm provides an improvement over the regret rate of $O(C^*_{2,T})$. We further verified that a conservative learner, that uses stale (previous round) information, always incurs a regret that is no worse than $O(C^*_{2,T})$, recovering the optimal worst-case. We finally revisited the online multiple gradient descent (OMGD) algorithm of \citep{zhang2017improved} and provided complementary analysis that shows the regret rate of $O(\min\{V_T, C^*_{2,T}\})$ for OMGD. The main benefit of the bound is that $V_T$ and $C_{2,T}^*$ are not comparable, and including $V_T$ in the regret bound can only make it tighter.

Our results mainly provide the following insight about dynamic online learning. It is unlikely that the smoothness assumption alone can provide improved regret rates over convex setting. This is in contrast to classical optimization that deals with {\it time-invariant} functions, where smoothness does provide faster convergence rates for optimization algorithms (e.g., gradient descent). In dynamic online setting, to decide on action $\xb_t$, the learner can only use the information of $\{f_s\}_{s=1}^{t-1}$; however, the consequence of this action is evaluated at $f_t$. Hence, the adversary can always change the function sequence drastically so that the learner suffers a large loss. Therefore, the assumption of strong convexity comes to rescue by translating the closeness of objective values to the closeness of actions. As a result, with smoothness and strong convexity together, dynamic regret bounds can be considerably better than the convex case. Given the improvement of OON over OGD when the predictable sequence is accurate enough, it would be interesting to see whether we can leverage predicted higher-order information to further improve the dynamic regret bound.

\newpage

\section{Appendix}

\begin{proof}[\textbf{Proof of Theorem \ref{T: Improved OPGD dynamic bound}}]
Recall the update rule of Algorithm \ref{alg:OPGD}: $\xb_{t+1} = \xb_t - \eta\Ab_t^{-1}\nabla f_t(\xb_t)$. Subtracting $\xb_t^*$ on both sides and computing the norm induced by $\Ab_t$, we get
\begin{equation}\label{eq:OPGD proof eq1}
\begin{gathered}
    (\xb_{t+1} - \xb_t^*)^\top\Ab_t(\xb_{t+1} - \xb_t^*) = \\ (\xb_{t} - \xb_t^*)^\top\Ab_t(\xb_{t} - \xb_t^*) - 2\eta\nabla f_t(\xb_t)^\top(\xb_{t} - \xb_t^*) + \eta^2\nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t).
\end{gathered}
\end{equation}
Dividing both sides by $2\eta$ and rearranging the equation, we get
\begin{equation}\label{eq:OPGD proof eq2}
\begin{gathered}
    \nabla f_t(\xb_t)^\top(\xb_{t} - \xb_t^*) = \\
     \frac{\eta}{2}\nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t) + \frac{1}{2\eta}(\xb_{t} - \xb_t^*)^\top\Ab_t(\xb_{t} - \xb_t^*) - \frac{1}{2\eta}(\xb_{t+1} - \xb_t^*)^\top\Ab_t(\xb_{t+1} - \xb_t^*).
\end{gathered}
\end{equation}

Due to $\lambda^\prime\cdot \Ib \preceq \Ab_t \preceq \lambda\cdot\Ib$, we have
\begin{equation}\label{eq:OPGD proof eq3}
    \frac{1}{2\eta}(\xb_{t} - \xb_t^*)^\top\Ab_t(\xb_{t} - \xb_t^*)\leq \frac{\lambda}{2\eta} \norm{\xb_{t} - \xb_t^*}^2.
\end{equation}

On the other hand,
\begin{eqnarray*}
    \norm{\xb_{t+1} - \xb^*_t}^2_{\Ab_t}&\geq&\lambda^\prime\norm{\xb_{t+1}-\xb^*_t}^2 \nonumber\\
    &\geq&\lambda^\prime(\norm{\xb_{t+1} - \xb^*_{t+1}}-\norm{\xb^*_{t+1} - \xb^*_{t}})^2 \nonumber\\
    &=&\lambda^\prime\bigg(\norm{\xb_{t+1} - \xb^*_{t+1}}^2-2\norm{\xb_{t+1} - \xb^*_{t+1}}\norm{\xb^*_{t+1} - \xb^*_{t}} + \norm{\xb^*_{t+1} - \xb^*_{t}}^2\bigg)\nonumber\\
    &\geq& \lambda^\prime\bigg[(1-c)\norm{\xb_{t+1} - \xb^*_{t+1}}^2 + (1-\frac{1}{c})\norm{\xb^*_{t+1} - \xb^*_{t}}^2\bigg],
\end{eqnarray*}
where the second inequality comes from the triangle inequality, and the third inequality comes from the fact that $2ab\leq ca^2 + \frac{1}{c}b^2,\quad \forall c>0$. Based on the result above, we have
\begin{equation}\label{eq:OPGD proof eq4}
    - \frac{1}{2\eta}(\xb_{t+1} - \xb_t^*)^\top\Ab_t(\xb_{t+1} - \xb_t^*)\leq - \frac{\lambda^\prime}{2\eta}\bigg[(1-c)\norm{\xb_{t+1} - \xb^*_{t+1}}^2 + (1-\frac{1}{c})\norm{\xb^*_{t+1} - \xb^*_{t}}^2\bigg].
\end{equation}\\
Combining \eqref{eq:OPGD proof eq2}, \eqref{eq:OPGD proof eq3} and \eqref{eq:OPGD proof eq4}, we get
\begin{equation}\label{eq:OPGD proof eq5}
\begin{split}
    \nabla f_t(\xb_t)^\top(\xb_{t} - \xb_t^*)&\leq \frac{\eta}{2}\nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t) + \frac{\lambda}{2\eta} \norm{\xb_{t} - \xb_t^*}^2\\ &- \frac{\lambda^\prime}{2\eta}\bigg[(1-c)\norm{\xb_{t+1} - \xb^*_{t+1}}^2 + (1-\frac{1}{c})\norm{\xb^*_{t+1} - \xb^*_{t}}^2\bigg].
\end{split}
\end{equation}
Summing \eqref{eq:OPGD proof eq5} over $t\in [T]$, we get
\begin{equation}\label{eq:OPGD proof eq6}
\begin{split}
    \sum_{t=1}^T\nabla f_t(\xb_t)^\top (\xb_t - \xb_t^*)&\leq \frac{\eta}{2}\sum_{t=1}^T \nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t) + \frac{1}{2\eta}(\lambda-\lambda^\prime(1-c))\sum^T_{t=1}\norm{\xb_t - \xb_t^*}^2\\ &+ \frac{\lambda^\prime}{2\eta}(\frac{1}{c}-1)\sum^T_{t=1}\norm{\xb_{t+1}^* - \xb_t^*}^2 + \frac{\lambda^\prime(1-c)}{2\eta}\norm{\xb_1-\xb_1^*}^2\\&-\frac{\lambda^\prime(1-c)}{2\eta}\norm{\xb_{T+1} - \xb_{T+1}^*}^2.
\end{split}
\end{equation}
By making $c\in (0,1)$, the term $\frac{\lambda^\prime(1-c)}{2\eta}\norm{\xb_{T+1} - \xb_{T+1}^*}^2$ can be dropped from \eqref{eq:OPGD proof eq6}.

As the functions are assumed to be unconstrained, the gradient at the minimizer is zero, and\\ $\nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t)$ can be bounded using $L$-smoothness as follows
\begin{eqnarray*}
    \nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t) &=& (\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))^\top\Ab_t^{-1}(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))\\

    &\leq&\frac{L^2}{\lambda^\prime}\norm{\xb_t-\xb_t^*}^2.
\end{eqnarray*}
Substituting above into \eqref{eq:OPGD proof eq6} and rearranging it, we get
\begin{equation}\label{eq:OPGD proof eq7}
\begin{split}
    &\sum_{t=1}^T\nabla f_t(\xb_t)^\top (\xb_t - \xb_t^*)
    -\bigg[\frac{\lambda-\lambda^\prime(1-c)}{2\eta}+\frac{\eta L^2}{2\lambda^\prime}\bigg]\sum_{t=1}^T\norm{\xb_t-\xb_t^*}^2\\\leq &\frac{\lambda^\prime}{2\eta}(\frac{1}{c}-1)\sum^T_{t=1}\norm{\xb_{t+1}^* - \xb_t^*}^2 + \frac{\lambda^\prime(1-c)}{2\eta}\norm{\xb_1-\xb_1^*}^2.
\end{split}
\end{equation}
Based on the assumption of strong convexity, we have the following relationship
$$\mathbf{Reg}^d_T=\sum_{t=1}^Tf_t(\xb_t)-f_t(\xb_t^*)\leq\sum_{t=1}^T\nabla f_t(\xb_t)^\top (\xb_t-\xb_t^*)-\frac{\mu}{2}\norm{\xb_t-\xb_t^*}^2.$$
Therefore, in view of \eqref{eq:OPGD proof eq7}, if
\begin{equation}\label{eq:OPGD proof eq8}
    \bigg[\frac{\lambda-\lambda^\prime(1-c)}{\eta}+\frac{\eta L^2}{\lambda^\prime}\bigg]\leq \mu,
\end{equation}
then $\mathbf{Reg}^d_T\leq \frac{\lambda^\prime}{2\eta}(\frac{1}{c}-1)\sum^T_{t=1}\norm{\xb_{t+1}^* - \xb_t^*}^2 + \frac{\lambda^\prime(1-c)}{2\eta}\norm{\xb_1-\xb_1^*}^2$.\\\\
Optimizing the left hand side of \eqref{eq:OPGD proof eq8} over $\eta$, we have the following relation
$$
\sqrt{\lambda-\lambda^\prime(1-c)} \leq \frac{\mu}{2L}\sqrt{\lambda^\prime}
$$
for $\eta=\frac{\sqrt{\lambda\lambda^\prime-{\lambda^\prime}^2(1-c)}}{L}$.

By setting $c = \frac{\mu^2}{4L^2}-\frac{\lambda}{\lambda^\prime}+1$, the inequality above holds, and $\eta = \frac{\mu\lambda^\prime}{2L^2}$. Note that the choice of $c$ satisfies the constraint $c\in (0,1)$ as $\frac{\lambda}{\lambda^\prime}<\frac{\mu^2}{4L^2}+1$ by assumption.

By substituting expressions of $c$ and $\eta$ into \eqref{eq:OPGD proof eq7}, the theorem is proved.
\end{proof}

In order to prove Theorem \ref{T:Online Newton dynamic bound}, we need the following two lemmas.\\

\begin{lemma}\label{L:Online Newton quadratic convergence}
Suppose the assumptions of Theorem \ref{T:Online Newton dynamic bound} hold. Then, we have the following inequality
\begin{equation}\label{eq: quadratic convergence}
\norm{\hat{\xb}_{t+1} - \xb_{t+1}^*}\leq \frac{L_H}{2\mu}\norm{\hat{\xb}_{t} - \xb_{t+1}^*}^2,
\end{equation}
for $t=0,\ldots,T$.
\begin{proof}
The proof closely follows the local quadratic convergence of Newton method. Consider step 5 of Algorithm \ref{alg:OON}. By subtracting $\xb_{t+1}^*$ on both sides, we get
    \begin{eqnarray*}
        \hat{\xb}_{t+1} - \xb_{t+1}^* &=& \hat{\xb}_{t} - \xb_{t+1}^* - \Hb_{t+1}^{-1}(\hat{\xb}_{t})\nabla f_{t+1}(\hat{\xb}_{t})\\
        &=& \hat{\xb}_{t} - \xb_{t+1}^* + \Hb_{t+1}^{-1}(\hat{\xb}_{t})(\nabla f_{t+1}(\xb_{t+1}^*)-\nabla f_{t+1}(\hat{\xb}_{t})).\\
    \end{eqnarray*}
    The equation above can be written as
    \begin{eqnarray*}
        \hat{\xb}_{t+1} - \xb_{t+1}^* &=& \hat{\xb}_{t} - \xb_{t+1}^* + \Hb_{t+1}^{-1}(\hat{\xb}_{t})\int_0^1 \Hb_{t+1}(\hat{\xb}_{t} + \tau (\xb^*_{t+1}-\hat{\xb}_{t}))(\xb^*_{t+1}-\hat{\xb}_{t})d\tau\\
        &=& \Hb_{t+1}^{-1}(\hat{\xb}_{t})\Hb_{t+1}(\hat{\xb}_{t})(\hat{\xb}_{t} - \xb_{t+1}^*)\\
        &+& \Hb_{t+1}^{-1}(\hat{\xb}_{t})\int_0^1 \Hb_{t+1}(\hat{\xb}_{t} + \tau (\xb^*_{t+1}-\hat{\xb}_{t}))(\xb^*_{t+1}-\hat{\xb}_{t})d\tau\\
        &=& \Hb_{t+1}^{-1}(\hat{\xb}_{t})\int_0^1 \Big[\Hb_{t+1}(\hat{\xb}_{t} + \tau (\xb^*_{t+1}-\hat{\xb}_{t})) - \Hb_{t+1}(\hat{\xb}_{t})\Big]\Big(\xb^*_{t+1}-\hat{\xb}_{t}\Big)d\tau.
    \end{eqnarray*}
    By computing the norms of both sides, we get
    \begin{eqnarray*}
        \norm{\hat{\xb}_{t+1} - \xb_{t+1}^*} &=& \norm{\Hb_{t+1}^{-1}(\hat{\xb}_{t})\int_0^1 \Big[\Hb_{t+1}(\hat{\xb}_{t} + \tau (\xb^*_{t+1}-\hat{\xb}_{t})) - \Hb_{t+1}(\hat{\xb}_{t})\Big]\Big(\xb^*_{t+1}-\hat{\xb}_{t}\Big)d\tau}\\
        &\leq& \norm{\Hb_{t+1}^{-1}(\hat{\xb}_{t})} \int_0^1 \norm{\Hb_{t+1}(\hat{\xb}_{t} + \tau (\xb^*_{t+1}-\hat{\xb}_{t})) - \Hb_{t+1}(\hat{\xb}_{t})}\norm{\xb^*_{t+1}-\hat{\xb}_{t}}d\tau\\
        &\leq& \norm{\Hb_{t+1}^{-1}(\hat{\xb}_{t})} \int_0^1 \tau L_H\norm{\hat{\xb}_{t}-\xb_{t+1}^*}^2d\tau\\
        &\leq& \frac{L_H}{2\mu}\norm{\hat{\xb}_{t}-\xb_{t+1}^*}^2,
    \end{eqnarray*}
    where the second inequality comes from the Lipschitz continuity in Hessian and the third inequality comes from strong convexity.
\end{proof}
\end{lemma}

The following result is close to Lemma 3 of \citep{lesage2020second}, but since our update is slightly different, we provide the proof for completeness.

\begin{lemma}\label{L:Boundness of distance to the minimizer}
Suppose the assumptions of Theorem \ref{T:Online Newton dynamic bound} holds. Then, we have the following inequality
\begin{equation}\label{eq: boundness}
    \norm{\hat{\xb}_{t} - \xb_{t+1}^*}\leq \frac{\mu}{L_H},
\end{equation}
for $t=0,\ldots,T$.
\begin{proof}
The proof is by induction. When $t=0$, we have $\norm{\hat{\xb}_{0} - \xb_{1}^*} = \norm{\xb_1-\xb_1^*}\leq \frac{\mu}{L_H}$. Suppose $\norm{\hat{\xb}_{t} - \xb_{t+1}^*}\leq \frac{\mu}{L_H}$ holds. Now for the case $t+1$, we have the following relation
    \begin{eqnarray*}
        \norm{\hat{\xb}_{t+1} - \xb_{t+2}^*} &\leq& \norm{\hat{\xb}_{t+1} - \xb_{t+1}^*} + \norm{\xb_{t+1}^* - \xb_{t+2}^*}\\
        &\leq& \frac{L_H}{2\mu}\norm{\hat{\xb}_{t} - \xb_{t+1}^*}^2 + \bar{c}\\
        &\leq& \frac{L_H}{2\mu}\left(\frac{\mu}{L_H}\right)^2 + \frac{\mu}{2L_H}\\
        &=&\frac{\mu}{L_H},
    \end{eqnarray*}
    where the second inequality comes from Lemma \ref{L:Online Newton quadratic convergence}.
\end{proof}
\end{lemma}

\begin{proof}[\textbf{Proof of Theorem \ref{T:Online Newton dynamic bound}}]

First, we bound the term $\norm{\hat{\xb}_{t+1} - \xb_{t+1}^*}$ as follows
\begin{eqnarray*}
    \norm{\hat{\xb}_{t+1} - \xb_{t+1}^*} &\leq& \frac{L_H}{2\mu}\norm{\hat{\xb}_{t} - \xb_{t+1}^*}^2\\
    &\leq& \frac{L_H}{2\mu} \bigg[(1+c_1)\norm{\hat{\xb}_{t} - \xb_{t}^*}^2 + \left(1+\frac{1}{c_1}\right)\norm{\xb_{t}^* - \xb_{t+1}^*}^2\bigg]\\
    &\leq& \frac{1}{4}(1+c_1)\norm{\hat{\xb}_{t} - \xb_{t}^*} + \frac{L_H}{2\mu}\left(1+\frac{1}{c_1}\right)\norm{\xb_{t}^* - \xb_{t+1}^*}^2.
\end{eqnarray*}
The first inequality is based on equation \eqref{eq: quadratic convergence}; the second inequality is based on the fact that $(a+b)^2\leq (1+c)a^2 + (1+\frac{1}{c})b^2,\quad \forall c>0$, and the third inequality is based on the fact that combining \eqref{eq: quadratic convergence} and \eqref{eq: boundness}, we can get $\norm{\hat{\xb}_t - \xb^*_t}\leq \frac{\mu}{2L_H}$.\\\\
Applying the inequality $(a+b)^2\leq (1+c)a^2 + (1+\frac{1}{c})b^2,\quad \forall c>0$ to the above inequality again, we can find {\small
\begin{equation}\label{quartic bound 1}
    \begin{split}
    \norm{\hat{\xb}_{t+1} - \xb_{t+1}^*}^2 &\leq \bigg[ \frac{1}{4}(1+c_1)\norm{\hat{\xb}_{t} - \xb_{t}^*} + \frac{L_H}{2\mu}\left(1+\frac{1}{c_1}\right)\norm{\xb_{t}^* - \xb_{t+1}^*}^2\bigg]^2\\
    &\leq \frac{1}{16}(1+c_1)^2(1+c_2)\norm{\hat{\xb}_{t} - \xb_{t}^*}^2 + \left(\frac{L_H}{2\mu}\right)^2\left(1+\frac{1}{c_1}\right)^2\left(1+\frac{1}{c_2}\right)\norm{\xb_{t}^* - \xb_{t+1}^*}^4.
    \end{split}
\end{equation}}
Let $\rho^\prime\triangleq\frac{1}{16}(1+c_1)^2(1+c_2)$ and $\rho^{\prime\prime}\triangleq(\frac{L_H}{2\mu})^2(1+\frac{1}{c_1})^2(1+\frac{1}{c_2})$.\\\\
Summing the term $\norm{\hat{\xb}_{t+1} - \xb_{t+1}^*}^2$ over $t$, based on \eqref{quartic bound 1}, we get
\begin{eqnarray*}
    \sum_{t=1}^T\norm{\hat{\xb}_t - \xb_t^*}^2&\leq& \norm{\hat{\xb}_1 - \xb_1^*}^2 + \rho^\prime\sum_{t=1}^{T-1}\norm{\hat{\xb}_t - \xb_t^*}^2 + \rho^{\prime\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4.
\end{eqnarray*}
Adding and subtracting $\rho^\prime\norm{\hat{\xb}_T - \xb_T}^2$ to the right hand side, we get
\begin{equation}\label{eq: quartic bound 2}
    \sum_{t=1}^T\norm{\hat{\xb}_t - \xb_t^*}^2\leq \norm{\hat{\xb}_1 - \xb_1^*}^2 -\rho^\prime\norm{\hat{\xb}_T - \xb_T}^2 + \rho^\prime\sum_{t=1}^{T}\norm{\hat{\xb}_t - \xb_t^*}^2 + \rho^{\prime\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4.
\end{equation}
Choosing any $c_1,c_2>0$ such that $\rho^\prime<1$, we can regroup \eqref{eq: quartic bound 2} to derive
\begin{equation}\label{eq: quartic bound 3}
    \sum_{t=1}^T\norm{\hat{\xb}_t - \xb_t^*}^2\leq \frac{\norm{\hat{\xb}_1 - \xb_1^*}^2 -\rho^\prime\norm{\hat{\xb}_T - \xb_T}^2}{1-\rho\prime} + \frac{\rho^{\prime\prime}}{1-\rho^\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4.
\end{equation}
Now let us return to the loss difference $f_t(\xb_t) - f_t(\xb_t^*)$. Based on the assumption of smoothness, we have
\begin{eqnarray*}
f_t(\xb_t) - f_t(\xb_t^*) \leq \frac{L}{2}\norm{\xb_t - \xb_t^*}^2.
\end{eqnarray*}
Summing the above inequality over $t\in [T]$, we get
\begin{equation}\label{eq: quartic bound 4}
    \begin{split}
    \mathbf{Reg}^d_T &= \sum_{t=1}^T f_t(\xb_t) - f_t(\xb_t^*)\\
    &\leq \frac{L}{2}\sum_{t=1}^T\norm{\xb_t - \xb_t^*}^2\\
    &\leq \frac{L}{2}\sum_{t=1}^T (2\norm{\xb_t-\hat{\xb}_t}^2 + 2\norm{\hat{\xb}_t - \xb_t^*}^2)\\
    &\leq L\sum_{t=1}^T\norm{\xb_t-\hat{\xb}_t}^2 + L\bigg(\frac{\norm{\hat{\xb}_1 - \xb_1^*}^2 -\rho^\prime\norm{\hat{\xb}_T - \xb_T}^2}{1-\rho\prime} + \frac{\rho^{\prime\prime}}{1-\rho^\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4\bigg)\\
    &=L\bigg(\frac{\norm{\hat{\xb}_1 - \xb_1^*}^2 -\rho^\prime\norm{\hat{\xb}_T - \xb_T}^2}{1-\rho\prime} + \frac{\rho^{\prime\prime}}{1-\rho^\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4\bigg)\\
    &+ L\norm{\Hb_{1}^{-1}(\hat{\xb}_{0})\nabla f_1(\hat{\xb}_{0})}^2 +L\sum_{t=2}^T \norm{\Mb_t^{-1}(\hat{\xb}_{t-1})\mb_t(\hat{\xb}_{t-1})-\Hb_{t}^{-1}(\hat{\xb}_{t-1})\nabla f_t(\hat{\xb}_{t-1})}^2,
    \end{split}
\end{equation}
where we used \eqref{eq: quartic bound 3} as well as steps 5-6 of Algorithm \ref{alg:OON}.
\end{proof}
\begin{proof}[\textbf{Proof of Corollary \ref{Corollary: Optimistic online Newton stale information}}]
Based on \eqref{eq: quartic bound 4}, we have that
\begin{equation}\label{eq: quartic bound 5}
\begin{split}
    \mathbf{Reg}^d_T &\leq L\bigg(\frac{\norm{\hat{\xb}_1 - \xb_1^*}^2 -\rho^\prime\norm{\hat{\xb}_T - \xb_T}^2}{1-\rho\prime} + \frac{\rho^{\prime\prime}}{1-\rho^\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4\bigg)\\
    &+ L\norm{\Hb_{1}^{-1}(\hat{\xb}_{0})\nabla f_1(\hat{\xb}_{0})}^2 +L\sum_{t=2}^T \norm{\Mb_t^{-1}(\hat{\xb}_{t-1})\mb_t(\hat{\xb}_{t-1})-\Hb_{t}^{-1}(\hat{\xb}_{t-1})\nabla f_t(\hat{\xb}_{t-1})}^2.
\end{split}
\end{equation}
For last term, by replacing $(\Mb_t,\mb_t)$ with $(\Hb_{t-1}, \nabla f_{t-1})$, we obtain
\begin{equation}\label{eq: quartic bound 6}
\begin{split}
    &\norm{\Mb_t^{-1}(\hat{\xb}_{t-1})\mb_t(\hat{\xb}_{t-1})-\Hb_{t}^{-1}(\hat{\xb}_{t-1})\nabla f_t(\hat{\xb}_{t-1})}^2\\ = &\norm{\Hb_{t-1}^{-1}(\hat{\xb}_{t-1})\nabla f_{t-1}(\hat{\xb}_{t-1})-\Hb_{t}^{-1}(\hat{\xb}_{t-1})\nabla f_t(\hat{\xb}_{t-1})}^2\\
    =&\norm{\Hb_{t-1}^{-1}(\hat{\xb}_{t-1})\big(\nabla f_{t-1}(\hat{\xb}_{t-1})-\nabla f_{t-1}(\xb^*_{t-1})\big)-\Hb_{t}^{-1}(\hat{\xb}_{t-1})\big(\nabla f_t(\hat{\xb}_{t-1})-\nabla f_t(\xb^*_{t})\big)}^2\\
    \leq &2\norm{\Hb_{t-1}^{-1}(\hat{\xb}_{t-1})\big(\nabla f_{t-1}(\hat{\xb}_{t-1})-\nabla f_{t-1}(\xb^*_{t-1})\big)}^2 + 2\norm{\Hb_{t}^{-1}(\hat{\xb}_{t-1})\big(\nabla f_t(\hat{\xb}_{t-1})-\nabla f_t(\xb^*_{t})\big)}^2\\
    \leq &\frac{2L^2}{\mu^2}\big(\norm{\hat{\xb}_{t-1} - \xb^*_{t-1}}^2+\norm{\hat{\xb}_{t-1} - \xb^*_{t}}^2\big)\\
    \leq &\frac{2L^2}{\mu^2}\norm{\hat{\xb}_{t-1} - \xb^*_{t-1}}^2 + \frac{4L^2}{\mu^2}\norm{\hat{\xb}_{t-1} - \xb^*_{t-1}}^2 + \frac{4L^2}{\mu^2}\norm{\xb^*_t - \xb^*_{t-1}}^2\\
    =&\frac{6L^2}{\mu^2}\norm{\hat{\xb}_{t-1} - \xb^*_{t-1}}^2 + \frac{4L^2}{\mu^2}\norm{\xb^*_t - \xb^*_{t-1}}^2,
\end{split}
\end{equation}
where the second inequality comes from strong convexity and smoothness.\\\\
Summing \eqref{eq: quartic bound 6} over $t=2,\ldots,T$, we get
\begin{equation}\label{eq: quartic bound 7}
\begin{split}
    &\sum_{t=2}^T\norm{\Mb_t^{-1}(\hat{\xb}_{t-1})\mb_t(\hat{\xb}_{t-1})-\Hb_{t}^{-1}(\hat{\xb}_{t-1})\nabla f_t(\hat{\xb}_{t-1})}^2\\
    \leq &\frac{6L^2}{\mu^2}\sum_{t=1}^{T-1}\norm{\hat{\xb}_t-\xb^*_t}^2 + \frac{4L^2}{\mu^2}\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2\\
    \leq &\frac{6L^2}{\mu^2}\bigg(\frac{\norm{\hat{\xb}_1 - \xb_1^*}^2 -\rho^\prime\norm{\hat{\xb}_T - \xb_T}^2}{1-\rho\prime} + \frac{\rho^{\prime\prime}}{1-\rho^\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4\bigg) + \frac{4L^2}{\mu^2}\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2,
\end{split}
\end{equation}
where the second inequality comes from \eqref{eq: quartic bound 3}.\\\\
Substituting \eqref{eq: quartic bound 7} into \eqref{eq: quartic bound 5}, we have
\begin{equation}\label{eq: quartic bound 8}
\begin{split}
    \mathbf{Reg}^d_T &\leq \frac{6L^3+\mu^2  L}{\mu^2}\bigg(\frac{\norm{\hat{\xb}_1 - \xb^*_1}^2}{1-\rho^\prime} + \frac{\rho^{\prime\prime}}{1-\rho^\prime}\sum_{t=2}^{T}\norm{\xb_{t}^* - \xb_{t-1}^*}^4\bigg) + L\norm{\Hb_{1}^{-1}(\hat{\xb}_{0})\nabla f_1(\hat{\xb}_{0})}^2\\

    &+ \frac{4L^3}{\mu^2}\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2\\
    &=O(C^*_{2,T}),
\end{split}
\end{equation}
by noting that $\max_{t\in\{2,\ldots,T\}}\norm{\xb_t^* - \xb_{t-1}^*} \leq \frac{\mu}{2L_H}$.
\end{proof}

\begin{lemma}\label{L: Convergence of GD in iterates for strongly convex and smooth} (Theorem 2.1.14 in \citep{nesterov1998introductory})
Suppose that $f:\mathrm{R}^n\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth. Letting $\xb^*=\argmin_{\xb\in\mathrm{R}^n}f(\xb)$ and $\vb=\ub-\eta\nabla f(\ub)$, where $0<\eta\leq \frac{2}{\mu+L}$, then we have
$$\norm{\vb-\xb^*}^2\leq \big(1-\frac{2\eta\mu L}{\mu+L}\big)\norm{\ub-\xb^*}^2.$$

\end{lemma}

\begin{proof}[\textbf{Proof of Theorem \ref{T:Online multiple gradient}}]
Observe that
\begin{equation}\label{eq: OMGD proof eq1}
\begin{split}
    f_t(\xb_t) - f_t(\xb^*_t) &= \big(f_t(\xb_t) - f_{t-1}(\xb_t)\big)\\
    &+ \big(f_{t-1}(\xb_t) - f_{t-1}(\xb^*_{t-1})\big)\\
    &+ \big(f_{t-1}(\xb^*_{t-1}) - f_t(\xb^*_t)\big).
\end{split}
\end{equation}
For the right hand side of \eqref{eq: OMGD proof eq1}, the first term is bounded as the following
\begin{equation}\label{eq: OMGD proof eq2}
    f_t(\xb_t) - f_{t-1}(\xb_t)\leq \sup_{\xb\in \Xc}|f_t(\xb) - f_{t-1}(\xb)|,
\end{equation}
and since $\xb^*_{t-1}$ is the minimizer of $f_{t-1}$, we have
\begin{equation}\label{eq: OMGD proof eq3}
    f_{t-1}(\xb^*_{t-1}) - f_t(\xb^*_t) \leq f_{t-1}(\xb^*_{t}) - f_t(\xb^*_t) \leq \sup_{\xb\in \Xc}|f_t(\xb) - f_{t-1}(\xb)|,
\end{equation}
where $\Xc$ in \eqref{eq: OMGD proof eq2} and \eqref{eq: OMGD proof eq3} is defined as the convex hull of $\{\xb_t,\xb^*_t\}_{t=1}^T$.\\\\
Based on the update rule of Algorithm \ref{alg:OMGD} and Lemma \ref{L: Convergence of GD in iterates for strongly convex and smooth}, we have
\begin{equation}\label{eq: OMGD proof eq4}
    \norm{\xb_t - \xb^*_{t-1}}^2\leq \big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t} \norm{\xb_{t-1} - \xb^*_{t-1}}^2\leq \big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t} D^2,
\end{equation}
where $D\triangleq \max_{t=1,\ldots, T}\norm{\xb_t-\xb^*_t}$.\\\\
Then, for the second term of \eqref{eq: OMGD proof eq1}, based on smoothness and \eqref{eq: OMGD proof eq4}, we have
\begin{equation}\label{eq: OMGD proof eq5}
    f_{t-1}(\xb_t) - f_{t-1}(\xb^*_{t-1})\leq \frac{L}{2}\norm{\xb_t-\xb^*_{t-1}}^2\leq \frac{L}{2}\big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t} D^2,
\end{equation}

Combining \eqref{eq: OMGD proof eq2}, \eqref{eq: OMGD proof eq3} and \eqref{eq: OMGD proof eq5} with \eqref{eq: OMGD proof eq1} and summing over $t$, we have
\begin{equation}\label{eq: OMGD proof eq6}
\begin{split}
    \sum_{t=1}^T f_t(\xb_t)-f_t(\xb^*_t)&\leq (f_1(\xb_1)-f_1(\xb^*_1)) + 2\sum_{t=2}^T \sup_{\xb\in \Xc}|f_t(\xb) - f_{t-1}(\xb)|\\ &+ \sum_{t=2}^T\frac{D^2L}{2} \big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t}\\
    &\leq (f_1(\xb_1)-f_1(\xb^*_1)) + 2V_T + \frac{D^2L}{2}\sum_{t=2}^T\frac{1}{t^2}\\
    &\leq (f_1(\xb_1)-f_1(\xb^*_1)) + 2V_T + \frac{D^2L}{2}(\frac{\pi^2}{6})\\
    &= O(V_T + 1),
\end{split}
\end{equation}
where the second inequality holds since $t^2\big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t}\leq 1$ based on the choice of $K_t$.\\\\
On the other hand, from \eqref{eq: OMGD proof eq4} we have that
\begin{equation}\label{eq: OMGD proof eq7}
\begin{split}
    \norm{\xb_t - \xb^*_t}^2&\leq 2\norm{\xb_t - \xb^*_{t-1}}^2 + 2\norm{\xb^*_{t-1}-\xb^*_t}^2\\
    &\leq 2\big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t}\norm{\xb_{t-1} - \xb^*_{t-1}}^2 + 2\norm{\xb^*_{t-1}-\xb^*_t}^2\\
    &\leq 2\big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t} D^2 + 2\norm{\xb^*_{t-1}-\xb^*_t}^2.
\end{split}
\end{equation}
Summing \eqref{eq: OMGD proof eq7} over $t=2,\ldots,T$ and adding $\norm{\xb_1 - \xb^*_1}^2 $ to both sides, we have
\begin{equation}\label{eq: OMGD proof eq8}
\begin{split}
    \sum_{t=1}^T \norm{\xb_t - \xb^*_t}^2&\leq \norm{\xb_1 - \xb^*_1}^2 + 2D^2\sum_{t=2}^T\big(1-\frac{2\eta\mu L}{\mu+L}\big)^{K_t}  + 2\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2\\
    &\leq \norm{\xb_1 - \xb^*_1}^2 + 2D^2(\frac{\pi^2}{6}) + 2\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2.
\end{split}
\end{equation}
Based on smoothness and the fact that $\norm{\nabla f_t(\xb^*_t)}=0$, we know
$$\sum_{t=1}^T f_t(\xb_t) - f_t(\xb^*_t)\leq \sum_{t=1}^T\frac{L}{2}\norm{\xb_t-\xb^*_t}^2.$$
Substituting \eqref{eq: OMGD proof eq8} into the inequality above, we have
\begin{equation}\label{eq: OMGD proof eq9}
\begin{split}
    \sum_{t=1}^T f_t(\xb_t) - f_t(\xb^*_t)&\leq \sum_{t=1}^T\frac{L}{2}\norm{\xb_t-\xb^*_t}^2\\
    &\leq \frac{L}{2}\big[\norm{\xb_1 - \xb^*_1}^2 + 2D^2(\frac{\pi^2}{6}) + 2\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2\big]\\
    &= O(C^*_{2,T}+1).
\end{split}
\end{equation}
\end{proof}

\begin{proof}[\textbf{Proof of Theorem \ref{T: Improved OPGD dynamic bound (constrained)}}]
This proof mainly follows the proof for Theorem \ref{T: Improved OPGD dynamic bound}. Therefore, we would just point out some different steps here. Recall the update rule of Algorithm \ref{alg:OPGD(constrained)}: $\xb_{t+1} = \Pi_{\Xc}\bigg(\xb_t - \eta\Ab_t^{-1}\nabla f_t(\xb_t)\bigg)$. Letting $\yb_{t+1} = \xb_t - \eta\Ab_t^{-1}\nabla f_t(\xb_t)$, based on the Pythagorean theorem (see section 2.1.1 in \citep{hazan2019introduction}) and \eqref{eq:OPGD proof eq1}, we get
\begin{equation}\label{eq:OPGD (constrained) proof eq1}
\begin{gathered}
    (\xb_{t+1} - \xb_t^*)^\top\Ab_t(\xb_{t+1} - \xb_t^*) \leq (\yb_{t+1} - \xb_t^*)^\top\Ab_t(\yb_{t+1} - \xb_t^*) = \\ (\xb_{t} - \xb_t^*)^\top\Ab_t(\xb_{t} - \xb_t^*) - 2\eta\nabla f_t(\xb_t)^\top(\xb_{t} - \xb_t^*) + \eta^2\nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t).
\end{gathered}
\end{equation}

Following the same steps in the proof of Theorem \ref{T: Improved OPGD dynamic bound}, we get the inequality like \eqref{eq:OPGD proof eq6}
\begin{equation}\label{eq:OPGD (constrained) proof eq2}
\begin{split}
    \sum_{t=1}^T\nabla f_t(\xb_t)^\top (\xb_t - \xb_t^*)&\leq \frac{\eta}{2}\sum_{t=1}^T \nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t) + \frac{1}{2\eta}(\lambda-\lambda^\prime(1-c))\sum^T_{t=1}\norm{\xb_t - \xb_t^*}^2\\ &+ \frac{\lambda^\prime}{2\eta}(\frac{1}{c}-1)\sum^T_{t=1}\norm{\xb_{t+1}^* - \xb_t^*}^2 + \frac{\lambda^\prime(1-c)}{2\eta}\norm{\xb_1-\xb_1^*}^2.
\end{split}
\end{equation}

Now, using the $L$-smoothness, $\nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t)$ can be bounded as follows
\begin{eqnarray*}
    \nabla f_t(\xb_t)^\top\Ab_t^{-1}\nabla f_t(\xb_t) &=& (\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*)+\nabla f_t(\xb_t^*))^\top\Ab_t^{-1}(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*)+\nabla f_t(\xb_t^*))\\
    &=&(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))^\top\Ab_t^{-1}(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))\\
    &+& 2(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))^\top\Ab_t^{-1}\nabla f_t(\xb_t^*) - \nabla f_t(\xb_t^*)^\top\Ab_t^{-1}f_t(\xb_t^*)\\
    &\leq&(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))^\top\Ab_t^{-1}(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))\\
    &+& 2(\nabla f_t(\xb_t)-\nabla f_t(\xb_t^*))^\top\Ab_t^{-1}\nabla f_t(\xb_t^*)\\
    &\leq&\frac{L^2}{\lambda^\prime}\norm{\xb_t-\xb_t^*}^2 + \frac{2L}{\lambda^\prime}D\norm{\nabla f_t(\xb_t^*)},
\end{eqnarray*}
where $D=\max_{\xb,\yb\in\Xc}\norm{\xb-\yb}$.

Substituting above into \eqref{eq:OPGD (constrained) proof eq2} and rearranging it, we get
\begin{equation}\label{eq:OPGD (constrained) proof eq3}
\begin{split}
    &\sum_{t=1}^T\nabla f_t(\xb_t)^\top (\xb_t - \xb_t^*)
    -\bigg[\frac{\lambda-\lambda^\prime(1-c)}{2\eta}+\frac{\eta L^2}{2\lambda^\prime}\bigg]\sum_{t=1}^T\norm{\xb_t-\xb_t^*}^2\\\leq &\frac{\lambda^\prime}{2\eta}(\frac{1}{c}-1)\sum^T_{t=1}\norm{\xb_{t+1}^* - \xb_t^*}^2 + \frac{\lambda^\prime(1-c)}{2\eta}\norm{\xb_1-\xb_1^*}^2+\frac{\eta\lambda D}{\lambda^\prime}\sum_{t=1}^T\norm{\nabla f_t(\xb^*_t)}.
\end{split}
\end{equation}
Following the rest steps in the proof of Theorem \ref{T: Improved OPGD dynamic bound}, the theorem is proved.
\end{proof}

\begin{lemma}\label{L: Convergence of GD in iterates for strongly convex and smooth (constrained)} (Lemma 5 in \citep{zhang2017improved})
Suppose that $f:\Xc\to \mathrm{R}$ is $\mu$-strongly convex and $L$-smooth. Letting $\xb^*=\argmin_{\xb\in\Xc}f(\xb)$ and $\vb=\Pi_{\Xc}\bigg(\ub-\eta\nabla f(\ub)\bigg)$, where $0<\eta\leq \frac{1}{L}$, then we have
$$\norm{\vb-\xb^*}^2\leq \big(1-\frac{2\mu }{1/\eta+\mu}\big)\norm{\ub-\xb^*}^2.$$
\end{lemma}

\begin{proof}[\textbf{Proof of Theorem \ref{T:Online multiple gradient (constrained)}}]
This proof mainly follows the proof of Theorem \ref{T:Online multiple gradient}, so we would just point out some different steps here.\\
Instead of having \eqref{eq: OMGD proof eq4} and \eqref{eq: OMGD proof eq5}, we get the following two equations:\\
Based on the update rule of Algorithm \ref{alg:OMGD(constrained)} and Lemma \ref{L: Convergence of GD in iterates for strongly convex and smooth (constrained)}, we get
\begin{equation}\label{eq: OMGD (constrained) proof eq1}
    \norm{\xb_t - \xb^*_{t-1}}^2\leq \big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t} \norm{\xb_{t-1} - \xb^*_{t-1}}^2\leq \big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t} D^2,
\end{equation}
where $D\triangleq \max_{\xb,\yb\in\Xc}\norm{\xb-\yb}$.\\
Based on the $L$-smoothness and \eqref{eq: OMGD (constrained) proof eq1}, we have
\begin{equation}\label{eq: OMGD (constrained) proof eq2}
\begin{split}
    f_{t-1}(\xb_t) - f_{t-1}(\xb^*_{t-1})&\leq\nabla f_{t-1}(\xb^*_{t-1})^\top(\xb_t - \xb^*_{t-1})+ \frac{L}{2}\norm{\xb_t-\xb^*_{t-1}}^2\\
    &\leq\norm{\nabla f_{t-1}(\xb^*_{t-1})}D+ \frac{L}{2}\big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t} D^2.
\end{split}
\end{equation}
Following the corresponding proof steps for Theorem \ref{T:Online multiple gradient}, we have
\begin{equation}\label{eq: OMGD (constrained) proof eq3}
\begin{split}
    \sum_{t=1}^T f_t(\xb_t)-f_t(\xb^*_t)&\leq (f_1(\xb_1)-f_1(\xb^*_1)) + 2\sum_{t=2}^T \sup_{\xb\in \Xc}|f_t(\xb) - f_{t-1}(\xb)|\\ &+ \sum_{t=2}^T\frac{D^2L}{2} \big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t} + D\sum_{t=2}^T\norm{\nabla f_{t-1}(\xb^*_{t-1})}\\
    &\leq (f_1(\xb_1)-f_1(\xb^*_1)) + 2V_T + \frac{D^2L}{2}\sum_{t=2}^T\frac{1}{t^2} + D\sum_{t=2}^T\norm{\nabla f_{t-1}(\xb^*_{t-1})}\\
    &\leq (f_1(\xb_1)-f_1(\xb^*_1)) + 2V_T + \frac{D^2L}{2}(\frac{\pi^2}{6}) + D\sum_{t=2}^T\norm{\nabla f_{t-1}(\xb^*_{t-1})},
\end{split}
\end{equation}
where the second inequality holds since $t^2\big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t}\leq 1$ based on the choice of $K_t.$\\
On the other hand, from \eqref{eq: OMGD (constrained) proof eq1} we have that
\begin{equation}\label{eq: OMGD (constrained) proof eq4}
\begin{split}
    \norm{\xb_t - \xb^*_t}^2&\leq 2\norm{\xb_t - \xb^*_{t-1}}^2 + 2\norm{\xb^*_{t-1}-\xb^*_t}^2\\
    &\leq 2\big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t}\norm{\xb_{t-1} - \xb^*_{t-1}}^2 + 2\norm{\xb^*_{t-1}-\xb^*_t}^2\\
    &\leq 2\big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t} D^2 + 2\norm{\xb^*_{t-1}-\xb^*_t}^2.
\end{split}
\end{equation}
Summing \eqref{eq: OMGD (constrained) proof eq4} over $t=2,\ldots,T$ and adding $\norm{\xb_1 - \xb^*_1}^2 $ to both sides, we have
\begin{equation}\label{eq: OMGD (constrained) proof eq5}
\begin{split}
    \sum_{t=1}^T \norm{\xb_t - \xb^*_t}^2&\leq \norm{\xb_1 - \xb^*_1}^2 + 2D^2\sum_{t=2}^T\big(1-\frac{2\mu }{1/\eta+\mu}\big)^{K_t}  + 2\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2\\
    &\leq \norm{\xb_1 - \xb^*_1}^2 + 2D^2(\frac{\pi^2}{6}) + 2\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2.
\end{split}
\end{equation}
Based on the $L$-smoothness, we know
\begin{eqnarray*}
\sum_{t=1}^T f_t(\xb_t) - f_t(\xb^*_t)&\leq& \sum_{t=1}^T\frac{L}{2}\norm{\xb_t-\xb^*_t}^2+\nabla f_t (\xb^*_t)^\top (\xb_t-\xb^*_t)\\
&\leq&\sum_{t=1}^T\frac{L}{2}\norm{\xb_t-\xb^*_t}^2+ D\sum_{t=1}^T\norm{\nabla f_t (\xb^*_t)}.
\end{eqnarray*}
Substituting \eqref{eq: OMGD (constrained) proof eq5} into the inequality above, we have
\begin{equation}\label{eq: OMGD (constrained) proof eq6}
\begin{split}
    \sum_{t=1}^T f_t(\xb_t) - f_t(\xb^*_t)&\leq \sum_{t=1}^T\frac{L}{2}\norm{\xb_t-\xb^*_t}^2+ D\sum_{t=1}^T\norm{\nabla f_t (\xb^*_t)}\\
    &\leq \frac{L}{2}\big[\norm{\xb_1 - \xb^*_1}^2 + 2D^2(\frac{\pi^2}{6}) + 2\sum_{t=2}^T\norm{\xb^*_t-\xb^*_{t-1}}^2\big]+ D\sum_{t=1}^T\norm{\nabla f_t (\xb^*_t)}.
\end{split}
\end{equation}

\end{proof}

\newpage
\bibliographystyle{apalike}
\bibliography{Reference}

\end{document}

config: arxiv


text:
/-
Copyright (c) 2022 Yaël Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies
-/
import data.finsupp.basic

/-!
# Building finitely supported functions off finsets

This file defines `finsupp.indicator` to help create finsupps from finsets.

## Main declarations

* `finsupp.indicator`: Turns a map from a `finset` into a `finsupp` from the entire type.
-/

noncomputable theory

open finset function
open_locale classical

variables {ι α : Type*}

namespace finsupp
variables [has_zero α] {s : finset ι} (f : Π i ∈ s, α) {i : ι}

/-- Create an element of `ι →₀ α` from a finset `s` and a function `f` defined on this finset. -/
def indicator (s : finset ι) (f : Π i ∈ s, α) : ι →₀ α :=
{ to_fun := λ i, if H : i ∈ s then f i H else 0,
  support := (s.attach.filter $ λ i : s, f i.1 i.2 ≠ 0).map $ embedding.subtype _,
  mem_support_to_fun := λ i, begin
    rw [mem_map, dite_ne_right_iff],
    exact ⟨λ ⟨⟨j, hj⟩, hf, rfl⟩, ⟨hj, (mem_filter.1 hf).2⟩,
      λ ⟨hi, hf⟩, ⟨⟨i, hi⟩, mem_filter.2 $ ⟨mem_attach _ _, hf⟩, rfl⟩⟩,
  end }

lemma indicator_of_mem (hi : i ∈ s) (f : Π i ∈ s, α) : indicator s f i = f i hi := dif_pos hi
lemma indicator_of_not_mem (hi : i ∉ s) (f : Π i ∈ s, α) : indicator s f i = 0 := dif_neg hi

variables (s i)

@[simp] lemma indicator_apply : indicator s f i = if hi : i ∈ s then f i hi else 0 := rfl

lemma indicator_injective : injective (λ f : Π i ∈ s, α, indicator s f) :=
begin
  intros a b h,
  ext i hi,
  rw [←indicator_of_mem hi a, ←indicator_of_mem hi b],
  exact congr_fun h i,
end

lemma support_indicator_subset : ((indicator s f).support : set ι) ⊆ s :=
begin
  intros i hi,
  rw [mem_coe, mem_support_iff] at hi,
  by_contra,
  exact hi (indicator_of_not_mem h _),
end

end finsupp

subset_name: curated


TITLE: Integrate the differentials
QUESTION [0 upvotes]: To simplify the integral I was thinking about using FTOC2 but is it supposed to be as f(t) because here it says $ln(x^2+1)$ I was confused where does it have to be as $ln(t^2+1)$ to use FTOC2 or can we simply says hat it is equal to $ln(x^2+1)$ ?
${\Large\int} _{-2}^{x} \dfrac{d}{dx}ln(x^2+1)dx$

REPLY [2 votes]: It's equal to $\int^x_{-2} \frac{2t}{t^2+1}dt = ln(t^2+1) \Biggr|_{-2}^x.$


TITLE: Find the derivative of the following using the POWER RULE?
QUESTION [0 upvotes]: problem:  $f(x)= 3x^2(x^2-20x^3+5) $
my answer:
$f(x) = 3x^4-60x^5+15x^2$
$ f'(x) = 3 \cdot 4x^3-60 \cdot 5x^4+15 \cdot 2x = 12x^3-300x^4+30x$
Am I correct?

REPLY [0 votes]: Yes, you are correct. Alternatively, you may use the product rule:
$$(u\cdot v)'=u'\cdot v+u\cdot v'$$
Let:
$$\begin{matrix} u=3x^2 & v=x^2-20x^3+5 \\ u'=6x & v'=2x-60x^2 \end{matrix}$$
This gives:
$$\begin{align} f'(x)&=\color{red}{6x(x^2-20x^3+5)}+\color{blue}{3x^2(2x-60x^2)}\\&=\color{red}{6x^3-120x^4+30x}+\color{blue}{6x^3-180x^4}\\&=-300x^4+12x^3+30x \end{align}$$
Which is the same answer you obtained.


TITLE: The sample mean convergence in quadratic mean and in probability
QUESTION [1 upvotes]: $X_1, X_2, \dots $ is a sequence of random variables such that $$\sup_{n \geq 1} E|X_n |^2 < \infty ~~ \text{and}~~  E[X_n X_m ] = 0 ~\text{for}~ n \neq m.$$
I want to show that the empirical "or sample" mean of $X_1 , . . . , X_n$ converges to $0$ in quadratic mean and in probability.
My attempt:
Assuming that $E(X_i) = \mu$ and $var(X_i) = \sigma^2$, the sample mean converges in quadratic mean if $E[(\bar{X} \ - \ \mu)^2] = 0$ as $n \rightarrow 0$.
\begin{eqnarray}
E[(\bar{X} \ - \ \mu)^2] = E[\bar{X}^2] - 2 \mu^2 + \mu
\end{eqnarray}
but how to continue to show that it is equal $0$. Also, I don't know how to use the weak law of large numbers to here to prove the convergence in probability?

REPLY [1 votes]: What you are asked to show is $E(\overline {X})^{2} \to 0$, not $E(\overline {X}-\mu)^{2} \to 0$. This quite easy. Just expand the square and use the hypothesis to get $E(\overline {X})^{2}=\frac 1 {n^{2}} \sum\limits_{k=1}^{n} EX_k^{2}$. If $EX_k^{2} \leq M$ then we get $E(\overline {X})^{2} \leq \frac M n \to 0$.
Any sequence which converges in quadratic mean also converges in probability.