arXiv research

Study shows convergence rate for empirical minimizer of unbounded functions with fast growth.

Paper shows SVM can achieve super fast convergence rates.

Paper offers a fast convergence theory for offline decision making.

Paper improves a method for fast global and local convergence in optimization.

Study the averaging principle for non-autonomous slow-fast systems and apply it to financial local stochastic volatility models.

PPGD solves nonconvex nonsmooth optimization problems without KL property.

This study explains why approximate NGD works well in wide neural networks.

We present a fast variational Bayesian algorithm for performing non-negative matrix factorisation and tri-factorisation. We show that our approach achieves faster convergence per iteration and timestep (wall-clock) than Gibbs sampling and non-probabilistic approaches, and do not require additional samples to estimate t…

We analyze a fast incremental aggregated gradient method for optimizing nonconvex problems of the form $\min_x \sum_i f_i(x)$. Specifically, we analyze the SAGA algorithm within an Incremental First-order Oracle framework, and show that it converges to a stationary point provably faster than both gradient descent and s…

Symmetric nonnegative matrix factorization (NMF), a special but important class of the general NMF, is demonstrated to be useful for data analysis and in particular for various clustering tasks. Unfortunately, designing fast algorithms for Symmetric NMF is not as easy as for the nonsymmetric counterpart, the latter adm…

New learning dynamics achieve fast convergence in games without needing to know utility scales.

Paper introduces a new gradient statistic to improve deep learning convergence.

Gradient-based temporal difference (GTD) algorithms are widely used in off-policy learning scenarios. Among them, the two time-scale TD with gradient correction (TDC) algorithm has been shown to have superior performance. In contrast to previous studies that characterized the non-asymptotic convergence rate of TDC only…

We analyze stochastic algorithms for optimizing nonconvex, nonsmooth finite-sum problems, where the nonconvex part is smooth and the nonsmooth part is convex. Surprisingly, unlike the smooth case, our knowledge of this fundamental problem is very limited. For example, it is not known whether the proximal stochastic gra…

The paper analyzes reinforcement learning methods for estimating weights and quality functions with fast convergence rates.

Stochastic gradient method converges as fast as deterministic for overparametrized models.

Ancient flows converge fast with finite curvature and convexity.

Paper tackles fast convergence for non-convex strongly-concave min-max problems.

We study the convergence properties of the VR-PCA algorithm introduced by \cite{shamir2015stochastic} for fast computation of leading singular vectors. We prove several new results, including a formal analysis of a block version of the algorithm, and convergence from random initialization. We also make a few observatio…

We derive the fast convergence rates of a deep neural network (DNN) classifier with the rectified linear unit (ReLU) activation function learned using the hinge loss. We consider three cases for a true model: (1) a smooth decision boundary, (2) smooth conditional class probability, and (3) the margin condition (i.e., t…

Novel framework proves fast RL convergence in continuous spaces.

We consider an SPDE description of a large portfolio limit model where the underlying asset prices evolve according to certain stochastic volatility models with default upon hitting a lower barrier. The asset prices and their volatilities are correlated via systemic Brownian motions, and the resulting SPDE is defined o…

Error bound conditions (EBC) are properties that characterize the growth of an objective function when a point is moved away from the optimal set. They have recently received increasing attention in the field of optimization for developing optimization algorithms with fast convergence. However, the studies of EBC in st…

Smooth convergence shown for curve diffusion flows.

EControl improves fast distributed optimization with compression and error control.

EM algorithm converges exponentially fast for overspecified Gaussian mixtures.

The alternating direction method of multipliers (ADMM) is a powerful optimization solver in machine learning. Recently, stochastic ADMM has been integrated with variance reduction methods for stochastic gradient, leading to SAG-ADMM and SDCA-ADMM that have fast convergence rates and low iteration complexities. However,…

Combines PCA and CEM for fast clustering and embedding.

Paper analyzes faster convergence rates for reinforcement learning from offline data.

We consider the stochastic contextual bandit problem with additional regularization. The motivation comes from problems where the policy of the agent must be close to some baseline policy which is known to perform well on the task. To tackle this problem we use a nonparametric model and propose an algorithm splitting t…

This paper proposes a new method for estimating sparse precision matrices in the high dimensional setting. It has been popular to study fast computation and adaptive procedures for this problem. We propose a novel approach, called Sparse Column-wise Inverse Operator, to address these two issues. We analyze an adaptive …

Given a Sasaki manifold S, we prove the Sasaki-Ricci flow converges exponentially fast to a Sasaki-Einstein metric if one exists, provided the automorphism group of the transverse holomorphic structure is trivial.

TD(0) with Polyak-Ruppert averaging achieves robust and fast convergence rates

A new algorithm speeds up neural network training with less data.

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…

Algorithm minimizes risk for multiclass classification of stochastic diffusion paths.

We consider binary classification problems with positive definite kernels and square loss, and study the convergence rates of stochastic gradient methods. We show that while the excess testing loss (squared loss) converges slowly to zero as the number of observations (and thus iterations) goes to infinity, the testing …

In this paper we propose a cyclical coordinate descent (CCD) algorithm for solving high dimensional risk parity problems. We show that this algorithm converges and is very fast even with large covariance matrices (n > 500). Comparison with existing algorithms also shows that it is one of the most efficient algorithms.

We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied by over-parameterized models. Under this condition, we show that the regularized subsampled Newton method (R-SSN) achieves global linear convergence with an adaptive step-size and a…

Paper proposes a new method to detect convergence in SGD.

The paper proves the stability of a flow in Schwarzschild space.

While optimizing convex objective (loss) functions has been a powerhouse for machine learning for at least two decades, non-convex loss functions have attracted fast growing interests recently, due to many desirable properties such as superior robustness and classification accuracy, compared with their convex counterpa…

The paper tackles fast rates in structured prediction problems.

This paper studies the normalized Ricci flow from a slight perturbation of the hyperbolic metric on $\mathbb H^n$. It's proved that if the perturbation is small and decays sufficiently fast at the infinity, then the flow will converge exponentially fast to the hyperbolic metric when the dimension $n>5$.

Paper proposes efficient optimizers for large language models with fast convergence and low memory usage.

Entropy-regularized NPG methods converge linearly in discounted MDPs.

In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for compos…

Neural operators achieve fast convergence rates for solving PDEs.