Página 1 dos resultados de 2075 itens digitais encontrados em 0.010 segundos

Stochastic algorithms assessment using performance profiles

Costa, L.; Espírito Santo, I. A. C. P.; Oliveira, Pedro
Fonte: ACM Publicador: ACM
Tipo: Conferência ou Objeto de Conferência
Publicado em //2011 ENG
Relevância na Pesquisa
66.39%
Optimization with stochastic algorithms has become a relevant approach, specially, in problems with complex search spaces. Due to the stochastic nature of these algorithms, the assessment and comparison is not straightforward. Several performance measures have been proposed to overcome this difficulty. In this work, the use of performance profiles and an analysis integrating a trade-off between accuracy and precision are carried out for the comparison of two stochastic algorithms. Traditionally, performance profiles are used to compare deterministic algorithms. This methodology is applied in the comparison of two stochastic algorithms - genetic algorithms and simulated annealing. The results highlight the advantages and drawbacks of the proposed assessment.

Phase stability analysis of liquid-liquid equilibrium with stochastic methods

Nagatani,G.; Ferrari,J.; Cardozo Filho,L.; Rossi,C. C. R. S.; Guirardello,R.; Oliveira,J. Vladimir; Corazza,M. L.
Fonte: Brazilian Society of Chemical Engineering Publicador: Brazilian Society of Chemical Engineering
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/09/2008 EN
Relevância na Pesquisa
56.21%
Minimization of Gibbs free energy using activity coefficient models and nonlinear equation solution techniques is commonly applied to phase stability problems. However, when conventional techniques, such as the Newton-Raphson method, are employed, serious convergence problems may arise. Due to the existence of multiple solutions, several problems can be found in modeling liquid-liquid equilibrium of multicomponent systems, which are highly dependent on the initial guess. In this work phase stability analysis of liquid-liquid equilibrium is investigated using the NRTL model. For this purpose, two distinct stochastic numerical algorithms are employed to minimize the tangent plane distance of Gibbs free energy: a subdivision algorithm that can find all roots of nonlinear equations for liquid-liquid stability analysis and the Simulated Annealing method. Results obtained in this work for the two stochastic algorithms are compared with those of the Interval Newton method from the literature. Several different binary and multicomponent systems from the literature were successfully investigated.

Mathematical analysis and algorithms for efficiently and accurately implementing stochastic simulations of short-term synaptic depression and facilitation

McDonnell, M.D.; Mohan, A.; Stricker, C.
Fonte: Frontiers Research Foundation Publicador: Frontiers Research Foundation
Tipo: Artigo de Revista Científica
Publicado em //2013 EN
Relevância na Pesquisa
36.27%
The release of neurotransmitter vesicles after arrival of a pre-synaptic action potential (AP) at cortical synapses is known to be a stochastic process, as is the availability of vesicles for release. These processes are known to also depend on the recent history of AP arrivals, and this can be described in terms of time-varying probabilities of vesicle release. Mathematical models of such synaptic dynamics frequently are based only on the mean number of vesicles released by each pre-synaptic AP, since if it is assumed there are sufficiently many vesicle sites, then variance is small. However, it has been shown recently that variance across sites can be significant for neuron and network dynamics, and this suggests the potential importance of studying short-term plasticity using simulations that do generate trial-to-trial variability. Therefore, in this paper we study several well-known conceptual models for stochastic availability and release. We state explicitly the random variables that these models describe and propose efficient algorithms for accurately implementing stochastic simulations of these random variables in software or hardware. Our results are complemented by mathematical analysis and statement of pseudo-code algorithms.; Mark D. McDonnell...

An accelerated algorithm for discrete stochastic simulation of reaction–diffusion systems using gradient-based diffusion and tau-leaping

