Search

Adaptive optimizers have emerged as powerful tools in deep learning, dynamically adjusting the learning rate based on iterative gradients. These adaptive methods have significantly succeeded in various deep learning tasks, outperforming stochastic gradient descent (SGD). However, although AdaGrad is a cornerstone adaptive optimizer, its theoretical analysis is inadequate in addressing asymptotic convergence and non-asymptotic convergence rates on non-convex optimization. This study aims to provide a comprehensive analysis and complete picture of AdaGrad. We first introduce a novel stopping time technique from probabilistic theory to establish stability for the norm version of AdaGrad under milder conditions. We further derive two forms of asymptotic convergence: almost sure and mean-square. Furthermore, we demonstrate the near-optimal non-asymptotic convergence rate measured by the average-squared gradients in expectation, which is rarely explored and stronger than the existing high-probability results, under the mild assumptions. The techniques developed in this work are potentially independent of interest for future research on other adaptive stochastic algorithms., Comment: 38 pages

We consider a key agreement setting where two parties observe correlated random sources, and want to agree on a secret key via public discussions. In order to allow the key length to adapt to the realizations of the random sources, we allow the key to be of variable length, subject to a novel variable-length version of the uniformity constraint based on random stopping time. We propose simple, computationally efficient key agreement schemes under the new constraint. The proposed scheme can be considered as the key agreement analogue of variable-length source coding via Huffman coding, and the Knuth-Yao random number generator., Comment: 8 pages

In this paper, we present an online reinforcement learning algorithm for constrained Markov decision processes with a safety constraint. Despite the necessary attention of the scientific community, considering stochastic stopping time, the problem of learning optimal policy without violating safety constraints during the learning phase is yet to be addressed. To this end, we propose an algorithm based on linear programming that does not require a process model. We show that the learned policy is safe with high confidence. We also propose a method to compute a safe baseline policy, which is central in developing algorithms that do not violate the safety constraints. Finally, we provide simulation results to show the efficacy of the proposed algorithm. Further, we demonstrate that efficient exploration can be achieved by defining a subset of the state-space called proxy set.

Define the map $T_1$ on $\mathbb{F}_2[x]$ by $T_1(f)=\frac{f}{x}$ if $f(0)=0$ and $T_1(f)=\frac{(x+1)f+1}{x}$ if $f(0)=1$. For a non-zero polynomial $f$ let $\tau_1(f)$ denote the least natural $k$ number for which $T_1^{k}(f)=1$. Define the average stopping time to be $\rho_1(n)=\frac{\sum_{f\in \mathbb{F}_2[x], \text{deg}(f)=n }\tau_1(f)}{2^n}$. We show that $\frac{\rho_1(n)}{n}$ converges to $2$ as $n\rightarrow\infty$ confirming a conjecture of Alon, Behajaina and Paran. Furthermore, we give a new proof that $\tau_1(f)\in O(\text{deg}(f)^{1.5})$ for all $f\in\mathbb{F}_2[x]\setminus\{0\}$.

We study the stopping time of the Collatz map for a polynomial $f \in \mathbb{F}_2[x]$, and bound it by $O({\rm deg} (f)^{1.5})$, improving upon the quadratic bound proven by Hicks, Mullen, Yucas and Zavislak. We also prove the existence arithmetic sequences of unbounded length in the stopping times of certain sequences of polynomials, a phenomenon observed in the classical Collatz map.

Define the map $\mathsf{T}$ on the positive integers by $\mathsf{T}(m)=\frac{m}{2}$ if $m$ is even and by $\mathsf{T}(m)=\frac{3m+1}{2}$ if $m$ is odd. Results of Terras and Everett imply that, given any $\epsilon>0$, almost all $m\in\mathbb{Z}^+$ (in the sense of natural density) fulfill $(\frac{\sqrt{3}}{2})^km^{1-\epsilon}\leq \mathsf{T}^k(m)\leq (\frac{\sqrt{3}}{2})^km^{1+\epsilon}$ simultaneously for all $0\leq k\leq \alpha\log m$ with $\alpha=(\log 2)^{-1}\approx 1.443$. We extend this result to $\alpha=2(\log\frac{4}{3})^{-1}\approx 6.952$, which is the maximally possible value. Set $\mathsf{T}_{\min}(m):=\min_{n\in\mathbb{N}}\mathsf{T}^n(m)$. As an immediate consequence, one has $\mathsf{T}_{\min}(m)\leq\mathsf{T}^{\left\lfloor2(\log\frac{4}{3})^{-1}\log m\right\rfloor}(m)\leq m^{\epsilon}$ for almost all $m\in\mathbb{Z}^+$ for any given $\epsilon>0$. Previously, Korec has shown that $\mathsf{T}_{\min}(m)\leq m^\epsilon$ for almost all $m\in\mathbb{Z}^+$ if $\epsilon>\frac{\log3}{\log4}$, and recently Tao proved that $\mathsf{T}_{\min}(m)\leq f(m)$ for almost all $m\in\mathbb{Z}^+$ (in the sense of logarithmic density) for all functions $f$ diverging to $\infty$. Denote by $\tau(m)$ the minimal $n\in\mathbb{N}$ for which $\mathsf{T}^n(m)=1$ if there exists such an $n$ and set $\tau(m)=\infty$ otherwise. As another application, we show that $\liminf_{x\rightarrow\infty}\frac{1}{x\log x}\sum_{m=1}^{\lfloor x\rfloor}\tau(m)\geq 2(\log\frac{4}{3})^{-1}$, partially answering a question of Crandall and Shanks. Under the assumption that the Collatz Conjecture is true in the strong sense that $\tau(m)$ is in $O(\log m)$, we show that $\lim_{x\rightarrow\infty}\frac{1}{x\log x}\sum_{m=1}^{\lfloor x\rfloor}\tau(m)= 2(\log\frac{4}{3})^{-1}$., Comment: New version with changes of exposition of results. An outline of proof of main result added. Approximation result for Syracuse map added. Further references added

What are the optimal times for an Internet of Things (IoT) device to act as a blockchain miner? The aim is to minimize the energy consumed by low-power IoT devices that log their data into a secure (tamper-proof) distributed ledger. We formulate a multiple stopping time Bayesian sequential detection problem to address energy-efficient blockchain mining for IoT devices. The objective is to identify $L$ optimal stops for mining, thereby maximizing the probability of successfully adding a block to the blockchain; we also present a model to optimize the number of stops (mining instants). The formulation is equivalent to a multiple stopping time POMDP. Since POMDPs are in general computationally intractable to solve, we show mathematically using submodularity arguments that the optimal mining policy has a useful structure: 1) it is monotone in belief space, and 2) it exhibits a threshold structure, which divides the belief space into two connected sets. Exploiting the structural results, we formulate a computationally-efficient linear mining policy for the blockchain-enabled IoT device. We present a policy gradient technique to optimize the parameters of the linear mining policy. Finally, we use synthetic and real Bitcoin datasets to study the performance of our proposed mining policy. We demonstrate the energy efficiency achieved by the optimal linear mining policy in contrast to other heuristic strategies.

We give an analytic description for the infinitesimal generator constructed by Applebaum-Estrade for L\'evy flights on a broad class of closed Riemannian manifolds including all negatively-curved manifolds, the flat torus and the sphere. Various properties of the associated semigroup and the asymptotics of the expected stopping time for L\'evy flight based random searches for small targets, also known as the narrow capture problem, are then obtained using our newfound understanding of the infinitesimal generator. Our study also relates to the L\'evy flight foraging hypothesis in the field of biology as we compute the expected time for finding a small target by using the L\'evy flight random search. A similar calculation for Brownian motion on surfaces was done in [arXiv:2209.12425]., Comment: 40 pages

We consider determining the optimal stopping time for the glue curing of wood panels in an automatic process environment. Using the near-infrared spectroscopy technology to monitor the manufacturing process ensures substantial savings in energy and time. We collect a time series of curves from a near-infrared spectrum probe consisting of 72 spectra and aim to detect an optimal stopping time. We propose an estimation procedure to determine the optimal stopping time of wood panel compression and the estimation uncertainty associated with the estimated stopping time. Our method first divides the entire data set into a training sample and a testing sample, then iteratively computes integrated squared forecast errors based on the testing sample. We then apply a structural break detection method with one breakpoint to determine an estimated optimal stopping time from a univariate time series of the integrated squared forecast errors. We also investigate the finite-sample performance of the proposed method via a series of simulation studies., Comment: 24 pages, 5 figures, to appear at the Journal of the Royal Statistical Society: Series C

