A stochastic line search method with expected complexity analysis
From MaRDI portal
(Redirected from Publication:5215517)
Abstract: For deterministic optimization, line-search methods augment algorithms by providing stability and improved efficiency. We adapt a classical backtracking Armijo line-search to the stochastic optimization setting. While traditional line-search relies on exact computations of the gradient and values of the objective function, our method assumes that these values are available up to some dynamically adjusted accuracy which holds with some sufficiently large, but fixed, probability. We show the expected number of iterations to reach a near stationary point matches the worst-case efficiency of typical first-order methods, while for convex and strongly convex objective, it achieves rates of deterministic gradient descent in function values.
Recommendations
- Probabilistic line searches for stochastic optimization
- A nonmonotone line search method for stochastic optimization problems
- Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums
Cites work
- A Stochastic Approximation Method
- Adaptive sampling strategies for stochastic optimization
- Adaptive stepsizes for recursive estimation with applications in approximate dynamic programming
- Adaptive subgradient methods for online learning and stochastic optimization
- An introduction to matrix concentration inequalities
- Convergence of trust-region methods based on probabilistic models
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Hybrid deterministic-stochastic methods for data fitting
- Minimization of functions having Lipschitz continuous first partial derivatives
- Probabilistic line searches for stochastic optimization
- Sample size selection in optimization methods for machine learning
- Stochastic optimization using a trust-region method and random models
Cited in
(71)- Stochastic mesh adaptive direct search for blackbox optimization using probabilistic estimates
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives
- Expected complexity analysis of stochastic direct-search
- Linesearch Newton-CG methods for convex optimization with noise
- A stochastic first-order trust-region method with inexact restoration for finite-sum minimization
- An inexact restoration-nonsmooth algorithm with variable accuracy for stochastic nonsmooth convex optimization problems in machine learning and stochastic linear complementarity problems
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- Parameter calibration in wake effect simulation model with stochastic gradient descent and stratified sampling
- Constrained stochastic blackbox optimization using a progressive barrier and probabilistic estimates
- Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
- The impact of noise on evaluation complexity: the deterministic trust-region case
- Probabilistic line searches for stochastic optimization
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise
- Optimization of stochastic blackboxes with adaptive precision
- Stochastic analysis of an adaptive cubic regularization method under inexact gradient evaluations and dynamic Hessian accuracy
- A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization
- Stochastic trust-region methods with trust-region radius depending on probabilistic models
- Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions
- SSLC: A Search Algorithm Based on Linear Collisions and Poisson Probability Distribution
- Analysis of the BFGS Method with Errors
- Derivative-free optimization methods
- Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
- Inexact SARAH algorithm for stochastic optimization
- LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums
- An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians
- Zeroth-order optimization with orthogonal random directions
- A stochastic gradient method for a class of nonlinear PDE-constrained optimal control problems under uncertainty
- Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programming
- A trust region method for noisy unconstrained optimization
- Direct Search Based on Probabilistic Descent in Reduced Spaces
- A simplified convergence theory for Byzantine resilient stochastic gradient descent
- Adaptive step size rules for stochastic optimization in large-scale learning
- Stochastic regularized Newton methods for nonlinear equations
- A line search based proximal stochastic gradient algorithm with dynamical variance reduction
- Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques
- A line search improvement of efficient MPC
- Stochastic trust-region and direct-search methods: a weak tail bound condition and reduced sample sizing
- A fast non-monotone line search for stochastic gradient descent
- High probability complexity bounds for adaptive step search based on stochastic oracles
- Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
- A stochastic gradient method with variance control and variable learning rate for deep learning
- Subsampled first-order optimization methods with applications in imaging
- First- and second-order high probability complexity bounds for trust-region methods with noisy oracles
- Bolstering stochastic gradient descent with model building
- AN-SPS: adaptive sample size nonmonotone line search spectral projected subgradient method for convex constrained optimization problems
- A sequential quadratic programming method with high-probability complexity bounds for nonlinear equality-constrained stochastic optimization
- SketchySGD: reliable stochastic optimization via randomized curvature estimates
- Sample complexity analysis for adaptive optimization algorithms with stochastic oracles
- A line search framework with restarting for noisy optimization problems
- Complexity and performance for two classes of noise-tolerant first-order algorithms
- Variable metric proximal stochastic gradient methods with additional sampling
- Direct-search methods in the year 2025: theoretical guarantees and algorithmic paradigms
- Inexact Gauss-Newton methods with matrix approximation by sampling for nonlinear least-squares and systems
- Blackbox simulation optimization
- Parameter estimation of bilinear state-space systems with nonlinear input via enhanced Nadam algorithm by line search method
- Complexity of zeroth- and first-order stochastic trust-region algorithms
- A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
- Data farming the parameters of simulation-optimization solvers
- Line-search based optimization using function approximations with tunable accuracy
- Inexact Riemannian gradient descent method for nonconvex optimization with strong convergence
- A stochastic objective-function-free adaptive regularization method with optimal complexity
- Convergence analysis of a proximal stochastic gradient algorithm with adaptive sampling for non-convex and non-smooth composite optimization problems
- The stochastic conjugate subgradient algorithm for kernel support vector machines
- Stochastic ISTA/FISTA adaptive step search algorithms for convex composite optimization
- A variable dimension sketching strategy for nonlinear least-squares
- A survey of trust-region radius update mechanisms. Part I: First-order analysis
- An inexact first-order descent method with general directions: theory and applications to DE-constrained optimization
- On the convergence of interior-point methods for bound-constrained nonlinear optimization problems with noise
- A discussion on variational analysis in derivative-free optimization
This page was built for publication: A stochastic line search method with expected complexity analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215517)
