New method reveals insights about stochastic optimization methods using modified equations.
problem Understanding the qualitative behavior of stochastic optimization algorithms.
method Developed a class of stochastic differential equations to approximate the dynamics of stochastic optimization methods.
result Mean-square stability of the modified equation provides qualitative insights about stochastic coordinate descent.
Develops a new method for efficient stochastic bilevel optimization.
problem Stochastic bilevel optimization problems in machine learning applications.
method Single-Timescale stochAstic BiLevEl optimization (STABLE) method.
result Achieves the same order of sample complexity as stochastic gradient descent for single-level optimization.
New methods optimize complex optimization problems with improved efficiency.
problem Optimizing complex problems with a convex lower-level objective.
method Uses stochastic cutting planes and conditional gradient updates.
result Improves complexity for both convex and non-convex upper-level functions.
We show that asymptotically, completely asynchronous stochastic gradient procedures achieve optimal (even to constant factors) convergence rates for the solution of convex optimization problems under nearly the same conditions required for asymptotic optimality of standard stochastic gradient procedures. Roughly, the n…
Stochastic gradient methods can converge in expectation under heavy-tailed noise.
problem Convergence of stochastic gradient methods under heavy-tailed noise.
method Comprehensive study of stochastic optimization under heavy-tailed noise for extsfSGD, extsfSMD, extsfASMD, extsfSGDM in convex and nonconvex optimization. result Established in-expectation convergence results for various stochastic gradient methods.
Stochastic gradient descent (\textsc{Sgd}) methods are the most powerful optimization tools in training machine learning and deep learning models. Moreover, acceleration (a.k.a. momentum) methods and diagonal scaling (a.k.a. adaptive gradient) methods are the two main techniques to improve the slow convergence of \text…
In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA c…
We improve optimization for data with varying variance.
problem Optimizing data with varying variance.
method Generalized learning and optimization frameworks for data-driven optimization.
result Asymptotic and finite sample guarantees for stochastic programs.
Stochastic compositional optimization arises in many important machine learning tasks such as value function evaluation in reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic functions, and is more challenging to optimize than vanilla stochastic o…
Paper develops efficient methods for estimating Hessian inverses in stochastic optimization.
problem Estimating the inverse Hessian for convex function minimization.
method Robbins-Monro procedure for recursive estimation of the inverse Hessian.
result Develops universal stochastic Newton methods with improved efficiency.
New method improves zeroth-order stochastic optimization with adaptive sampling.
problem Optimization problems without gradient information.
method Adaptive sampling quasi-Newton method using finite differences.
result Significant improvement in performance with adaptive sample sizes.
The paper connects higher order risk measures and stochastic dominance, showing their equivalence and integrating them with optimization.
problem Comparing and characterizing random outcomes in risk assessment.
method Exploring the equivalence between higher order risk measures and stochastic dominance, using stochastic optimization and expectiles as examples.
result Higher order risk measures and stochastic dominance are equivalent and can be used to characterize random outcomes.
Optimizes trading in markets with unpredictable price impacts.
problem Optimizing trading strategies in markets with stochastic price impacts.
method Singular perturbation methods to approximate optimal control problem.
result Proves approximations are accurate to specified order using sub- and super-solutions.
NOVAS uses adaptive stochastic search for non-convex optimization in deep networks.
problem Non-convex optimization challenges in deep neural networks.
method Adaptive stochastic search for non-convex optimization.
result NOVAS outperforms existing alternatives in a structured prediction task.
A new algorithm reduces communication rounds for distributed convex optimization.
problem Efficiently solving convex optimization problems in distributed systems.
method Proposes a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization.
result Reduces the number and frequency of communication rounds compared to existing methods.
A new hybrid algorithm reduces stochastic gradient evaluations for nonconvex optimization.
problem Solving stochastic composite nonconvex optimization problems efficiently.
method Proposes a new hybrid variance-reduced proximal gradient method with a stochastic gradient estimator.
result Achieves optimal stochastic oracle complexity bound with one less gradient evaluation.
Optimized method tackles convex optimization with heavy-tailed noise.
problem Convex optimization problems with noisy gradients.
method Vanilla stochastic proximal subgradient method without gradient clipping or normalization.
result Achieves optimal complexity for various convex optimization types under heavy-tailed noise.
Paper improves learning rates for SGD and NAG.
problem Generalization performance of stochastic optimization algorithms.
method Establishes new learning rates for SGD and NAG.
result Improved guarantees in some settings or comparable rates under weaker assumptions.
We study local complexity measures for stochastic convex optimization problems, providing a local minimax theory analogous to that of Hájek and Le Cam for classical statistical problems. We give complementary optimality results, developing fully online methods that adaptively achieve optimal convergence guarantees. Our…
PALS extends PAL for optimizing stochastic simulators efficiently.
problem Optimizing stochastic simulators with high output variance and expensive evaluations.
method Bayesian optimization with probabilistic models, extending PAL for stochastic settings.
result PALS outperforms other methods in optimizing stochastic simulators.
Many machine learning algorithms minimize a regularized risk, and stochastic optimization is widely used for this task. When working with massive data, it is desirable to perform stochastic optimization in parallel. Unfortunately, many existing stochastic optimization algorithms cannot be parallelized efficiently. In t…
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.
Stochastic cutting planes improve data-driven optimization speed.
problem Data-driven Mixed-Integer Nonlinear Optimization problems.
method Stochastic version of cutting-plane method.
result Stochastic algorithm converges to ε-optimal solution with high probability.
The paper relaxes assumptions for analyzing stochastic optimization algorithms.
problem Analyzing the convergence of stochastic gradient algorithms under weaker variance assumptions.
method Building on and extending a connection to the Halpern iteration, the paper analyzes algorithms for convex nonsmooth optimization and min-max problems.
result Rates for optimality measures are obtained without requiring boundedness of the feasible set for problems beyond simple constrained optimization.
Optimizes control of infectious disease spread using stochastic methods.
problem Optimizing control of highly infectious diseases like COVID-19.
method Reformulated Hamilton-Jacobi-Bellman equation as stochastic minimum principle, leading to forward-backward stochastic differential equations.
result Numerous numerical solutions presented under various scenarios.
We study online convex optimization under stochastic sub-gradient observation faults, where we introduce adaptive algorithms with minimax optimal regret guarantees. We specifically study scenarios where our sub-gradient observations can be noisy or even completely missing in a stochastic manner. To this end, we propose…
This paper proposes the first-ever algorithmic framework for tuning hyper-parameters of stochastic optimization algorithm based on reinforcement learning. Hyper-parameters impose significant influences on the performance of stochastic optimization algorithms, such as evolutionary algorithms (EAs) and meta-heuristics. Y…
This paper provides a unifying theoretical framework for stochastic optimization algorithms by means of a latent stochastic variational problem. Using techniques from stochastic control, the solution to the variational problem is shown to be equivalent to that of a Forward Backward Stochastic Differential Equation (FBS…
Enhanced ROOT-SGD optimizes stochastic optimization with diminishing stepsizes.
problem Improving statistical efficiency in stochastic optimization.
method Integrates a diminishing stepsize strategy into ROOT-SGD.
result Achieves optimal convergence rates with improved stability and precision.
Optimizes CM for stochastic convex optimization with progressive precision.
problem Stochastic nature of objective function in convex optimization.
method Iterative coordinate minimization with optimal precision control.
result Order-optimal regret performance for strongly convex and nonsmooth functions.
New adaptive step-size method for convex optimization without tuning.
problem Optimizing convex functions efficiently with stochastic gradients.
method Adapted Adaptive Gradient Descent Without Descent to stochastic setting.
result Stochastic gradient descent converges under various assumptions.
Study shows Stochastic Mirror Descent optimizes convex problems with infinite noise variance.
problem Optimizing convex problems with infinite noise variance.
method Stochastic Mirror Descent algorithm with uniformly convex mirror maps.
result Demonstrates convergence rate quantified in terms of iterations, dimensionality, and geometric parameters.
Bayesian approach to optimal transport with stochastic costs.
problem Inferring optimal transport plans with uncertain costs.
method Bayesian framework and Hamiltonian Monte Carlo (HMC) sampling.
result Inference of optimal transport plans under stochastic cost functions.
New framework improves stochastic optimization for variational inference.
problem Improving variational posterior approximations in high-dimensional models.
method Developed a robust stochastic optimization framework using Markov chains.
result Demonstrated improved accuracy and robustness across diverse models.
GeoAdaLer enhances geometric understanding of Adam for stochastic optimization.
problem Understanding geometric principles behind Adam's success in stochastic optimization.
method Introduces GeoAdaLer, an adaptive learning method based on geometric properties.
result Extends interpretability and effectiveness in complex optimization scenarios.
Study proves optimal controls for stochastic Volterra equations with singular kernels.
problem Existence of optimal controls for stochastic Volterra equations with singular kernels.
method Sufficient conditions based on integrability and growth hypotheses.
result Existence of optimal relaxed and strict controls under classical convexity assumptions.
Optimization is becoming increasingly common in scientific and engineering domains. Oftentimes, these problems involve various levels of stochasticity or uncertainty in generating proposed solutions. Therefore, optimization in these scenarios must consider this stochasticity to properly guide the design of future exper…
We study PCA as a stochastic optimization problem and propose a novel stochastic approximation algorithm which we refer to as "Matrix Stochastic Gradient" (MSG), as well as a practical variant, Capped MSG. We study the method both theoretically and empirically.
We analyze convergence rates of stochastic optimization procedures for non-smooth convex optimization problems. By combining randomized smoothing techniques with accelerated gradient methods, we obtain convergence rates of stochastic optimization procedures, both in expectation and with high probability, that have opti…
Proposes reducing random error in stochastic optimization by variance regularization.
problem Random error accumulation in stochastic optimization algorithms.
method Regularizes learning-rate based on mini-batch variances.
result Speeds up convergence and stabilizes stochastic optimization.
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…
New method relaxes optimization problems to find solutions more reliably.
problem Optimizing functions with stochastic or non-differentiable elements.
method Using measure theory and Fourier analysis to impose structure on optimization problems.
result Consistency of optimal values, Lipschitzness of gradients, and convexity are key traits for fast and reliable optimization.
First-order method solves stochastic bilevel optimization with linear constraints.
problem Stochastic bilevel optimization with linear constraints and noise.
method Developed a novel framework using gradient-based techniques and smoothed penalty functions.
result Achieved finite-time convergence guarantees for (δ,ε)-Goldstein stationary points. Derives optimal control conditions using calculus of variations.
problem Optimizing Markov control in stochastic control problems.
method Calculus of variations approach to derive necessary conditions.
result Solves the Merton portfolio optimization problem.
Optimizes reinsurance and investment strategies to minimize ruin probability.
problem Optimizing reinsurance and investment strategies to minimize ruin probability.
method Stochastic projected gradient method based on Malliavin calculus.
result Effectiveness of the proposed method demonstrated through numerical experiments.
In this paper, we study stochastic non-convex optimization with non-convex random functions. Recent studies on non-convex optimization revolve around establishing second-order convergence, i.e., converging to a nearly second-order optimal stationary points. However, existing results on stochastic non-convex optimizatio…
A new method for stochastic optimal control improves accuracy over existing techniques.
problem Improving the accuracy of stochastic optimal control for noisy systems.
method Stochastic Optimal Control Matching (SOCM) using Iterative Diffusion Optimization (IDO) with path-wise reparameterization trick.
result SOCM achieves lower error than existing techniques for three out of four control problems, sometimes by an order of magnitude.
A new stochastic method tackles bi-level optimization problems in deep learning.
problem Bi-level optimization problems in deep learning, including hyperparameter optimization and meta learning.
method Turning a BLO problem into a stochastic optimization, using SGLD MCMC and a recurrent algorithm to compute MC-estimated hypergradient.
result Our method is more robust to suboptimal inner optimization and non-unique inner minima, leading to more reliable solutions.