3 citations · 11 across the 9 of their papers we have counts for
10 papers
Computing Lewis Weights to High Precision by Fixed-Point Iteration
Swati Padmanabhan
The -Lewis weights of a matrix are defined by a fixed-point equation. For , Cohen and Peng [CP15] showed that iterating an equivalent rearrangement of this equation co…
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan +3
We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen kno…
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
Sally Dong, Haotian Jiang, Yin Tat Lee +2
Many fundamental problems in machine learning can be formulated by the convex program \[ \min_{θ\in R^d}\ \sum_{i=1}^{n}f_{i}(θ), \] where each is a convex, Lipschitz functio…
Online Bidding Algorithms for Return-on-Spend Constrained Advertisers
Zhe Feng, Swati Padmanabhan, Di Wang
Online advertising has recently grown into a highly competitive and complex multi-billion-dollar industry, with advertisers bidding for ad slots at large scales and high frequencie…
A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data
Jelena Diakonikolas, Chenghui Li, Swati Padmanabhan +1
Nonnegative (linear) least square problems are a fundamental class of problems that is well-studied in statistical learning and for which solvers have been implemented in many of t…
A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions
Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee +2
Zhang et al. introduced a novel modification of Goldstein's classical subgradient method, with an efficiency guarantee of for minimizing Lipschitz functions.…
Computing Lewis Weights to High Precision
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan +1
We present an algorithm for computing approximate Lewis weights to high precision. Given a full-rank with and a scalar…
A Faster Interior Point Method for Semidefinite Programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee +2
Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, a…
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li +2
We give the first approximation algorithm for mixed packing and covering semidefinite programs (SDPs) with polylogarithmic dependence on width. Mixed packing and covering SDPs cons…
An -Cost Algorithm for Semidefinite Programs with Diagonal Constraints
Yin Tat Lee, Swati Padmanabhan
We study semidefinite programs with diagonal constraints. This problem class appears in combinatorial optimization and has a wide range of engineering applications such as in circu…