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

## Stochastic algorithms assessment using performance profiles

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.

Link permanente para citações:

## Phase stability analysis of liquid-liquid equilibrium with stochastic methods

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.

Link permanente para citações:

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

Fonte: Frontiers Research Foundation
Publicador: Frontiers Research Foundation

Tipo: Artigo de Revista Científica

Publicado em //2013
EN

Relevância na Pesquisa

36.27%

#Short term synaptic dynamics#short term depression#facilitation#stochastic simulation#stochastic synapse#vesicle site model#synaptic plasticity models#short term plasticity

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...

Link permanente para citações:

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

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 24/06/2015

Relevância na Pesquisa

56.29%

#Statistics - Machine Learning#Computer Science - Data Structures and Algorithms#Computer Science - Learning

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.

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 05/06/2015

Relevância na Pesquisa

36.31%

#Computer Science - Learning#Computer Science - Data Structures and Algorithms#Mathematics - Optimization and Control#Statistics - Machine Learning

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.

Link permanente para citações:

## Non-negative submodular stochastic probing via stochastic contention resolution schemes

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.

Link permanente para citações:

## Learning Equilibria in Games by Stochastic Distributed Algorithms

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...

Link permanente para citações:

## Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 24/07/2015

Relevância na Pesquisa

36.27%

#Statistics - Machine Learning#Computer Science - Distributed, Parallel, and Cluster Computing#Computer Science - Data Structures and Algorithms#Computer Science - Learning#Mathematics - Optimization and Control

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

Link permanente para citações:

## Almost sure convergence of randomly truncated stochastic algorithms under verifiable conditions

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

Link permanente para citações:

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

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

Link permanente para citações:

## Asymptotic normality of randomly truncated stochastic algorithms

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.

Link permanente para citações:

## Feasibility Study of Stochastic Streaming with 4K UHD Video Traces

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

Link permanente para citações:

## Splash: User-friendly Programming Interface for Parallelizing Stochastic Algorithms

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

Link permanente para citações:

## Fast Algorithms for Online Stochastic Convex Programming

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 28/10/2014

Relevância na Pesquisa

36.3%

#Computer Science - Learning#Computer Science - Data Structures and Algorithms#Mathematics - Optimization and Control#F.1.2#G.1.6

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

Link permanente para citações:

## Linear-scaling and parallelizable algorithms for stochastic quantum chemistry

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

36.32%

#Physics - Computational Physics#Condensed Matter - Strongly Correlated Electrons#Physics - Chemical Physics

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...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

46.17%

#Mathematics - Numerical Analysis#Computer Science - Numerical Analysis#Mathematics - Statistics Theory#Statistics - Applications#65C20, 65C05, 60E05, 68W20

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.

Link permanente para citações:

## Stochastic Optimization for Machine Learning

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...

Link permanente para citações:

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

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...

Link permanente para citações:

## Asymptotic normality of randomly truncated stochastic algorithms

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.

Link permanente para citações: