In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of (Nemirovski, 2004). In this paper, we show that the last…
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,657 papers · 148 categories
Trend · papers per month
48 results for “last-iterate convergence”
In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \t…
New convergence rates for shuffling gradient methods without strong convexity.
problem Theoretical gap between shuffling gradient methods' empirical success and established convergence rates.
method Proved last-iterate convergence rates for shuffling gradient methods using function value gap.
result First last-iterate convergence rates for shuffling gradient methods without strong convexity.
While classic work in convex-concave min-max optimization relies on average-iterate convergence results, the emergence of nonconvex applications such as training Generative Adversarial Networks has led to renewed interest in last-iterate convergence guarantees. Proving last-iterate convergence is challenging because ma…
This work addresses the convergence of SGD's final iterate without restrictive assumptions.
problem Prove optimal convergence rate of SGD's final iterate without compact domains or bounded noise.
method Unified proof for general domains, composite objectives, non-Euclidean norms, etc.
result First unified convergence rates in expectation and high probability.
Improved convergence rates for saddle-point optimization algorithms.
problem Understanding last-iterate convergence rates for saddle-point optimization algorithms in constrained settings.
method Expanding the understanding of last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) in the constrained setting.
result Linear last-iterate convergence achieved with a universal constant learning rate for OMWU in bilinear games over the simplex.
Optimizes convergence rate of stochastic proximal algorithms for composite convex problems.
problem Solving composite convex optimization problems with composite regularizers.
method Analyzed proximal stochastic gradient method and randomized incremental proximal method under relaxed variance assumptions.
result Proves convergence rate for last iterate of both algorithms under componentwise convexity and smoothness.
Paper proves suboptimal convergence rate of last iterate for SGDM.
problem Proves suboptimal convergence rate of last iterate for SGDM.
method Focuses on convergence rate of last iterate of SGDM, introduces Follow-The-Regularized-Leader-based algorithms.
result Shows optimal convergence rate of last iterate for unconstrained convex stochastic optimization problems.
In this paper, we consider multi-agent learning via online gradient descent in a class of games called -cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained strongly monotone games. We characterize the finite-time last-iterate convergence rate for …
Efficient algorithm converges to Nash equilibrium in bilinear problems with bandit feedback.
problem Learning dynamics in bilinear saddle-point problems with bandit feedback.
method Uncoupled learning algorithm combining experimental design and FTRL with a tailored regularizer.
result Last-iterate convergence rate of in high probability.
Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationsmath.OC
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.
Mutation improves FTRL convergence in zero-sum games.
problem Lack of last-iterate convergence in FTRL variants.
method Introduced mutation to perturb action probabilities in FTRL.
result M-FTRL converges to Nash equilibria under full-information feedback.
Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimizationmath.OC
Improved shuffling gradient methods converge faster for nonsmooth convex optimization.
problem Improving convergence rates for nonsmooth convex optimization problems.
method Analysis of shuffling gradient methods, focusing on Random Reshuffle and Single Shuffle strategies.
result Shuffling gradient methods, particularly Random Reshuffle and Single Shuffle, converge faster than Proximal Gradient Descent for nonsmooth convex optimization.
SGD achieves near optimal convergence rate in smooth interpolation regime.
problem Optimization of smooth convex objectives with zero noise at optimum.
method Stochastic Gradient Descent (SGD) with large stepsize analysis.
result Last iterate of SGD achieves expected excess risk of O(1/T + σ* / √T) with optimal stepsize.
Last-iterate guarantees for learning in co-coercive games under noisy feedback.
problem Learning in co-coercive games with noisy feedback.
method Vanilla stochastic gradient descent with a new noise model.
result Last-iterate bound of order for co-coercive games.
This paper advances extragradient methods for solving inclusions under co-hypomonotonicity.
problem Solving inclusions with non-Lipschitz mappings.
method Unified and generalized extragradient methods under co-hypomonotonicity.
result Achieved convergence rates for residual norms.
Extragradient-Type Methods with Last-Iterate Convergence Rates for Co-Hypomonotone Inclusionsmath.OC
Two accelerated extragradient methods converge at rate for co-hypomonotone inclusions.
problem Solving co-hypomonotone inclusions with sum of Lipschitz and multivalued operators.
method Developed two Nesterov's accelerated extragradient methods for co-hypomonotone inclusions.
result Achieve last-iterate convergence rates on the residual norm.
New study shows faster convergence of SGD and Kaczmarz methods.
problem Improving convergence rates of iterative linear system solvers.
method Last-iterate convergence analysis of SGD with greedy step size over smooth quadratics.
result The -th iterate attains an convergence rate.
The paper analyzes convergence rates for SGD and SHB methods.
problem Analyzing convergence rates for stochastic gradient descent and heavy ball methods.
method Stochastic gradient descent and stochastic heavy ball method for general stochastic approximation problems.
result The last iterate of SHB converges almost surely to a minimizer and has faster convergence rates than SGD.
Gradient methods converge exponentially in concave network games.
problem Finding Nash equilibria in concave network zero-sum games.
method Gradient Ascent and Optimistic Gradient Ascent analyses.
result Exponential convergence rates in various game settings.
Algorithm converges to Nash equilibria in competitive games.
problem Finding Nash equilibria in decentralized, competitive Markov games.
method Decentralized Optimistic Gradient Descent/Ascent with a critic.
result Converges to the set of Nash equilibria under self-play.
Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al \cite{DISZ17} and follow-up work of Liang and Stokes \cite{LiangS18} have established that a variant of the widely used Gradient Descent/Ascent procedure, called "Optimistic Gradient Descent/Asce…
In this paper, we study the online learning algorithm without explicit regularization terms. This algorithm is essentially a stochastic gradient descent scheme in a reproducing kernel Hilbert space (RKHS). The polynomially decaying step size in each iteration can play a role of regularization to ensure the generalizati…
New algorithms converge faster to Nash equilibrium in zero-sum games with bandit feedback.
problem Learning in zero-sum games with bandit feedback without communication.
method Developed two uncoupled algorithms achieving optimal rate of .
result Achieved optimal rate of for convergence of policy profiles to Nash equilibrium.
Non-affine aggregation rules cannot preserve monotonicity in convex learning.
problem Designing non-affine aggregation rules that maintain monotonicity in convex learning.
method Proving that monotonicity of aggregated gradients is preserved only if the aggregation rule is positively affine.
result Non-affine aggregation prevents steady convergence and substantially degrades algorithmic stability.
Last SGD iterate bounds for overparameterized linear regression.
problem Analyzing the last iterate risk bounds of SGD with decaying stepsize for overparameterized linear regression.
method Problem-dependent analysis of last iterate risk bounds of SGD with geometrically decaying stepsize.
result Proved nearly matching upper and lower bounds on the excess risk for last iterate SGD with geometrically decaying stepsize.
A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Ratesmath.OC
We develop a novel unified randomized block-coordinate primal-dual algorithm to solve a class of nonsmooth constrained convex optimization problems, which covers different existing variants and model settings from the literature. We prove that our algorithm achieves optimal and …
SGD converges to optimal solution in perfect data fitting problem.
problem Noiseless least-squares with perfect data fitting.
method Last iterate of SGD with constant step-size.
result Convergence of SGD final iterate for non-strongly convex problem.
New privacy bounds for DP-SGD's last iterate, even with cyclic sampling.
problem Privacy of the last iterate in DP-SGD with cyclic sampling.
method Established new RDP upper bounds for the last iterate under realistic assumptions.
result Privacy bounds for DP-SGD's last iterate with cyclic sampling and clipping, even for nonconvex losses.
This work provides formal guarantees for heuristic optimization methods in machine learning.
problem Lack of theoretical understanding of heuristic optimization methods in machine learning.
method Analysis and formal guarantees for AdaGrad, SGD with exponential and cosine step sizes, and momentum methods.
result First formal guarantees for AdaGrad and SGD variants, including convergence and adaptivity to noise.
Despite remarkable empirical success, the training dynamics of generative adversarial networks (GAN), which involves solving a minimax game using stochastic gradients, is still poorly understood. In this work, we analyze last-iterate convergence of simultaneous gradient descent (simGD) and its variants under the assump…
A new method for RLHF using proximal point Nash learning.
problem Capturing real human preferences in RLHF.
method Proximal point Nash learning, embedding self-play updates into a proximal point framework.
result High-probability last-iterate convergence for the combined method.
WSqD extends learning rate schedules for large model training without fixed horizons.
problem Fixed learning rate schedules limit training horizon extension.
method WSqD replaces constant stable phase with a shifted inverse-square-root base, retaining linear cooldown.
result WSqD achieves minimax-optimal convergence rate and horizon-independence.
Federated learning (FL) provides a communication-efficient approach to solve machine learning problems concerning distributed data, without sending raw data to a central server. However, existing works on FL only utilize first-order gradient descent (GD) and do not consider the preceding iterations to gradient update w…
Counterfactual Regret Minimization (CFR) has found success in settings like poker which have both terminal states and perfect recall. We seek to understand how to relax these requirements. As a first step, we introduce a simple algorithm, local no-regret learning (LONR), which uses a Q-learning-like update rule to allo…
Improved SEG method converges to Nash equilibrium in bilinear games.
problem Stochastic bilinear minimax optimization problem
method Stochastic ExtraGradient (SEG) method with constant step size, iteration averaging, and scheduled restarting.
result Provable convergence to Nash equilibrium under standard settings, optimal convergence rate in interpolation setting.
Improves training GANs by escaping limit cycles.
problem Limit cycling behavior in training GANs.
method Predictive Centripetal Acceleration Algorithm (PCAA) combined with Adam.
result PCAA improves convergence rates and effectively trains GANs.
ROOT-SGD solves convex optimization problems with optimal nonasymptotic and near-optimal asymptotic performance.
problem Solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms.
method ROOT-SGD: Recursive One-Over-T SGD, averaging past stochastic gradients.
result Achieves state-of-the-art performance in both nonasymptotic and asymptotic senses.
Improved SGD for non-strongly-convex regression with faster convergence.
problem Non-strongly-convex least squares regression problems.
method Modified accelerated gradient descent.
result Achieves optimal prediction error rates of and forgets initial conditions faster to .
New algorithm for solving minimax problems over distributions converges to Nash equilibrium.
problem Solving minimax problems over probability distributions.
method Symmetric Mean-field Langevin Dynamics (MFL-AG and MFL-ABR) with weighted averaging and best response dynamics.
result Converges to mixed Nash equilibrium with average-iterate and last-iterate convergence.
New convergence guarantees for SGDA and SCO under expected co-coercivity.
problem Solving smooth games with stochastic gradient descent-ascent and consensus optimization.
method Introducing expected co-coercivity and proving convergence guarantees for SGDA and SCO.
result Linear convergence of SGDA and SCO to a neighborhood of the solution with constant step-size, and convergence to the exact solution with stepsize-switching rules.
Paper studies a robust online learning algorithm for regression.
problem Develops a robust online learning algorithm for regression problems.
method Introduces an online learning algorithm with a robust loss function over RKHS.
result The algorithm achieves optimal convergence rates in mean square and RKHS.
Risk management in dynamic decision problems is a primary concern in many fields, including financial investment, autonomous driving, and healthcare. The mean-variance function is one of the most widely used objective functions in risk management due to its simplicity and interpretability. Existing algorithms for mean-…
New method improves convergence for smooth games.
problem Improving convergence for smooth games.
method Stochastic Hamiltonian Gradient Methods (SHGD).
result SHGD converges linearly to the neighbourhood of a stationary point.
In this paper, we consider unregularized online learning algorithms in a Reproducing Kernel Hilbert Spaces (RKHS). Firstly, we derive explicit convergence rates of the unregularized online learning algorithms for classification associated with a general gamma-activating loss (see Definition 1 in the paper). Our results…
Study on SGD for overparameterized neural networks, focusing on convergence rates.
problem Understanding convergence rates of SGD in overparameterized two-layer neural networks.
method Combines NTK approximation with RKHS analysis to explore SGD dynamics.
result Established sharp convergence rates for SGD in overparameterized two-layer neural networks.
Paper analyzes convergence rates of mean-field SVGD method.
problem Establishing quantitative rates of convergence for mean-field SVGD.
method Quantitative analysis of mean-field SVGD dynamics on torus.
result Explicit polynomial convergence rates in L2-norm for Riesz-type kernels.
Riemannian algorithms converge at Euclidean rates for geodesically convex-concave problems.
problem Min-max optimization on Riemannian manifolds.
method RCEG method and RGDA for geodesically strongly-convex-concave problems.
result RCEG achieves linear convergence rate in geodesically strongly-convex-concave cases.