skip to main content

This content will become publicly available on June 12, 2024

Title: Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators
We study the convergence rate of discretized Riemannian Hamiltonian Monte Carlo on sampling from distributions in the form of e^{−f(x)} on a convex body M ⊂ R^n. We show that for distributions in the form of e−^{a x} on a polytope with m constraints, the convergence rate of a family of commonly-used integrators is independent of ∥a∥_2 and the geometry of the polytope. In particular, the implicit midpoint method (IMM) and the generalized Leapfrog method (LM) have a mixing time of mn^3 to achieve ϵ total variation distance to the target distribution. These guarantees are based on a general bound on the convergence rate for densities of the form e^{−f(x)} in terms of parameters of the manifold and the integrator. Our theoretical guarantee complements the empirical results of our old result, which shows that RHMC with IMM can sample ill-conditioned, non-smooth and constrained distributions in very high dimension efficiently in practice.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
COLT 2013
Date Published:
Journal Name:
COLT 2013
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a non-negative supermodular function $f: 2^V \rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$. For \dsg we describe a simple flow-based algorithm that outputs a $(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time where $m$ is the number of edges. Our algorithm is the first to have a near-linear dependence on $m$ and $1/\eps$ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed \dsg. Greedy peeling algorithms have been very popular for \dsg and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for \dssp and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al.\ \cite{bgpstww-20} developed an \emph{iterative} peeling algorithm for \dsg which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a $(1-\eps)$-approximation for \emph{any} supermodular function $f$; the key to our proof is to consider an LP formulation that is derived via the \Lovasz extension of a supermodular function. For \dsg the bound on the number of iterations we prove is $O(\frac{\Delta \ln |V|}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is the maximum degree and $\lambda^*$ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the $2$-approximation for densest-at-least-$k$ subgraph \cite{ks-09} extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of \dssp to maximize $f(S)/g(|S|)$ for a concave function $g$. 
    more » « less
  2. Abstract The 4 ⁢ N {4N} -carpets are a class of infinitely ramified self-similar fractals with a large group of symmetries. For a 4 ⁢ N {4N} -carpet F , let { F n } n ≥ 0 {\{F_{n}\}_{n\geq 0}} be the natural decreasing sequence of compact pre-fractal approximations with ⋂ n F n = F {\bigcap_{n}F_{n}=F} . On each F n {F_{n}} , let ℰ ⁢ ( u , v ) = ∫ F N ∇ ⁡ u ⋅ ∇ ⁡ v ⁢ d ⁢ x {\mathcal{E}(u,v)=\int_{F_{N}}\nabla u\cdot\nabla v\,dx} be the classical Dirichlet form and u n {u_{n}} be the unique harmonic function on F n {F_{n}} satisfying a mixed boundary value problem corresponding to assigning a constant potential between two specific subsets of the boundary. Using a method introduced by [M. T. Barlow and R. F. Bass,On the resistance of the Sierpiński carpet, Proc. Roy. Soc. Lond. Ser. A 431 (1990), no. 1882, 345–360], we prove a resistance estimate of the following form: there is ρ = ρ ⁢ ( N ) > 1 {\rho=\rho(N)>1} such that ℰ ⁢ ( u n , u n ) ⁢ ρ n {\mathcal{E}(u_{n},u_{n})\rho^{n}} is bounded above and below by constants independent of n . Such estimates have implications for the existence and scaling properties of Brownian motion on F . 
    more » « less
  3. Neurotransmitters are small molecules involved in neuronal signaling and can also serve as stress biomarkers.1Their abnormal levels have been also proposed to be indicative of several neurological diseases such as Alzheimer’s disease, Parkinson’s disease, Huntington disease, among others. Hence, measuring their levels is highly important for early diagnosis, therapy, and disease prognosis. In this work, we investigate facile functionalization methods to tune and enhance sensitivity of printed graphene sensors to neurotransmitters. Sensors based on direct laser scribing and screen-printed graphene ink are studied. These printing methods offer ease of prototyping and scalable fabrication at low cost.

    The effect of functionalization of laser induced graphene (LIG) by electrodeposition and solution-based deposition of TMDs (molybdenum disulfide2and tungsten disulfide) and metal nanoparticles is studied. For different processing methods, electrochemical characteristics (such as electrochemically active surface area: ECSA and heterogenous electron transfer rate: k0) are extracted and correlated to surface chemistry and defect density obtained respectively using X-ray photoelectron spectroscopy (XPS) and Raman spectroscopy. These functionalization methods are observed to directly impact the sensitivity and limit of detection (LOD) of the graphene sensors for the studied neurotransmitters. For example, as compared to bare LIG, it is observed that electrodeposition of MoS2on LIG improves ECSA by 3 times and k0by 1.5 times.3Electrodeposition of MoS2also significantly reduces LOD of serotonin and dopamine in saliva, enabling detection of their physiologically relevant concentrations (in pM-nM range). In addition, chemical treatment of LIG sensors is carried out in the form of acetic acid treatment. Acetic acid treatment has been shown previously to improve C-C bonds improving the conductivity of LIG sensors.4In our work, in particular, acetic acid treatment leads to larger improvement of LOD of norepinephrine compared to MoS2electrodeposition.

    In addition, we investigate the effect of plasma treatment to tune the sensor response by modifying the defect density and chemistry. For example, we find that oxygen plasma treatment of screen-printed graphene ink greatly improves LOD of norepinephrine up to three orders of magnitude, which may be attributed to the increased defects and oxygen functional groups on the surface as evident by XPS measurements. Defects are known to play a key role in enhancing the sensitivity of 2D materials to surface interactions, and have been explored in tuning/enhancing the sensor sensitivity.5Building on our previous work,3we apply a custom machine learning-based data processing method to further improve that sensitivity and LOD, and also to automatically benchmark different molecule-material pairs.

    Future work includes expanding the plasma chemistry and conditions, studying the effect of precursor mixture in laser-induced solution-based functionalization, and understanding the interplay between molecule-material system. Work is also underway to improve the machine learning model by using nonlinear learning models such as neural networks to improve the sensor sensitivity, selectivity, and robustness.


    A. J. Steckl, P. Ray, (2018), doi:10.1021/acssensors.8b00726.

    Y. Lei, D. Butler, M. C. Lucking, F. Zhang, T. Xia, K. Fujisawa, T. Granzier-Nakajima, R. Cruz-Silva, M. Endo, H. Terrones, M. Terrones, A. Ebrahimi,Sci. Adv.6, 4250–4257 (2020).

    V. Kammarchedu, D. Butler, A. Ebrahimi,Anal. Chim. Acta.1232, 340447 (2022).

    H. Yoon, J. Nah, H. Kim, S. Ko, M. Sharifuzzaman, S. C. Barman, X. Xuan, J. Kim, J. Y. Park,Sensors Actuators B Chem.311, 127866 (2020).

    T. Wu, A. Alharbi, R. Kiani, D. Shahrjerdi,Adv. Mater.31, 1–12 (2019).

    more » « less
  4. null (Ed.)
    We study the application of iterative first-order methods to the problem of computing equilibria of large-scale two-player extensive-form games. First-order methods must typically be instantiated with a regularizer that serves as a distance-generating function for the decision sets of the players. For the case of two-player zero-sum games, the state-of-the-art theoretical convergence rate for Nash equilibrium is achieved by using the dilated entropy function. In this paper, we introduce a new entropy-based distance-generating function for two-player zero-sum games, and show that this function achieves significantly better strong convexity properties than the dilated entropy, while maintaining the same easily-implemented closed-form proximal mapping. Extensive numerical simulations show that these superior theoretical properties translate into better numerical performance as well. We then generalize our new entropy distance function, as well as general dilated distance functions, to the scaled extension operator. The scaled extension operator is a way to recursively construct convex sets, which generalizes the decision polytope of extensive-form games, as well as the convex polytopes corresponding to correlated and team equilibria. By instantiating first-order methods with our regularizers, we develop the first accelerated first-order methods for computing correlated equilibra and ex-ante coordinated team equilibria. Our methods have a guaranteed 1/T rate of convergence, along with linear-time proximal updates. 
    more » « less
  5. Abstract We present observations of ≳10–100 keV nucleon −1 suprathermal (ST) H, He, O, and Fe ions associated with crossings of the heliospheric current sheet (HCS) at radial distances of <0.1 au from the Sun. Our key findings are as follows: (1) very few heavy ions are detected during the first full crossing, the heavy-ion intensities are reduced during the second partial crossing and peak just after the second crossing; (2) ion arrival times exhibit no velocity dispersion; (3) He pitch-angle distributions track the magnetic field polarity reversal and show up to ∼10:1 anti-sunward, field-aligned flows and beams closer to the HCS that become nearly isotropic farther from the HCS; (4) the He spectrum steepens either side of the HCS, and the He, O, and Fe spectra exhibit power laws of the form ∼ E −4 – E 6 ; and (5) maximum energies E X increase with the ion’s charge-to-mass ( Q / M ) ratio as E X / E H ∝ ( Q X / M X ) δ , where δ ∼ 0.65–0.76, assuming that the average Q states are similar to those measured in gradual and impulsive solar energetic particle events at 1 au. The absence of velocity dispersion in combination with strong field-aligned anisotropies closer to the HCS appears to rule out solar flares and near-Sun coronal-mass-ejection-driven shocks. These new observations present challenges not only for mechanisms that employ direct parallel electric fields and organize maximum energies according to E / Q but also for local diffusive and magnetic-reconnection-driven acceleration models. Reevaluation of our current understanding of the production and transport of energetic ions is necessary to understand this near-solar, current-sheet-associated population of ST ions. 
    more » « less