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…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “second-order convergence”
Negative step sizes improve second-order methods for neural networks.
problem Second-order methods discard negative curvature, limiting their effectiveness.
method Introduce negative step sizes in second-order methods combined with Wolfe line search.
result Negative step sizes lead to global convergence and improved performance.
Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Ratemath.OC
A new method for faster optimization in high dimensions.
problem Slow convergence in high-dimensional optimization problems.
method Subspace cubic regularized Newton method within Krylov subspace.
result Achieves a dimension-independent convergence rate of O(1/mk + 1/k^2).
Paper proposes a second-order method for faster SVI convergence.
problem Poor convergence rate of first-order SVI algorithms.
method Derives Hessian matrix and implements two numerical schemes for efficient second-order SVI.
result Proposed approach achieves faster convergence compared to first-order SVI.
What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneitycs.LG
Improved Local SGD convergence for general convex objectives with bounded second-order heterogeneity.
problem Understanding when and why Local SGD outperforms alternatives in distributed optimization.
method Established improved convergence guarantees for Local SGD on general convex objectives under bounded second-order heterogeneity.
result Upper bounds for Local SGD are nearly tight, providing a sharper convergence theory.
Stochastic second-order methods converge fast under interpolation conditions.
problem Minimizing smooth and strongly-convex functions efficiently.
method Regularized subsampled Newton method (R-SSN) and stochastic BFGS algorithms.
result R-SSN achieves global linear convergence and quadratic rate in a local neighbourhood.
A new method for faster optimization of noisy functions.
problem Optimizing noisy functions efficiently.
method A universal and adaptive second-order method for convex functions.
result Achieves convergence for stochastic oracles and for deterministic oracles.
We introduce TrustVI, a fast second-order algorithm for black-box variational inference based on trust-region optimization and the reparameterization trick. At each iteration, TrustVI proposes and assesses a step based on minibatches of draws from the variational distribution. The algorithm provably converges to a stat…
First-order methods such as stochastic gradient descent (SGD) are currently the standard algorithm for training deep neural networks. Second-order methods, despite their better convergence rate, are rarely used in practice due to the prohibitive computational cost in calculating the second-order information. In this pa…
A new algorithm for solving constrained convex optimization problems efficiently.
problem Constrained convex optimization problems requiring high accuracy solutions.
method Second-Order Conditional Gradient Sliding (SOCGS) algorithm, using projection-free methods to solve quadratic subproblems inexactly.
result Converges quadratically in primal gap after a finite number of linearly convergent iterations.
Second-order methods improve differential privacy in convex optimization.
problem Improving differential privacy in convex optimization.
method Developed a private variant of the regularized cubic Newton method for strongly convex loss functions.
result Achieves quadratic convergence and optimal excess loss for strongly convex loss functions.
Paper analyzes convergence and speedup of asynchronous parallel SGD.
problem Achieving good convergence and linear speedup in asynchronous parallel SGD.
method Second-order convergence analysis of APSGD with consistent read near strictly saddle points.
result Theoretical guarantee for using at most workers for good convergence and linear speedup.
New algorithm provably converges to second-order stationary points in NMF.
problem Understanding convergence to local minima in NMF.
method Multiplicative weight update dynamics, concurrent updates, and simplex reduction.
result Provable convergence to second-order stationary points.
A Stochastic Variance Reduced Gradient using Barzilai-Borwein Techniques as Second Order Informationmath.OC
Improved SVRG method using BB techniques for faster convergence.
problem Improving the convergence speed of stochastic variance reduction methods.
method Incorporates Barzilai-Borwein (BB) techniques as second-order information into SVRG.
result Proves linear convergence of the proposed method and its variants.
Simple stochastic Newton and cubic Newton methods with fast convergence.
problem Minimizing large numbers of smooth and strongly convex functions.
method Stochastic Newton and cubic Newton methods with simple local linear-quadratic rates.
result Local linear-quadratic convergence results with fast adaptation to problem's curvature.
Method provides bounds for sparse PCA and nuclear norm problems.
problem Semidefinite optimization problems (SDOs).
method Cutting-plane method with focus on initial outer approximation as a second-order cone approximation.
result Method provides bound gaps of 0.5-6.5% for sparse PCA problems with 1000 covariates and solves nuclear norm problems over 500x500 matrices.
We solve the local equivalence problem for second order (smooth or analytic) ordinary differential equations. We do so by presenting a {\em complete convergent normal form} for this class of ODEs. The normal form is optimal in the sense that it is defined up to the automorphism group of the model (flat) ODE . For…
New method solves stochastic optimization problems with random models.
problem Optimizing stochastic objectives with deterministic constraints.
method Trust-Region Sequential Quadratic Programming with random model.
result Global convergence guarantees for first- and second-order stationary points.
PWGF escapes saddle points in nonconvex optimization.
problem Escaping saddle points in nonconvex optimization.
method PWGF uses noisy perturbations via Gaussian process to escape saddle points.
result PWGF achieves second-order optimality for nonconvex objectives.
Non-asymptotic approximations of Gaussian neural networks via second-order Poincaré inequalitiescs.LG
This paper uses second-order Poincaré inequalities to establish quantitative central limit theorems for Gaussian neural networks.
problem Establishing quantitative central limit theorems for Gaussian neural networks.
method Using second-order Poincaré inequalities to reduce the problem to computing the gradient and Hessian of the NN's output.
result Suboptimal rates of convergence for the NN's output due to the use of second-order Poincaré inequalities.
First-order stochastic methods are the state-of-the-art in large-scale machine learning optimization owing to efficient per-iteration complexity. Second-order methods, while able to provide faster convergence, have been much less explored due to the high cost of computing the second-order information. In this paper we …
Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov Decision Process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first order method and therefore …
COMRADE is a communication-efficient, Byzantine-resilient second-order optimization algorithm.
problem Byzantine failures in distributed optimization.
method COMRADE is a communication-efficient, second-order optimization algorithm that uses a simple norm-based thresholding rule to filter out Byzantine workers.
result COMRADE achieves linear-quadratic convergence and is robust against Byzantine workers.
We present high-order compact schemes for a linear second-order parabolic partial differential equation (PDE) with mixed second-order derivative terms in two spatial dimensions. The schemes are applied to option pricing PDE for a family of stochastic volatility models. We use a non-uniform grid with more grid-points ar…
We study the limiting behaviour of Darboux and Calapso transforms of polarized curves in the conformal n-dimensional sphere, when the polarization has a pole of first or second order at some point. We prove that for a pole of first order, as the singularity is approached all Darboux transforms converge to the original …
The paper solves complex swing option pricing equations with numerical methods.
problem Valuation of swing options with jumps under a mean-reverting model.
method Proposes second-order numerical methods to solve PIDEs convection-dominated and with nonlocal integral terms.
result Numerical methods confirm second-order convergence behavior.
AdaSub optimizes with second-order info in low-dims subspace.
problem Efficiently use second-order optimization methods with low computational cost.
method Adaptive subspace selection for second-order optimization.
result AdaSub outperforms other stochastic optimizers in time and iterations.
A new optimization method improves deep learning accuracy without hyper-parameter tuning.
problem Computational demands and convergence behavior in deep learning training.
method Stochastic quasi-Gauss-Newton (SQGN) optimization method combining stochastic quasi-Newton, Gauss-Newton, and variance reduction.
result SQGN provides excellent accuracy without hyper-parameter experimentation, improving convergence and computational performance.
Momentum is a popular technique to accelerate the convergence in practical training, and its impact on convergence guarantee has been well-studied for first-order algorithms. However, such a successful acceleration technique has not yet been proposed for second-order algorithms in nonconvex optimization.In this paper, …
New method avoids saddle points without gradients.
problem Optimizing non-convex functions efficiently.
method Zero-order derivative-free algorithm using only function evaluations.
result Converges to second-order stationary points efficiently.
NMC improves MCMC convergence by analyzing gradients to determine optimal proposal densities.
problem Improving MCMC convergence in structured relational models.
method Newtonian Monte Carlo (NMC) uses first and second order gradients to determine a suitable proposal density.
result NMC outperforms existing methods in various domains, including non-conjugate models.
Paper proposes a new method for efficient second-order neural network training.
problem Infeasibility of Hessian calculation and noisy second-order information in deep learning.
method Adopting complex-step directional derivative (CSFD) for accurate Hessian computation and designing an effective Newton Krylov procedure.
result Our method outperforms existing methods and often converges one-order faster.
A new method for faster optimization on statistical manifolds.
problem Slow convergence of first-order methods in manifold optimization.
method Dual Riemannian Newton method on manifolds with dual connections.
result Local quadratic convergence of the dual Riemannian Newton method.
This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the well-known convergence rate of gradient descent to…
Paper improves compressed SGD to reach second-order stationary points.
problem Efficiently reaching second-order stationary points in distributed machine learning.
method Gradient compression and RandomK compressor to improve convergence to second-order stationary points.
result Compressed SGD reaches second-order stationary points with improved communication efficiency.
New method improves online covariance estimation for SGD.
problem Improving online covariance estimation for SGD.
method Proposes a de-biased covariance estimator that eliminates second-order derivatives.
result Achieves a convergence rate of , outperforming existing methods.
Second-order optimization speeds up deep hedging for complex options.
problem Hedging exotic options with market frictions in realistic markets.
method Second-order optimization scheme leveraging pathwise differentiability and Kronecker-factoring.
result Our method optimizes the policy in 1/4 the steps of standard optimization.
The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothn…
We develop a second-order model for limit order books in a single scaling regime.
problem Modeling price and volume dynamics in a limit order book with market and limit orders at a common time scale.
method Established a first- and second-order approximation for an infinite dimensional limit order book model.
result Proved the existence and uniqueness of a solution for the second-order approximation.
AdamNX improves Adam's stability by adjusting its learning rate.
problem Adam's tendency to converge to non-flat minima in large-scale models.
method Proposes a novel exponential decay mechanism for Adam's second-order moment estimate.
result AdamNX outperforms Adam and its variants in stability and performance.
Local search heuristics for non-convex optimizations are popular in applied machine learning. However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points su…
Improved robustness in optimization methods using second-order information.
problem Scalability and sensitivity to mini-batch size in optimization methods.
method Mini-Batch Stochastic Variance-Reduced Newton () algorithm incorporating partial second-order information.
result Achieves a fast linear convergence rate independent of mini-batch size for large data sizes.
Study stabilizes second-order systems to first-order dynamics.
problem Stabilizing second-order systems to first-order dynamics.
method Feedback control of second-order systems on manifolds.
result Second-order systems can globally exponentially stabilize first-order dynamics for fully actuated systems.
Optimistic method adapted for faster convex-concave min-max problems.
problem Solving convex-concave min-max optimization problems efficiently.
method Adaptive, line search-free second-order methods combining optimistic updates and second-order information.
result Achieves optimal convergence rate without line search or backtracking.
We consider the problem of efficiently computing the maximum likelihood estimator in Generalized Linear Models (GLMs) when the number of observations is much larger than the number of coefficients (). In this regime, optimization algorithms can immensely benefit from approximate second order information.…
New method speeds up deep learning optimization.
problem Scalable second-order optimization for deep learning.
method Second-order optimization with algorithmic and numerical improvements.
result Significant convergence and wall-clock time improvements.
Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularizationcs.LG
New technique debiases distributed optimization, improving convergence rate.
problem Bias in local estimates limits effectiveness of distributed second order optimization.
method Surrogate sketching and scaled regularization to eliminate bias.
result The debiased local estimates lead to faster convergence in distributed optimization.
New SGD algorithm finds critical points faster with second-order corrections.
problem Finding critical points in non-convex optimization efficiently.
method Uses Hessian-vector products to correct momentum bias in SGD.
result Finds -critical points in time.