p7math.OC

math.OC

855 papers

Regularized Nonlinear Acceleration

Damien Scieur, Alexandre d'Aspremont, Francis Bach

1606.04133

Accelerated Methods for Non-Convex Optimization

Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford

1611.00756

Linear Convergence of Primal-Dual Gradient Methods and their Performance in Distributed Optimization

Sulaiman A. Alghunaim, Ali H. Sayed

1904.01196

Recurrent neural networks: vanishing and exploding gradients are not the end of the story

Nicolas Zucchet, Antonio Orvieto

2405.21064

Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach

Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, Sujay Sanghavi

1609.03240

A Theory on Adam Instability in Large-Scale Machine Learning

Igor Molybog, Peter Albert, Moya Chen, Zachary DeVito, David Esiobu, Naman Goyal, Punit Singh Koura, Sharan Narang, Andrew Poulton, Ruan Silva, Binh Tang, Diana Liskovich, Puxin Xu, Yuchen Zhang, Melanie Kambadur, Stephen Roller, Susan Zhang

2304.09871

signSGD: Compressed Optimisation for Non-Convex Problems

Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, Anima Anandkumar

1802.04434

Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks

Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu

1811.08888

Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers

Zeyuan Allen-Zhu, Yuanzhi Li, Yingyu Liang

1811.04918

SMART: Robust and Efficient Fine-Tuning for Pre-trained Natural Language Models through Principled Regularized Optimization

Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, Tuo Zhao

1911.03437

Training Deep Learning Models with Norm-Constrained LMOs

Thomas Pethick, Wanyun Xie, Kimon Antonakopoulos, Zhenyu Zhu, Antonio Silveti-Falls, Volkan Cevher

2502.07529

Orthonormal Expansion l1-Minimization Algorithms for Compressed Sensing

Zai Yang, Cishen Zhang, Jun Deng, Wenmiao Lu

1108.5037

Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit

Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, Cyril Zhang

2207.08799

How Does Adaptive Optimization Impact Local Neural Network Geometry?

Kaiqi Jiang, Dhruv Malik, Yuanzhi Li

2211.02254

Decoupled Weight Decay Regularization

Ilya Loshchilov, Frank Hutter

1711.05101

On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima

Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, Ping Tak Peter Tang

1609.04836

SGDR: Stochastic Gradient Descent with Warm Restarts

Ilya Loshchilov, Frank Hutter

1608.03983

Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

Mahdi Soltanolkotabi, Adel Javanmard, Jason D. Lee

1707.04926

Learning to Optimize

Ke Li, Jitendra Malik

1606.01885

Geometric Median in Nearly Linear Time

Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford

1606.05225

On the Convergence Rate of Training Recurrent Neural Networks

Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song

1810.12065

Can SGD Learn Recurrent Neural Networks with Provable Generalization?

Zeyuan Allen-Zhu, Yuanzhi Li

1902.01028

The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares

Rong Ge, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli

1904.12838

Breaking the Curse of Dimensionality with Convex Neural Networks

Francis Bach

1412.8690

A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach

Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil

1901.08511

AIDE: Fast and Communication Efficient Distributed Optimization

Sashank J. Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczós, Alex Smola

1608.06879

Convex Optimization: Algorithms and Complexity

Sébastien Bubeck

1405.4980

Learning ReLUs via Gradient Descent

Mahdi Soltanolkotabi

1705.04591

Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method

Anatoli Juditsky, Alexander Nazin, Arkadi Nemirovsky, Alexandre Tsybakov

1907.02707

Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs

Alon Brutzkus, Amir Globerson

1702.07966

On sums and convex combinations of projectors onto convex sets

Heinz H. Bauschke, Minh N. Bui, Xianfu Wang

1802.02287

Low-rank Matrix Completion using Alternating Minimization

Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi

1212.0467

How degenerate is the parametrization of neural networks with the ReLU activation function?

Julius Berner, Dennis Elbrächter, Philipp Grohs

1905.09803

Stochastic Block BFGS: Squeezing More Curvature out of Data

Robert M. Gower, Donald Goldfarb, Peter Richtárik

1603.09649

Tight Complexity Bounds for Optimizing Composite Objectives

Blake Woodworth, Nathan Srebro

1605.08003

Stochastic Variance Reduction for Nonconvex Optimization

Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, Alex Smola

1603.06160

Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

Zeyuan Allen-Zhu, Lorenzo Orecchia

1407.1537

Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

Yuchen Zhang, Lin Xiao

1409.3257

A geometric alternative to Nesterov's accelerated gradient descent

Sébastien Bubeck, Yin Tat Lee, Mohit Singh

1506.08187

Gradient Descent Learns Linear Dynamical Systems

Moritz Hardt, Tengyu Ma, Benjamin Recht

1609.05191

A Lower Bound for the Optimization of Finite Sums

Alekh Agarwal, Leon Bottou

1410.0723

Understanding the unstable convergence of gradient descent

Kwangjun Ahn, Jingzhao Zhang, Suvrit Sra

2204.01050

Sub-Sampled Newton Methods I: Globally Convergent Algorithms

Farbod Roosta-Khorasani, Michael W. Mahoney

1601.04737

Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver

Zeyuan Allen-Zhu, Yin Tat Lee, Lorenzo Orecchia

1507.02259

Variance Reduction for Faster Non-Convex Optimization

Zeyuan Allen-Zhu, Elad Hazan

1603.05643

An optimal randomized incremental gradient method

Guanghui Lan, Yi Zhou

1507.02000

A Linearly-Convergent Stochastic L-BFGS Algorithm

Philipp Moritz, Robert Nishihara, Michael I. Jordan

1508.02087

A Universal Catalyst for First-Order Optimization

Hongzhou Lin, Julien Mairal, Zaid Harchaoui

1506.02186

Communication Complexity of Distributed Convex Learning and Optimization

Yossi Arjevani, Ohad Shamir

1506.01900

Optimal Black-Box Reductions Between Optimization Objectives

Zeyuan Allen-Zhu, Elad Hazan

1603.05642

Gotta Go Fast When Generating Data with Score-Based Models

Alexia Jolicoeur-Martineau, Ke Li, Rémi Piché-Taillefer, Tal Kachman, Ioannis Mitliagkas

2105.14080

Katyusha: The First Direct Acceleration of Stochastic Gradient Methods

Zeyuan Allen-Zhu

1603.05953

Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling

Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, Yang Yuan

1512.09103

Bounding and Counting Linear Regions of Deep Neural Networks

Thiago Serra, Christian Tjandraatmadja, Srikumar Ramalingam

1711.02114

Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence

Mert Pilanci, Martin J. Wainwright

1505.02250

Much Faster Algorithms for Matrix Scaling

Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, Avi Wigderson

1704.02315

Minimizing Finite Sums with the Stochastic Average Gradient

Mark Schmidt, Nicolas Le Roux, Francis Bach

1309.2388

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD

Zeyuan Allen-Zhu

1801.02982

Stochastic Dual Ascent for Solving Linear Systems

Robert Mansel Gower, Peter Richtarik

1512.06890

Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

Francis Bach, Eric Moulines

1306.2119

A Stochastic Quasi-Newton Method for Large-Scale Optimization

R. H. Byrd, S. L. Hansen, J. Nocedal, Y. Singer

1401.7020

Semi-Stochastic Coordinate Descent

Jakub Konečný, Zheng Qu, Peter Richtárik

1412.6293

Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields

Mark Schmidt, Reza Babanezhad, Mohamed Osama Ahmed, Aaron Defazio, Ann Clifton, Anoop Sarkar

1504.04406

On Stochastic Gradient and Subgradient Methods with Adaptive Steplength Sequences

Farzad Yousefian, Angelia Nedić, Uday V. Shanbhag

1105.4549

Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm

Deanna Needell, Nathan Srebro, Rachel Ward

1310.5715

A Proximal Stochastic Gradient Method with Progressive Variance Reduction

Lin Xiao, Tong Zhang

1403.4699

Rank-Sparsity Incoherence for Matrix Decomposition

Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, Alan S. Willsky

0906.2220

Forward-backward quasi-Newton methods for nonsmooth optimization problems

Lorenzo Stella, Andreas Themelis, Panagiotis Patrinos

1604.08096

Latent variable graphical model selection via convex optimization

Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. Willsky

1008.1290

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Benjamin Recht, Maryam Fazel, Pablo A. Parrilo

0706.4138

NESTA: A Fast and Accurate First-order Method for Sparse Recovery

Stephen Becker, Jerome Bobin, Emmanuel Candes

0904.3367

How to Escape Saddle Points Efficiently

Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, Michael I. Jordan

1703.00887

Communication-Efficient Algorithms for Decentralized and Stochastic Optimization

Guanghui Lan, Soomin Lee, Yi Zhou

1701.03961

Coordinate Descent Algorithms

Stephen J. Wright

1502.04759

Convex and Non-convex Optimization Under Generalized Smoothness

Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, Ali Jadbabaie

2306.01264

Prodigy: An Expeditiously Adaptive Parameter-Free Learner

Konstantin Mishchenko, Aaron Defazio

2306.06101

Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms

Andreas Themelis, Lorenzo Stella, Panagiotis Patrinos

1606.06256

Learning-Rate-Free Learning by D-Adaptation

Aaron Defazio, Konstantin Mishchenko

2301.07733

Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient

Puya Latafat, Andreas Themelis, Lorenzo Stella, Panagiotis Patrinos

2301.04431

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution

Antonio Orvieto, Simon Lacoste-Julien, Nicolas Loizou

2205.04583

DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule

Maor Ivgi, Oliver Hinder, Yair Carmon

2302.12022

Making SGD Parameter-Free

Yair Carmon, Oliver Hinder

2205.02160

The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

Aurélien Garivier, Olivier Cappé

1102.2490

Deterministic Sequencing of Exploration and Exploitation for Multi-Armed Bandit Problems

Sattar Vakili, Keqin Liu, Qing Zhao

1106.6104

Computing in Operations Research using Julia

Miles Lubin, Iain Dunning

1312.1431

Implicit Bias of AdamW: $\ell_\infty$ Norm Constrained Optimization

Shuo Xie, Zhiyuan Li

2404.04454

Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training

Hong Liu, Zhiyuan Li, David Hall, Percy Liang, Tengyu Ma

2305.14342

Adam Can Converge Without Any Modification On Update Rules

Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, Zhi-Quan Luo

2208.09632

Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability

Alex Damian, Eshaan Nichani, Jason D. Lee

2209.15594

Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be

Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, Mark Schmidt

2304.13960

Robustness to Unbounded Smoothness of Generalized SignSGD

Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, Zhenxun Zhuang

2208.11195

On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport

Lenaic Chizat, Francis Bach

1805.09545

Scaling provable adversarial defenses

Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, J. Zico Kolter

1805.12514

Using Optimization to Solve Positive LPs Faster in Parallel

Zeyuan Allen-Zhu, Lorenzo Orecchia

1407.1925

Dimension-Free Iteration Complexity of Finite Sum Optimization Problems

Yossi Arjevani, Ohad Shamir

1606.09333

Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey

Dimitri P. Bertsekas

1507.01030

Communication Efficient Distributed Optimization using an Approximate Newton-type Method

Ohad Shamir, Nathan Srebro, Tong Zhang

1312.7853

Sub-Sampled Newton Methods II: Local Convergence Rates

Farbod Roosta-Khorasani, Michael W. Mahoney

1601.04738

X-Armed Bandits

Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvari

1001.4475

Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates

Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia

1506.04838

Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity

Zheng Qu, Peter Richtárik

1412.8060

Non-convex Finite-Sum Optimization Via SCSG Methods

Lihua Lei, Cheng Ju, Jianbo Chen, Michael I. Jordan

1706.09156

Natasha 2: Faster Non-Convex Optimization Than SGD

Zeyuan Allen-Zhu

1708.08694

Randomized Dual Coordinate Ascent with Arbitrary Sampling

Zheng Qu, Peter Richtárik, Tong Zhang

1411.5873

Introduction to Online Convex Optimization

Elad Hazan

1909.05207

Communication-Efficient Distributed Dual Coordinate Ascent

Martin Jaggi, Virginia Smith, Martin Takáč, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, Michael I. Jordan

1409.1458

Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization

Zeyuan Allen-Zhu

1802.03866

Finding Approximate Local Minima Faster than Gradient Descent

Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, Tengyu Ma

1611.01146

A Sufficient Condition for Convergences of Adam and RMSProp

Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, Wei Liu

1811.09358

Convergence and Dynamical Behavior of the ADAM Algorithm for Non-Convex Stochastic Optimization

Anas Barakat, Pascal Bianchi

1810.02263

A general system of differential equations to model first order adaptive algorithms