Koh, Wonryull; Blackwell, Kim T.
Fonte: American Institute of Physics Publicador: American Institute of Physics
Tipo: Artigo de Revista Científica
EN
Relevância na Pesquisa
36.3%
Stochastic simulation of reaction–diffusion systems enables the investigation of stochastic events arising from the small numbers and heterogeneous distribution of molecular species in biological cells. Stochastic variations in intracellular microdomains and in diffusional gradients play a significant part in the spatiotemporal activity and behavior of cells. Although an exact stochastic simulation that simulates every individual reaction and diffusion event gives a most accurate trajectory of the system's state over time, it can be too slow for many practical applications. We present an accelerated algorithm for discrete stochastic simulation of reaction–diffusion systems designed to improve the speed of simulation by reducing the number of time-steps required to complete a simulation run. This method is unique in that it employs two strategies that have not been incorporated in existing spatial stochastic simulation algorithms. First, diffusive transfers between neighboring subvolumes are based on concentration gradients. This treatment necessitates sampling of only the net or observed diffusion events from higher to lower concentration gradients rather than sampling all diffusion events regardless of local concentration gradients. Second...

Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

Frostig, Roy; Ge, Rong; Kakade, Sham M.; Sidford, Aaron
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/06/2015
Relevância na Pesquisa
56.29%
We develop a family of accelerated stochastic algorithms that minimize sums of convex functions. Our algorithms improve upon the fastest running time for empirical risk minimization (ERM), and in particular linear least-squares regression, across a wide range of problem settings. To achieve this, we establish a framework based on the classical proximal point algorithm. Namely, we provide several algorithms that reduce the minimization of a strongly convex function to approximate minimizations of regularizations of the function. Using these results, we accelerate recent fast stochastic algorithms in a black-box fashion. Empirically, we demonstrate that the resulting algorithms exhibit notions of stability that are advantageous in practice. Both in theory and in practice, the provided algorithms reap the computational benefits of adding a large strongly convex regularization term, without incurring a corresponding bias to the original problem.

UniVR: A Universal Variance Reduction Framework for Proximal Stochastic Gradient Method

Allen-Zhu, Zeyuan; Yuan, Yang
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/06/2015
Relevância na Pesquisa
36.31%
We revisit an important class of composite stochastic minimization problems that often arises from empirical risk minimization settings, such as Lasso, Ridge Regression, and Logistic Regression. We present a new algorithm UniVR based on stochastic gradient descent with variance reduction. Our algorithm supports non-strongly convex objectives directly, and outperforms all of the state-of-the-art algorithms, including both direct algorithms (SAG, MISO, and SAGA) and indirect algorithms (SVRG, ProxSVRG, SDCA, ProxSDCA, and Finito) for such objectives. Our algorithm supports strongly convex objectives as well, and matches the best known linear convergence rate. Experiments support our theory. As a result, UniVR closes an interesting gap in the literature because all the existing direct algorithms for the non-strongly convex case perform much slower than the indirect algorithms. We thus believe that UniVR provides a unification between the strongly and the non-strongly convex stochastic minimization theories.

Non-negative submodular stochastic probing via stochastic contention resolution schemes

