Stochastic Non-convex Optimization with Strong High Probability Second-order Convergence
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 optimization are limited, especially with a high probability second-order convergence. We propose a novel updating step (named NCG-S) by leveraging a stochastic gradient and a noisy negative curvature of a stochastic Hessian, where the stochastic gradient and Hessian are based on a proper mini-batch of random functions. Building on this step, we develop two algorithms and establish their high probability second-order convergence. To the best of our knowledge, the proposed stochastic algorithms are the first with a second-order convergence in {\it high probability} and a time complexity that is {\it almost linear} in the problem's dimensionality.
Code (0)
등록된 구현이 없습니다.
Tasks
Vocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance
During recent years the interest of optimization and machine learning communities in high-probability convergence of stochastic optimization methods has been growing. One of the main reasons for this is that high-probabi…
Stochastic OptimizationStochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
In this paper, we propose a new accelerated stochastic first-order method called clipped-SSTM for smooth convex stochastic optimization with heavy-tailed distributed noise in stochastic gradients and derive the first hig…
Stochastic OptimizationFrom low probability to high confidence in stochastic convex optimization
Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. More nuanced high probability guarantees are rare, and …
Stochastic OptimizationVocal Bursts Intensity PredictionO(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
Traditional algorithms for stochastic optimization require projecting the solution at each iteration into a given domain to ensure its feasibility. When facing complex domains, such as positive semi-definite cones, the p…
Stochastic OptimizationImproved Learning Rates for Stochastic Optimization: Two Theoretical Viewpoints
Generalization performance of stochastic optimization stands a central place in learning theory. In this paper, we investigate the excess risk performance and towards improved learning rates for two popular approaches of…
Learning TheoryStochastic OptimizationVocal Bursts Valence Prediction