André Belotto da Silva, Maxime Gazeau

1810.13108

Funnel Libraries for Real-Time Robust Feedback Motion Planning

Anirudha Majumdar, Russ Tedrake

1601.04037

Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method

Lihua Lei, Michael I. Jordan

1609.03261

Fast Multiple Splitting Algorithms for Convex Optimization

Donald Goldfarb, Shiqian Ma

0912.4570

On the Linear Convergence of the Alternating Direction Method of Multipliers

Mingyi Hong, Zhi-Quan Luo

1208.3922

Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization

Shai Shalev-Shwartz, Tong Zhang

1209.1873

Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation

Zheng Qu, Peter Richtárik

1412.8063

Fast Distributed Coordinate Descent for Non-Strongly Convex Losses

Olivier Fercoq, Zheng Qu, Peter Richtárik, Martin Takáč

1405.5300

An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization

Qihang Lin, Zhaosong Lu, Lin Xiao

1407.1296

Distributed Block Coordinate Descent for Minimizing Partially Separable Functions

Jakub Marecek, Peter Richtarik, Martin Takac

1406.0238

Distributed Coordinate Descent Method for Learning with Big Data

Peter Richtárik, Martin Takáč

1310.2059

"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Yair Carmon, Oliver Hinder, John C. Duchi, Aaron Sidford

1705.02766

Distributed Optimization with Arbitrary Local Solvers

Chenxin Ma, Jakub Konečný, Martin Jaggi, Virginia Smith, Michael I. Jordan, Peter Richtárik, Martin Takáč

1512.04039

Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss

Yuchen Zhang, Lin Xiao

1501.00263

An Asynchronous Parallel Stochastic Coordinate Descent Algorithm

Ji Liu, Stephen J. Wright, Christopher Ré, Victor Bittorf, Srikrishna Sridhar

1311.1873

From Knothe's transport to Brenier's map and a continuation method for optimal transport

Guillaume Carlier, Alfred Galichon, Filippo Santambrogio

0810.4153

Global Optimality of Local Search for Low Rank Matrix Recovery

Srinadh Bhojanapalli, Behnam Neyshabur, Nathan Srebro

1605.07221

Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets

Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, Tianbao Yang

1912.11940

On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

Xiaoyu Li, Francesco Orabona

1805.08114

Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions

Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, Tianbao Yang

1808.06296

Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice

Hongzhou Lin, Julien Mairal, Zaid Harchaoui

1712.05654

SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

Cong Fang, Chris Junchi Li, Zhouchen Lin, Tong Zhang

1807.01695

Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration

Soham De, Anirbit Mukherjee, Enayat Ullah

1807.06766

On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization

Xiangyi Chen, Sijia Liu, Ruoyu Sun, Mingyi Hong

1808.02941

WNGrad: Learn the Learning Rate in Gradient Descent

Xiaoxia Wu, Rachel Ward, Léon Bottou

1803.02865

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi

1509.03917

When Are Nonconvex Problems Not Scary?

Ju Sun, Qing Qu, John Wright

1510.06096

Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization

Guanghui Lan, Yu Yang

1805.05411

An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration

Hongzhou Lin, Julien Mairal, Zaid Harchaoui

1610.00960

Catalyst Acceleration for Gradient-Based Non-Convex Optimization

Courtney Paquette, Hongzhou Lin, Dmitriy Drusvyatskiy, Julien Mairal, Zaid Harchaoui

1703.10993

Complete Dictionary Recovery over the Sphere

Ju Sun, Qing Qu, John Wright

1504.06785

Adaptive Proximal Gradient Method for Convex Optimization

Yura Malitsky, Konstantin Mishchenko

2308.02261

Accelerated Gradient Descent via Long Steps

Benjamin Grimmer, Kevin Shu, Alex L. Wang

2309.09961

Stochastic Cubic Regularization for Fast Nonconvex Optimization

Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, Michael I. Jordan

1711.02838

Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

Samet Oymak, Mahdi Soltanolkotabi

1812.10004

Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems

Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, Volkan Cevher

2302.09831

Optimal Algorithms for Distributed Optimization

César A. Uribe, Soomin Lee, Alexander Gasnikov, Angelia Nedić

1712.00232

Non-Convex Distributed Optimization

Tatiana Tatarenko, Behrouz Touri

1512.00895

Non-convex Optimization for Machine Learning

Prateek Jain, Purushottam Kar

1712.07897

Acceleration Methods

Alexandre d'Aspremont, Damien Scieur, Adrien Taylor

2101.09545

Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization

Ziyi Chen, Yi Zhou, Yingbin Liang, Zhaosong Lu

2303.02854

Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD

Matthew Faw, Litu Rout, Constantine Caramanis, Sanjay Shakkottai

2302.06570

Convergence of Adam Under Relaxed Assumptions

Haochuan Li, Alexander Rakhlin, Ali Jadbabaie

2304.13972

A Distributed Newton Method for Large Scale Consensus Optimization

Rasul Tutunov, Haitham Bou Ammar, Ali Jadbabaie

1606.06593

Stochastic Nested Variance Reduction for Nonconvex Optimization

Dongruo Zhou, Pan Xu, Quanquan Gu

1806.07811

Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Rong Ge, Furong Huang, Chi Jin, Yang Yuan

1503.02101

Probabilistic Interpretation of Linear Solvers

Philipp Hennig

1402.2058

Decentralized Learning for Multi-player Multi-armed Bandits

Dileep Kalathil, Naumaan Nayyar, Rahul Jain

1206.3582

Beyond the Golden Ratio for Variational Inequality Algorithms

Ahmet Alacaoglu, Axel Böhm, Yura Malitsky

2212.13955

A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

Yuchen Zhang, Percy Liang, Moses Charikar

1702.05575

A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization

Aryan Mokhtari, Wei Shi, Qing Ling, Alejandro Ribeiro

1602.00596

Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization

Jelena Diakonikolas, Constantinos Daskalakis, Michael I. Jordan

2011.00364

Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities

Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, Yi Ma

2103.04410

The Complexity of Constrained Min-Max Optimization

Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis

2009.09623

An Improved Analysis of Stochastic Gradient Descent with Momentum

Yanli Liu, Yuan Gao, Wotao Yin

2007.07989

On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization

Dongruo Zhou, Jinghui Chen, Yuan Cao, Ziyan Yang, Quanquan Gu

1808.05671

Provably Faster Gradient Descent via Long Steps

Benjamin Grimmer

2307.06324

Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards

Yi Gai, Bhaskar Krishnamachari, Rahul Jain

1011.4748

DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method

Ahmed Khaled, Konstantin Mishchenko, Chi Jin

2305.16284

Neon2: Finding Local Minima via First-Order Oracles

Zeyuan Allen-Zhu, Yuanzhi Li

1711.06673

Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities

Jelena Diakonikolas

2002.08872

On the convergence of single-call stochastic extra-gradient methods

Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

1908.08465

Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar

2002.00057

Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems

Junchi Yang, Negar Kiyavash, Niao He

2002.09621

Understanding the Role of Momentum in Stochastic Gradient Methods

Igor Gitman, Hunter Lang, Pengchuan Zhang, Lin Xiao

1910.13962

Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods

Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D. Lee, Meisam Razaviyayn

1902.08297

Optimization for deep learning: theory and algorithms

Ruoyu Sun

1912.08957

Accelerating Smooth Games by Manipulating Spectral Shapes

Waïss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, Gauthier Gidel

2001.00602

On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization

Hao Yu, Rong Jin, Sen Yang

1905.03817

SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients

Feihu Huang, Junyi Li, Heng Huang

2106.08208

Improved Analysis of Clipping Algorithms for Non-convex Optimization

Bohang Zhang, Jikai Jin, Cong Fang, Liwei Wang

2010.02519

A Novel Convergence Analysis for Algorithms of the Adam Family

Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, Tianbao Yang

2112.03459

Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent

James P. Bailey, Gauthier Gidel, Georgios Piliouras

1907.04392

Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration

Congliang Chen, Li Shen, Fangyu Zou, Wei Liu

2101.05471

Last-iterate convergence rates for min-max optimization

Jacob Abernethy, Kevin A. Lai, Andre Wibisono

1906.02027

Momentum Improves Normalized SGD

Ashok Cutkosky, Harsh Mehta

2002.03305

Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning

Hao Yu, Sen Yang, Shenghuo Zhu

1807.06629

Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping

Eduard Gorbunov, Marina Danilova, Alexander Gasnikov

2005.10785

Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains

Aymeric Dieuleveut, Alain Durmus, Francis Bach

1707.06386

On the insufficiency of existing momentum schemes for Stochastic Optimization

Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, Sham M. Kakade

1803.05591

Local SGD Converges Fast and Communicates Little

Sebastian U. Stich

1805.09767

Understanding Gradient Clipping in Private SGD: A Geometric Perspective

Xiangyi Chen, Zhiwei Steven Wu, Mingyi Hong

2006.15429

Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs

Angelia Nedich, Alex Olshevsky, Wei Shi

1607.03218

Fully Decentralized Policies for Multi-Agent Systems: An Information Theoretic Approach

Roel Dobbe, David Fridovich-Keil, Claire Tomlin

1707.06334

Distributed Learning in Multi-Armed Bandit with Multiple Players

Keqin Liu, Qing Zhao

0910.2065

The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

2011.01929

On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games

Eric V. Mazumdar, Michael I. Jordan, S. Shankar Sastry

1901.00838

The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization

Constantinos Daskalakis, Ioannis Panageas

1807.03907

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization

Constantinos Daskalakis, Ioannis Panageas

1807.04252

Asynchronous Decentralized Parallel Stochastic Gradient Descent

Xiangru Lian, Wei Zhang, Ce Zhang, Ji Liu

1710.06952

Why gradient clipping accelerates training: A theoretical justification for adaptivity

Jingzhao Zhang, Tianxing He, Suvrit Sra, Ali Jadbabaie

1905.11881

Why are Adaptive Methods Good for Attention Models?

Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J Reddi, Sanjiv Kumar, Suvrit Sra

1912.03194

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

Blake Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, Nathan Srebro

1805.10222

Accelerating Stochastic Gradient Descent For Least Squares Regression

Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford

1704.08227

Parallel Coordinate Descent Methods for Big Data Optimization

Peter Richtárik, Martin Takáč

1212.0873

Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, Benjamin Recht

1507.03566

Optimal algorithms for smooth and strongly convex distributed optimization in networks

Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, Laurent Massoulié

1702.08704

Primal-Dual Rates and Certificates

Celestine Dünner, Simone Forte, Martin Takáč, Martin Jaggi

1602.05205

Distributed Delayed Stochastic Optimization

Alekh Agarwal, John C. Duchi

1104.5525

Generalized Conditional Gradient for Sparse Estimation

Yaoliang Yu, Xinhua Zhang, Dale Schuurmans

1410.4828

A Geometric Analysis of Phase Retrieval

Ju Sun, Qing Qu, John Wright

1602.06664

Accelerated, Parallel and Proximal Coordinate Descent

Olivier Fercoq, Peter Richtárik

1312.5799

Gradient Descent Converges to Minimizers

Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht

1602.04915

Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization

Angelia Nedić, Alex Olshevsky, Michael G. Rabbat

1709.08765

Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis

Kun Yuan, Bicheng Ying, Xiaochuan Zhao, Ali H. Sayed

1702.05142

Beyond Convexity: Stochastic Quasi-Convex Optimization

Elad Hazan, Kfir Y. Levy, Shai Shalev-Shwartz

1507.02030

Lower bounds on the size of semidefinite programming relaxations

James R. Lee, Prasad Raghavendra, David Steurer

1411.6317

Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

John Duchi, Alekh Agarwal, Martin Wainwright

1005.2012

Optimal Distributed Online Prediction using Mini-Batches

Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, Lin Xiao

1012.1367

Escaping Saddle Points with Adaptive Gradient Methods

Matthew Staib, Sashank J. Reddi, Satyen Kale, Sanjiv Kumar, Suvrit Sra

1901.09149

Acceleration of RED via Vector Extrapolation

Tao Hong, Yaniv Romano, Michael Elad

1805.02158

Slow Learners are Fast

John Langford, Alexander Smola, Martin Zinkevich

0911.0491

Three Puzzles on Mathematics, Computation, and Games

Gil Kalai

1801.02602

Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

Aymeric Dieuleveut, Nicolas Flammarion, Francis Bach

1602.05419

Decentralized RLS with Data-Adaptive Censoring for Regressions over Large-Scale Networks

Zifeng Wang, Zheng Yu, Qing Ling, Dimitris Berberidis, Georgios B. Giannakis

1612.08263

A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates

Zhi Li, Wei Shi, Ming Yan

1704.07807

