research
∙
09/08/2023
Parallel Submodular Function Minimization
We consider the parallel complexity of submodular function minimization ...
share
research
∙
05/29/2023
Forward and Inverse Approximation Theory for Linear Temporal Convolutional Networks
We present a theoretical analysis of the approximation properties of con...
research
∙
05/29/2023
Approximation theory of transformer networks for sequence modeling
The transformer is a widely applied architecture in sequence modeling ap...
research
∙
05/25/2023
Learning across Data Owners with Joint Differential Privacy
In this paper, we study the setting in which data owners train machine l...
research
∙
04/07/2023
Convex Minimization with Integer Minima in O(n^4) Time
Given a convex function f on ℝ^n with an integer minimizer, we show how ...
research
∙
02/27/2023
A Brief Survey on the Approximation Theory for Sequence Modelling
We survey current developments in the approximation theory of sequence m...
research
∙
08/24/2022
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
We give a simple proof of the matrix Spencer conjecture up to poly-logar...
research
∙
08/07/2022
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
Many fundamental problems in machine learning can be formulated by the c...
research
∙
07/09/2022
Improved Lower Bounds for Submodular Function Minimization
We provide a generic technique for constructing families of submodular f...
research
∙
05/20/2022
Low-cost Relevance Generation and Evaluation Metrics for Entity Resolution in AI
Entity Resolution (ER) in voice assistants is a prime component during r...
research
∙
04/25/2022
Smoothed Analysis of the Komlós Conjecture
The well-known Komlós conjecture states that given n vectors in ℝ^d with...
research
∙
11/13/2021
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
A well-known result of Banaszczyk in discrepancy theory concerns the pre...
research
∙
11/04/2021
A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent
Motivated by the Matrix Spencer conjecture, we study the problem of find...
research
∙
08/18/2021
A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound
In seminal work, Lovász, Spencer, and Vesztergombi [European J. Combin.,...
research
∙
07/20/2021
Approximation Theory of Convolutional Architectures for Time Series Modelling
We study the approximation properties of convolutional architectures app...
research
∙
09/21/2020
A Faster Interior Point Method for Semidefinite Programming
Semidefinite programs (SDPs) are a fundamental class of optimization pro...
research
∙
07/21/2020
Online Discrepancy Minimization for Stochastic Arrivals
In the stochastic online vector balancing problem, vectors v_1,v_2,…,v_T...
research
∙
07/03/2020
Minimizing Convex Functions with Integral Minimizers
Given a separation oracle 𝖲𝖮 for a convex function f that has an integra...
research
∙
04/08/2020
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
Given a separation oracle for a convex set K ⊂R^n that is contained in a...
research
∙
12/06/2019
Online Vector Balancing and Geometric Discrepancy
We consider an online vector balancing question where T vectors, chosen ...
research
∙
11/06/2019
Algorithms and Adaptivity Gaps for Stochastic k-TSP
Given a metric (V,d) and a root∈ V, the classic k-TSP problem is to find...
research
∙
10/02/2019
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
Consider a unit interval [0,1] in which n points arrive one-by-one indep...
research
∙
07/09/2019
Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization
Minimum storage regenerating (MSR) codes are MDS codes which allow for r...
research
∙
02/21/2019
The Markovian Price of Information
Suppose there are n Markov chains and we need to pay a per-step price to...
research
∙
10/01/2017
Delay Asymptotics and Bounds for Multi-Task Parallel Jobs
We study delay of jobs that consist of multiple parallel tasks, which is...
research
∙
10/01/2017
Asymptotic response time analysis for multi-task parallel jobs
The response time of jobs with multiple parallel tasks is a critical per...
research
∙
05/19/2017