The paper guarantees global stability for stochastic subgradient methods in nonsmooth nonconvex optimization.
problem Minimizing nonsmooth nonconvex functions with convergence guarantees.
method Developed a framework for stochastic subgradient methods with global stability guarantees.
result Iterates are uniformly bounded and asymptotically stabilize around the stable set of the differential inclusion.
The paper develops methods to analyze sensitivity in stochastic models using surrogate models.
problem Quantifying the impact of input variability on stochastic simulators with randomness.
method The authors propose using generalized lambda models to emulate response distributions of stochastic simulators and estimate sensitivity indices.
result The proposed method can estimate sensitivity indices even with strong heteroskedasticity and small signal-to-noise ratio.
Paper introduces stochastic HJB on Jacobi structures.
problem Stochastic analysis on Jacobi manifolds.
method Global stochastic analysis techniques, extending Bismut and Lázaro-Camí work.
result Proposes a stochastic HJB framework.
SGD converges to global minimum for certain non-convex functions.
problem Theoretical challenges in optimizing non-convex functions in machine learning.
method Perturbed SGD on a broad class of non-convex functions.
result SGD converges to global minimum for certain non-convex functions.
Derivative-free method solves stochastic optimization problems with noisy objectives and constraints.
problem Solving nonlinear optimization problems with stochastic objectives and deterministic constraints using only zero-order information.
method Derivative-Free Stochastic Sequential Quadratic Programming (DF-SSQP) method using simultaneous perturbation stochastic approximation (SPSA) for gradient and Hessian estimation.
result Global almost-sure convergence of the DF-SSQP method under standard assumptions, with local asymptotic normality and statistical inference.
We present a unified framework to analyze the global convergence of Langevin dynamics based algorithms for nonconvex finite-sum optimization with n component functions. At the core of our analysis is a direct analysis of the ergodicity of the numerical approximations to Langevin dynamics, which leads to faster conver…
Paper analyzes SHB method for neural networks, proving stability, connectivity, and global convergence.
problem Theoretical understanding of SHB method for neural networks.
method Mean-field analysis of SHB dynamics related to a partial differential equation.
result SHB method converges to global optimum and exhibits stability and connectivity.
NSGLD improves SGLD for non-convex optimization problems.
problem Optimizing non-convex objectives efficiently.
method Introducing non-reversible SGLD by adding an anti-symmetric matrix to the drift term of the Langevin diffusion.
result NSGLD converges faster to the same stationary distribution with non-asymptotic guarantees.
Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) is a momentum version of stochastic gradient descent with properly injected Gaussian noise to find a global minimum. In this paper, non-asymptotic convergence analysis of SGHMC is given in the context of non-convex optimization, where subsampling techniques are used o…
Studied SGD convergence under weak conditions.
problem Convergence of SGD in nonconvex optimization.
method Analyzed biased nonconvex SGD under mild conditions.
result Provided convergence rates and complexities.
New algorithm tackles stochastic optimization with inequality constraints.
problem Stochastic optimization with inequality constraints in various applications.
method Active-set stochastic sequential quadratic programming (StoSQP) with a differentiable exact augmented Lagrangian.
result Global convergence for any initialization, KKT residuals converge to zero almost surely.
New model for pairwise comparisons without stochastic transitivity.
problem Suboptimal performance of models assuming stochastic transitivity in real-world scenarios.
method Proposes a general family of statistical models using a skew-symmetric matrix.
result Achieves minimax-rate optimality and adapts to data sparsity.
We consider the minimization of an objective function given access to unbiased estimates of its gradient through stochastic gradient descent (SGD) with constant step-size. While the detailed analysis was only performed for quadratic functions, we provide an explicit asymptotic expansion of the moments of the averaged S…
We study nonconvex finite-sum problems and analyze stochastic variance reduced gradient (SVRG) methods for them. SVRG and related methods have recently surged into prominence for convex optimization given their edge over stochastic gradient descent (SGD); but their theoretical analysis almost exclusively assumes convex…
Paper analyzes Scaffold algorithm for federated learning, proving linear speed-up with stochastic gradients.
problem Understanding the impact of stochastic gradients on the Scaffold algorithm's performance.
method Proved linear speed-up in the number of clients using a Markov chain analysis of global parameters and control variates.
result Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size, but retains a higher-order bias.
In this paper, we study the problems of principal Generalized Eigenvector computation and Canonical Correlation Analysis in the stochastic setting. We propose a simple and efficient algorithm, Gen-Oja, for these problems. We prove the global convergence of our algorithm, borrowing ideas from the theory of fast-mixing M…
Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite, number of loss functions. In this paper, we propose a novel Riemannian extension of the Euclidean stochastic variance reduced gradient algorithm (R-SVRG) to a compact manifold search space. To this e…
Diffusion approximation provides weak approximation for stochastic gradient descent algorithms in a finite time horizon. In this paper, we introduce new tools motivated by the backward error analysis of numerical stochastic differential equations into the theoretical framework of diffusion approximation, extending the …
In recent years, stochastic variance reduction algorithms have attracted considerable attention for minimizing the average of a large but finite number of loss functions. This paper proposes a novel Riemannian extension of the Euclidean stochastic variance reduced gradient (R-SVRG) algorithm to a manifold search space.…
Geodesic convexity generalizes the notion of (vector space) convexity to nonlinear metric spaces. But unlike convex optimization, geodesically convex (g-convex) optimization is much less developed. In this paper we contribute to the understanding of g-convex optimization by developing iteration complexity analysis for …
SGD with machine learning noise converges to global minimum exponentially fast.
problem Optimizing machine learning models with stochastic gradient descent.
method Analysis of SGD with machine learning noise, focusing on energy landscapes and gradient noise.
result SGD converges to the global minimum exponentially fast under certain conditions.
New approach uses SGLD to minimize CVaR for portfolio weights.
problem Minimizing CVaR for portfolio weights with complete theoretical guarantees.
method Stochastic Gradient Langevin Dynamics (SGLD) with discontinuous updating.
result Theoretical guarantees for convergence in Wasserstein distances for convex and non-convex functions.
Multiview representation learning is very popular for latent factor analysis. It naturally arises in many data analysis, machine learning, and information retrieval applications to model dependent structures among multiple data sources. For computational convenience, existing approaches usually formulate the multiview …
Improved convergence analysis for decentralized non-convex optimization.
problem Minimizing a sum of smooth non-convex functions over a network.
method Gradient tracking in decentralized stochastic gradient descent (GT-DSGD).
result GT-DSGD achieves network-independent performances matching centralized SGD under certain conditions.
StoSOO optimistically maximizes noisy, locally smooth functions.
problem Global maximization of noisy, locally smooth functions with unknown semi-metric.
method StoSOO uses optimistic upper confidence bounds to iteratively decide on the next evaluation point.
result StoSOO performs almost as well as the best tuned algorithms, even without knowing the semi-metric.
Solving statistical learning problems often involves nonconvex optimization. Despite the empirical success of nonconvex statistical optimization methods, their global dynamics, especially convergence to the desirable local minima, remain less well understood in theory. In this paper, we propose a new analytic paradigm …
We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allo…
Stochastic Gradient Langevin Dynamics (SGLD) is a popular variant of Stochastic Gradient Descent, where properly scaled isotropic Gaussian noise is added to an unbiased estimate of the gradient at each iteration. This modest change allows SGLD to escape local minima and suffices to guarantee asymptotic convergence to g…
New scalable MARL framework for dynamic networked systems.
problem Scalability in multi-agent reinforcement learning with dynamic dependencies.
method Scalable Actor Critic framework for non-local and stochastic dependencies.
result Finite-time error bound showing convergence rate dependence on information spread speed.
We analyze single-layer neural networks with the Xavier initialization in the asymptotic regime of large numbers of hidden units and large numbers of stochastic gradient descent training steps. The evolution of the neural network during training can be viewed as a stochastic system and, using techniques from stochastic…
Stochastic gradient Markov chain Monte Carlo (SG-MCMC) methods are Bayesian analogs to popular stochastic optimization methods; however, this connection is not well studied. We explore this relationship by applying simulated annealing to an SGMCMC algorithm. Furthermore, we extend recent SG-MCMC methods with two key co…
We prove a geometrically meaningful stochastic representation of the derivative of the heat semigroup on sub-Riemannian manifolds with tranverse symmetries. This representation is obtained from the study of Bochner-Weitzenbock type formulas for sub-Laplacians on 1-forms. As a consequence, we prove new hypoelliptic heat…
Study applies Gai-Kapadia framework to global equity markets to assess systemic risk and default cascades.
problem Assessing systemic risk and default cascades in global equity markets.
method Used Gai-Kapadia framework, 20-asset network, Monte Carlo simulations, and deterministic propagation analysis.
result High clustering among Brazilian assets leads to localized contagion, while developed markets show resilience.
New algorithms improve privacy in bandit problems with partial information.
problem Privacy constraints in multi-armed bandit problems with partial reward information.
method Proposed a generic framework for designing ε-global DP extensions of UCB and KL-UCB algorithms. result AdaP-KLUCB algorithm achieves optimal regret bound under ε-global DP constraints. New approach combines PCA and t-sne for better data analysis.
problem Multiscale complexity in high-dimensional data.
method Multiscale joint characterization using PCA and t-sne.
result Joint characterization detects signals not seen by PCA or t-sne alone.
Probability versions of Li-Yau inequalities for manifolds with boundary.
problem Establishing Li-Yau inequalities for manifolds with non-convex boundaries.
method Stochastic analysis and Bakry-Emery curvature-dimension approach.
result Explicit probability versions of Li-Yau inequalities for manifolds with boundary.
Averaged SGD achieves optimal convergence rate for neural networks in the NTK regime.
problem Convergence analysis of averaged stochastic gradient descent for neural networks.
method Analyzed convergence of averaged stochastic gradient descent for overparameterized two-layer neural networks.
result Achieved minimax optimal convergence rate with global convergence guarantee.
Study shows how deep residual networks can be analyzed as shallow network ensembles for optimization.
problem Understanding why deep neural networks can be trained to zero loss despite non-convex optimization landscapes.
method Mean-field analysis of deep residual networks, focusing on their continuum limit as a two-layer network.
result Derives the first global convergence result for multilayer neural networks in the mean-field regime.
New algorithm optimizes stochastic optimization with circular dependency.
problem Circular dependency between decision variable and importance sampling.
method Single-loop stochastic approximation algorithm based on Nesterov's dual averaging.
result Achieves minimal asymptotic variance and resolves circular optimization challenge.
A recent line of research has shown that gradient-based algorithms with random initialization can converge to the global minima of the training loss for over-parameterized (i.e., sufficiently wide) deep neural networks. However, the condition on the width of the neural network to ensure the global convergence is very s…
Stochastic gradient descent (SGD) has been found to be surprisingly effective in training a variety of deep neural networks. However, there is still a lack of understanding on how and why SGD can train these complex networks towards a global minimum. In this study, we establish the convergence of SGD to a global minimu…
When using stochastic gradient descent to solve large-scale machine learning problems, a common practice of data processing is to shuffle the training data, partition the data across multiple machines if needed, and then perform several epochs of training on the re-shuffled (either locally or globally) data. The above …
We analyze stochastic algorithms for optimizing nonconvex, nonsmooth finite-sum problems, where the nonconvex part is smooth and the nonsmooth part is convex. Surprisingly, unlike the smooth case, our knowledge of this fundamental problem is very limited. For example, it is not known whether the proximal stochastic gra…
Develops a flexible deep autoencoding topic model with scalable hybrid Bayesian inference.
problem Flexible and interpretable document analysis models.
method DATM with hybrid Bayesian inference, including topic-layer-adaptive stochastic gradient Riemannian MCMC and Weibull variational encoder.
result Demonstrates scalability and efficacy on big corpora in unsupervised and supervised learning tasks.
Paper improves a method for fast global and local convergence in optimization.
problem Slow global convergence in optimization methods with noisy Hessian estimates.
method Stochastic Newton Proximal Extragradient method using HPE framework.
result Faster global linear rate and superlinear convergence in fewer iterations.
This paper analyses the implementation and calibration of the Heston Stochastic Volatility Model. We first explain how characteristic functions can be used to estimate option prices. Then we consider the implementation of the Heston model, showing that relatively simple solutions can lead to fast and accurate vanilla o…
We consider parallel global optimization of derivative-free expensive-to-evaluate functions, and propose an efficient method based on stochastic approximation for implementing a conceptual Bayesian optimization algorithm proposed by Ginsbourger et al. (2007). At the heart of this algorithm is maximizing the information…
We consider maximum likelihood estimation for Gaussian Mixture Models (Gmms). This task is almost invariably solved (in theory and practice) via the Expectation Maximization (EM) algorithm. EM owes its success to various factors, of which is its ability to fulfill positive definiteness constraints in closed form is of …