A Lyapunov Analysis of Momentum Methods in Optimization

Ashia C. Wilson, Benjamin Recht, Michael I. Jordan

1611.02635

On Optimal Probabilities in Stochastic Coordinate Descent Methods

Peter Richtárik, Martin Takáč

1310.3438

Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent

Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, Ji Liu

1705.09056

Mini-Batch Primal and Dual Methods for SVMs

Martin Takáč, Avleen Bijral, Peter Richtárik, Nathan Srebro

1303.2314

The Power of Normalization: Faster Evasion of Saddle Points

Kfir Y. Levy

1611.04831

Harnessing Smoothness to Accelerate Distributed Optimization

Guannan Qu, Na Li

1605.07112

Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis

Maxim Raginsky, Alexander Rakhlin, Matus Telgarsky

1702.03849

A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order

Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, Ji Liu

1606.00498

Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization

Necdet Serhat Aybat, Zi Wang, Tianyi Lin, Shiqian Ma

1512.08122

Convergence Rate of Distributed ADMM over Networks

Ali Makhdoumi, Asuman Ozdaglar

1601.00194

Phase Retrieval via Wirtinger Flow: Theory and Algorithms

Emmanuel Candes, Xiaodong Li, Mahdi Soltanolkotabi

1407.1065

On the low-rank approach for semidefinite programs arising in synchronization and community detection

Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski

1602.04426

Proximal Quasi-Newton Methods for Regularized Convex Optimization with Linear and Accelerated Sublinear Convergence Rates

Hiva Ghanbari, Katya Scheinberg

1607.03081

Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints

Laurent Lessard, Benjamin Recht, Andrew Packard

1408.3595

Performance of first-order methods for smooth convex minimization: a novel approach

Yoel Drori, Marc Teboulle

1206.3209

Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, Yoshua Bengio

1406.2572

Phase retrieval for imaging problems

Fajwel Fogel, Irène Waldspurger, Alexandre d'Aspremont

1304.7735

The local convexity of solving systems of quadratic equations

Chris D. White, Sujay Sanghavi, Rachel Ward

1506.07868

Adaptive Gradient Descent without Descent

Yura Malitsky, Konstantin Mishchenko

1910.09529

Sparse PCA via Bipartite Matchings

Megasthenis Asteris, Dimitris Papailiopoulos, Anastasios Kyrillidis, Alexandros G. Dimakis

1508.00625

Inexact Successive Quadratic Approximation for Regularized Optimization

Ching-pei Lee, Stephen J. Wright

1803.01298

Lower Bounds for Finding Stationary Points I

Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford

1710.11606

Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Chi Jin, Praneeth Netrapalli, Michael I. Jordan

1711.10456

On the Iteration Complexity of Oblivious First-Order Optimization Algorithms

Yossi Arjevani, Ohad Shamir

1605.03529

Asynchronous Optimization Over Heterogeneous Networks via Consensus ADMM

Sandeep Kumar, Rahul Jain, Ketan Rajawat

1605.00076

DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

Aryan Mokhtari, Wei Shi, Qing Ling, Alejandro Ribeiro

1508.02073

Convex Optimization for Big Data

Volkan Cevher, Stephen Becker, Mark Schmidt

1411.0972

Network Newton-Part I: Algorithm and Convergence

Aryan Mokhtari, Qing Ling, Alejandro Ribeiro

1504.06017

A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data

Mingyi Hong, Meisam Razaviyayn, Zhi-Quan Luo, Jong-Shi Pang

1511.02746

Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent

Chi Jin, Sham M. Kakade, Praneeth Netrapalli

1605.08370

The non-convex Burer-Monteiro approach works on smooth semidefinite programs

Nicolas Boumal, Vladislav Voroninski, Afonso S. Bandeira

1606.04970

Newton-like method with diagonal correction for distributed optimization

Dragana Bajovic, Dusan Jakovetic, Natasa Krejic, Natasa Krklec Jerinkic

1509.01703

Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack

Anna R. Karlin, Claire Mathieu, C. Thach Nguyen

1007.1283

A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization

Shun Zheng, Jialei Wang, Fen Xia, Wei Xu, Tong Zhang

1604.03763

DSA: Decentralized Double Stochastic Averaging Gradient Algorithm

Aryan Mokhtari, Alejandro Ribeiro

1506.04216

A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization

Ching-pei Lee, Cong Han Lim, Stephen J. Wright

1803.01370

Phase Retrieval from Coded Diffraction Patterns

Emmanuel Candes, Xiaodong Li, Mahdi Soltanolkotabi

1310.3240

Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties

Ji Liu, Stephen J. Wright

1403.3862

From Averaging to Acceleration, There is Only a Step-size

Nicolas Flammarion, Francis Bach

1504.01577

Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, Michael I. Jordan

1507.06970

On Distributed Cooperative Decision-Making in Multiarmed Bandits

Peter Landgren, Vaibhav Srivastava, Naomi Ehrich Leonard

1512.06888

Newton-Raphson Consensus for Distributed Convex Optimization

Damiano Varagnolo, Filippo Zanella, Angelo Cenedese, Gianluigi Pillonetto, Luca Schenato

1511.01509

Stable Architectures for Deep Neural Networks

Eldad Haber, Lars Ruthotto

1705.03341

Mutually Unbiased Bases and Semi-definite Programming

Stephen Brierley, Stefan Weigert

1006.0093

Phase Recovery, MaxCut and Complex Semidefinite Programming

Irène Waldspurger, Alexandre d'Aspremont, Stéphane Mallat

1206.0102

Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

Yuejie Chi, Yue M. Lu, Yuxin Chen

1809.09573

Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks

Gauthier Gidel, Francis Bach, Simon Lacoste-Julien

1904.13262

First-order methods almost always avoid saddle points: the case of vanishing step-sizes

Ioannis Panageas, Georgios Piliouras, Xiao Wang

1906.07772

Inference and Uncertainty Quantification for Noisy Matrix Completion

Yuxin Chen, Jianqing Fan, Cong Ma, Yuling Yan

1906.04159

Nonconvex Low-Rank Tensor Completion from Noisy Data

Changxiao Cai, Gen Li, H. Vincent Poor, Yuxin Chen

1911.04436

Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction

Dominik Stöger, Mahdi Soltanolkotabi

2106.15013

Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK

Yuanzhi Li, Tengyu Ma, Hongyang R. Zhang

2007.04596

Phase retrieval with random Gaussian sensing vectors by alternating projections

Irène Waldspurger

1609.03088

Understanding Gradient Descent on Edge of Stability in Deep Learning

Sanjeev Arora, Zhiyuan Li, Abhishek Panigrahi

2205.09745

On the Convergence of Adam and Beyond

Sashank J. Reddi, Satyen Kale, Sanjiv Kumar

1904.09237

Optimization Methods for Large-Scale Machine Learning

Léon Bottou, Frank E. Curtis, Jorge Nocedal

1606.04838

Label Noise SGD Provably Prefers Flat Global Minimizers

Alex Damian, Tengyu Ma, Jason D. Lee

2106.06530

Safely Learning to Control the Constrained Linear Quadratic Regulator

Sarah Dean, Stephen Tu, Nikolai Matni, Benjamin Recht

1809.10121

Deep Networks and the Multiple Manifold Problem

Sam Buchanan, Dar Gilboa, John Wright

2008.11245

Global optimality conditions for deep neural networks

Chulhee Yun, Suvrit Sra, Ali Jadbabaie

1707.02444

Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss

Lenaic Chizat, Francis Bach

2002.04486

Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks

Yu Bai, Jason D. Lee

1910.01619

Train faster, generalize better: Stability of stochastic gradient descent

Moritz Hardt, Benjamin Recht, Yoram Singer

1509.01240

Flat minima generalize for low-rank matrix recovery

Lijun Ding, Dmitriy Drusvyatskiy, Maryam Fazel, Zaid Harchaoui

2203.03756

Feature Purification: How Adversarial Training Performs Robust Deep Learning

Zeyuan Allen-Zhu, Yuanzhi Li

2005.10190

Sum-of-squares proofs and the quest toward optimal algorithms

Boaz Barak, David Steurer

1404.5236

Splitting methods with variable metric for KL functions

Pierre Frankel, Guillaume Garrigos, Juan Peypouquet

1405.1357

Network Newton-Part II: Convergence Rate and Implementation

Aryan Mokhtari, Qing Ling, Alejandro Ribeiro

1504.06020

Variable metric inexact line-search based methods for nonsmooth optimization

Silvia Bonettini, Ignace Loris, Federica Porta, Marco Prato

1506.00385

Lower Bounds for Non-Convex Stochastic Optimization

Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth

1912.02365

Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions

Donald Goldfarb, Shiqian Ma, Katya Scheinberg

0912.4571

A Universally Optimal Multistage Accelerated Stochastic Gradient Method

Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, Asuman Ozdaglar

1901.08022

Precise Tradeoffs in Adversarial Training for Linear Regression

Adel Javanmard, Mahdi Soltanolkotabi, Hamed Hassani

2002.10477

Provable defenses against adversarial examples via the convex outer adversarial polytope

Eric Wong, J. Zico Kolter

1711.00851

What Can ResNet Learn Efficiently, Going Beyond Kernels?

Zeyuan Allen-Zhu, Yuanzhi Li

1905.10337

A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints

Nicolas Boumal

1506.00575

HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright

1106.5730

Deep Learning without Poor Local Minima

Kenji Kawaguchi

1605.07110

Adaptive Restart for Accelerated Gradient Schemes

Brendan O'Donoghue, Emmanuel Candes

1204.3982

Krylov Subspace Descent for Deep Learning

Oriol Vinyals, Daniel Povey

1111.4259

Batched High-dimensional Bayesian Optimization via Structural Kernel Learning

Zi Wang, Chengtao Li, Stefanie Jegelka, Pushmeet Kohli

1703.01973

Learning in A Changing World: Restless Multi-Armed Bandit with Unknown Dynamics

Haoyang Liu, Keqin Liu, Qing Zhao

1011.4969

Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize

Ryan D'Orazio, Nicolas Loizou, Issam Laradji, Ioannis Mitliagkas

2110.15412

Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization

Tian Ye, Simon S. Du

2106.14289

Instabilities of Offline RL with Pre-Trained Neural Representation

Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, Sham M. Kakade

2103.04947

Gradient descent GAN optimization is locally stable

Vaishnavh Nagarajan, J. Zico Kolter

1706.04156

Feedback stabilization of discrete-time quantum systems subject to non-demolition measurements with imperfections and delays

Hadis Amini, Abhinav Somaraju, Igor Dotsenko, Clement Sayrin, Mazyar Mirrahimi, Pierre Rouchon

1201.1387

Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution

Cong Ma, Kaizheng Wang, Yuejie Chi, Yuxin Chen

1711.10467

Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks

Yuan Cao, Quanquan Gu

1905.13210

On the Power of Over-parametrization in Neural Networks with Quadratic Activation

Simon S. Du, Jason D. Lee

1803.01206

Spectral Compressed Sensing via Projected Gradient Descent

Jian-Feng Cai, Tianming Wang, Ke Wei

1707.09726

The Non-Bayesian Restless Multi-Armed Bandit: a Case of Near-Logarithmic Regret

Wenhan Dai, Yi Gai, Bhaskar Krishnamachari, Qing Zhao

1011.4752

Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced

Simon S. Du, Wei Hu, Jason D. Lee

1806.00900

Templates for Convex Cone Problems with Applications to Sparse Signal Recovery

Stephen R. Becker, Emmanuel J. Candès, Michael Grant

1009.2065

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence

Nicolas Loizou, Sharan Vaswani, Issam Laradji, Simon Lacoste-Julien

2002.10542

No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis

Rong Ge, Chi Jin, Yi Zheng

1704.00708

Fast Image Recovery Using Variable Splitting and Constrained Optimization

Manya V. Afonso, José M. Bioucas-Dias, Mário A. T. Figueiredo

0910.4887

Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity

Kaiqing Zhang, Sham M. Kakade, Tamer Başar, Lin F. Yang

2007.07461

An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax

Paul Hand, Vladislav Voroninski

1611.03935

Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis

Katya Scheinberg, Xiaocheng Tang

1311.6547

Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems

Christoph Reisinger, Yufei Zhang

1903.06652

Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

Christopher De Sa, Kunle Olukotun, Christopher Ré

1411.1134

Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter

Zeyuan Allen-Zhu

1702.00763

The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices

Zhouchen Lin, Minming Chen, Yi Ma

1009.5055

Alternating Projection, Ptychographic Imaging and Phase Synchronization

Stefano Marchesini, Yu-Chao Tu, Hau-tieng Wu

