3 April 2020 in The Electronic Journal of Combinatorics
A weighted $d$-complex is a simplicial complex of dimension $d$ in which each face is assigned a real-valued weight. We derive three key results here concerning persistence diagrams and minimal spanning acycles (MSAs) of such complexes. First, we establish an equivalence between the MSA face-weights and death times in the persistence diagram. Next, we show a novel stability result for the MSA face-weights which, due to our first result, also holds true for the death and birth times, separately. Our final result concerns a perturbation of a mean-field model of randomly weighted $d$-complexes. The $d$-face weights here are perturbations of some i.i.d. distribution while all the lower-dimensional faces have a weight of $0$. If the perturbations decay sufficiently quickly, we show that suitably scaled extremal nearest face-weights, face-weights of the $d$-MSA, and the associated death times converge to an inhomogeneous Poisson point process. This result completely characterizes the extremal points of persistence diagrams and MSAs. The point process convergence and the asymptotic equivalence of three point processes are new for any weighted random complex model, including even the non-perturbed case. Lastly, as a consequence of our stability result, we show that Frieze's $\zeta(3)$ limit for random minimal spanning trees and the recent extension to random MSAs by Hino and Kanazawa also hold in suitable noisy settings.
1 March 2019 in Stochastic Systems
Given an ordinary differential equation (ODE) and its perturbation, the Alekseev formula expresses the solutions of the latter in terms related to the former. By exploiting this formula and a new concentration inequality for martingale-differences, we develop a novel approach for analyzing nonlinear stochastic approximation (SA). This approach is useful for studying a SA’s behavior close to a locally asymptotically stable equilibrium (LASE) of its limiting ODE; this LASE need not be the limiting ODE’s only attractor. As an application, we obtain a new concentration bound for nonlinear SA. That is, given ϵ > and that the current iterate is in a neighborhood of a LASE, we provide an estimate for (i) the time required to hit the ϵ-ball of this LASE, and (ii) the probability that after this time the iterates are indeed within this ϵ-ball and stay there thereafter. The latter estimate can also be viewed as the “lock-in” probability. Compared with related results, our concentration bound is tighter and holds under significantly weaker assumptions. In particular, our bound applies even when the stepsizes are not square-summable. Despite the weaker hypothesis, we show that the celebrated Kushner-Clark lemma continues to hold.
1 February 2022 in Performance Evaluation
10 November 2025 in IEEE Transactions on Automatic Control
A primary requirement for any reinforcement learning method is that it should produce policies that improve upon the initial guess. In this work, we show that the widely used Deep Q-Network (DQN) fails to satisfy this minimal criterion—even when it gets to see all possible states and actions infinitely often (a condition under which tabular Q-learning is guaranteed to converge to the optimal Q-value function). Our specific contributions are twofold. First, we numerically show that DQN often returns a policy that performs worse than the initial one. Second, we offer a theoretical explanation for this phenomenon in linear DQN, a simplified version of DQN that uses linear function approximation in place of neural networks while retaining the other key components such as $\epsilon$-greedy exploration, experience replay, and target network. Using tools from differential inclusion theory, we prove that the limit points of linear DQN correspond to fixed points of projected Bellman operators. Crucially, we show that these fixed points need not relate to optimal—or even near-optimal—policies, thus explaining linear DQN's sub-optimal behaviors. We also give a scenario where linear DQN always identifies the worst policy. Our work fills a longstanding gap in understanding the convergence behaviors of Q-learning with function approximation and $\epsilon$-greedy exploration.