Establishes geometric convergence of iterative optimization algorithms.
problem Analyzes convergence of iterative optimization algorithms under general assumptions.
method General framework for iterative optimization algorithms, proving asymptotic geometric convergence and providing convergence rates.
result Asymptotic geometric convergence of iterative optimization algorithms with exact rate.
PAGE optimizes nonconvex problems with optimal convergence rates.
problem Nonconvex optimization problems.
method PAGE algorithm for achieving optimal convergence rates.
result PAGE achieves optimal convergence rates for nonconvex optimization.
Adam optimizer converges to zeros of a new vector field, not just gradient zeros.
problem Prove convergence rates for Adam optimizer in simple quadratic optimization problems.
method Introduced Adam vector field to analyze Adam optimizer's convergence.
result Established optimal convergence rates for Adam optimizer.
Proof of convergence for multi-objective optimization using inverse reinforcement learning.
problem Proving convergence in multi-objective optimization problems.
method Wasserstein inverse reinforcement learning with projective subgradient method and gradient descent.
result Convergence of inverse reinforcement learning for multi-objective optimization.
This paper presents a Bayesian optimization method with exponential convergence without the need of auxiliary optimization and without the delta-cover sampling. Most Bayesian optimization methods require auxiliary optimization: an additional non-convex global optimization problem, which can be time-consuming and hard t…
Characterizes problems solvable via linear convergence algorithms.
problem Optimization problems solvable with linear convergence.
method Riemannian gradient descent.
result Characterized problems solvable via linear convergence.
New method uses momentum to converge in DC optimization with small batches.
problem Lack of convergence properties for stochastic difference-of-convex optimization with small batch sizes.
method Introduces momentum to enable convergence under standard assumptions for any batch size.
result Proves convergence of the algorithm under smoothness and bounded variance assumptions.
The paper studies convergence rates of Tsallis entropic regularization in optimal transport.
problem Optimal transport with regularization.
method Γ-convergence and quantization/shadow arguments.
result Derives convergence rate of Tsallis entropic regularization.
Proves weak convergence equals mean convergence in GGC.
problem Proving convergence in GGC distributions.
method Using generalized gamma convolution (GGC) and expected utility maximization.
result Weak convergence implies mean convergence in GGC.
GAIL with neural networks converges to global optima and has a known rate.
problem Uncertainty about GAIL with neural networks achieving global optimality.
method Gradient-based alternating updates algorithm.
result Established sublinear convergence to globally optimal solution.
New ODE models show saddle-point optimization methods converge differently, with last-iterate convergence for OGDA.
problem Analyzing convergence properties of saddle-point optimization methods.
method High-Resolution Differential Equations (HRDEs) to design differential equation models for saddle-point optimization methods.
result HRDEs reveal last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) in bilinear games.
Random permutations can offer faster convergence than with-replacement sampling for some functions.
problem Understanding when and how random permutations outperform with-replacement sampling in SGD convergence.
method Analyzing convergence rates for different function classes (1D strongly convex, general strongly convex, quadratic strongly convex).
result The optimal convergence gap between random and permutation-based SGD varies from exponential to nonexistent, depending on the function class.
This study shows the moment-SOS hierarchy converges in polynomial optimization over product of spheres.
problem Minimizing multihomogeneous polynomials over product of spheres.
method Moment-SOS hierarchy, local optimality conditions, differential geometry, Morse theory.
result The moment-SOS hierarchy has finite convergence for generic multihomogeneous objective functions.
New method accelerates optimization in fixed time, improving convergence rates.
problem Optimization in large-scale data-driven problems.
method Gradient-based optimization framework with fixed-time stable dynamical systems.
result Achieves convergence to the optimizer in a fixed number of iterations, independent of initialization.
This work establishes uniform convergence of subdifferentials in stochastic optimization.
problem Understanding how empirical stationary points approximate population ones in nonsmooth, nonconvex stochastic optimization.
method Reduction principle for weakly convex stochastic objectives, focusing on subgradient convergence.
result Sharp uniform convergence rates for subdifferential mappings in stochastic convex-composite optimization.
The paper analyzes convergence rates of bilevel optimization algorithms and introduces a new stochastic algorithm.
problem Nonconvex-strongly-convex bilevel optimization problems in machine learning.
method Comprehensive convergence rate analysis for deterministic bilevel optimization using AID and ITD, and a novel stochastic algorithm stocBiO.
result Theoretical convergence rates for AID and ITD methods, and stocBiO's superior performance.
The Sinkhorn-Knopp derivatives converge with linear rate.
problem Optimal transport problem with entropic regularization.
method Iterative proportional fitting procedure.
result Derivatives converge with linear rate.
New factorial power constants improve optimization convergence rates.
problem Optimization convergence rates depend on various constants.
method Proposes using factorial powers for defining these constants.
result Factorial powers simplify or improve convergence rates of optimization methods.
Frank-Wolfe optimization applied to a small deep network shows slower convergence compared to gradient descent.
problem Training deep neural networks is challenging due to many parameters and optimization difficulties.
method Frank-Wolfe optimization method applied to a deep network.
result Frank-Wolfe optimization converges slowly and is unstable in a stochastic setting.
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.
Local Bayesian optimization shows strong performance and converges well, contrary to folklore.
problem Understanding the behavior and convergence of local Bayesian optimization methods.
method Studied the behavior of local optimization strategies and rigorously analyzed a specific algorithm.
result Local Bayesian optimization algorithms converge well and perform strongly, contrary to the folklore.
This paper analyzes OCBA algorithms' convergence rates for DEDS optimization.
problem Optimizing discrete-event dynamic systems with limited computing resources.
method Characterizes convergence rates of two OCBA algorithms under different performance measures.
result OCBA algorithms achieve optimal convergence rates under probability of correct selection and expected opportunity cost measures.
Study shows convergence of stochastic gradient method for unregularized Wasserstein optimization.
problem Wasserstein distributionally robust optimization under potential distribution shifts.
method Regularized approximation with stochastic gradient methods, convergence analysis.
result Stochastic gradient method converges to subgradients of unregularized objective as regularization vanishes.
Paper proves EM algorithm convergence for mixtures of discrete and continuous parameters.
problem Nontrivial convergence analysis for EM algorithms with mixed-integer parameters.
method Introduces conditions for EM convergence in mixed-integer optimization.
result Proves convergence of EM-based sparse Bayesian learning algorithm.
Nesterov's extrapolation improves convergence in nonsmooth optimization.
problem Improving convergence rate in nonsmooth convex optimization.
method Nesterov's extrapolation applied to projected subgradient methods.
result Nesterov's extrapolation optimizes individual convergence for nonsmooth problems.
Hamiltonian dynamics-based algorithms achieve deterministic and accelerated convergence for convex optimization.
problem Accelerating convex optimization
method Hamiltonian dynamics
result Hamiltonian dynamics-based algorithms achieve deterministic and accelerated convergence for convex optimization.
Policy gradient methods with actor-critic schemes demonstrate tremendous empirical successes, especially when the actors and critics are parameterized by neural networks. However, it remains less clear whether such "neural" policy gradient methods converge to globally optimal policies and whether they even converge at …
This thesis analyzes and improves convergence rates of bilevel optimization algorithms in machine learning.
problem Convergence analysis and algorithm design for bilevel optimization in machine learning.
method Comprehensive convergence rate analysis for both problem-based and algorithm-based bilevel optimization formulations.
result First lower bounds and matching upper bounds for bilevel optimization, and new stochastic algorithms with lower complexity.
We study the rates of convergence from empirical surrogate risk minimizers to the Bayes optimal classifier. Specifically, we introduce the notion of \emph{consistency intensity} to characterize a surrogate loss function and exploit this notion to obtain the rate of convergence from an empirical surrogate risk minimizer…
Unified parametric assumption improves convergence guarantees for nonconvex optimization.
problem Weak convergence guarantees for nonconvex optimization.
method Introducing a novel unified parametric assumption.
result Unified convergence theorem for gradient-based methods.
This study analyzes AdaGrad's stability and convergence in non-convex optimization.
problem Lack of theoretical analysis for AdaGrad in non-convex optimization.
method Novel stopping time-based techniques from probability theory.
result Established stability and derived convergence rates for AdaGrad.
Study on convergence rates for optimal transport with regularization.
problem Convergence analysis of divergence-regularized optimal transport.
method Novel methodology using quantization and martingale couplings.
result Sharp rates for various divergences and transport costs.
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…
New algorithm guarantees optimal convergence rate for stochastic optimization.
problem Optimal convergence rate for stochastic optimization algorithms.
method Regularized versions of Minimization by Incremental Surrogate Optimization (MISO) with arbitrary recurrent data sampling.
result Expected optimality gap converges at O(n−1/2) under general recurrent sampling schemes. 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.
This work accelerates gradient descent with anytime convergence guarantees.
problem Improving the convergence rate of gradient descent methods.
method Proposes a stepsize schedule for gradient descent that achieves anytime convergence rates.
result Gradient descent can achieve convergence rates of O(T−1.119) for any stopping time T. Study on Adam-family methods for nonsmooth optimization with convergence guarantees.
problem Training nonsmooth neural networks with convergence guarantees.
method Two-timescale updating scheme and stochastic subgradient methods with gradient clipping.
result Convergence guarantees for various Adam-family methods in training nonsmooth neural networks.
In this paper we study randomized optimal stopping problems and consider corresponding forward and backward Monte Carlo based optimisation algorithms. In particular we prove the convergence of the proposed algorithms and derive the corresponding convergence rates.
ADOPT optimizes Adam to converge with any β2 without bounded noise.
problem Non-convergence of Adam optimization algorithm.
method ADOPT removes current gradient from second moment estimate and changes momentum update order.
result ADOPT achieves optimal convergence rate of O(1 / √T) with any β2.
Improved SGD methods converge faster for nonconvex optimization.
problem Nonconvex optimization challenges in machine learning.
method Adaptive SGD with line-search and Polyak stepsizes.
result Unified convergence rates for various nonconvex functions.
Improved convergence for nonconvex optimization with dependent data.
problem Constrained smooth nonconvex optimization with dependent data.
method Stochastic projected gradient methods under a general dependent data sampling scheme.
result Achieved worst-case rate of convergence ildeO(t−1/4) and complexity ildeO(ε−4). PPGD solves nonconvex nonsmooth optimization problems without KL property.
problem Nonconvex and nonsmooth optimization problems in statistics and machine learning.
method Projective Proximal Gradient Descent (PPGD) for solving a class of nonconvex and nonsmooth problems.
result PPGD achieves a fast convergence rate of O(1/k^2) for k ≥ k_0.
Unified framework for optimal liquidation with small market impact and semimartingale strategies.
problem Optimal liquidation under small market impact and portfolio liquidation.
method Semimartingale strategies and convergence results for BSDEs with singular terminal conditions.
result Unified framework for embedding two common liquidation models and microscopic foundation for semimartingale strategies.
We present an approach to obtain convergence guarantees of optimization algorithms for deep networks based on elementary arguments and computations. The convergence analysis revolves around the analytical and computational structures of optimization oracles central to the implementation of deep networks in machine lear…
The study analyzes momentum-based optimization algorithms from dynamical systems perspective.
problem Understanding convergence rates of momentum-based optimization algorithms.
method Exploits dynamical systems, control theory, and symplectic perspectives to analyze convergence rates.
result Provides closed-form expressions relating algorithm parameters to convergence rates.
Proposes batch version of Greenkhorn for multimarginal OT, proving convergence.
problem Optimal transport problems with multiple marginals.
method Batch Greenkhorn algorithm, iterative Bregman projections, greedy control.
result Global linear rate of convergence and explicit iteration complexity bounds.
New algorithm improves convergence for non-convex problems with boundaries.
problem Optimizing non-convex problems with constraints.
method Reflected Gradient Langevin Dynamics with probabilistic representation.
result Promising convergence rates, faster than existing methods.
This work analyzes the convergence rate of unrolling for optimizing quadratic objectives.
problem The challenge of accurately computing Jacobians through optimization.
method Non-asymptotic convergence-rate analysis of unrolled differentiation for gradient descent and Chebyshev method.
result There is a trade-off between fast asymptotic convergence and immediate but slower convergence due to the learning rate.