1402.0550

Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Afonso S. Bandeira, Nicolas Boumal, Amit Singer

1411.3272

A Three-Operator Splitting Scheme and its Optimization Applications

Damek Davis, Wotao Yin

1504.01032

Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Cong Fang, Zhouchen Lin, Tong Zhang

1902.00247

Assessing Algorithmic Fairness with Unobserved Protected Class Using Data Combination

Nathan Kallus, Xiaojie Mao, Angela Zhou

1906.00285

An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

Hamid Reza Feyzmahdavian, Arda Aytekin, Mikael Johansson

1505.04824

The Rate of Convergence of AdaBoost

Indraneel Mukherjee, Cynthia Rudin, Robert E. Schapire

1106.6024

Online Batch Selection for Faster Training of Neural Networks

Ilya Loshchilov, Frank Hutter

1511.06343

A General Analysis of the Convergence of ADMM

Robert Nishihara, Laurent Lessard, Benjamin Recht, Andrew Packard, Michael I. Jordan

1502.02009

ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

Zhimin Peng, Yangyang Xu, Ming Yan, Wotao Yin

1506.02396

Distributed Algorithms for Aggregative Games on Graphs

Jayash Koshal, Angelia Nedić, Uday V. Shanbhag

1605.00267

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition

Hamed Karimi, Julie Nutini, Mark Schmidt

1608.04636

Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers

Xiangfeng Wang, Mingyi Hong, Shiqian Ma, Zhi-Quan Luo

1308.5294

Quantized Adam with Error Feedback

Congliang Chen, Li Shen, Haozhi Huang, Wei Liu

2004.14180

Convergence rates of efficient global optimization algorithms

Adam D. Bull

1101.3501

Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm

TaeHo Yoon, Ernest K. Ryu

2102.07922

Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks

Pratik Chaudhari, Stefano Soatto

1710.11029

Error bounds, quadratic growth, and linear convergence of proximal methods

Dmitriy Drusvyatskiy, Adrian S. Lewis

1602.06661

Distributed Nonconvex Multiagent Optimization Over Time-Varying Networks

Ying Sun, Gesualdo Scutari, Daniel Palomar

1607.00249

Near-Optimal Algorithms for Minimax Optimization

Tianyi Lin, Chi Jin, Michael. I. Jordan

2002.02417

An optimal first order method based on optimal quadratic averaging

Dmitriy Drusvyatskiy, Maryam Fazel, Scott Roy

1604.06543

Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms

Christopher De Sa, Ce Zhang, Kunle Olukotun, Christopher Ré

1506.06438

Breaking Locality Accelerates Block Gauss-Seidel

Stephen Tu, Shivaram Venkataraman, Ashia C. Wilson, Alex Gittens, Michael I. Jordan, Benjamin Recht

1701.03863

Learning One-hidden-layer Neural Networks with Landscape Design

Rong Ge, Jason D. Lee, Tengyu Ma

1711.00501

Directional convergence and alignment in deep learning

Ziwei Ji, Matus Telgarsky

2006.06657

Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval

Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma

1803.07726

Deep Neural Networks Motivated by Partial Differential Equations

Lars Ruthotto, Eldad Haber

1804.04272

Loss landscapes and optimization in over-parameterized non-linear systems and neural networks

Chaoyue Liu, Libin Zhu, Mikhail Belkin

2003.00307

Recovery of Sparse 1-D Signals from the Magnitudes of their Fourier Transform

Kishore Jaganathan, Samet Oymak, Babak Hassibi

1206.1405

Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method

Ju Sun, Qing Qu, John Wright

1511.04777

Efficient First-order Methods for Convex Minimization: a Constructive Approach

Yoel Drori, Adrien B. Taylor

1803.05676

Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization

S. Sundhar Ram, A. Nedich, V. V. Veeravalli

0811.2595

The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance

Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, Rachel Ward

2202.05791

A Singular Value Thresholding Algorithm for Matrix Completion

Jian-Feng Cai, Emmanuel J. Candes, Zuowei Shen

0810.3286

A New Perspective on Shampoo's Preconditioner

Depen Morwani, Itai Shapira, Nikhil Vyas, Eran Malach, Sham Kakade, Lucas Janson

2406.17748

Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always

Ioannis Panageas, Georgios Piliouras, Xiao Wang

1810.05355

Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule

Jason M. Altschuler, Pablo A. Parrilo

2309.07879

Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares

Mert Pilanci, Martin J. Wainwright

1411.0347

A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization

Tsung-Hui Chang

1409.3307

Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits

Paul Reverdy, Vaibhav Srivastava, Naomi E. Leonard

1307.6134

Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems

Luo Luo, Haishan Ye, Zhichao Huang, Tong Zhang

2001.03724

Global Convergence of Online Limited Memory BFGS

Aryan Mokhtari, Alejandro Ribeiro

1409.2045

EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

Wei Shi, Qing Ling, Gang Wu, Wotao Yin

1404.6264

Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation

Sohail Bahmani, Justin Romberg

1610.04210

Efficient-Adam: Communication-Efficient Distributed Adam

Congliang Chen, Li Shen, Wei Liu, Zhi-Quan Luo

2205.14473

PhaseMax: Convex Phase Retrieval via Basis Pursuit

Tom Goldstein, Christoph Studer

1610.07531

The Hirsch conjecture holds for normal flag complexes

Karim Alexander Adiprasito, Bruno Benedetti

1303.3598

Exact Worst-case Performance of First-order Methods for Composite Convex Optimization

Adrien B. Taylor, Julien M. Hendrickx, François Glineur

1512.07516

Corrupted Sensing: Novel Guarantees for Separating Structured Signals

Rina Foygel, Lester Mackey

1305.2524

Federated Optimization:Distributed Optimization Beyond the Datacenter

Jakub Konečný, Brendan McMahan, Daniel Ramage

1511.03575

LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

Zeyuan Allen-Zhu, Yuanzhi Li

1607.03463

Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization

Xiangru Lian, Yijun Huang, Yuncheng Li, Ji Liu

1506.08272

A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise

Francis Bach, Kfir Y. Levy

1902.01637

A Variational Perspective on Accelerated Methods in Optimization

Andre Wibisono, Ashia C. Wilson, Michael I. Jordan

1603.04245

Two steps at a time -- taking GAN training in stride with Tseng's method

Axel Böhm, Michael Sedlmayer, Ernö Robert Csetnek, Radu Ioan Boţ

2006.09033

Learning with Differentiable Perturbed Optimizers

Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, Francis Bach

2002.08676

Stochastic Optimization for Large-scale Optimal Transport

Genevay Aude, Marco Cuturi, Gabriel Peyré, Francis Bach

1605.08527

Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications

Mingyi Hong

1604.00543

Fast as CHITA: Neural Network Pruning with Combinatorial Optimization

Riade Benbaki, Wenyu Chen, Xiang Meng, Hussein Hazimeh, Natalia Ponomareva, Zhe Zhao, Rahul Mazumder

2302.14623

Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality

Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto I. Oliveira

1703.08729

Sparse Optimization on Measures with Over-parameterized Gradient Descent

Lenaic Chizat

1907.10300

Error Feedback Fixes SignSGD and other Gradient Compression Schemes

Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, Martin Jaggi

1901.09847

Reducing Noise in GAN Training with Variance Reduced Extragradient

Tatjana Chavdarova, Gauthier Gidel, François Fleuret, Simon Lacoste-Julien

1904.08598

Escaping Saddles with Stochastic Gradients

Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, Thomas Hofmann

1803.05999

Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications

Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, Yongxin Chen

1902.08294

Adaptive Federated Optimization

Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, H. Brendan McMahan

2003.00295

On the Complexity Analysis of Randomized Block-Coordinate Descent Methods

Zhaosong Lu, Lin Xiao

1305.4723

Understanding training and generalization in deep learning by Fourier analysis

Zhiqin John Xu

1808.04295

A new regret analysis for Adam-type algorithms

Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, Volkan Cevher

2003.09729

On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

Tianyi Lin, Chi Jin, Michael I. Jordan

1906.00331

A Variational Inequality Perspective on Generative Adversarial Networks

Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, Simon Lacoste-Julien

1802.10551

Stochastic Proximal Gradient Consensus Over Random Networks

Mingyi Hong, Tsung-Hui Chang

1511.08905

Information-Theoretic Bounded Rationality

Pedro A. Ortega, Daniel A. Braun, Justin Dyer, Kee-Eung Kim, Naftali Tishby

1512.06789

A Simpler Approach to Matrix Completion

Benjamin Recht

0910.0651

Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information

Peng Xu, Fred Roosta, Michael W. Mahoney

1708.07164

Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization

Clément W. Royer, Stephen J. Wright

1706.03131

Fast Linearized Bregman Iteration for Compressive Sensing and Sparse Denoising

Stanley Osher, Yu Mao, Bin Dong, Wotao Yin

1104.0262

Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU

Zeyuan Allen-Zhu, Yuanzhi Li

1701.01722

Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs

Weiwei Kong, Jefferson G. Melo, Renato D. C. Monteiro

1802.03504

Faster Eigenvector Computation via Shift-and-Invert Preconditioning

Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford

1605.08754

Tight Analyses for Non-Smooth Stochastic Gradient Descent

Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, Sikander Randhawa

1812.05217

A Generic Acceleration Framework for Stochastic Composite Optimization

Andrei Kulunchakov, Julien Mairal

1906.01164

Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis

Jikai Jin, Bohang Zhang, Haiyang Wang, Liwei Wang

2110.12459

Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, Georgios Piliouras

1807.02629

Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems

Sucheol Lee, Donghwan Kim

2106.02326

Distributed optimization over time-varying directed graphs

Angelia Nedic, Alex Olshevsky

1303.2289

Stability of Schrödinger Potentials and Convergence of Sinkhorn's Algorithm

Marcel Nutz, Johannes Wiesel

2201.10059

Factoring nonnegative matrices with linear programs

Victor Bittorf, Benjamin Recht, Christopher Re, Joel A. Tropp

1206.1270

Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses

Dominik Csiba, Peter Richtárik

1506.02227

Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

Xiao Wang, Shiqian Ma, Donald Goldfarb, Wei Liu

1607.01231

VeLO: Training Versatile Learned Optimizers by Scaling Up

Luke Metz, James Harrison, C. Daniel Freeman, Amil Merchant, Lucas Beyer, James Bradbury, Naman Agrawal, Ben Poole, Igor Mordatch, Adam Roberts, Jascha Sohl-Dickstein

2211.09760

Lower Bounds for Finding Stationary Points II: First-Order Methods

Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford

1711.00841

On the Efficiency of Random Permutation for ADMM and Coordinate Descent

Ruoyu Sun, Zhi-Quan Luo, Yinyu Ye

1503.06387

Spurious Valleys in Two-layer Neural Network Optimization Landscapes

Luca Venturi, Afonso S. Bandeira, Joan Bruna

1802.06384

Scaling Algorithms for Unbalanced Transport Problems

Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, François-Xavier Vialard

1607.05816

Gradient Descent Finds Global Minima of Deep Neural Networks

Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, Xiyu Zhai

1811.03804

Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture

Ju Sun, Qing Qu, John Wright

1511.03607

New Analysis and Results for the Frank-Wolfe Method

Robert M. Freund, Paul Grigas

1307.0873

A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games

Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, Gauthier Gidel

1906.05945

You Only Propagate Once: Accelerating Adversarial Training via Maximal Principle

Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, Bin Dong

1905.00877

A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale

Hao-Jun Michael Shi, Tsung-Hsien Lee, Shintaro Iwasaki, Jose Gallego-Posada, Zhijing Li, Kaushik Rangadurai, Dheevatsa Mudigere, Michael Rabbat

2309.06497

Communication trade-offs for synchronized distributed SGD with large step size

Kumar Kshitij Patel, Aymeric Dieuleveut

1904.11325

Distributed Mini-Batch SDCA

Martin Takáč, Peter Richtárik, Nathan Srebro

1507.08322

Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

Gang Wang, Georgios B. Giannakis, Jie Chen

1610.09540

Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

Yossi Arjevani, Ohad Shamir, Ron Shiff

1705.07260

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs

Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, Patrick Pletscher

1207.4747

First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time

Yi Xu, Rong Jin, Tianbao Yang

1711.01944

Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection

Julie Nutini, Mark Schmidt, Issam H. Laradji, Michael Friedlander, Hoyt Koepke

1506.00552

Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization

Nicolas Gillis, Stephen A. Vavasis

1208.1237

An Inexact Successive Quadratic Approximation Method for Convex L-1 Regularized Optimization

Richard H. Byrd, Jorge Nocedal, Figen Oztoprak

1309.3529

Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods

Shuvomoy Das Gupta, Bart P. G. Van Parys, Ernest K. Ryu

2203.07305

Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number

Tian Tong, Cong Ma, Yuejie Chi

2010.13364

Efficient Algorithms for Smooth Minimax Optimization

Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh

1907.01543

Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems

Damek Davis, Benjamin Grimmer

1707.03505

Step Size Matters in Deep Learning

Kamil Nar, S. Shankar Sastry

1805.08890

Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity

Ohad Shamir

1507.08788

Sub-sampled Cubic Regularization for Non-convex Optimization

Jonas Moritz Kohler, Aurelien Lucchi

1705.05933

Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods

Nicolas Loizou, Peter Richtárik

1712.09677

GloptiPoly 3: moments, optimization and semidefinite programming

Didier Henrion, Jean Bernard Lasserre, Johan Lofberg

0709.2559

Large-Scale Methods for Distributionally Robust Optimization

Daniel Levy, Yair Carmon, John C. Duchi, Aaron Sidford

2010.05893

Accelerated Distributed Nesterov Gradient Descent

Guannan Qu, Na Li

1705.07176

iPiano: Inertial Proximal Algorithm for Non-Convex Optimization

Peter Ochs, Yunjin Chen, Thomas Brox, Thomas Pock

1404.4805

Old Optimizer, New Norm: An Anthology

Jeremy Bernstein, Laker Newhouse

2409.20325

First-order Methods Almost Always Avoid Saddle Points

Jason D. Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I. Jordan, Benjamin Recht

1710.07406

Stochastic AUC Maximization with Deep Neural Networks

Mingrui Liu, Zhuoning Yuan, Yiming Ying, Tianbao Yang

1908.10831

Decentralized learning for wireless communications and networking

Georgios B. Giannakis, Qing Ling, Gonzalo Mateos, Ioannis D. Schizas, Hao Zhu

1503.08855

Positive Definite $\ell_1$ Penalized Estimation of Large Covariance Matrices

Lingzhou Xue, Shiqian Ma, Hui Zou

1208.5702

Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization

Navid Azizan, Sahin Lale, Babak Hassibi

1906.03830

Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems

Mingyi Hong, Zhi-Quan Luo, Meisam Razaviyayn

1410.1390

Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Damek Davis, Wotao Yin

1407.5210

Unified Optimal Analysis of the (Stochastic) Gradient Method

Sebastian U. Stich

1907.04232

Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

Gang Wang, Georgios B. Giannakis, Yonina C. Eldar

1605.08285

Deep Neural Network Structures Solving Variational Inequalities

Patrick L. Combettes, Jean-Christophe Pesquet

1808.07526

Optimal Primal-Dual Methods for a Class of Saddle Point Problems

Yunmei Chen, Guanghui Lan, Yuyuan Ouyang

1309.5548

On the Equivalence between Herding and Conditional Gradient Algorithms

Francis Bach, Simon Lacoste-Julien, Guillaume Obozinski

1203.4523

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points

Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, Michael I. Jordan

1902.04811

On the Linear Convergence of the ADMM in Decentralized Consensus Optimization

Wei Shi, Qing Ling, Kun Yuan, Gang Wu, Wotao Yin

1307.5561

RES: Regularized Stochastic BFGS Algorithm

Aryan Mokhtari, Alejandro Ribeiro

1401.7625

A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics

Weinan E, Chao Ma, Lei Wu

1904.04326

Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection

Shiqian Ma, Lingzhou Xue, Hui Zou

1206.1275

Simultaneously Structured Models with Application to Sparse and Low-rank Matrices

Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C. Eldar, Babak Hassibi

1212.3753

Simple random search provides a competitive approach to reinforcement learning

Horia Mania, Aurelia Guy, Benjamin Recht

1803.07055

Estimating operator norms using covering nets

Fernando G. S. L. Brandao, Aram W. Harrow

1509.05065

Efficiency of minimizing compositions of convex functions and smooth maps

Dmitriy Drusvyatskiy, Courtney Paquette

1605.00125

Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably

Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, Sujay Sanghavi

1606.03168

Convex Relaxation of Optimal Power Flow, Part I: Formulations and Equivalence

Steven H. Low

1405.0766

Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks

Ziwei Ji, Matus Telgarsky

1909.12292

Hessian Riemannian gradient flows in convex programming

Felipe Alvarez, Jérôme Bolte, Olivier Brahic

1811.10331

Theory of the Frequency Principle for General Deep Neural Networks

Tao Luo, Zheng Ma, Zhi-Qin John Xu, Yaoyu Zhang

1906.09235

Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima

Simon S. Du, Jason D. Lee, Yuandong Tian, Barnabas Poczos, Aarti Singh

1712.00779

Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

Adrien Taylor, Francis Bach

1902.00947

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang

2302.11068

The Slingshot Mechanism: An Empirical Study of Adaptive Optimizers and the Grokking Phenomenon

Vimal Thilak, Etai Littwin, Shuangfei Zhai, Omid Saremi, Roni Paiss, Joshua Susskind

2206.04817

Error Bounds and Metric Subregularity

Alexander Y. Kruger

1405.1130

Random Permutations Fix a Worst Case for Cyclic Coordinate Descent

Ching-Pei Lee, Stephen J. Wright

1607.08320

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Nicolas Le Roux, Mark Schmidt, Francis Bach

1202.6258

Revisiting the Polyak step size

Elad Hazan, Sham Kakade

1905.00313

Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods

Guoyin Li, Ting Kei Pong

1602.02915

A quasi-Newton proximal splitting method

Stephen Becker, M. Jalal Fadili

1206.1156

Convergence rate analysis of the forward-Douglas-Rachford splitting scheme

Damek Davis

1410.2654

Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks

Peter L. Bartlett, David P. Helmbold, Philip M. Long

1802.06093

A Unified Approach to Error Bounds for Structured Convex Optimization Problems

Zirui Zhou, Anthony Man-Cho So

1512.03518

A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints

Guodong Zhang, Xuchan Bao, Laurent Lessard, Roger Grosse

2009.11359

The Uncertainty Bellman Equation and Exploration

Brendan O'Donoghue, Ian Osband, Remi Munos, Volodymyr Mnih

1709.05380

On the Randomized Kaczmarz Algorithm

Liang Dai, Mojtaba Soltanalian, Kristiaan Pelckmans

1402.2863

Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions

Axel Böhm

2201.12247

Deep backward schemes for high-dimensional nonlinear PDEs

Côme Huré, Huyên Pham, Xavier Warin

1902.01599

Stochastic Gradient Push for Distributed Deep Learning

Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, Michael Rabbat

1811.10792

Golden Ratio Algorithms for Variational Inequalities

Yura Malitsky

1803.08832

On the Convergence of Decentralized Gradient Descent

Kun Yuan, Qing Ling, Wotao Yin

1310.7063

Proximal Newton-type methods for minimizing composite functions

Jason D. Lee, Yuekai Sun, Michael A. Saunders

1206.1623

From error bounds to the complexity of first-order descent methods for convex functions

Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, Bruce Suter

1510.08234

Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems

Dmitrii M. Ostrovskii, Andrew Lowy, Meisam Razaviyayn

2002.07919

Neural networks-based backward scheme for fully nonlinear PDEs

Huyen Pham, Xavier Warin, Maximilien Germain

1908.00412

Machine Learning from a Continuous Viewpoint

Weinan E, Chao Ma, Lei Wu

1912.12777

On the Convergence of FedAvg on Non-IID Data

Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, Zhihua Zhang

1907.02189

Stochastic Recursive Variance-Reduced Cubic Regularization Methods

Dongruo Zhou, Quanquan Gu

1901.11518

MADMM: a generic algorithm for non-smooth optimization on manifolds

Artiom Kovnatsky, Klaus Glashoff, Michael M. Bronstein

1505.07676

A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block

Min Li, Defeng Sun, Kim-Chuan Toh

1410.7933

Few-Shot Learning via Learning the Representation, Provably

Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, Qi Lei

2002.09434

Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach

Ashutosh Nayyar, Aditya Mahajan, Demosthenis Teneketzis

1209.1695

A New Convex Relaxation for Tensor Completion

Bernardino Romera-Paredes, Massimiliano Pontil

1307.4653

Towards moderate overparameterization: global convergence guarantees for training shallow neural networks

Samet Oymak, Mahdi Soltanolkotabi

1902.04674

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations

Bin Shi, Simon S. Du, Michael I. Jordan, Weijie J. Su

1810.08907

Mean-Field Langevin Dynamics: Exponential Convergence and Annealing

Lénaïc Chizat

2202.01009

Monte Carlo Gradient Estimation in Machine Learning

Shakir Mohamed, Mihaela Rosca, Michael Figurnov, Andriy Mnih

1906.10652

SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient

Lam M. Nguyen, Jie Liu, Katya Scheinberg, Martin Takáč

1703.00102

Convergence of sequences: a survey

Barbara Franci, Sergio Grammatico

2111.11374

Entropic Optimal Transport: Geometry and Large Deviations

Espen Bernton, Promit Ghosal, Marcel Nutz

2102.04397

Stop Wasting My Gradients: Practical SVRG

Reza Babanezhad, Mohamed Osama Ahmed, Alim Virani, Mark Schmidt, Jakub Konečný, Scott Sallinen

1511.01942

Rate of Convergence and Error Bounds for LSTD($λ$)

Manel Tagorti, Bruno Scherrer

1405.3229

Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization

Daniel Golovin, Qiuyi Zhang

2006.04655

An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems

Manya V. Afonso, José M. Bioucas-Dias, Mário A. T. Figueiredo

0912.3481

Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction

Radu-Alexandru Dragomir, Mathieu Even, Hadrien Hendrikx

2104.09813

Optimal Hour-Ahead Bidding in the Real-Time Electricity Market with Battery Storage using Approximate Dynamic Programming

Daniel R. Jiang, Warren B. Powell

1402.3575

On Acceleration with Noise-Corrupted Gradients

Michael B. Cohen, Jelena Diakonikolas, Lorenzo Orecchia

1805.12591

DimmWitted: A Study of Main-Memory Statistical Analytics

Ce Zhang, Christopher Ré

1403.7550

XNAS: Neural Architecture Search with Expert Advice

Niv Nayman, Asaf Noy, Tal Ridnik, Itamar Friedman, Rong Jin, Lihi Zelnik-Manor

1906.08031

Sparse Inverse Covariance Selection via Alternating Linearization Methods

Katya Scheinberg, Shiqian Ma, Donald Goldfarb

1011.0097

Online Learning: Sufficient Statistics and the Burkholder Method

Dylan J. Foster, Alexander Rakhlin, Karthik Sridharan

1803.07617

An Asynchronous Distributed Proximal Gradient Method for Composite Convex Optimization

Necdet Serhat Aybat, Garud Iyengar, Zi Wang

1409.8547

Stability and Generalization of Learning Algorithms that Converge to Global Optima

Zachary Charles, Dimitris Papailiopoulos

1710.08402

Solving high-dimensional partial differential equations using deep learning

Jiequn Han, Arnulf Jentzen, Weinan E

1707.02568

Design of Strict Control-Lyapunov Functions for Quantum Systems with QND Measurements

Hadis Amini, Pierre Rouchon, Mazyar Mirrahimi

1103.1365

Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence

Dongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, Mihailo R. Jovanović

2202.04129

Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

Coralia Cartis, Nick I. M. Gould, Philippe L. Toint

1709.07180

A globally convergent algorithm for nonconvex optimization based on block coordinate update

Yangyang Xu, Wotao Yin

1410.1386

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian

Samet Oymak, Zalan Fabian, Mingchen Li, Mahdi Soltanolkotabi

1906.05392

Geometrical Convergence Rate for Distributed Optimization with Time-Varying Directed Graphs and Uncoordinated Step-Sizes

Qingguo Lü, Huaqing Li

1611.00990

Gradient Descent Provably Optimizes Over-parameterized Neural Networks

Simon S. Du, Xiyu Zhai, Barnabas Poczos, Aarti Singh

1810.02054

On Tensor Completion via Nuclear Norm Minimization

Ming Yuan, Cun-Hui Zhang

1405.1773

A generative adversarial network approach to calibration of local stochastic volatility models

Christa Cuchiero, Wahid Khosrawi, Josef Teichmann

2005.02505

How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics

Anirudha Majumdar, Marco Pavone

1710.11040

On the Convergence and Robustness of Training GANs with Regularized Optimal Transport

Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, Jason D. Lee

1802.08249

Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems

Ruoyu Sun, Mingyi Hong

1512.04680

Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions

Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, Asuman Ozdaglar

1805.10579

Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback

Shuai Zheng, Ziyue Huang, James T. Kwok

1905.10936

