skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


This content will become publicly available on October 17, 2026

Title: Accelerated convergence in Hit-and-Run Monte Carlo and a coordinate-free randomized Kaczmarz algorithm
Hit-and-Run is a coordinate-free Gibbs sampler, yet the quantitative advantages of its coordinate-free property remain largely unexplored beyond empirical studies. In this paper, we prove sharp estimates for the Wasserstein contraction of Hit-and-Run in Gaussian target measures via coupling methods and conclude mixing time bounds. Our results uncover accelerated convergence rates in certain settings. Furthermore, we extend these insights to a coordinate-free variant of the randomized Kaczmarz algorithm, an iterative method for linear systems, and demonstrate analogous convergence rates. These findings offer new insights into the advantages and limitations of coordinate-free methods for both sampling and optimization.  more » « less
Award ID(s):
2111224
PAR ID:
10643216
Author(s) / Creator(s):
 ;  ;  
Publisher / Repository:
Institute of Mathematical Statistics
Date Published:
Journal Name:
Electronic Journal of Probability
Volume:
30
ISSN:
1083-6489
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, ACM Symposium on Computational Geometry)
    Buchin, Kevin; Colin de Verdi\` (Ed.)
    The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all the other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body K in ℝⁿ with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the mixing rate of CHAR, showing that it is strictly worse than hit-and-run and the ball walk in the worst case. 
    more » « less
  2. ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    null (Ed.)
    We provide new adaptive first-order methods for constrained convex optimization. Our main algorithms AdaACSA and AdaAGD+ are accelerated methods, which are universal in the sense that they achieve nearly-optimal convergence rates for both smooth and non-smooth functions, even when they only have access to stochastic gradients. In addition, they do not require any prior knowledge on how the objective function is parametrized, since they automatically adjust their per-coordinate learning rate. These can be seen as truly accelerated Adagrad methods for constrained optimization. We complement them with a simpler algorithm AdaGrad+ which enjoys the same features, and achieves the standard non-accelerated convergence rate. We also present a set of new results involving adaptive methods for unconstrained optimization and variational inequalities arising from monotone operators. 
    more » « less
  3. ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    We provide new adaptive first-order methods for constrained convex optimization. Our main algorithms AdaACSA and AdaAGD+ are accelerated methods, which are universal in the sense that they achieve nearly-optimal convergence rates for both smooth and non-smooth functions, even when they only have access to stochastic gradients. In addition, they do not require any prior knowledge on how the objective function is parametrized, since they automatically adjust their per-coordinate learning rate. These can be seen as truly accelerated Adagrad methods for constrained optimization. We complement them with a simpler algorithm AdaGrad+ which enjoys the same features, and achieves the standard non-accelerated convergence rate. We also present a set of new results involving adaptive methods for unconstrained optimization and variational inequalities arising from monotone operators. 
    more » « less
  4. ; (, Journal of Complexity)
    Kernel methods for solving partial differential equations work coordinate-free on the surface and yield high approximation rates for smooth solutions. Localized Lagrange bases have proven to alleviate the computational complexity of usual kernel methods for data fitting problems, but the efficient numerical solution of the ill-conditioned linear systems of equations arising from kernel- based Galerkin solutions to PDEs is a challenging problem which has not been addressed in the literature so far. In this article we apply the framework of the geometric multigrid method with a τ ≥ 2-cycle to scattered, quasi-uniform point clouds on the surface. We show that the resulting solver can be accelerated by using the Lagrange function decay and obtain satisfying convergence rates by a rigorous analysis. In particular, we show that the computational cost of the linear solver scales log-linear in the degrees of freedom. 
    more » « less
  5. ; ; ; ; ; (, Journal of The Electrochemical Society)
    Single-entity electrochemistry is of fundamental importance and shows promise for ultrasensitive biosensing applications. Recently, we have demonstrated that various charged nanoparticles can be detected individually based on the non-redox open-circuit potential (OCP) changes induced by their collision events on a floating carbon nanoelectrode (CNE). Unlike the widely used amperometry approach, the potentiometric method provides the label-free detection of individual nanoscale entities without redox mediators in the solution. However, the CNE lacks specificity for molecular recognition during the collision events because of the limited methods of surface functionalization for carbon surfaces. Herein, we used surface-functionalized gold nanoelectrode (GNE) to overcome this limitation of CNE. The GNE modified with Raman reporter molecule also enabled surface-enhanced Raman spectroscopy (SERS) measurements. By using simultaneous time-resolved OCP and SERS measurements, both the OCP and SERS signals induced by the “hit-n-run” type of gold nanoparticle (GNP) collision events can be better understood. Also, by introducing a zwitterionic molecule, we formed near “stealth” surface and demonstrated that the non-specific adsorptions of GNPs to the surface of GNE have been suppressed, allowing continuous detection of hit-n-run events for over 30 min. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email