research
∙
05/25/2023
Online and Streaming Algorithms for Constrained k-Submodular Maximization
Constrained k-submodular maximization is a general framework that captur...
share
research
∙
02/28/2023
High Probability Convergence of Stochastic Gradient Methods
In this work, we describe a generic approach to show convergence with hi...
research
∙
02/03/2023
Online Ad Allocation with Predictions
Display Ads and the generalized assignment problem are two well-studied ...
research
∙
10/03/2022
High Probability Convergence for Accelerated Stochastic Mirror Descent
In this work, we describe a generic approach to show convergence with hi...
research
∙
09/29/2022
META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions
We study the application of variance reduction (VR) techniques to genera...
research
∙
09/29/2022
On the Convergence of AdaGrad on ^d: Beyond Convexity, Non-Asymptotic Rate and Acceleration
Existing analysis of AdaGrad and other adaptive methods for smooth conve...
research
∙
01/28/2022
Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction
In this paper, we study the finite-sum convex optimization problem focus...
research
∙
12/22/2020
Projection-Free Bandit Optimization with Privacy Guarantees
We design differentially private algorithms for the bandit convex optimi...
research
∙
10/15/2020
Adaptive and Universal Single-gradient Algorithms for Variational Inequalities
Variational inequalities with monotone operators capture many problems o...
research
∙
07/17/2020
Adaptive Gradient Methods for Constrained Convex Optimization
We provide new adaptive first-order methods for constrained convex optim...
research
∙
02/18/2020
A note on maximizing the difference between a monotone submodular function and a linear function
Motivated by team formation applications, we study discrete optimization...
research
∙
11/29/2019
An Optimal Streaming Algorithm for Non-monotone Submodular Maximization
We study the problem of maximizing a non-monotone submodular function su...
research
∙
10/16/2019
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
We consider node-weighted survivable network design (SNDP) in planar gra...
research
∙
05/30/2019
Parallel Algorithm for Non-Monotone DR-Submodular Maximization
In this work, we give a new parallel algorithm for the problem of maximi...
research
∙
02/18/2019
Improved Convergence for ℓ_∞ and ℓ_1 Regression via Iteratively Reweighted Least Squares
The iteratively reweighted least squares method (IRLS) is a popular tech...
research
∙
12/04/2018
A Parallel Double Greedy Algorithm for Submodular Maximization
We study parallel algorithms for the problem of maximizing a non-negativ...
research
∙
11/19/2018
Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
We consider fast algorithms for monotone submodular maximization subject...
research
∙
08/29/2018
Submodular Maximization with Packing Constraints in Parallel
We consider the problem of maximizing the multilinear extension of a sub...
research
∙
04/15/2018
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
In this paper, we study the tradeoff between the approximation guarantee...
research
∙
06/27/2016
A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns
A function f: Z_+^E →R_+ is DR-submodular if it satisfies f( + χ_i) -f (...
research
∙
02/09/2015