Global convergence of the Heavy-ball method for convex optimization

Euhanna Ghadimi, Hamid Reza Feyzmahdavian, Mikael Johansson

1412.7457

Adaptive extra-gradient methods for min-max optimization and games

Kimon Antonakopoulos, E. Veronica Belmega, Panayotis Mertikopoulos

2010.12100

On exponential convergence of SGD in non-convex over-parametrized learning

Raef Bassily, Mikhail Belkin, Siyuan Ma

1811.02564

Convergence rate analysis of primal-dual splitting schemes

Damek Davis

1408.4419

Stable Neural Flows

Stefano Massaroli, Michael Poli, Michelangelo Bin, Jinkyoo Park, Atsushi Yamashita, Hajime Asama

2003.08063

Stochastic Frank-Wolfe Methods for Nonconvex Optimization

Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alex Smola

1607.08254

Decentralized Deep Learning with Arbitrary Communication Compression

Anastasia Koloskova, Tao Lin, Sebastian U. Stich, Martin Jaggi

1907.09356

Dual-Free Stochastic Decentralized Optimization with Variance Reduction

Hadrien Hendrikx, Francis Bach, Laurent Massoulié

2006.14384

On the Local Minima of the Empirical Risk

Chi Jin, Lydia T. Liu, Rong Ge, Michael I. Jordan

1803.09357

Stochastic subgradient method converges on tame functions

Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, Jason D. Lee

1804.07795

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates

Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, Simon Lacoste-Julien

1905.09997

PhasePack: A Phase Retrieval Library

Rohan Chandra, Ziyuan Zhong, Justin Hontz, Val McCulloch, Christoph Studer, Tom Goldstein

1711.10175

The Non-convex Geometry of Low-rank Matrix Optimization

Qiuwei Li, Zhihui Zhu, Gongguo Tang

1611.03060

Learning time-scales in two-layers neural networks

Raphaël Berthier, Andrea Montanari, Kangjie Zhou

2303.00055

Black-Box Reductions for Parameter-free Online Learning in Banach Spaces

Ashok Cutkosky, Francesco Orabona

1802.06293

Coordinate Friendly Structures, Algorithms and Applications

Zhimin Peng, Tianyu Wu, Yangyang Xu, Ming Yan, Wotao Yin

1601.00863

Fast Multi-class Dictionaries Learning with Geometrical Directions in MRI Reconstruction

Zhifang Zhan, Jian-Feng Cai, Di Guo, Yunsong Liu, Zhong Chen, Xiaobo Qu

1503.02945

Fast Stochastic Methods for Nonsmooth Nonconvex Optimization

Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alex Smola

1605.06900

Geometric descent method for convex composite minimization

Shixiang Chen, Shiqian Ma, Wei Liu

1612.09034

On the Global Linear Convergence of Frank-Wolfe Optimization Variants

Simon Lacoste-Julien, Martin Jaggi

1511.05932

ASAGA: Asynchronous Parallel SAGA

Rémi Leblond, Fabian Pedregosa, Simon Lacoste-Julien

1606.04809

Stabilization of a delayed quantum system: the photon box case-study

Hadis Amini, Mazyar Mirrahimi, Pierre Rouchon

1007.3584

Decentralized Optimal Dispatch of Photovoltaic Inverters in Residential Distribution Systems

Emiliano Dall'Anese, Sairaj V. Dhople, Brian B. Johnson, Georgios B. Giannakis

1403.1341

Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry

Ziyi Chen, Yi Zhou, Tengyu Xu, Yingbin Liang

2102.04653

The Road Less Scheduled

Aaron Defazio, Xingyu Alice Yang, Harsh Mehta, Konstantin Mishchenko, Ahmed Khaled, Ashok Cutkosky

2405.15682

On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems

Sindri Magnússon, Pradeep Chathuranga Weeraddana, Michael G. Rabbat, Carlo Fischione

1409.8033

How is Distributed ADMM Affected by Network Topology?

Guilherme França, José Bento

1710.00889

Max-value Entropy Search for Efficient Bayesian Optimization

Zi Wang, Stefanie Jegelka

1703.01968

Bandit learning in concave $N$-person games

Mario Bravo, David S. Leslie, Panayotis Mertikopoulos

1810.01925

Provably Efficient Reinforcement Learning with Linear Function Approximation

Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan

1907.05388

Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation

Ying Sun, Amir Daneshmand, Gesualdo Scutari

1905.02637

Barrier Frank-Wolfe for Marginal Inference

Rahul G. Krishnan, Simon Lacoste-Julien, David Sontag

1511.02124

A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group

Huikang Liu, Man-Chung Yue, Anthony Man-Cho So

2009.07514

The limits of min-max optimization algorithms: convergence to spurious non-critical sets

Ya-Ping Hsieh, Panayotis Mertikopoulos, Volkan Cevher

2006.09065

Near-Optimal Joint Object Matching via Convex Relaxation

Yuxin Chen, Leonidas J. Guibas, Qi-Xing Huang

1402.1473

Multi-channel Opportunistic Access: A Case of Restless Bandits with Multiple Plays

Sahand Haji Ali Ahmad, Mingyan Liu

0910.1954

Convergence Analysis of Inexact Randomized Iterative Methods

Nicolas Loizou, Peter Richtárik

1903.07971

A Multi-Batch L-BFGS Method for Machine Learning

Albert S. Berahas, Jorge Nocedal, Martin Takáč

1605.06049

NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization

Davood Hajinezhad, Mingyi Hong, Tuo Zhao, Zhaoran Wang

1605.07747

Nonsmooth Implicit Differentiation for Machine Learning and Optimization

Jérôme Bolte, Tam Le, Edouard Pauwels, Antonio Silveti-Falls

2106.04350

Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval

Yan Shuo Tan, Roman Vershynin

1910.12837

Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank

Hung-Hsu Chou, Carsten Gieshoff, Johannes Maly, Holger Rauhut

2011.13772

Foundations of gauge and perspective duality

Alexandre Y. Aravkin, James V. Burke, Dmitriy Drusvyatskiy, Michael P. Friedlander, Kellie MacPhee

1702.08649

Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems

Nikos Komodakis, Jean-Christophe Pesquet

1406.5429

Finite-Sum Smooth Optimization with SARAH

Lam M. Nguyen, Marten van Dijk, Dzung T. Phan, Phuong Ha Nguyen, Tsui-Wei Weng, Jayant R. Kalagnanam

1901.07648

A Robust Accelerated Optimization Algorithm for Strongly Convex Functions

Saman Cyrus, Bin Hu, Bryan Van Scoy, Laurent Lessard

1710.04753

Constrained Reinforcement Learning Has Zero Duality Gap

Santiago Paternain, Luiz F. O. Chamon, Miguel Calvo-Fullana, Alejandro Ribeiro

1910.13393

The exact information-based complexity of smooth convex minimization

Yoel Drori

1606.01424

A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method

Simon Lacoste-Julien, Mark Schmidt, Francis Bach

1212.2002

Reducing the variance in online optimization by transporting past gradients

Sébastien M. R. Arnold, Pierre-Antoine Manzagol, Reza Babanezhad, Ioannis Mitliagkas, Nicolas Le Roux

1906.03532

STFT Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms

Kishore Jaganathan, Yonina C. Eldar, Babak Hassibi

1508.02820

Learning with Submodular Functions: A Convex Optimization Perspective

Francis Bach

1111.6453

Distributed Subgradient Methods and Quantization Effects

Angelia Nedić, Alex Olshevsky, Asuman Ozdaglar, John N. Tsitsiklis

0803.1202

Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets

Dan Garber, Elad Hazan

1406.1305

Make Sharpness-Aware Minimization Stronger: A Sparsified Perturbation Approach

Peng Mi, Li Shen, Tianhe Ren, Yiyi Zhou, Xiaoshuai Sun, Rongrong Ji, Dacheng Tao

2210.05177

A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems

Zi Xu, Huiling Zhang, Yang Xu, Guanghui Lan

2006.02032

Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization

Xuefeng Gao, Mert Gurbuzbalaban, Lingjiong Zhu

1812.07725

Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method

Tsung-Hui Chang, Angelia Nedić, Anna Scaglione

1304.5590

Stochastic Controlled Averaging for Federated Learning with Communication Compression

Xinmeng Huang, Ping Li, Xiaoyun Li

2308.08165

No-regret learning and mixed Nash equilibria: They do not mix

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Thanasis Lianeas, Panayotis Mertikopoulos, Georgios Piliouras

2010.09514

Solving Variational Inequalities with Monotone Operators on Domains Given by Linear Minimization Oracles

Anatoli Juditsky, Arkadi Nemirovski

1312.1073

Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols

Nicolas Loizou, Peter Richtárik

1905.08645

On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers

Ermin Wei, Asuman Ozdaglar

1307.8254

Global Optimality in Low-rank Matrix Optimization

Zhihui Zhu, Qiuwei Li, Gongguo Tang, Michael B. Wakin

1702.07945

On Reward-Free Reinforcement Learning with Linear Function Approximation

Ruosong Wang, Simon S. Du, Lin F. Yang, Ruslan Salakhutdinov

2006.11274

Incremental Stochastic Subgradient Algorithms for Convex Optimization

S Sundhar Ram, A Nedich, V. V. Veeravalli

0806.1092

Accelerated methods for composite non-bilinear saddle point problem

Mohammad Alkousa, Darina Dvinskikh, Fedor Stonyakin, Alexander Gasnikov, Dmitry Kovalev

1906.03620

On the Outsized Importance of Learning Rates in Local Update Methods

Zachary Charles, Jakub Konečný

2007.00878

Multi-Agent Distributed Optimization via Inexact Consensus ADMM

Tsung-Hui Chang, Mingyi Hong, Xiangfeng Wang

1402.6065

A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions

Xudong Li, Defeng Sun, Kim-Chuan Toh

1409.2679

Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems

Radu Ioan Boţ, Axel Böhm

2007.13605

Sparse Phase Retrieval via Truncated Amplitude Flow

Gang Wang, Liang Zhang, Georgios B. Giannakis, Mehmet Akcakaya, Jie Chen

1611.07641

A Survey of Optimization Methods from a Machine Learning Perspective

Shiliang Sun, Zehui Cao, Han Zhu, Jing Zhao

1906.06821

The Practicality of Stochastic Optimization in Imaging Inverse Problems

Junqi Tang, Karen Egiazarian, Mohammad Golbabaee, Mike Davies

1910.10100

Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity

Puya Latafat, Andreas Themelis, Masoud Ahookhosh, Panagiotis Patrinos

2102.10312

Fast inertial dynamics and FISTA algorithms in convex optimization. Perturbation aspects

H. Attouch, Z. Chbani

1507.01367

Improvements to deep convolutional neural networks for LVCSR

Tara N. Sainath, Brian Kingsbury, Abdel-rahman Mohamed, George E. Dahl, George Saon, Hagen Soltau, Tomas Beran, Aleksandr Y. Aravkin, Bhuvana Ramabhadran

1309.1501

Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales

Jose Blanchet, Coralia Cartis, Matt Menickelly, Katya Scheinberg

1609.07428

Linear Convergence of the Douglas-Rachford Method for Two Closed Sets

Hung M. Phan

1401.6509

Relatively-Smooth Convex Optimization by First-Order Methods, and Applications

Haihao Lu, Robert M. Freund, Yurii Nesterov

1610.05708

Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism

Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, Stuart Russell

2103.12021

An Optimal Multistage Stochastic Gradient Method for Minimax Problems

Alireza Fallah, Asuman Ozdaglar, Sarath Pattathil

2002.05683

Second-Order Methods with Cubic Regularization Under Inexact Information

Saeed Ghadimi, Han Liu, Tong Zhang

1710.05782

The Squared-Error of Generalized LASSO: A Precise Analysis

Samet Oymak, Christos Thrampoulidis, Babak Hassibi

1311.0830

Complexity Guarantees for Polyak Steps with Momentum

Mathieu Barré, Adrien Taylor, Alexandre d'Aspremont

2002.00915

Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information

Samet Oymak, Christos Thrampoulidis, Babak Hassibi

1312.0641

Analysis of nonsmooth stochastic approximation: the differential inclusion approach

Szymon Majewski, Błażej Miasojedow, Eric Moulines

1805.01916

On the Nuclear Norm and the Singular Value Decomposition of Tensors

Harm Derksen

1308.3860

On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization

Cristobal Guzman, Arkadi Nemirovski

1307.5001

Online Algorithms for the Multi-Armed Bandit Problem with Markovian Rewards

Cem Tekin, Mingyan Liu

1007.2238

Training Generative Adversarial Networks via stochastic Nash games

