New algorithm solves federated minimax optimization problems.
problem Federated minimax optimization challenges.
method Federated Stochastic Smoothed Gradient Descent Ascent (FESS-GDA).
result FESS-GDA uniformly solves federated minimax problems.
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,695 papers · 148 categories
Trend · papers per month
48 results for “smoothed gradient ascent”
Introduces a new theoretical framework for exponential smoothing.
problem Theoretical foundation and robustness of simple exponential smoothing.
method Stochastic gradient ascent to optimize Gaussian log-likelihood functions.
result Simple exponential smoothing converges to the trend of a trend-stationary process.
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.
A scalable method for BED with implicit models using approximate gradients.
problem Efficiently estimating posterior distribution and maximizing MI for implicit models.
method Stochastic approximate gradient ascent with smoothed variational MI estimator.
result Significantly improves scalability of BED in high-dimensional problems.
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.
Improves posterior approximation speed for Dirichlet process mixture models.
problem Inefficiency of stochastic variational inference in large datasets.
method Uses stochastic gradient ascent with adaptive stepsize optimization.
result Adaptive stepsize improves speed and performance of posterior approximation.
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.
Sampling without replacement speeds up optimization in minimax problems.
problem Optimizing minimax problems with faster convergence rates.
method Analysis of gradient descent ascent and proximal point method with two sampling strategies.
result Sampling without replacement leads to faster convergence rates in minimax optimization.
Gradient ascent method successfully removes specific data points from neural networks without retraining.
problem Addressing privacy and ethical concerns by removing specific data points from trained models.
method Gradient ascent approach to unlearning, leveraging the implicit bias of gradient descent towards margin maximization conditions.
result Gradient ascent method can successfully unlearn specific data points from two-layer ReLU neural networks without retraining.
Paper tackles efficient BAI in graph-smooth bandits.
problem Best arm identification with graph smoothness constraint.
method Gradient ascent algorithm for sample complexity.
result Asymptotically optimal strategy for BAI.
Gradient Descent Ascent converges to von-Neumann solution in hidden zero-sum games.
problem Understanding dynamics of zero-sum games with hidden structure.
method Gradient Descent Ascent applied to hidden zero-sum games with specific convex-concave structure.
result Gradient Descent Ascent converges to von-Neumann solution in strictly convex-concave hidden games.
Alt-GDA outperforms Sim-GDA in minimax games with near-optimal local convergence.
problem Minimax optimization convergence rate comparison
method Alternating Gradient Descent-Ascent (Alt-GDA) vs. Simultaneous Gradient Descent-Ascent (Sim-GDA)
result Alt-GDA achieves near-optimal local convergence rate for strongly convex-strongly concave problems, while Sim-GDA converges slower.
We present a new algorithm based on an gradient ascent for a general Active Exploration bandit problem in the fixed confidence setting. This problem encompasses several well studied problems such that the Best Arm Identification or Thresholding Bandits. It consists of a new sampling rule based on an online lazy mirror …
Optimal multistage method solves noisy minimax problems.
problem Minimizing/maximizing in noisy conditions with smooth and strongly convex-strongly concave settings.
method Multistage Stochastic Gradient Descent Ascent (M-GDA) and Optimistic Gradient Descent Ascent (M-OGDA).
result Achieves optimal linear decay rate with respect to initial error and condition number.
Algorithm improves variational inference in Wasserstein distance.
problem Improving variational inference methods for complex models.
method Wasserstein contraction analysis of coordinate ascent.
result General and sharp convergence guarantees for various models.
Gradient descent-ascent converges to strict local minmax equilibria with a finite timescale separation.
problem Analyzing the convergence of gradient descent-ascent in non-convex, non-concave games with a finite timescale separation.
method Investigates the role of a finite timescale separation parameter τ on gradient descent-ascent in two-player zero-sum games, providing convergence rates and non-convergence results.
result Gradient descent-ascent converges to strict local minmax equilibria for a finite timescale separation parameter τ*.
Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysismath.OC
Paper introduces SGA for barycenter optimization in optimal transport.
problem Optimizing Wasserstein barycenter for discrete distributions.
method Sobolev gradient ascent algorithm tailored to Wasserstein geometry.
result SGA achieves convergence rate similar to subgradient descent.
Lazy neural networks are vulnerable to adversarial attacks.
problem Adversarial robustness issues in lazy training models.
method Extending recent work on adversarial examples to lazy training models.
result Over-parametrized neural networks that generalize well remain vulnerable to single-step gradient ascent attacks.
SoftAD improves classification accuracy with less fine-tuning and fewer computational costs.
problem Improving classification accuracy with less fine-tuning and fewer computational costs.
method SoftAD is a softened, pointwise mechanism that downweights borderline points and limits the effects of outliers.
result SoftAD achieves classification accuracy competitive with flooding and SAM, with a smaller loss generalization gap and model norm.
The paper connects two clustering methods by showing gradient ascent flow can move up the cluster tree.
problem Establishing a strong correspondence between clustering methods.
method Moving up the cluster tree by following the gradient ascent flow.
result Gradient ascent flow can be used to move up the cluster tree.
We propose regularizing the empirical loss for semi-supervised learning by acting on both the input (data) space, and the weight (parameter) space. We show that the two are not equivalent, and in fact are complementary, one affecting the minimality of the resulting representation, the other insensitivity to nuisance va…
SMAVE optimizes SDR by projecting onto a low-dimensional subspace on a Riemannian manifold.
problem High-dimensional regression challenges due to the curse of dimensionality.
method SMAVE combines nearest-neighbor localization and Riemannian stochastic gradient ascent.
result SMAVE achieves almost-sure convergence and matches RMAVE's synthetic subspace recovery rate.
SAVO actor improves reinforcement learning by avoiding local optima in complex Q-functions.
problem Gradient ascent in complex Q-functions leads to suboptimal solutions.
method SAVO actor generates multiple action proposals and truncates poor local optima.
result SAVO actor finds optimal actions more frequently and outperforms other architectures.
In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods. We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving…
New SGDA method speeds up nonconvex minimax optimization.
problem Improving convergence of nonconvex minimax optimization.
method SGDA with random reshuffling for nonconvex-PŁ objectives.
result Convergence rates faster than with-replacement SGDA.
We study a wide class of non-convex non-concave min-max games that generalizes over standard bilinear zero-sum games. In this class, players control the inputs of a smooth function whose output is being applied to a bilinear zero-sum game. This class of games is motivated by the indirect nature of the competition in Ge…
Generative adversarial networks (GANs) are a widely used framework for learning generative models. Wasserstein GANs (WGANs), one of the most successful variants of GANs, require solving a minmax optimization problem to global optimality, but are in practice successfully trained using stochastic gradient descent-ascent.…
Optimizes binary regression models with gradient ascent-descent methods.
problem Regression problems with binary weights in quantized learning and digital communication.
method Maximin optimization using gradient ascent-descent methods.
result The approach is optimal in linear regression with low noise and robust regression with few outliers.
We consider nonconvex-concave minimax optimization problems of the form , where is strongly-concave in but possibly nonconvex in and is a convex and compact set. We focus on the stochastic setting, where we can only access an…
New algorithm solves non-convex, non-differentiable min-max games.
problem Limited theoretical understanding of non-smooth min-max games.
method Proximal gradient descent-ascent algorithm for convex-strongly convex games.
result Algorithm converges to ε-Nash equilibrium with polynomial gradient evaluations.
Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcs.LG
New algorithms ensure reproducibility and optimal convergence in convex optimization.
problem Trade-off between reproducibility and convergence rate in convex optimization.
method Regularization-based algorithms for smooth convex minimization and minimax optimization.
result Achieves optimal reproducibility and near-optimal gradient complexity for various oracle settings.
On Policy Gradientscs.LG
The goal of policy gradient approaches is to find a policy in a given class of policies which maximizes the expected return. Given a differentiable model of the policy, we want to apply a gradient-ascent technique to reach a local optimum. We mainly use gradient ascent, because it is theoretically well researched. The …
Epoch-GDA achieves optimal convergence rate for SCSC min-max problems.
problem Solving stochastic min-max problems with strong convexity and strong concavity.
method Epoch-wise stochastic gradient descent ascent method (Epoch-GDA) without additional assumptions.
result Achieves the optimal rate of for the duality gap of general SCSC min-max problems.
Paper studies convergence of Mean-Field GDA dynamics for MNE of continuous games.
problem Finding mixed Nash equilibria in continuous games.
method Two-scale Mean-Field Gradient Descent Ascent dynamics.
result Two-scale Mean-Field GDA converges exponentially to MNE without convexity assumptions.
Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked go…
This paper introduces a new method to evaluate multiple policies simultaneously.
problem Estimating the value of many policies for a single set of states.
method Developed a scalable, differentiable fingerprinting mechanism to represent complex policies.
result The method can produce policies that outperform those that generated the training data, in zero-shot manner.
Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is often used in practice. Our main contribution is to introduce an accelerated mini-batch version of SDC…
Improves BED scalability for implicit models.
problem Designing experiments for implicit models with intractable data distributions.
method Hybrid gradient approach combining variational MI estimator, ES, and SGA.
result Significantly improves scalability of BED for implicit models.
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.
Method identifies mixed Nash equilibria in high dimensions for training mixtures of GANs.
problem Finding Nash equilibria in two-player zero-sum continuous games, especially in high dimensions.
method Parametrizing mixed strategies as mixtures of particles, updating their positions and weights using gradient descent-ascent.
result Global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic.
Paper proposes algorithms for solving nonconvex-nonconcave problems with complexity guarantees.
problem Nonconvex-nonconcave minimax problems with PL condition.
method Zeroth-order AGDA and VRAGDA algorithms.
result Iteration complexities for obtaining ε-stationary points.
Study local convergence of GDA for training GANs with kernel-based discriminators.
problem Analyzing the local dynamics of GDA for GANs with kernel-based discriminators.
method Linearization of a non-linear dynamical system, under an isolated points model assumption.
result Showed phase transitions indicating convergence, oscillation, or divergence of GDA.
Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradientscs.LG
New framework improves variational inference with Markov chain methods.
problem Challenges of minimizing KL divergence with stochastic gradient descent.
method Markov chain score ascent (MCSA) methods, including parallel MCSA (pMCSA).
result Improved theoretical and empirical performance of MCSA methods.
We introduce a useful tool for analyzing boosting algorithms called the ``smooth margin function,'' a differentiable approximation of the usual margin for boosting algorithms. We present two boosting algorithms based on this smooth margin, ``coordinate ascent boosting'' and ``approximate coordinate ascent boosting,'' w…
Paper improves risk bounds for nonconvex-strongly-concave minimax problems.
problem Achieving sharper risk bounds for nonconvex-strongly-concave minimax problems.
method Using uniform localized convergence to derive high probability generalization error bounds.
result Derives n times faster excess primal risk bounds for popular algorithms.
This paper analyzes saddle points and minimax points in non-convex smooth games.
problem Understanding local optimal points in non-convex smooth games.
method Comprehensive analysis of local minimax points, including their optimality conditions and stability.
result Local saddle points are uniformly local minimax points under mild continuity assumptions.
RSGDA improves convergence rates for nonconvex-strongly concave optimization.
problem Optimization of nonconvex-strongly concave problems.
method Randomized Stochastic Gradient Descent Ascent (RSGDA) with optimal loop sizes.
result First almost sure convergence rates for SGDA algorithms on nonconvex-strongly concave settings.
Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscs.LG
This paper analyzes OGDA and EG methods for nonconvex minimax problems.
problem Theoretical guarantees of OGDA and EG methods in nonconvex settings.
method Unified analysis through single-call extra-gradient methods.
result Established convergence of OGDA and EG methods under NC-SC and NC-C settings.