Stopping-time Banach spaces is a collective term for the class of spaces of eventually null integrable processes that are defined in terms of the behaviour of the stopping times with respect to some fixed filtration. From the point of view of Banach space theory, these spaces in many regards resemble the classical spaces such as $L^1$ or $C(\Delta)$, but unlike these, they do have unconditional bases. In the present paper we study the canonical bases in the stopping-time spaces in relation to factorising the identity operator thereon. Since we work exclusively with the dyadic-tree filtration, this set-up enables us to work with tree-indexed bases rather than directly with stochastic processes. \emph{En route} to the factorisation results, we develop general criteria that allow one to deduce the uniqueness of the maximal ideal in the algebra of operators on a Banach space. These criteria are applicable to many classical Banach spaces such as (mixed-norm) $L^p$-spaces, BMO, $\mathrm{SL^\infty}$ and others., Comment: 25 pages, accepted by Advances in Mathematics

The aim of this paper is to study the existence of variational inequality weak solutions and of a finite stopping time for a large class of generalized Newtonian fluids shear-thinning flows. The existence of dissipative solutions for such flows is known since \cite{abbatiello-feireisl-20}. We submit here an alternative approach using variational inequality solutions as presented in \cite{duvaut-lions} in the two-dimensional Bingham flow. In order to prove the existence of such solutions we regularize the non-linear term and then we apply a Galerkin method for finally passing to the limit with respect to both regularization and Galerkin discretization parameters. In a second time, we prove the existence of a finite stopping time for Ostwald-De Waele and Bingham flows in dimension \(N \in \{2, 3\}\).

In this paper, we consider the optimal stopping problem on semi-Markov processes (SMPs) with finite horizon, and aim to establish the existence and computation of optimal stopping times. To achieve the goal, we first develop the main results of finite horizon semi-Markov decision processes (SMDPs) to the case with additional terminal costs, introduce an explicit construction of SMDPs, and prove the equivalence between the optimal stopping problems on SMPs and SMDPs. Then, using the equivalence and the results on SMDPs developed here, we not only show the existence of optimal stopping time of SMPs, but also provide an algorithm for computing optimal stopping time on SMPs. Moreover, we show that the optimal and "-optimal stopping time can be characterized by the hitting time of some special sets, respectively., Comment: 27 pages, 0 figures

Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs., Comment: LMCS paper (a preliminary version appeared at LICS 2021)

This paper attempts to study the optimal stopping time for semi-Markov processes (SMPs) under the discount optimization criteria with unbounded cost rates. In our work, we introduce an explicit construction of the equivalent semi-Markov decision processes (SMDPs). The equivalence is embodied in the value functions of SMPs and SMDPs, that is, every stopping time of SMPs can induce a policy of SMDPs such that the value functions are equal, and vice versa. The existence of the optimal stopping time of SMPs is proved by this equivalence relation. Next, we give the optimality equation of the value function and develop an effective iterative algorithm for computing it. Moreover, we show that the optimal and {\epsilon}-optimal stopping time can be characterized by the hitting time of the special sets. Finally, to illustrate the validity of our results, an example of a maintenance system is presented in the end., Comment: 24 pages, 0 figure

In protoplanetary disks, zones of dense particle configuration promote planet formation. Solid particles in dense clouds alter their motion through collective effects and back reaction to the gas. The effect of particle-gas feedback with ambient solid-to-gas ratios $\epsilon > 1$ on the stopping time of particles is investigated. In experiments on board the International Space Station we studied the evolution of a dense granular gas while interacting with air. We observed diffusion of clusters released at the onset of an experiment but also the formation of new dynamical clusters. The solid-to-gas mass ratio outside the cluster varied in the range of about $\epsilon_{\rm avg} \sim 2.5 - 60$. We find that the concept of gas drag in a viscous medium still holds, even if the medium is strongly dominated in mass by solids. However, a collective factor has to be used, depending on $\epsilon_{\rm avg} $, i.e. the drag force is reduced by a factor 18 at the highest mass ratios. Therefore, flocks of grains in protoplanetary disks move faster and collide faster than their constituents might suggest.

This paper presents an inverse reinforcement learning~(IRL) framework for Bayesian stopping time problems. By observing the actions of a Bayesian decision maker, we provide a necessary and sufficient condition to identify if these actions are consistent with optimizing a cost function. In a Bayesian (partially observed) setting, the inverse learner can at best identify optimality wrt the observed strategies. Our IRL algorithm identifies optimality and then constructs set-valued estimates of the cost function.To achieve this IRL objective, we use novel ideas from Bayesian revealed preferences stemming from microeconomics. We illustrate the proposed IRL scheme using two important examples of stopping time problems, namely, sequential hypothesis testing and Bayesian search. As a real-world example, we illustrate using a YouTube dataset comprising metadata from 190000 videos how the proposed IRL method predicts user engagement in online multimedia platforms with high accuracy. Finally, for finite datasets, we propose an IRL detection algorithm and give finite sample bounds on its error probabilities.

