More Like this

1. Comparison of the predictions of Langevin Dynamics-based diffusion charging collision kernel models with canonical experiments

   https://doi.org/https://doi.org/10.1016/j.jaerosci.2019.105481  

   Li, Li Chahl ( February 2020 , Journal of aerosol science)

   Based on the prior work of Chahl and Gopalakrishnan (2019) to infer particle-ion collision time distributions using a Langevin Dynamics (LD) approach, we develop a model for the non-dimensional diffusion charging collision kernel β_i or H that is applicable for 0≤Ψ_E≤60,0≤Ψ_I/Ψ_E ≤1,Kn_D≤2000 (defined in the main text). The developed model for β_i for attractive Coulomb and image potential interactions, along with the model for β_i for repulsive Coulomb and image potential interactions from Gopalakrishnan et al. (2013b), is tested against published diffusion charging experimental data. Current state of the art charging models, Fuchs (1963) and Wiedensohler (1988) regression for bipolar charging, are also evaluated and discussed. Comparisons reveal that the LD-based model accurately describes unipolar fractions for 10 – 100 nm particles measured in air (Adachi et al., 1985), nitrogen and argon but not in helium (Adachi et al., 1987). Fuchs model and the LD-based model yield similar predictions in the experimental conditions considered, except in helium. In the case of bipolar charging, the LD-based model captures the experimental trends quantitatively (within ±20%) across the entire size range of 4 – 40 nm producing superior agreement than Wiedensohler’s regression. The latter systematically underpredicts charge fraction below ~20 nm in air (by up to 40%) for the data presented in Adachi et al. (1985). Comparison with the data of Gopalakrishnan et al. (2015), obtained in UHP air along with measurements of the entire ion mass-mobility distribution, shows excellent agreement with the predictions of the LD-based model. This demonstrates the capability to accommodate arbitrary ion populations in any background gas, when such data is available. Wiedensohler’s regression, derived for bipolar charging in air using average ion mass-mobility, also describes the data reasonably well in the conditions examined. However, both models failed to capture the fraction of singly and doubly charged particles in carbon dioxide warranting further investigation. 

   more » « less
2. SpecPart: A Supervised Spectral Framework for Hypergraph Partitioning Solution Improvement

   https://doi.org/10.1145/3508352.3549390  

   Bustany, Ismail ; Kahng, Andrew B. ; Koutis, Ioannis ; Pramanik, Bodhisatta ; Wang, Zhiang ( October 2022 , Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design)

   State-of-the-art hypergraph partitioners follow the multilevel paradigm that constructs multiple levels of progressively coarser hypergraphs that are used to drive cut refinements on each level of the hierarchy. Multilevel partitioners are subject to two limitations: (i) Hypergraph coarsening processes rely on local neighborhood structure without fully considering the global structure of the hypergraph. (ii) Refinement heuristics can stagnate on local minima. In this paper, we describe SpecPart, the first supervised spectral framework that directly tackles these two limitations. SpecPart solves a generalized eigenvalue problem that captures the balanced partitioning objective and global hypergraph structure in a low-dimensional vertex embedding while leveraging initial high-quality solutions from multilevel partitioners as hints. SpecPart further constructs a family of trees from the vertex embedding and partitions them with a tree-sweeping algorithm. Then, a novel overlay of multiple tree-based partitioning solutions, followed by lifting to a coarsened hypergraph, where an ILP partitioning instance is solved to alleviate local stagnation. We have validated SpecPart on multiple sets of benchmarks. Experimental results show that for some benchmarks, our SpecPart can substantially improve the cutsize by more than 50% with respect to the best published solutions obtained with leading partitioners hMETIS and KaHyPar. 

   more » « less
3. Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms

   Wang, Yazhen ; Wu, Shang ( September 2020 , Journal of machine learning research)

   Bach, Francis ; Blei, David ; Scholkopf, Bernhard (Ed.)

   This paper investigates the asymptotic behaviors of gradient descent algorithms (particularly accelerated gradient descent and stochastic gradient descent) in the context of stochastic optimization arising in statistics and machine learning, where objective functions are estimated from available data. We show that these algorithms can be computationally modeled by continuous-time ordinary or stochastic differential equations. We establish gradient flow central limit theorems to describe the limiting dynamic behaviors of these computational algorithms and the large-sample performances of the related statistical procedures, as the number of algorithm iterations and data size both go to infinity, where the gradient flow central limit theorems are governed by some linear ordinary or stochastic differential equations, like time-dependent Ornstein-Uhlenbeck processes. We illustrate that our study can provide a novel unified framework for a joint computational and statistical asymptotic analysis, where the computational asymptotic analysis studies the dynamic behaviors of these algorithms with time (or the number of iterations in the algorithms), the statistical asymptotic analysis investigates the large-sample behaviors of the statistical procedures (like estimators and classifiers) that are computed by applying the algorithms; in fact, the statistical procedures are equal to the limits of the random sequences generated from these iterative algorithms, as the number of iterations goes to infinity. The joint analysis results based on the obtained The joint analysis results based on the obtained gradient flow central limit theorems lead to the identification of four factors---learning rate, batch size, gradient covariance, and Hessian---to derive new theories regarding the local minima found by stochastic gradient descent for solving non-convex optimization problems. 

   more » « less
4. Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms

   Wang, Yazhen ; Wu, Shang ( September 2021 , Journal of machine learning research)

   Bach, Francis ; Blei, David ; Scholkopf, Bernhard (Ed.)

   This paper investigates the asymptotic behaviors of gradient descent algorithms (particularly accelerated gradient descent and stochastic gradient descent) in the context of stochastic optimization arising in statistics and machine learning, where objective functions are estimated from available data. We show that these algorithms can be computationally modeled by continuous-time ordinary or stochastic differential equations. We establish gradient flow central limit theorems to describe the limiting dynamic behaviors of these computational algorithms and the large-sample performances of the related statistical procedures, as the number of algorithm iterations and data size both go to infinity, where the gradient flow central limit theorems are governed by some linear ordinary or stochastic differential equations, like time-dependent Ornstein-Uhlenbeck processes. We illustrate that our study can provide a novel unified framework for a joint computational and statistical asymptotic analysis, where the computational asymptotic analysis studies the dynamic behaviors of these algorithms with time (or the number of iterations in the algorithms), the statistical asymptotic analysis investigates the large-sample behaviors of the statistical procedures (like estimators and classifiers) that are computed by applying the algorithms; in fact, the statistical procedures are equal to the limits of the random sequences generated from these iterative algorithms, as the number of iterations goes to infinity. The joint analysis results based on the obtained gradient flow central limit theorems lead to the identification of four factors—learning rate, batch size, gradient covariance, and Hessian—to derive new theories regarding the local minima found by stochastic gradient descent for solving non-convex optimization problems. 

   more » « less
5. Solving Sparse Linear Systems Faster than Matrix Multiplication

   https://doi.org/10.1137/1.9781611976465.31  

   Peng, Richard ; Vempala, Santosh S. ( January 2021 , Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021)

   null (Ed.)

   Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general setting, the bit complexity of solving an $n \times n$ linear system $Ax=b$ is $\tilde{O}(n^\omega)$, where $\omega < 2.372864$ is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly$(n)$ condition number. In this paper, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any $\omega > 2$. This speedup holds for any input matrix $A$ with $o(n^{\omega -1}/\log(\kappa(A)))$ non-zeros, where $\kappa(A)$ is the condition number of $A$. For poly$(n)$-conditioned matrices with $\tilde{O}(n)$ nonzeros, and the current value of $\omega$, the bit complexity of our algorithm to solve to within any $1/\text{poly}(n)$ error is $O(n^{2.331645})$. Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly et al. ISSAC `06 `07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices. 

   more » « less