Optimization Research Papers in JMLR Volume 22

Nam Le
Sep 29, 2021

Table of Contents

Optimization Research Papers in JMLR Volume 22 (2021) #

This document lists papers from JMLR Volume 22 (2021) that focus on optimization research, categorized by their primary themes. Each paper is numbered starting from 1 within its subsection, with a brief description of its key contributions to optimization theory, algorithms, or applications.

Convex Optimization #

Papers addressing convex optimization problems, including clustering, Wasserstein barycenters, sparse optimization, and bandits.

Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm
Authors: Defeng Sun, Kim-Chuan Toh, Yancheng Yuan
Description: Proposes a convex clustering model with theoretical guarantees and an efficient algorithm.
A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
Authors: Lei Yang, Jia Li, Defeng Sun, Kim-Chuan Toh
Description: Develops a fast, globally linearly convergent algorithm for computing Wasserstein barycenters.
Wasserstein Barycenters Can Be Computed in Polynomial Time in Fixed Dimension
Authors: Jason M. Altschuler, Enric Boix-Adsera
Description: Demonstrates that Wasserstein barycenters can be computed in polynomial time for fixed dimensions.
From Low Probability to High Confidence in Stochastic Convex Optimization
Authors: Damek Davis, Dmitriy Drusvyatskiy, Lin Xiao, Junyu Zhang
Description: Analyzes methods to achieve high-confidence solutions in stochastic convex optimization.
Sparse and Smooth Signal Estimation: Convexification of L0-Formulations
Authors: Alper Atamturk, Andres Gomez, Shaoning Han
Description: Proposes convexification techniques for L0-formulations in sparse and smooth signal estimation.
Stochastic Proximal AUC Maximization
Authors: Yunwen Lei, Yiming Ying
Description: Develops stochastic proximal methods for maximizing the area under the ROC curve (AUC) in convex settings.
Sparse Convex Optimization via Adaptively Regularized Hard Thresholding
Authors: Kyriakos Axiotis, Maxim Sviridenko
Description: Introduces adaptively regularized hard thresholding for sparse convex optimization.
Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
Authors: Antoine Dedieu, Hussein Hazimeh, Rahul Mazumder
Description: Explores continuous and mixed-integer optimization approaches for learning sparse classifiers.
First-Order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
Authors: Mingrui Liu, Hassan Rafique, Qihang Lin, Tianbao Yang
Description: Provides first-order convergence theory for weakly convex-weakly concave min-max problems.
Convex Geometry and Duality of Over-parameterized Neural Networks
Authors: Tolga Ergen, Mert Pilanci
Description: Analyzes convex geometry and duality in over-parameterized neural networks.
Linear Bandits on Uniformly Convex Sets
Authors: Thomas Kerdreux, Christophe Roux, Alexandre d’Aspremont, Sebastian Pokutta
Description: Studies linear bandits on uniformly convex sets, focusing on convex optimization techniques.

Nonconvex Optimization #

Papers tackling nonconvex optimization, including stochastic gradient descent, neural network training, and stability properties.

Online Stochastic Gradient Descent on Non-Convex Losses from High-Dimensional Inference
Authors: Gerard Ben Arous, Reza Gheissari, Aukosh Jagannath
Description: Analyzes online stochastic gradient descent for nonconvex losses in high-dimensional inference.
Non-attracting Regions of Local Minima in Deep and Wide Neural Networks
Authors: Henning Petzka, Cristian Sminchisescu
Description: Investigates non-attracting regions of local minima in deep and wide neural networks.
When Does Gradient Descent with Logistic Loss Find Interpolating Two-Layer Networks?
Authors: Niladri S. Chatterji, Philip M. Long, Peter L. Bartlett
Description: Examines conditions under which gradient descent with logistic loss finds interpolating two-layer networks.
Replica Exchange for Non-Convex Optimization
Authors: Jing Dong, Xin T. Tong
Description: Proposes replica exchange methods for nonconvex optimization problems.
Failures of Model-Dependent Generalization Bounds for Least-Norm Interpolation
Authors: Peter L. Bartlett, Philip M. Long
Description: Analyzes limitations of model-dependent generalization bounds in least-norm interpolation.
On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
Authors: Constantin Christof
Description: Studies stability and optimization landscapes for neural network training with squared loss.