The widespread availability of behavioral data has led to the development of data-driven personalized pricing algorithms: sellers attempt to maximize their revenue by estimating the consumer's willingness-to-pay and pricing accordingly. Our objective is to develop algorithms that protect consumer interests against personalized pricing schemes. In this paper, we consider a consumer who learns more and more about a potential purchase across time, while simultaneously revealing more and more information about herself to a potential seller. We formalize a strategic consumer's purchasing decision when interacting with a seller who uses personalized pricing algorithms, and contextualize this problem among the existing literature in optimal stopping time theory and computational finance. We provide an algorithm that consumers can use to protect their own interests against personalized pricing algorithms. This algorithmic stopping method uses sample paths to train estimates of the optimal stopping time. To the best of our knowledge, this is one of the first works that provides computational methods for the consumer to maximize her utility when decision making under surveillance. We demonstrate the efficacy of the algorithmic stopping method using a numerical simulation, where the seller uses a Kalman filter to approximate the consumer's valuation and sets prices based on myopic expected revenue maximization. Compared to a myopic purchasing strategy, we demonstrate increased payoffs for the consumer in expectation.

A new method for stochastic control based on neural networks and using randomisation of discrete random variables is proposed and applied to optimal stopping time problems. The method models directly the policy and does not need the derivation of a dynamic programming principle nor a backward stochastic differential equation. Unlike continuous optimization where automatic differentiation is used directly, we propose a likelihood ratio method for gradient computation. Numerical tests are done on the pricing of American and swing options. The proposed algorithm succeeds in pricing high dimensional American and swing options in a reasonable computation time, which is not possible with classical algorithms.

The Collatz sequence for a given natural number $N$ is generated by repeatedly applying the map $N$ $\rightarrow$ $3N+1$ if $N$ is odd and $N$ $\rightarrow$ $N/2$ if $N$ is even. One elusive open problem in Mathematics is whether all such sequences end in 1 (Collatz conjecture), the alternative being the possibility of cycles or of unbounded sequences. In this paper, we present a formula relating the stopping time and the number of odd terms in a Collatz sequence, obtained numerically and tested for all numbers up to $10^7$ and for random numbers up to $2^{128.000}$. This result is presented as a conjecture, and with the hope that it could be useful for constructing a proof of the Collatz conjecture., Comment: 7 pages, 4 figures, 1 table; Table 1 has been fixed (an element was missing before the end of each sequence displayed); minor clarifications in the text

It is proved that the law of a possibly killed L\'evy process $X$, seen up to and including (resp. up to strictly before) a stopping time, determines already the law of $X$ (resp. up to a compound Poisson component and killing).

In this study, we consider an optimal control problem driven by a stochastic differential system with a stopping time terminal cost functional. We establish the stochastic maximum principle for this new kind of an optimal control problem by introducing a discrete terminal system. Finally, we provide an example to describe the main results of this study., Comment: 19. arXiv admin note: text overlap with arXiv:1610.05843

We consider the normalized distribution of the overall running times of some cryptographic algorithms, and what information they reveal about the algorithms. Recent work of Deift, Menon, Olver, Pfrang, and Trogdon has shown that certain numerical algorithms applied to large random matrices exhibit a characteristic distribution of running times, which depends only on the algorithm but are independent of the choice of probability distributions for the matrices. Different algorithms often exhibit different running time distributions, and so the histograms for these running time distributions provide a time-signature for the algorithms, making it possible, in many cases, to distinguish one algorithm from another. In this paper we extend this analysis to cryptographic algorithms, and present examples of such algorithms with time-signatures that are indistinguishable, and others with time-signatures that are clearly distinct., Comment: 20 pages

The objective in this paper is to obtain fast converging reinforcement learning algorithms to approximate solutions to the problem of discounted cost optimal stopping in an irreducible, uniformly ergodic Markov chain, evolving on a compact subset of $\mathbb{R}^n$. We build on the dynamic programming approach taken by Tsitsikilis and Van Roy, wherein they propose a Q-learning algorithm to estimate the optimal state-action value function, which then defines an optimal stopping rule. We provide insights as to why the convergence rate of this algorithm can be slow, and propose a fast-converging alternative, the "Zap-Q-learning" algorithm, designed to achieve optimal rate of convergence. For the first time, we prove the convergence of the Zap-Q-learning algorithm under the assumption of linear function approximation setting. We use ODE analysis for the proof, and the optimal asymptotic variance property of the algorithm is reflected via fast convergence in a finance example.