Accelerating Optimization and Reinforcement Learning with Quasi Stochastic Approximation
The paper sets out to obtain precise convergence rates for quasi-stochastic approximation (QSA), with applications to optimization and reinforcement learning.
SEARCH · Engineering Papers
Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
The paper sets out to obtain precise convergence rates for quasi-stochastic approximation (QSA), with applications to optimization and reinforcement learning.
No abstract prepared.
Explore the source record for details and available documents.
Abstract not provided.
Abstract not provided.
Abstract not provided.
Abstract not provided.
According to the direct exposure measurements from flash radiographic image, regularized-based method and compressive sensing (CS)-based method for inverse transport equation are presented. The linear absorption coefficients and interface locations of objects are reconstructed directly at the same time. With a large number of measurements, least-square method is utilized to complete the reconstruction. Owing to the ill-posedness of the inverse problems, regularized algorithm is employed. Tikhonov method is applied with an appropriate posterior regularization parameter to get a meaningful solution. However, it's always very costly to obtain enough measurements. With limited measurements, CS sparse reconstruction technique Orthogonal Matching Pursuit (OMP) is applied to obtain the sparse coefficients by solving an optimization problem. This paper constructs and takes the forward projection matrix rather than Gauss matrix as measurement matrix. In the CS-based algorithm, Fourier expansion and wavelet expansion are adopted to convert an underdetermined system to a well-posed system. Simulations and numerical results of regularized method with appropriate regularization parameter and that of CS-based agree well with the reference value, furthermore, both methods avoid amplifying the noise. (authors)
This final technical report summarizes the accomplishments of work performed under DOE Office of Science Award DE-SC0022266, which is titled “Leverage Score Sampling for Parametric PDEs”. The goal of the project was to extend methods from Randomized Numerical Linear Algebra (RandNLA) to tackle central computational challenges in model order reduction and uncertainty quantification (UQ) for parametric partial differential equations (PDEs). In particular, we sought to use importance sampling methods originally developed for RandNLA to develop sample efficient active learning algorithms for approximating high-dimensional scalar functions, e.g. by polynomials, Gaussian process models, and simple neural networks. Such methods can be immediately applied to developing surrogate models or to approximating quantity of interest (QoI) surfaces. In the context of PDEs, each sample used for learning equates to the solution of the differential equation for a particular set of parameters, so sample efficiency translates to improved computational efficiency for a variety of downstream tasks.
This work extends Quantum Framework (QFw) by integrating it with Northwest Quantum Simulator (NWQ-Sim) and by introducing a lightweight python library that allows multiple frontends (e.g., Qiskit) to interact with QFw. This extension enables QFw to flexibly decouple frontends from backends (e.g., NWQ-Sim). We demonstrate this capability by executing a Greenberger-Horne-Zeilinger (GHZ) circuit using Qiskit and Pennylane with NWQ-Sim and Tensor-Network Quantum Virtual-Machine (TN-QVM). QFw enables easy scaling to multiple nodes. We showcase this with scaling tests using GHZ with up to 32 qubits for different number of nodes on the Frontier supercomputer. And, to demonstrate the use of QFw for real world problems, we solve a metamaterial optimization problem, using a Quantum Approximate Optimization Algorithm (QAOA). We observe that QFw over NWQ-Sim marginally improves Qiskit-aer’s accuracy in reaching the lowest energy state. These additions to QFw prepare it to run hybrid applications in a hybrid resource environment since it treats actual quantum hardware and simulators alike.
Traffic simulation serves as a powerful tool for pre-evaluating policies and technologies. In this context, simulation-based Dynamic traffic assignment (DTA) models are capable of capturing traffic dynamics. They are well-known as critical tools in controlling and predicting traffic situations. The reliability of simulation results heavily depends on the calibration process. Most studies in the literature formulate and calibrate simulators based on a single source of collected data or multiple data sets with the same spatiotemporal characteristics. However, in practice, traffic data is collected by various tools with usually different spatial and temporal resolutions. This study introduces a novel approach to taking into account diverse input data from a variety of sources. An iterative bi-level solution is proposed. to equally treat traffic flow and speed data. The upper level solves flow calibration with the exact solution method, and the lower level calibrates the speed with the simultaneous perturbation stochastic approximation (SPSA) algorithm. Subsequently, the effectiveness of the proposed model is investigated using data from a six-mile section of Nashville's I-24 highway in Tennessee. The results demonstrate that our proposed model creates an effective feedback loop between the optimizer and the simulator for calibrating flow and speed to reduce the error between simulated and real data.
The secretory pro-hormone chromogranin A (CHGA) is densely packed into storage granules along with catecholamines, playing a catalytic role in granule biogenesis. 3-Dimensional structural data on CHGA are lacking. We found a superfamily structural homology for CHGA in the tropomyosin family of alpha-helical coiled-coils, even in mid-molecule regions where primary sequence identity is only modest. The assignment was confirmed by an independent algorithm, suggesting approximately 6-7 such domains spanning CHGA. We provide additional physiochemical evidence (chromatographic, spectral, microscopic) consistent with this unusual structure. Alpha-helical secondary structure (at up to approximately 45%) was confirmed by circular dichroism. CHGA molecular mass was estimated by MALDI-TOF mass spectrometry at approximately 50 kDa and by denaturing gel filtration at approximately 50-61 kDa, while its native Stokes radius was approximately 84.8 A, as compared to an expected approximately 30 A; the increase gave rise to an apparent native molecular weight of approximately 578 kDa, also consistent with the extended conformation of a coiled-coil. Small-angle X-ray scattering (SAXS) on CHGA in solution best fit an elongated cylindrical conformation in the monodisperse region with a radius of gyration of the rod cross-section (Rt) of approximately 52 A, compatible with a coiled-coil in the hydrated, aqueous state, or a multimeric coiled-coil. Electron microscopy with negative staining revealed an extended, filamentous CHGA structure with a diameter of approximately 94 +/- 4.5 A. Extended, coiled-coil conformation is likely to permit protein 'packing' in the secretory granule at approximately 50% higher density than a globular/spherical conformation. Natural allelic variation in the catestatin region was predicted to disrupt the coiled-coil. Chromaffin granule ultrastructure revealed a approximately 108 +/- 6.3 A periodicity of electron density, suggesting nucleation of a binding complex by the CHGA core. Inhibition of CHGA expression, by siRNA, disrupted regulated secretory protein traffic by approximately 65%, while targeted ablation of the CHGA gene in the mouse reduced chromaffin granule cotransmitter concentrations by approximately 40-80%. These results suggest new roles for secretory protein tertiary structure in hormone and transmitter storage, with implications for secretory cargo condensation (or dense core 'packing' structure) within the regulated pathway.
Recent years have seen growth in the number of algorithms designed to solve challenging simulation-based nonlinear optimization problems. One such algorithm is the Trust-Region Parallel Direct Search (TRPDS) method developed by Hough and Meza. In this paper, we take advantage of the theoretical properties of TRPDS to make use of approximation models in order to reduce the computational cost of simulation-based optimization. We describe the extension, which we call mTRPDS, and present the results of a case study for two earth penetrator design problems. In the case study, we conduct computational experiments with an array of approximations within the mTRPDS algorithm and compare the numerical results to the original TRPDS algorithm and a trust-region method implemented using the speculative gradient approach described by Byrd, Schnabel, and Shultz. The results suggest new ways to improve the algorithm.
Rapid penetration of renewable energy based Distributed Energy Resources (DER) has the potential to exacerbate the challenges inherent in grid frequency and voltage regulation. However, their real time controllability can be leveraged to not only mitigate such challenges, but improve the economics and quality of grid operations. A plethora of DER scheduling algorithms have been developed for fast and efficient scheduling of these resources. These algorithms schedule the complex - real and reactive power injected into (or drawn from) the grid by the DERs under various cost objective functions and grid constraints. However, a vast majority of such algorithms assume the feasible range of power injections to be continuous. In reality, the control options available for several DERs form a discrete space. This implies that the feasible range of power injections also forms a discrete space. This makes DER scheduling an NP-hard problem. Integer/Mixed Integer program based algorithms, which guarantee optimality in the objective value, have been developed. But these are prohibitively expensive in terms of computational time requirements. On the other hand, fast heuristic based solutions have also been developed. But as they do not provide any guarantee on the optimality of the objective, or on satisfying the constraints, they are unreliable for grid operations. Recent works have developed approximation algorithms which offer the best of both the approaches above: (near) optimality and low computational complexity, both of which are governed by a user defined accuracy parameter ϵ. In this work, we significantly improve upon such existing works by developing an approximation algorithm which schedules DERs with complex injections (as opposed to only real injection) and whose runtime is polynomial (as opposed to exponential) in 1/ϵ. We provide theoretical analysis and support them with experimental results to validate the guarantees provided by our approximation algorithm.
The gamma-ray burst (GRB) rate is essential for revealing the connection between GRBs, supernovae, and stellar evolution. Additionally, the GRB rate at high redshift provides a strong probe of star formation history in the early universe. While hundreds of GRBs are observed by Swift, it remains difficult to determine the intrinsic GRB rate due to the complex trigger algorithm of Swift. Current studies of the GRB rate usually approximate the Swift trigger algorithm by a single detection threshold. However, unlike the previously flown GRB instruments, Swift has over 500 trigger criteria based on photon count rate and an additional image threshold for localization. To investigate possible systematic biases and explore the intrinsic GRB properties, we develop a program that is capable of simulating all the rate trigger criteria and mimicking the image threshold. Our simulations show that adopting the complex trigger algorithm of Swift increases the detection rate of dim bursts. As a result, our simulations suggest that bursts need to be dimmer than previously expected to avoid overproducing the number of detections and to match with Swift observations. Moreover, our results indicate that these dim bursts are more likely to be high redshift events than low-luminosity GRBs. This would imply an even higher cosmic GRB rate at large redshifts than previous expectations based on star formation rate measurements, unless other factors, such as the luminosity evolution, are taken into account. The GRB rate from our best result gives a total number of 4568{sub −1429}{sup +825} GRBs per year that are beamed toward us in the whole universe.
Constraint satisfaction problems are an important area of computer science. Many of these problems are in the complexity class NP which is exponentially hard for all known methods, both for worst cases and often typical. Fundamentally, the lack of any guided local minimum escape method ensures the hardness of both exact and approximate optimization classically, but the intuitive mechanism for approximation hardness in quantum algorithms based on Hamiltonian time evolution is poorly understood. We explore this question using the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as quantum adiabatic optimization are not good approximation algorithms. We propose a new spectral folding optimization method that does not suffer from these issues and study it analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies an anomalously high fraction of constraints compared to truly random problems. We show that, if we define the energy to be $E = N_{unsat}-N_{sat}$, then spectrally folded quantum optimization will return states with energy $E \leq A E_{GS}$ (where $E_{GS}$ is the ground state energy) in polynomial time, where conservatively, $A \simeq 0.6$. We thoroughly benchmark variations of spectrally folded quantum optimization for random classically approximation-hard (planted solution) instances in simulation, and find performance consistent with this prediction. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.
Discrete-state, continuous-time Markov models are widely used in the modeling of biochemical reaction networks. Their complexity often precludes analytic solution, and we rely on stochastic simulation algorithms (SSA) to estimate system statistics. The Gillespie algorithm is exact, but computationally costly as it simulates every single reaction. As such, approximate stochastic simulation algorithms such as the tau-leap algorithm are often used. Potentially computationally more efficient, the system statistics generated suffer from significant bias unless tau is relatively small, in which case the computational time can be comparable to that of the Gillespie algorithm. The multi-level method [Anderson and Higham, “Multi-level Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics,” SIAM Multiscale Model. Simul. 10(1), 146–179 (2012)] tackles this problem. A base estimator is computed using many (cheap) sample paths at low accuracy. The bias inherent in this estimator is then reduced using a number of corrections. Each correction term is estimated using a collection of paired sample paths where one path of each pair is generated at a higher accuracy compared to the other (and so more expensive). By sharing random variables between these paired paths, the variance of each correction estimator can be reduced. This renders the multi-level method very efficient as only a relatively small number of paired paths are required to calculate each correction term. In the original multi-level method, each sample path is simulated using the tau-leap algorithm with a fixed value of τ. This approach can result in poor performance when the reaction activity of a system changes substantially over the timescale of interest. By introducing a novel adaptive time-stepping approach where τ is chosen according to the stochastic behaviour of each sample path, we extend the applicability of the multi-level method to such cases. We demonstrate the efficiency of our method using a number of examples.
Graph algorithms with polynomial space and time requirements often become infeasible for massive graphs with billions of edges or more. State-of-the-art approaches therefore employ approximate serial, parallel, and distributed algorithms to tackle these challenges. However, such approaches require storing the entire graph in memory and thus need access to costly computing resources such as clusters and supercomputers. In this paper, we present practical streaming approaches for solving massive graph problems using limited memory for two prototypical graph problems: maximum weighted matching and minimum weighted edge cover. For matching, we conduct a thorough computational study on two of the semi-streaming algorithms including a recent breakthrough result that achieves a $1/(2+\varepsilon)$-approximation of the weight while using $O( n \log W /\epsilon)$ memory (here $n$ is the number of vertices and $W$ is the maximum edge weight), designed by Paz and Schwartzman [SODA, 2017]. Empirically, we show that the semi-streaming algorithms produce matchings whose weight is close to the best $1/2$-approximate offline algorithm while requiring less time and an order-of-magnitude less memory. For minimum weighted edge cover, we develop three novel semi-streaming algorithms. Two of these algorithms require a single pass through the input graph, require $O(n \log n)$ memory, and provide a 2-approximation guarantee on the objective. We also leverage a relationship between approximate maximum weighted matching and approximate minimum weighted edge cover to develop a two-pass $3/2+\epsilon$-approximate algorithm with the memory requirement of Paz and Schwartzman's semi-streaming matching algorithm. These streaming approaches are compared against the state-of-the-art 3/2-approximate offline algorithm. The semi-streaming matching and the novel edge cover algorithms proposed in this paper can process graphs with several billions of edges in under 30 minutes using 6 GB of memory, which is at least an order of magnitude improvement from the offline (non-streaming) algorithms. For the largest graph, the best alternative offline parallel approximation algorithm (GPA+ROMA) could not finish in three hours even while employing hundreds of processors and 1 TB of memory. We also demonstrate an application of the semi-streaming algorithm by computing a matching using linearly bounded memory on item intersection graphs derived from three machine learning datasets, whereas the existing offline algorithms could not complete on one of these datasets since their memory requirements exceeded 1TB.