Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method

DOI10.4230/LIPIcs.ITCS.2018.23zbMath1462.90088arXiv1706.04680MaRDI QIDQ4993286

Jelena Diakonikolas, Lorenzo Orecchia

Publication date: 15 June 2021

Full work available at URL: https://arxiv.org/abs/1706.04680

zbMATH Keywords

discretizationdynamical systemsaccelerationfirst-order methods

Mathematics Subject Classification ID

Convex programming (90C25)

Related Items (7)

Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization ⋮ Cyclic Coordinate Dual Averaging with Extrapolation ⋮ No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization ⋮ The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods ⋮ Computing the Best Approximation over the Intersection of a Polyhedral Set and the Doubly Nonnegative Cone ⋮ Unified Acceleration of High-Order Algorithms under General Hölder Continuity ⋮ Generalized Momentum-Based Methods: A Hamiltonian Perspective

Uses Software

• NESUN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• Gradient methods for minimizing composite functions
• First-order methods of smooth convex optimization with inexact oracle
• An optimal method for stochastic composite optimization
• Universal gradient methods for convex optimization problems
• Accelerating the cubic regularization of Newton's method on convex problems
• Introductory lectures on convex optimization. A basic course.
• Lectures on Modern Convex Optimization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Solving Ordinary Differential Equations I
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Excessive Gap Technique in Nonsmooth Convex Minimization
• Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel
• QIP = PSPACE
• A new approach to computing maximum flows using electrical flows
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time

This page was built for publication: Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method