Barbara Franci, Sergio Grammatico

2010.10013

Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs

Angelia Nedic, Alex Olshevsky

1406.2075

A counterexample to the Hirsch conjecture

Francisco Santos

1006.2814

Optimization Techniques on Riemannian Manifolds

Steven Thomas Smith

1407.5965

Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances

Bugra Can, Mert Gurbuzbalaban, Lingjiong Zhu

1901.07445

Large Scale Kernel Learning using Block Coordinate Descent

Stephen Tu, Rebecca Roelofs, Shivaram Venkataraman, Benjamin Recht

1602.05310

Provable Submodular Minimization using Wolfe's Algorithm

Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari

1411.0095

Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data

Yuxin Chen, Jianqing Fan, Cong Ma, Yuling Yan

2001.05484

Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise

Andrei Kulunchakov, Julien Mairal

1901.08788

Can We Remove the Square-Root in Adaptive Gradient Methods? A Second-Order Perspective

Wu Lin, Felix Dangel, Runa Eschenhagen, Juhan Bae, Richard E. Turner, Alireza Makhzani

2402.03496

Low-rank semidefinite programming for the MAX2SAT problem

Po-Wei Wang, J. Zico Kolter

1812.06362

Stability of Entropic Optimal Transport and Schrödinger Bridges

Promit Ghosal, Marcel Nutz, Espen Bernton

2106.03670

AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods

Alexandre Défossez, Francis Bach

1711.01761

Optimal Control Via Neural Networks: A Convex Approach

Yize Chen, Yuanyuan Shi, Baosen Zhang

1805.11835

Meta-Learning with Implicit Gradients

Aravind Rajeswaran, Chelsea Finn, Sham Kakade, Sergey Levine

1909.04630

Signature Methods in Stochastic Portfolio Theory

Christa Cuchiero, Janka Möller

2310.02322

Quantitative convergence analysis of iterated expansive, set-valued mappings

D. Russell Luke, Nguyen H. Thao, Matthew K. Tam

1605.05725

4+3 Phases of Compute-Optimal Neural Scaling Laws

Elliot Paquette, Courtney Paquette, Lechao Xiao, Jeffrey Pennington

2405.15074

A Universal Primal-Dual Convex Optimization Framework

Alp Yurtsever, Quoc Tran-Dinh, Volkan Cevher

1502.03123

Enforcing robust control guarantees within neural network policies

Priya L. Donti, Melrose Roderick, Mahyar Fazlyab, J. Zico Kolter

2011.08105

Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration

Xuefeng Gao, Mert Gürbüzbalaban, Lingjiong Zhu

1809.04618

Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras

1910.13010

Poisson Inverse Problems by the Plug-and-Play scheme

Arie Rond, Raja Giryes, Michael Elad

1511.02500

A Sparse Multi-Scale Algorithm for Dense Optimal Transport

Bernhard Schmitzer

1510.05466

A Faster Small Treewidth SDP Solver

Yuzhou Gu, Zhao Song

2211.06033

Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, Kunal Talwar

2006.06914

Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop

Dmitry Kovalev, Samuel Horvath, Peter Richtarik

1901.08689

Stochastic Dual Coordinate Ascent with Adaptive Probabilities

Dominik Csiba, Zheng Qu, Peter Richtárik

1502.08053

Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems

Bernhard Schmitzer

1610.06519

Exact Support Recovery for Sparse Spikes Deconvolution

Vincent Duval, Gabriel Peyré

1306.6909

What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?

Chi Jin, Praneeth Netrapalli, Michael I. Jordan

1902.00618

New Convergence Aspects of Stochastic Gradient Algorithms

Lam M. Nguyen, Phuong Ha Nguyen, Peter Richtárik, Katya Scheinberg, Martin Takáč, Marten van Dijk

1811.12403

Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Functions

Michael O'Neill, Stephen J. Wright

1706.07993

Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysis

Shuyang Ling

2006.00902

Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization

Junyu Zhang, Lin Xiao, Shuzhong Zhang

1811.11637

Stochastic Gradient Descent in Continuous Time

Justin Sirignano, Konstantinos Spiliopoulos

1611.05545

Learning Single-Index Models with Shallow Neural Networks

Alberto Bietti, Joan Bruna, Clayton Sanford, Min Jae Song

2210.15651

ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization

Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, David Cox

1910.06513

Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds

Hongyi Zhang, Sashank J. Reddi, Suvrit Sra

1605.07147

Decentralized and Parallel Primal and Dual Accelerated Methods for Stochastic Convex Programming Problems

Darina Dvinskikh, Alexander Gasnikov

1904.09015

BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization

Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, Andrew Gordon Wilson, Eytan Bakshy

1910.06403

Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

Bo Jiang, Tianyi Lin, Shiqian Ma, Shuzhong Zhang

1605.02408

SGD: General Analysis and Improved Rates

Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtarik

1901.09401

The Computational Complexity of Duality

Shmuel Friedland, Lek-Heng Lim

1601.07629

Deep Learning Approximation for Stochastic Control Problems

Jiequn Han, Weinan E

1611.07422

Convex Relaxation of Optimal Power Flow, Part II: Exactness

Steven H. Low

1405.0814

SCAFFOLD: Stochastic Controlled Averaging for Federated Learning

Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, Ananda Theertha Suresh

1910.06378

A Distributed Approach for the Optimal Power Flow Problem Based on ADMM and Sequential Convex Approximations

S. Magnússon, P. C. Weeraddana, C. Fischione

1401.4621

Monotone Operator Theory in Convex Optimization

Patrick L. Combettes

1802.02694

Input Convex Neural Networks

Brandon Amos, Lei Xu, J. Zico Kolter

1609.07152

Differentiable Convex Optimization Layers

Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, Zico Kolter

1910.12430

Near-Optimal Stochastic Approximation for Online Principal Component Estimation

Chris Junchi Li, Mengdi Wang, Han Liu, Tong Zhang

1603.05305

Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses

Shuvomoy Das Gupta, Robert M. Freund, Xu Andy Sun, Adrien Taylor

2301.01530

Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization

Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, Tuo Zhao

1612.09296

Universal regularization methods - varying the power, the smoothness and the accuracy

Coralia Cartis, Nicholas I. M. Gould, Philippe L. Toint

1811.07057

On the Convergence Rates of Policy Gradient Methods

Lin Xiao

2201.07443

Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning

Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, Soroosh Shafieezadeh-Abadeh

1908.08729

On the oracle complexity of smooth strongly convex minimization

Yoel Drori, Adrien Taylor

2101.09740

GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training

Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-Yan Liu, Liwei Wang

2009.03294

Byzantine-Tolerant Machine Learning

Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, Julien Stainer

1703.02757

Hypermodels for Exploration

Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, Benjamin Van Roy

2006.07464

Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions

Xuxing Chen, Tesi Xiao, Krishnakumar Balasubramanian

2306.12067

Sub-sampled Newton Methods with Non-uniform Sampling

Peng Xu, Jiyan Yang, Farbod Roosta-Khorasani, Christopher Ré, Michael W. Mahoney

1607.00559

A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients

Weimin Miao, Shaohua Pan, Defeng Sun

1210.3709

On Learning Rates and Schrödinger Operators

Bin Shi, Weijie J. Su, Michael I. Jordan

2004.06977

Local Exact-Diffusion for Decentralized Optimization and Learning

Sulaiman A. Alghunaim

2302.00620

Stochastic Optimization Using a Trust-Region Method and Random Models

Ruobing Chen, Matt Menickelly, Katya Scheinberg

1504.04231

Convergence of gradient descent for deep neural networks

Sourav Chatterjee

2203.16462

Exact Reconstruction using Beurling Minimal Extrapolation

Yohann de Castro, Fabrice Gamboa

1103.4951

A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction

Mathukumalli Vidyasagar

1104.4521

A framework to characterize performance of LASSO algorithms

Mihailo Stojnic

1303.7291

Is Local SGD Better than Minibatch SGD?

Blake Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, Nathan Srebro

2002.07839

High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm

Wenlong Mou, Yi-An Ma, Martin J. Wainwright, Peter L. Bartlett, Michael I. Jordan

1908.10859

Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization

Shicong Cen, Yuting Wei, Yuejie Chi

2105.15186

Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for $\ell_1$-Norm Principal Component Analysis

Peng Wang, Huikang Liu, Anthony Man-Cho So

2107.07107

A Dynamical Central Limit Theorem for Shallow Neural Networks

Zhengdao Chen, Grant M. Rotskoff, Joan Bruna, Eric Vanden-Eijnden

2008.09623

On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging

Angelia Nedich, Soomin Lee

1307.1879

Theoretical guarantees for sampling and inference in generative models with latent diffusions

Belinda Tzen, Maxim Raginsky

1903.01608

Bayesian Optimization of Composite Functions

Raul Astudillo, Peter I. Frazier

1906.01537

AUC Maximization in the Era of Big Data and AI: A Survey

Tianbao Yang, Yiming Ying

2203.15046

Differentiating Through a Cone Program

Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, Walaa M. Moursi

1904.09043

From Local SGD to Local Fixed-Point Methods for Federated Learning

Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, Peter Richtárik

2004.01442

Convex relaxations of structured matrix factorizations

Francis Bach

1309.3117

Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking

Ran Xin, Usman A. Khan

1808.02942

Provably Efficient Exploration in Policy Optimization

Qi Cai, Zhuoran Yang, Chi Jin, Zhaoran Wang

1912.05830

Dual subgradient algorithms for large-scale nonsmooth learning problems

Bruce Cox, Anatoli Juditsky, Arkadi Nemirovski

1302.2349

Global registration of multiple point clouds using semidefinite programming

Kunal N. Chaudhury, Yuehaw Khoo, Amit Singer

1306.5226

Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

Saeed Ghadimi, Guanghui Lan

1309.5549

Private Adaptive Gradient Methods for Convex Optimization

Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, Kunal Talwar

2106.13756

Optimal mini-batch and step sizes for SAGA

Nidham Gazagnadou, Robert M. Gower, Joseph Salmon

1902.00071

On Distributionally Robust Chance Constrained Programs with Wasserstein Distance

Weijun Xie

1806.07418

Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization

Tianxiang Gao, Songtao Lu, Jia Liu, Chris Chu

2001.05202

Forward-backward-forward methods with variance reduction for stochastic variational inequalities

Radu Ioan Bot, Panayotis Mertikopoulos, Mathias Staudigl, Phan Tu Vuong

1902.03355

Online Adaptive Methods, Universality and Acceleration

Kfir Y. Levy, Alp Yurtsever, Volkan Cevher

1809.02864

Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling

Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, Leandros Tassiulas

2112.11256

Nonlinear Kalman Filtering with Divergence Minimization

San Gultekin, John Paisley

1705.00722

A mathematical model for automatic differentiation in machine learning

Jerome Bolte, Edouard Pauwels

2006.02080

CYCLADES: Conflict-free Asynchronous Machine Learning

Xinghao Pan, Maximilian Lam, Stephen Tu, Dimitris Papailiopoulos, Ce Zhang, Michael I. Jordan, Kannan Ramchandran, Chris Re, Benjamin Recht

1605.09721

An update on the Hirsch conjecture

Edward D. Kim, Francisco Santos

0907.1186

Massively scalable Sinkhorn distances via the Nyström method

Jason Altschuler, Francis Bach, Alessandro Rudi, Jonathan Niles-Weed

1812.05189

Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression

Xinmeng Huang, Yiming Chen, Wotao Yin, Kun Yuan

2206.03665

Distributed Nesterov gradient methods over arbitrary graphs

Ran Xin, Dusan Jakovetic, Usman A. Khan

1901.06995

Information-based complexity, feedback and dynamics in convex programming

Maxim Raginsky, Alexander Rakhlin

1010.2285

PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python

Baptiste Goujaud, Céline Moucer, François Glineur, Julien Hendrickx, Adrien Taylor, Aymeric Dieuleveut

2201.04040

Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning

Zachary Charles, Jakub Konečný

2103.05032

Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching

Robert M. Gower, Peter Richtárik, Francis Bach

1805.02632

Momentum Benefits Non-IID Federated Learning Simply and Provably

Ziheng Cheng, Xinmeng Huang, Pengfei Wu, Kun Yuan

2306.16504

Parameter-free accelerated gradient descent for nonconvex minimization

Naoki Marumo, Akiko Takeda

2212.06410

Set Regularities and Feasibility Problems

Alexander Y. Kruger, D. Russell Luke, Nguyen H. Thao

1602.04935

Projecting onto the intersection of a cone and a sphere

Heinz H. Bauschke, Minh N. Bui, Xianfu Wang

1708.00585

Tradeoffs between Convergence Speed and Reconstruction Accuracy in Inverse Problems