Stochastic Optimization #

Papers focusing on stochastic optimization methods, including momentum, Langevin dynamics, and communication-efficient algorithms.

Continuous Time Analysis of Momentum Methods
Authors: Nikola B. Kovachki, Andrew M. Stuart
Description: Provides a continuous-time analysis of momentum methods in stochastic optimization.
Generalization Performance of Multi-pass Stochastic Gradient Descent with Convex Loss Functions
Authors: Yunwen Lei, Ting Hu, Ke Tang
Description: Analyzes generalization performance of multi-pass stochastic gradient descent for convex losses.
High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
Authors: Wenlong Mou, Yi-An Ma, Martin J. Wainwright, Peter L. Bartlett, Michael I. Jordan
Description: Develops an accelerated MCMC algorithm using high-order Langevin diffusion.
Path Length Bounds for Gradient Descent and Flow
Authors: Chirag Gupta, Sivaraman Balakrishnan, Aaditya Ramdas
Description: Establishes path length bounds for gradient descent and flow in stochastic optimization.
Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
Authors: Michael Muehlebach, Michael I. Jordan
Description: Analyzes momentum-based optimization from dynamical, control-theoretic, and symplectic perspectives.
L-SVRG and L-Katyusha with Arbitrary Sampling
Authors: Xun Qian, Zheng Qu, Peter Richtárik
Description: Introduces L-SVRG and L-Katyusha algorithms with arbitrary sampling for stochastic optimization.
A Lyapunov Analysis of Accelerated Methods in Optimization
Authors: Ashia C. Wilson, Ben Recht, Michael I. Jordan
Description: Provides a Lyapunov analysis for accelerated optimization methods.
NUQSGD: Provably Communication-Efficient Data-Parallel SGD via Nonuniform Quantization
Authors: Ali Ramezani-Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, Daniel M. Roy
Description: Proposes NUQSGD, a communication-efficient stochastic gradient descent method using nonuniform quantization.
An Inertial Newton Algorithm for Deep Learning
Authors: Camille Castera, Jérôme Bolte, Cédric Févotte, Edouard Pauwels
Description: Develops an inertial Newton algorithm for deep learning optimization.
Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
Authors: Tian Tong, Cong Ma, Yuejie Chi
Description: Proposes scaled gradient descent for accelerating ill-conditioned low-rank matrix estimation.
On ADMM in Deep Learning: Convergence and Saturation-Avoidance
Authors: Jinshan Zeng, Shao-Bo Lin, Yuan Yao, Ding-Xuan Zhou
Description: Analyzes convergence and saturation-avoidance properties of ADMM in deep learning.
A Unified Convergence Analysis for Shuffling-Type Gradient Methods
Authors: Lam M. Nguyen, Quoc Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, Marten van Dijk
Description: Provides a unified convergence analysis for shuffling-type gradient methods.
Stochastic Online Optimization Using Kalman Recursion
Authors: Joseph de Vilmarest, Olivier Wintenberger
Description: Applies Kalman recursion to stochastic online optimization.
Expanding Boundaries of Gap Safe Screening
Authors: Cassio F. Dantas, Emmanuel Soubies, Cédric Févotte
Description: Expands gap safe screening techniques for stochastic optimization.
Consensus-Based Optimization on the Sphere: Convergence to Global Minimizers and Machine Learning
Authors: Massimo Fornasier, Lorenzo Pareschi, Hui Huang, Philippe Sünnen
Description: Develops consensus-based optimization on the sphere with applications to machine learning.
Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
Authors: Mert Gürbüzbalaban, Xuefeng Gao, Yuanhan Hu, Lingjiong Zhu
Description: Proposes decentralized stochastic gradient Langevin dynamics and Hamiltonian Monte Carlo methods.