Adamczyk, Marek
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.27%
The abstract model of stochastic probing was presented by Gupta and Nagarajan (IPCO'13), and provides a unified view of a number of problems. Adamczyk, Sviridenko, Ward (STACS'14) gave better approximation for matroid environments and linear objectives. At the same time this method was easily extendable to settings, where the objective function was monotone submodular. However, the case of non-negative submodular function could not be handled by previous techniques. In this paper we address this problem, and our results are twofold. First, we adapt the notion of contention resolution schemes of Chekuri, Vondr\'ak, Zenklusen (SICOMP'14) to show that we can optimize non-negative submodular functions in this setting with a constant factor loss with respect to the deterministic setting. Second, we show a new contention resolution scheme for transversal matroids, which yields better approximations in the stochastic probing setting than the previously known tools. The rounding procedure underlying the scheme can be of independent interest --- Bansal, Gupta, Li, Mestre, Nagarajan, Rudra (Algorithmica'12) gave two seemingly different algorithms for stochastic matching and stochastic $k$-set packing problems with two different analyses, but we show that our single technique can be used to analyze both their algorithms.

Learning Equilibria in Games by Stochastic Distributed Algorithms

Bournez, Olivier; Cohen, Johanne
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/07/2009
Relevância na Pesquisa
36.3%
We consider a class of fully stochastic and fully distributed algorithms, that we prove to learn equilibria in games. Indeed, we consider a family of stochastic distributed dynamics that we prove to converge weakly (in the sense of weak convergence for probabilistic processes) towards their mean-field limit, i.e an ordinary differential equation (ODE) in the general case. We focus then on a class of stochastic dynamics where this ODE turns out to be related to multipopulation replicator dynamics. Using facts known about convergence of this ODE, we discuss the convergence of the initial stochastic dynamics: For general games, there might be non-convergence, but when convergence of the ODE holds, considered stochastic algorithms converge towards Nash equilibria. For games admitting Lyapunov functions, that we call Lyapunov games, the stochastic dynamics converge. We prove that any ordinal potential game, and hence any potential game is a Lyapunov game, with a multiaffine Lyapunov function. For Lyapunov games with a multiaffine Lyapunov function, we prove that this Lyapunov function is a super-martingale over the stochastic dynamics. This leads a way to provide bounds on their time of convergence by martingale arguments. This applies in particular for many classes of games that have been considered in literature...

Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

Mania, Horia; Pan, Xinghao; Papailiopoulos, Dimitris; Recht, Benjamin; Ramchandran, Kannan; Jordan, Michael I.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/07/2015
Relevância na Pesquisa
36.27%
We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyze asynchronous implementations of stochastic optimization algorithms.In this framework, asynchronous stochastic optimization algorithms can be thought of as serial methods operating on noisy inputs. Using our perturbed iterate framework, we provide new analyses of the Hogwild! algorithm and asynchronous stochastic coordinate descent, that are simpler than earlier analyses, remove many assumptions of previous models, and in some cases yield improved upper bounds on the convergence rates. We proceed to apply our framework to develop and analyze KroMagnon: a novel, parallel, sparse stochastic variance-reduced gradient (SVRG) algorithm. We demonstrate experimentally on a 16-core machine that the sparse and parallel version of SVRG is in some cases more than four orders of magnitude faster than the standard SVRG algorithm.; Comment: 25 pages

Almost sure convergence of randomly truncated stochastic algorithms under verifiable conditions

Lelong, Jérôme
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 06/06/2007
Relevância na Pesquisa
46.17%
We study the almost sure convergence of randomly truncated stochastic algorithms. We present a new convergence theorem which extends the already known results by making vanish the classical condition on the noise terms. The aim of this work is to prove an almost sure convergence result of randomly truncated stochastic algorithms under easily verifiable conditions

Stochastic Representations of Ion Channel Kinetics and Exact Stochastic Simulation of Neuronal Dynamics

Anderson, David F.; Ermentrout, Bard; Thomas, Peter J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.26%
In this paper we provide two representations for stochastic ion channel kinetics, and compare the performance of exact simulation with a commonly used numerical approximation strategy. The first representation we present is a random time change representation, popularized by Thomas Kurtz, with the second being analogous to a "Gillespie" representation. Exact stochastic algorithms are provided for the different representations, which are preferable to either (a) fixed time step or (b) piecewise constant propensity algorithms, which still appear in the literature. As examples, we provide versions of the exact algorithms for the Morris-Lecar conductance based model, and detail the error induced, both in a weak and a strong sense, by the use of approximate algorithms on this model. We include ready-to-use implementations of the random time change algorithm in both XPP and Matlab. Finally, through the consideration of parametric sensitivity analysis, we show how the representations presented here are useful in the development of further computational methods. The general representations and simulation strategies provided here are known in other parts of the sciences, but less so in the present setting.; Comment: 39 pages, 6 figures, appendix with XPP and Matlab code

Asymptotic normality of randomly truncated stochastic algorithms

Lelong, Jérôme
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 25/03/2010
Relevância na Pesquisa
46.09%
We study the convergence rate of randomly truncated stochastic algorithms, which consist in the truncation of the standard Robbins-Monro procedure on an increasing sequence of compact sets. Such a truncation is often required in practice to ensure convergence when standard algorithms fail because the expected-value function grows too fast. In this work, we give a self contained proof of a central limit theorem for this algorithm under local assumptions on the expected-value function, which are fairly easy to check in practice.

Feasibility Study of Stochastic Streaming with 4K UHD Video Traces

Kim, Joongheon; Ryu, Eun-Seok
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 17/11/2015
Relevância na Pesquisa
36.38%
This paper performs the feasibility study of stochastic video streaming algorithms with up-to-date 4K ultra-high-definition (UHD) video traces. In previous work, various stochastic video streaming algorithms were proposed which maximize time-average video streaming quality subject to queue stability based on the information of queue-backlog length. The performance improvements with the stochastic video streaming algorithms were verified with traditional MPEG test sequences; but there is no study how much the proposed stochastic algorithm is better when we consider up-to-date 4K UHD video traces. Therefore, this paper evaluates the stochastic streaming algorithms with 4K UHD video traces; and verifies that the stochastic algorithms perform better than queue-independent algorithms, as desired.; Comment: Presented at the International Conference on ICT Convergence (ICTC), Jeju Island, Korea, 28 - 30 October 2015

Splash: User-friendly Programming Interface for Parallelizing Stochastic Algorithms

Zhang, Yuchen; Jordan, Michael I.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.34%
Stochastic algorithms are efficient approaches to solving machine learning and optimization problems. In this paper, we propose a general framework called Splash for parallelizing stochastic algorithms on multi-node distributed systems. Splash consists of a programming interface and an execution engine. Using the programming interface, the user develops sequential stochastic algorithms without concerning any detail about distributed computing. The algorithm is then automatically parallelized by a communication-efficient execution engine. We provide theoretical justifications on the optimal rate of convergence for parallelizing stochastic gradient descent. Splash is built on top of Apache Spark. The real-data experiments on logistic regression, collaborative filtering and topic modeling verify that Splash yields order-of-magnitude speedup over single-thread stochastic algorithms and over state-of-the-art implementations on Spark.; Comment: redo experiments to learn bigger models; compare Splash with state-of-the-art implementations on Spark

Fast Algorithms for Online Stochastic Convex Programming

Agrawal, Shipra; Devanur, Nikhil R.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/10/2014
Relevância na Pesquisa
36.3%
We introduce the online stochastic Convex Programming (CP) problem, a very general version of stochastic online problems which allows arbitrary concave objectives and convex feasibility constraints. Many well-studied problems like online stochastic packing and covering, online stochastic matching with concave returns, etc. form a special case of online stochastic CP. We present fast algorithms for these problems, which achieve near-optimal regret guarantees for both the i.i.d. and the random permutation models of stochastic inputs. When applied to the special case online packing, our ideas yield a simpler and faster primal-dual algorithm for this well studied problem, which achieves the optimal competitive ratio. Our techniques make explicit the connection of primal-dual paradigm and online learning to online stochastic CP.; Comment: To appear in SODA 2015

Linear-scaling and parallelizable algorithms for stochastic quantum chemistry

Booth, George H.; Smart, Simon D.; Alavi, Ali
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.32%
For many decades, quantum chemical method development has been dominated by algorithms which involve increasingly complex series of tensor contractions over one-electron orbital spaces. Procedures for their derivation and implementation have evolved to require the minimum amount of logic and rely heavily on computationally efficient library-based matrix algebra and optimized paging schemes. In this regard, the recent development of exact stochastic quantum chemical algorithms to reduce computational scaling and memory overhead requires a contrasting algorithmic philosophy, but one which when implemented efficiently can often achieve higher accuracy/cost ratios with small random errors. Additionally, they can exploit the continuing trend for massive parallelization which hinders the progress of deterministic high-level quantum chemical algorithms. In the Quantum Monte Carlo community, stochastic algorithms are ubiquitous but the discrete Fock space of quantum chemical methods is often unfamiliar, and the methods introduce new concepts required for algorithmic efficiency. In this paper, we explore these concepts and detail an algorithm used for Full Configuration Interaction Quantum Monte Carlo (FCIQMC), which is implemented and available in MOLPRO and as a standalone code...

Assessing stochastic algorithms for large scale nonlinear least squares problems using extremal probabilities of linear combinations of gamma random variables

Roosta-Khorasani, Farbod; Székely, Gábor J.; Ascher, Uri
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.17%
This article considers stochastic algorithms for efficiently solving a class of large scale non-linear least squares (NLS) problems which frequently arise in applications. We propose eight variants of a practical randomized algorithm where the uncertainties in the major stochastic steps are quantified. Such stochastic steps involve approximating the NLS objective function using Monte-Carlo methods, and this is equivalent to the estimation of the trace of corresponding symmetric positive semi-definite (SPSD) matrices. For the latter, we prove tight necessary and sufficient conditions on the sample size (which translates to cost) to satisfy the prescribed probabilistic accuracy. We show that these conditions are practically computable and yield small sample sizes. They are then incorporated in our stochastic algorithm to quantify the uncertainty in each randomized step. The bounds we use are applications of more general results regarding extremal tail probabilities of linear combinations of gamma distributed random variables. We derive and prove new results concerning the maximal and minimal tail probabilities of such linear combinations, which can be considered independently of the rest of this paper.

Stochastic Optimization for Machine Learning

Cotter, Andrew
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/08/2013
Relevância na Pesquisa
36.28%
It has been found that stochastic algorithms often find good solutions much more rapidly than inherently-batch approaches. Indeed, a very useful rule of thumb is that often, when solving a machine learning problem, an iterative technique which relies on performing a very large number of relatively-inexpensive updates will often outperform one which performs a smaller number of much "smarter" but computationally-expensive updates. In this thesis, we will consider the application of stochastic algorithms to two of the most important machine learning problems. Part i is concerned with the supervised problem of binary classification using kernelized linear classifiers, for which the data have labels belonging to exactly two classes (e.g. "has cancer" or "doesn't have cancer"), and the learning problem is to find a linear classifier which is best at predicting the label. In Part ii, we will consider the unsupervised problem of Principal Component Analysis, for which the learning task is to find the directions which contain most of the variance of the data distribution. Our goal is to present stochastic algorithms for both problems which are, above all, practical--they work well on real-world data, in some cases better than all known competing algorithms. A secondary...

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

Deshpande, Amol; Hellerstein, Lisa; Kletenik, Devorah
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.32%
Stochastic Boolean Function Evaluation is the problem of determining the value of a given Boolean function f on an unknown input x, when each bit of x_i of x can only be determined by paying an associated cost c_i. The assumption is that x is drawn from a given product distribution, and the goal is to minimize the expected cost. This problem has been studied in Operations Research, where it is known as "sequential testing" of Boolean functions. It has also been studied in learning theory in the context of learning with attribute costs. We consider the general problem of developing approximation algorithms for Stochastic Boolean Function Evaluation. We give a 3-approximation algorithm for evaluating Boolean linear threshold formulas. We also present an approximation algorithm for evaluating CDNF formulas (and decision trees) achieving a factor of O(log kd), where k is the number of terms in the DNF formula, and d is the number of clauses in the CNF formula. In addition, we present approximation algorithms for simultaneous evaluation of linear threshold functions, and for ranking of linear functions. Our function evaluation algorithms are based on reductions to the Stochastic Submodular Set Cover (SSSC) problem. This problem was introduced by Golovin and Krause. They presented an approximation algorithm for the problem...

Asymptotic normality of randomly truncated stochastic algorithms

Lelong, Jérôme
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/03/2010
Relevância na Pesquisa
46.09%
We study the convergence rate of randomly truncated stochastic algorithms, which consist in the truncation of the standard Robbins-Monro procedure on an increasing sequence of compact sets. Such a truncation is often required in practice to ensure convergence when standard algorithms fail because the expected-value function grows too fast. In this work, we give a self contained proof of a central limit theorem for this algorithm under local assumptions on the expected-value function, which are fairly easy to check in practice.