Raja Giryes, Yonina C. Eldar, Alex M. Bronstein, Guillermo Sapiro

1605.09232

Distributed reactive power feedback control for voltage regulation and loss minimization

Saverio Bolognani, Guido Cavraro, Ruggero Carli, Sandro Zampieri

1303.7173

Personalized Federated Learning: A Meta-Learning Approach

Alireza Fallah, Aryan Mokhtari, Asuman Ozdaglar

2002.07948

Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms

Aram Harrow, John Napp

1901.05374

In Perfect Shape: Certifiably Optimal 3D Shape Reconstruction from 2D Landmarks

Heng Yang, Luca Carlone

1911.11924

Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity

Jonathan M. Borwein, Guoyin Li, Matthew K. Tam

1510.06823

Dynamic Energy Management

Nicholas Moehle, Enzo Busseti, Stephen Boyd, Matt Wytock

1903.06230

On the Convergence Proof of AMSGrad and a New Version

Tran Thi Phuong, Le Trieu Phong

1904.03590

Bilinear Classes: A Structural Framework for Provable Generalization in RL

Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, Ruosong Wang

2103.10897

Gradient Methods for Submodular Maximization

Hamed Hassani, Mahdi Soltanolkotabi, Amin Karbasi

1708.03949

Fast ADMM Algorithm for Distributed Optimization with Adaptive Penalty

Changkyu Song, Sejong Yoon, Vladimir Pavlovic

1506.08928

Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets

Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, Jack Xin

1903.05662

Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization

Eduard Gorbunov, Darina Dvinskikh, Alexander Gasnikov

1911.07363

Benign Overfitting in Two-layer Convolutional Neural Networks

Yuan Cao, Zixiang Chen, Mikhail Belkin, Quanquan Gu

2202.06526

Linear and strong convergence of algorithms involving averaged nonexpansive operators

Heinz H. Bauschke, Dominikus Noll, Hung M. Phan

1402.5460

Submodular Combinatorial Information Measures with Applications in Machine Learning

Rishabh Iyer, Ninad Khargonkar, Jeff Bilmes, Himanshu Asnani

2006.15412

Quadratically-Regularized Optimal Transport on Graphs

Montacer Essid, Justin Solomon

1704.08200

Risk and parameter convergence of logistic regression

Ziwei Ji, Matus Telgarsky

1803.07300

Multi-consensus Decentralized Accelerated Gradient Descent

Haishan Ye, Luo Luo, Ziang Zhou, Tong Zhang

2005.00797

Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension

Ruosong Wang, Ruslan Salakhutdinov, Lin F. Yang

2005.10804

Optimized first-order methods for smooth convex minimization

Donghwan Kim, Jeffrey A. Fessler

1406.5468

First-order Methods for Geodesically Convex Optimization

Hongyi Zhang, Suvrit Sra

1602.06053

FedSplit: An algorithmic framework for fast federated optimization

Reese Pathak, Martin J. Wainwright

2005.05238

The mean field Schrödinger problem: ergodic behavior, entropy estimates and functional inequalities

Julio Backhoff-Veraguas, Giovani Conforti, Ivan Gentil, Christian Léonard

1905.02393

Robust Hypothesis Testing Using Wasserstein Uncertainty Sets

Rui Gao, Liyan Xie, Yao Xie, Huan Xu

1805.10611

Simple Error Bounds for Regularized Noisy Linear Inverse Problems

Christos Thrampoulidis, Samet Oymak, Babak Hassibi

1401.6578

Asynchronous Distributed Optimization using a Randomized Alternating Direction Method of Multipliers

Franck Iutzeler, Pascal Bianchi, Philippe Ciblat, Walid Hachem

1303.2837

Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networks

Jinming Xu, Ye Tian, Ying Sun, Gesualdo Scutari

1910.10666

An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms

Simon Lacoste-Julien, Martin Jaggi

1312.7864

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, Sebastian U. Stich

2003.10422

Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization

Guodong Zhang, Yuanhao Wang, Laurent Lessard, Roger Grosse

2102.09468

On Feature Learning in Neural Networks with Global Convergence Guarantees

Zhengdao Chen, Eric Vanden-Eijnden, Joan Bruna

2204.10782

BM3D Frames and Variational Image Deblurring

Aram Danielyan, Vladimir Katkovnik, Karen Egiazarian

1106.6180

Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points

Krishnakumar Balasubramanian, Saeed Ghadimi

1809.06474

Single Trajectory Nonparametric Learning of Nonlinear Dynamics

Ingvar Ziemann, Henrik Sandberg, Nikolai Matni

2202.08311

Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

Zhize Li, Dmitry Kovalev, Xun Qian, Peter Richtárik

2002.11364

The connections between Lyapunov functions for some optimization algorithms and differential equations

J. M. Sanz-Serna, Konstantinos C. Zygalakis

2009.00673

Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization

Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, Martin J. Wainwright

1009.0571

SDPNAL$+$: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints

Liuqin Yang, Defeng Sun, Kim-Chuan Toh

1406.0942

Neural Algorithmic Reasoning

Petar Veličković, Charles Blundell

2105.02761

Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras

2101.05248

Accelerated Gossip via Stochastic Heavy Ball Method

Nicolas Loizou, Peter Richtárik

1809.08657

Accelerated Sampling Kaczmarz Motzkin Algorithm for The Linear Feasibility Problem

Md Sarowar Morshed, Md Saiful Islam, Md. Noor-E-Alam

1902.03502

Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization

Gang Wang, Georgios B. Giannakis, Jie Chen

1808.04685

A Faster Interior Point Method for Semidefinite Programming

Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, Zhao Song

2009.10217

Perspective Functions: Proximal Calculus and Applications in High-Dimensional Statistics

Patrick L. Combettes, Christian L. Müller

1610.01478

Uniform Convergence of Gradients for Non-Convex Learning and Optimization

Dylan J. Foster, Ayush Sekhari, Karthik Sridharan

1810.11059

Private Convex Optimization via Exponential Mechanism

Sivakanth Gopi, Yin Tat Lee, Daogao Liu

2203.00263

Variance-reduced $Q$-learning is minimax optimal

Martin J. Wainwright

1906.04697

Why Random Reshuffling Beats Stochastic Gradient Descent

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo Parrilo

1510.08560

Linearly convergent stochastic heavy ball method for minimizing generalization error

Nicolas Loizou, Peter Richtárik

1710.10737

Stochastic Variance-Reduced Cubic Regularized Newton Method

Dongruo Zhou, Pan Xu, Quanquan Gu

1802.04796

Gradient descent aligns the layers of deep linear networks

Ziwei Ji, Matus Telgarsky

1810.02032

Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations

Debraj Basu, Deepesh Data, Can Karakus, Suhas Diggavi

1906.02367

ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning

Zhixiong Yang, Waheed U. Bajwa

1708.08155

Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks

Yuan Cao, Quanquan Gu

1902.01384

Deconvolving Images with Unknown Boundaries Using the Alternating Direction Method of Multipliers

Mariana S. C. Almeida, Mário A. T. Figueiredo

1210.2687

A Provably Convergent Scheme for Compressive Sensing under Random Generative Priors

Wen Huang, Paul Hand, Reinhard Heckel, Vladislav Voroninski

1812.04176

Visualizing Data using GTSNE

Songting Shi

2108.01301

Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility

Robert Hesse, D. Russell Luke, Patrick Neumann

1307.2009

Improved Convergence Rates for Distributed Resource Allocation

Angelia Nedić, Alex Olshevsky, Wei Shi

1706.05441

Is Pessimism Provably Efficient for Offline RL?

Ying Jin, Zhuoran Yang, Zhaoran Wang

2012.15085

Making an Invisibility Cloak: Real World Adversarial Attacks on Object Detectors

Zuxuan Wu, Ser-Nam Lim, Larry Davis, Tom Goldstein

1910.14667

A Convergence Theory for Deep Learning via Over-Parameterization

Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song

1811.03962

Tight last-iterate convergence rates for no-regret learning in multi-player games

Noah Golowich, Sarath Pattathil, Constantinos Daskalakis

2010.13724

Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing

Arun Jambulapati, Jerry Li, Kevin Tian

2006.06980

Adaptive Federated Learning in Resource Constrained Edge Computing Systems

Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, Kevin Chan

1804.05271

Convergence properties of the expected improvement algorithm

Emmanuel Vazquez, Julien Bect

0712.3744

Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization

A. Patrascu, I. Necoara

1305.4027

Iteration Complexity Analysis of Block Coordinate Descent Methods

Mingyi Hong, Xiangfeng Wang, Meisam Razaviyayn, Zhi-Quan Luo

1310.6957

A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

Ion Necoara, Andrei Patrascu

1302.3074

Efficient parallel coordinate descent algorithm for convex optimization problems with separable constraints: application to distributed MPC

Ion Necoara, Dragos Clipici

1302.3092

Online Robust Subspace Tracking from Partial Information

Jun He, Laura Balzano, John C. S. Lui

1109.3827

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

Alexander Rakhlin, Ohad Shamir, Karthik Sridharan

1109.5647

Geometric Optimization Methods for Adaptive Filtering

Steven Thomas Smith

1305.1886

Parallel and distributed optimization methods for estimation and control in networks

Ion Necoara, Valentin Nedelcu, Ioan Dumitrache

1302.3103

An Interior-Point Lagrangian Decomposition Method for Separable Convex Optimization

I. Necoara, J. A. K. Suykens

1302.3136

Online Identification and Tracking of Subspaces from Highly Incomplete Information

Laura Balzano, Robert Nowak, Benjamin Recht

1006.4046

Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization

Shiqian Ma, Donald Goldfarb, Lifeng Chen

0905.1643

Convex optimization

Evgeniya Vorontsova, Roland Hildebrand, Alexander Gasnikov, Fedor Stonyakin

2106.01946

Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences

Benjamin Recht, Christopher Re

1202.4184

Randomized Methods for Linear Constraints: Convergence Rates and Conditioning

D. Leventhal, A. S. Lewis

0806.3015

Characterizing arbitrarily slow convergence in the method of alternating projections

H. H. Bauschke, F. Deutsch, H. Hundal

0710.2387

Metric Subregularity and the Proximal Point Method

D. Leventhal

0902.4200

Computational and Statistical Tradeoffs via Convex Relaxation

Venkat Chandrasekaran, Michael I. Jordan

1211.1073

The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing

Andreas M. Tillmann, Marc E. Pfetsch

1205.2081

On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

Anatoli Juditsky, Fatma Kilinc Karzan, Arkadii S. Nemirovski

1001.5103

Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study

Peng Xu, Farbod Roosta-Khorasani, Michael W. Mahoney

1708.07827

Semi-Stochastic Gradient Descent Methods

Jakub Konečný, Peter Richtárik

1312.1666

A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights

Weijie Su, Stephen Boyd, Emmanuel J. Candes

1503.01243

An Investigation of Newton-Sketch and Subsampled Newton Methods

Albert S. Berahas, Raghu Bollapragada, Jorge Nocedal

1705.06211

Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm

Ming-Jun Lai, Wotao Yin

1201.4615

Accelerated Linearized Bregman Method

Bo Huang, Shiqian Ma, Donald Goldfarb

1106.5413

Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions

Damek Davis, Dmitriy Drusvyatskiy

1802.02988

Learning Optimized Risk Scores

Berk Ustun, Cynthia Rudin

1610.00168

Lower Bounds for Higher-Order Convex Optimization

Naman Agarwal, Elad Hazan

1710.10329

The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

Guanghui Lan

1309.5550

Reflection methods for user-friendly submodular optimization

Stefanie Jegelka, Francis Bach, Suvrit Sra

1311.4296

Efficient Minimization of Decomposable Submodular Functions

Peter Stobbe, Andreas Krause

1010.5511

A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization

Dan Garber, Elad Hazan

1301.4666

Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization

Zaid Harchaoui, Anatoli Juditsky, Arkadi Nemirovski

1302.2325

Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games

Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, Michael I. Jordan

2002.09806

Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling

Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

2003.10162

Momentum-Based Variance Reduction in Non-Convex SGD

Ashok Cutkosky, Francesco Orabona

1905.10018

Computing the partition function for graph homomorphisms

Alexander Barvinok, Pablo Soberón

1406.1771

Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy

Zuyue Fu, Zhuoran Yang, Zhaoran Wang

2008.00483

Iteration complexity analysis of random coordinate descent methods for $\ell_0$ regularized convex problems

Andrei Patrascu, Ion Necoara

1403.6622

An Asynchronous Parallel Randomized Kaczmarz Algorithm

Ji Liu, Stephen J. Wright, Srikrishna Sridhar

1401.4780