Distributed/Decentralized Optimization #

Papers addressing distributed or decentralized optimization algorithms, focusing on communication efficiency and scalability.

Projection-Free Decentralized Online Learning for Submodular Maximization over Time-Varying Networks
Authors: Junlong Zhu, Qingtao Wu, Mingchuan Zhang, Ruijuan Zheng, Keqin Li
Description: Develops projection-free decentralized online learning for submodular maximization over time-varying networks.
Communication-Efficient Distributed Covariance Sketch, with Application to Distributed PCA
Authors: Zengfeng Huang, Xuemin Lin, Wenjie Zhang, Ying Zhang
Description: Proposes a communication-efficient distributed covariance sketch for distributed PCA.
Optimal Rates of Distributed Regression with Imperfect Kernels
Authors: Hongwei Sun, Qiang Wu
Description: Establishes optimal rates for distributed regression with imperfect kernels.
One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Them
Authors: Saber Salehkaleybar, Arsalan Sharifnassab, S. Jamaloddin Golestani
Description: Analyzes theoretical limits and algorithms for one-shot federated learning.
Cooperative SGD: A Unified Framework for the Design and Analysis of Local-Update SGD Algorithms
Authors: Jianyu Wang, Gauri Joshi
Description: Introduces a unified framework for designing and analyzing local-update SGD algorithms.
DeEPCA: Decentralized Exact PCA with Linear Convergence Rate
Authors: Haishan Ye, Tong Zhang
Description: Develops DeEPCA, a decentralized exact PCA method with linear convergence.

Submodular Optimization #

Papers focusing on submodular optimization, particularly in experimental design.

Batch Greedy Maximization of Non-Submodular Functions: Guarantees and Applications to Experimental Design
Authors: Jayanth Jagalur-Mohan, Youssef Marzouk
Description: Provides guarantees for batch greedy maximization of non-submodular functions with applications to experimental design.

Bandits and Online Learning #

Papers addressing multi-armed bandits, online optimization, and regret minimization.

Regulating Greed Over Time in Multi-Armed Bandits
Authors: Stefano Tracà, Cynthia Rudin, Weiyu Yan
Description: Studies methods to regulate greed over time in multi-armed bandits.
Preference-Based Online Learning with Dueling Bandits: A Survey
Authors: Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, Eyke Hüllermeier
Description: Surveys preference-based online learning with dueling bandits.
On Multi-Armed Bandit Designs for Dose-Finding Trials
Authors: Maryam Aziz, Emilie Kaufmann, Marie-Karelle Riviere
Description: Explores multi-armed bandit designs for dose-finding trials.
Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
Authors: Julian Zimmert, Yevgeny Seldin
Description: Proposes Tsallis-INF, an optimal algorithm for stochastic and adversarial bandits.
Bandit Convex Optimization in Non-Stationary Environments
Authors: Peng Zhao, Guanghui Wang, Lijun Zhang, Zhi-Hua Zhou
Description: Addresses bandit convex optimization in non-stationary environments.
A Contextual Bandit Bake-off
Authors: Alberto Bietti, Alekh Agarwal, John Langford
Description: Compares contextual bandit algorithms in a comprehensive evaluation.
MetaGrad: Adaptation Using Multiple Learning Rates in Online Learning
Authors: Tim van Erven, Wouter M. Koolen, Dirk van der Hoeven
Description: Introduces MetaGrad, an adaptive online learning algorithm with multiple learning rates.
Achieving Fairness in the Stochastic Multi-Armed Bandit Problem
Authors: Vishakha Patil, Ganesh Ghalme, Vineet Nair, Y. Narahari
Description: Develops methods for achieving fairness in stochastic multi-armed bandits.
Refined Approachability Algorithms and Application to Regret Minimization with Global Costs
Authors: Joon Kwon
Description: Proposes refined approachability algorithms for regret minimization with global costs.
Bandit Learning in Decentralized Matching Markets
Authors: Lydia T. Liu, Feng Ruan, Horia Mania, Michael I. Jordan
Description: Applies bandit learning to decentralized matching markets.
Thompson Sampling Algorithms for Cascading Bandits
Authors: Zixin Zhong, Wang Chi Chueng, Vincent Y. F. Tan
Description: Develops Thompson sampling algorithms for cascading bandits.
Fast Learning for Renewal Optimization in Online Task Scheduling
Authors: Michael J. Neely
Description: Proposes fast learning methods for renewal optimization in online task scheduling.

Bayesian and Hyperparameter Optimization #

Papers addressing Bayesian optimization and hyperparameter tuning for scalable and robust optimization.

An Empirical Study of Bayesian Optimization: Acquisition Versus Partition
Authors: Erich Merrill, Alan Fern, Xiaoli Fern, Nima Dolatnia
Description: Conducts an empirical study comparing acquisition and partition strategies in Bayesian optimization.
Hyperparameter Optimization via Sequential Uniform Designs
Authors: Zebin Yang, Aijun Zhang
Description: Proposes sequential uniform designs for hyperparameter optimization.
Are We Forgetting about Compositional Optimisers in Bayesian Optimisation?
Authors: Antoine Grosnit, Alexander I. Cowen-Rivers, Rasul Tutunov, Ryan-Rhys Griffiths, Jun Wang, Haitham Bou-Ammar
Description: Explores the role of compositional optimizers in Bayesian optimization.
GIBBON: General-Purpose Information-Based Bayesian Optimisation
Authors: Henry B. Moss, David S. Leslie, Javier Gonzalez, Paul Rayson
Description: Introduces GIBBON, a general-purpose information-based Bayesian optimization framework.
On lp-Hyperparameter Learning via Bilevel Nonsmooth Optimization
Authors: Takayuki Okuno, Akiko Takeda, Akihiro Kawana, Motokazu Watanabe
Description: Studies lp-hyperparameter learning using bilevel nonsmooth optimization.

Optimization in Reinforcement Learning #

Papers focusing on optimization techniques for reinforcement learning, including policy iteration and Q-learning.

Safe Policy Iteration: A Monotonically Improving Approximate Policy Iteration Approach
Authors: Alberto Maria Metelli, Matteo Pirotta, Daniele Calandriello, Marcello Restelli
Description: Proposes a safe policy iteration method with monotonic improvement for reinforcement learning.
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
Authors: Alekh Agarwal, Sham M. Kakade, Jason D. Lee, Gaurav Mahajan
Description: Analyzes the optimality, approximation, and distribution shift in policy gradient methods.
Langevin Dynamics for Adaptive Inverse Reinforcement Learning of Stochastic Gradient Algorithms
Authors: Vikram Krishnamurthy, George Yin
Description: Applies Langevin dynamics to adaptive inverse reinforcement learning for stochastic gradient algorithms.
Hamilton-Jacobi Deep Q-Learning for Deterministic Continuous-Time Systems with Lipschitz Continuous Controls
Authors: Jeongho Kim, Jaeuk Shin, Insoon Yang
Description: Develops Hamilton-Jacobi deep Q-learning for deterministic continuous-time systems.
Partial Policy Iteration for L1-Robust Markov Decision Processes
Authors: Chin Pang Ho, Marek Petrik, Wolfram Wiesemann
Description: Introduces partial policy iteration for L1-robust Markov decision processes.
Gaussian Approximation for Bias Reduction in Q-Learning
Authors: Carlo D’Eramo, Andrea Cini, Alessandro Nuara, Matteo Pirotta, Cesare Alippi, Jan Peters, Marcello Restelli
Description: Proposes Gaussian approximation techniques for bias reduction in Q-learning.