p7cs.DS

Category

cs.DS

408 papers

Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity

Amit Daniely, Roy Frostig, Yoram Singer

1602.05897

Accelerated Methods for Non-Convex Optimization

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

1611.00756

Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes

Nima Anari, Shayan Oveis Gharan, Alireza Rezaei

1602.05242

SpecTr: Fast Speculative Decoding via Optimal Transport

Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, Felix Yu

2310.15141

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds

Mark Bun, Thomas Steinke

1605.02065

Algorithmic Stability for Adaptive Data Analysis

Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman

1511.02513

Between Pure and Approximate Differential Privacy

Thomas Steinke, Jonathan Ullman

1501.06095

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

Zeyuan Allen-Zhu, Yuanzhi Li, Yingyu Liang

1811.04918

Communication-Optimal Convolutional Neural Nets

James Demmel, Grace Dinh

1802.06905

The Composition Theorem for Differential Privacy

Peter Kairouz, Sewoong Oh, Pramod Viswanath

1311.0776

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

Vitaly Feldman, David Xiao

1402.6278

Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians

Constantinos Daskalakis, Gautam Kamath

1312.1054

Polynomial Learning of Distribution Families

Mikhail Belkin, Kaushik Sinha

1004.4864

Learning Poisson Binomial Distributions

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

1107.2702

Near-optimal-sample estimators for spherical Gaussian mixtures

Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, Ananda Theertha Suresh

1402.4746

Generalization in Adaptive Data Analysis and Holdout Reuse

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

1506.02629

Preserving Statistical Validity in Adaptive Data Analysis

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

1411.2664

Sever: A Robust Meta-Algorithm for Stochastic Optimization

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart

1803.02815

Learning mixtures of structured distributions over discrete domains

Siu-on Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun

1210.0864

Relative-Error CUR Matrix Decompositions

Petros Drineas, Michael W. Mahoney, S. Muthukrishnan

0708.3696

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

Agnostic Estimation of Mean and Covariance

Kevin A. Lai, Anup B. Rao, Santosh Vempala

1604.06968

Robust Estimators in High Dimensions without the Computational Intractability

Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart

1604.06443

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction

Jacob Steinhardt, Gregory Valiant, Moses Charikar

1606.05374

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

Surbhi Goel, Adam Klivans

1709.06010

Settling the Polynomial Learnability of Mixtures of Gaussians

Ankur Moitra, Gregory Valiant

1004.4223

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

1206.5349

Recovery Guarantees for One-hidden-layer Neural Networks

Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon

1706.03175

Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Thomas Steinke, Jonathan Ullman

1410.1228

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant

1112.5659

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

1307.2205

How Robust are Reconstruction Thresholds for Community Detection?

Ankur Moitra, William Perry, Alexander S. Wein

1511.01473

Fast Wavenet Generation Algorithm

Tom Le Paine, Pooya Khorrami, Shiyu Chang, Yang Zhang, Prajit Ramachandran, Mark A. Hasegawa-Johnson, Thomas S. Huang

1611.09482

Practical and Optimal LSH for Angular Distance

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, Ludwig Schmidt

1509.02897

Preventing False Discovery in Interactive Data Analysis is Hard

Moritz Hardt, Jonathan Ullman

1408.1655

Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

Zeyuan Allen-Zhu, Lorenzo Orecchia

1407.1537

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

Beyond Locality-Sensitive Hashing

Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya Razenshteyn

1306.1547

Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing

Alexandr Andoni, Ilya Razenshteyn

1507.04299

Optimal Data-Dependent Hashing for Approximate Near Neighbors

Alexandr Andoni, Ilya Razenshteyn

1501.01062

Sparser Johnson-Lindenstrauss Transforms

Daniel M. Kane, Jelani Nelson

1012.1577

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

Optimal Black-Box Reductions Between Optimization Objectives

Zeyuan Allen-Zhu, Elad Hazan

1603.05642

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

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

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

Zeyuan Allen-Zhu

1801.02982

Fast approximation of matrix coherence and statistical leverage

Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff

1109.3843

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings

Jelani Nelson, Huy L. Nguyen

1211.1002

Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program

Prasad Raghavendra, Tselil Schramm

1507.05136

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems

Yin Tat Lee, Aaron Sidford

1305.1922

Further Optimal Regret Bounds for Thompson Sampling

Shipra Agrawal, Navin Goyal

1209.3353

Concentrated Differential Privacy

Cynthia Dwork, Guy N. Rothblum

1603.01887

The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1511.03592

A Size-Free CLT for Poisson Multinomials and its Applications

Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos

1511.03641

Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions

Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi

2207.04380

The Geometry of Differential Privacy: the Sparse and Approximate Cases

Aleksandar Nikolov, Kunal Talwar, Li Zhang

1212.0297

An Efficient Parallel Solver for SDD Linear Systems

Richard Peng, Daniel A. Spielman

1311.3286

QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, Milan Vojnovic

1610.02132

Generalization Bounds for Uniformly Stable Algorithms

Vitaly Feldman, Jan Vondrak

1812.09859

Relative Error Tensor Low Rank Approximation

Zhao Song, David P. Woodruff, Peilin Zhong

1704.08246

The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures

Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, James Voss

1311.2891

Smoothed Analysis of Tensor Decompositions

Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan

1311.3651

Fast and robust tensor decomposition with applications to dictionary learning

Tselil Schramm, David Steurer

1706.08672

Interactive Privacy via the Median Mechanism

Aaron Roth, Tim Roughgarden

0911.1813

Simple, Efficient, and Neural Algorithms for Sparse Coding

Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra

1503.00778

A Learning Theory Approach to Non-Interactive Database Privacy

Avrim Blum, Katrina Ligett, Aaron Roth

1109.2229

Polynomial-time Tensor Decompositions with Sum-of-Squares

Tengyu Ma, Jonathan Shi, David Steurer

1610.01980

Provable learning of Noisy-or Networks

Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski

1612.08795

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

Boaz Barak, Jonathan A. Kelner, David Steurer

1407.1543

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

1512.02337

Twice-Ramanujan Sparsifiers

Joshua Batson, Daniel A. Spielman, Nikhil Srivastava

0808.0163

Fairness Through Computationally-Bounded Awareness

Michael P. Kim, Omer Reingold, Guy N. Rothblum

1803.03239

Ranking with Fairness Constraints

L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi

1704.06840

Calibration for the (Computationally-Identifiable) Masses

Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum

1711.08513

Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

Michael Kearns, Seth Neel, Aaron Roth, Zhiwei Steven Wu

1711.05144

Using Optimization to Solve Positive LPs Faster in Parallel

Zeyuan Allen-Zhu, Lorenzo Orecchia

1407.1925

Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments

Jiyan Yang, Xiangrui Meng, Michael W. Mahoney

1502.03032

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

Dimitri P. Bertsekas

1507.01030

Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates

Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia

1506.04838

Natasha 2: Faster Non-Convex Optimization Than SGD

Zeyuan Allen-Zhu

1708.08694

Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford

1506.07512

Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Richard Peng, Kanat Tangwongsan, Peng Zhang

1201.5135

Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms

Se-Young Yun, Alexandre Proutiere

1412.7335

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

Uniform Sampling for Matrix Approximation

Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford

1408.5099

Multi-Armed Bandits in Metric Spaces

Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal

0809.4882

Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms

Aleksander Madry

1003.5907

Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

Dan Feldman, Melanie Schmidt, Christian Sohler

1807.04518

Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method

Lihua Lei, Michael I. Jordan

1609.03261

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu

1410.6801

Principal Component Analysis and Higher Correlations for Distributed Data

Ravindran Kannan, Santosh Vempala, David Woodruff

1304.3162

Relative Errors for Deterministic Low-Rank Matrix Approximations

Mina Ghashami, Jeff M. Phillips

1307.7454

Matrix Completion has No Spurious Local Minimum

Rong Ge, Jason D. Lee, Tengyu Ma

1605.07272

Sum-of-squares lower bounds for planted clique

Raghu Meka, Aaron Potechin, Avi Wigderson

1503.06447

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

Rasmus Kyng, Sushant Sachdeva

1605.02353

Near-Optimal Column-Based Matrix Reconstruction

Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail

1103.0995

Dropping Convexity for Faster Semi-definite Optimization

Srinadh Bhojanapalli, Anastasios Kyrillidis, Sujay Sanghavi

1509.03917

Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

1201.1214

Hypercontractivity, Sum-of-Squares Proofs, and their Applications

Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou

1205.4484

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou

1110.1360

Non-commutative Edmonds' problem and matrix semi-invariants

Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam

1508.00690

Optimal Column-Based Low-Rank Matrix Reconstruction

Venkatesan Guruswami, Ali Kemal Sinop

1104.1732

Optimal Time Bounds for Approximate Clustering

Ramgopal Mettu, Greg Plaxton

1301.0587

Numerical Composition of Differential Privacy

Sivakanth Gopi, Yin Tat Lee, Lukas Wutschitz

2106.02848

Thompson Sampling for Contextual Bandits with Linear Payoffs

Shipra Agrawal, Navin Goyal

1209.3352

Mixture Models, Robustness, and Sum of Squares Proofs

Samuel B. Hopkins, Jerry Li

1711.07454

Being Robust (in High Dimensions) Can Be Practical

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

1703.00893

List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1711.07211

Efficient volume sampling for row/column subset selection

Amit Deshpande, Luis Rademacher

1004.4057

The power of sum-of-squares for detecting hidden structures

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer

1710.05017

Faster Subset Selection for Matrices and Applications

Haim Avron, Christos Boutsidis

1201.0127

Robust Communication-Optimal Distributed Clustering Algorithms

Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David Woodruff

1703.00830

Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization

Jelena Diakonikolas, Constantinos Daskalakis, Michael I. Jordan

2011.00364

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 Geometry of Differential Privacy

Moritz Hardt, Kunal Talwar

0907.3754

Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents

Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender

2007.15125

Sparsified SGD with Memory

Sebastian U. Stich, Jean-Baptiste Cordonnier, Martin Jaggi

1809.07599

Unique End of Potential Line

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

1811.03841

The Hardness of Approximation of Euclidean k-means

Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop

1502.03316

Randomized Composable Core-sets for Distributed Submodular Maximization

Vahab Mirrokni, Morteza Zadimoghaddam

1506.06715

Simple and Deterministic Matrix Sketching

Edo Liberty

1206.0594

Randomized Rounding for the Largest Simplex Problem

Aleksandar Nikolov

1412.0036

A Lyapunov Analysis of Momentum Methods in Optimization

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

1611.02635

Succinct progress measures for solving parity games

Marcin Jurdzinski, Ranko Lazic

1702.05051

Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1611.03473

Local max-cut in smoothed polynomial time

Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei

1610.04807

Rounding Semidefinite Programming Hierarchies via Global Correlation

Boaz Barak, Prasad Raghavendra, David Steurer

1104.4680

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Venkatesan Guruswami, Ali Kemal Sinop

1104.4746

Bipartite Perfect Matching is in quasi-NC

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

1601.06319

Generalized Wong sequences and their applications to Edmonds' problems

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

1307.6429

Sparse PCA via Bipartite Matchings

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

1508.00625

Constructive noncommutative rank computation is in deterministic polynomial time

Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam

1512.03531

An Improved Approximation Algorithm for the Column Subset Selection Problem

Christos Boutsidis, Michael W. Mahoney, Petros Drineas

0812.4293

Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems

Ilias Diakonikolas, Mihalis Yannakakis

0805.2646

Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

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

1507.06970

Near-optimal RNA-Seq quantification

Nicolas Bray, Harold Pimentel, Páll Melsted, Lior Pachter

1505.02710

Robust polynomial regression up to the information theoretic limit

Daniel Kane, Sushrut Karmalkar, Eric Price

1708.03257

Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression

Xiangrui Meng, Michael W. Mahoney

1210.3135

A Sparse Johnson--Lindenstrauss Transform

Anirban Dasgupta, Ravi Kumar, Tamás Sarlós

1004.4240

The Power of Linear Reconstruction Attacks

Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith

1210.2381

Revisiting the Nystrom Method for Improved Large-Scale Machine Learning

Alex Gittens, Michael W. Mahoney

1303.1849

Graph Sparsification by Effective Resistances

Daniel A. Spielman, Nikhil Srivastava

0803.0929

The Fast Cauchy Transform and Faster Robust Linear Regression

Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff

1207.4684

The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks

Emmanuel Abbe, Enric Boix-Adsera, Theodor Misiakiewicz

2202.08658

A Practical Algorithm for Topic Modeling with Provable Guarantees

Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, Michael Zhu

1212.4777

Improved matrix algorithms via the Subsampled Randomized Hadamard Transform

Christos Boutsidis, Alex Gittens

1204.0062

Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform

Nir Ailon, Edo Liberty

1005.5513

Rounding Sum-of-Squares Relaxations

Boaz Barak, Jonathan Kelner, David Steurer

1312.6652

LSRN: A Parallel Iterative Solver for Strongly Over- or Under-Determined Systems

Xiangrui Meng, Michael A. Saunders, Michael W. Mahoney

1109.5981

Neural Execution of Graph Algorithms

Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, Charles Blundell

1910.10593

Tensor principal component analysis via sum-of-squares proofs

Samuel B. Hopkins, Jonathan Shi, David Steurer

1507.03269

More Algorithms for Provable Dictionary Learning

Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

1401.0579

Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms

Rong Ge, Tengyu Ma

1504.05287

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

Boaz Barak, David Steurer

1404.5236

Improved analysis of the subsampled randomized Hadamard transform

Joel A. Tropp

1011.1595

Lower Bounds on Near Neighbor Search via Metric Expansion

Rina Panigrahy, Kunal Talwar, Udi Wieder

1005.0418

Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi

1111.1491

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu

1301.6628

What Can ResNet Learn Efficiently, Going Beyond Kernels?

Zeyuan Allen-Zhu, Yuanzhi Li

1905.10337

Probably Approximately Metric-Fair Learning

Guy N. Rothblum, Gal Yona

1803.03242

Runtime Guarantees for Regression Problems

Hui Han Chin, Aleksander Madry, Gary Miller, Richard Peng

1110.1358

Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension

Yichuan Deng, Sridhar Mahadevan, Zhao Song

2304.04397

Robust Learning of Fixed-Structure Bayesian Networks

Yu Cheng, Ilias Diakonikolas, Daniel Kane, Alistair Stewart

1606.07384

A faster algorithm for finding Tarski fixed points

John Fearnley, Dömötör Pálvölgyi, Rahul Savani

2010.02618

Optimal lower bounds for locality sensitive hashing (except when q is tiny)

Ryan O'Donnell, Yi Wu, Yuan Zhou

0912.0250

Tighter Low-rank Approximation via Sampling the Leveraged Element

Srinadh Bhojanapalli, Prateek Jain, Sujay Sanghavi

1410.3886

Spectral algorithms for tensor completion

Andrea Montanari, Nike Sun

1612.07866

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Umang Bhaskar, Yu Cheng, Young Kun Ko, Chaitanya Swamy

1512.03543

Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations

Haris Aziz, Chun Ye

1307.2908

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

Zeyuan Allen-Zhu

1702.00763

Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1505.00662

A simple and practical algorithm for differentially private data release

Moritz Hardt, Katrina Ligett, Frank McSherry

1012.4763

Learning Geometric Concepts with Nasty Noise

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1707.01242

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward

1612.07925

Exact tensor completion with sum-of-squares

Aaron Potechin, David Steurer

1702.06237

A bi-criteria approximation algorithm for $k$ Means

Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward

1507.04227

Learning One-hidden-layer Neural Networks with Landscape Design

Rong Ge, Jason D. Lee, Tengyu Ma

1711.00501

An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization

Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh

1406.2951

Iterative Constructions and Private Data Release

Anupam Gupta, Aaron Roth, Jonathan Ullman

1107.3731

Quantum entanglement, sum of squares, and the log rank conjecture

Boaz Barak, Pravesh Kothari, David Steurer

1701.06321

Deterministic Polynomial Time Algorithms for Matrix Completion Problems

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

0907.0774

Near-optimal Coresets For Least-Squares Regression

Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail

1202.3505

Outlier-robust moment-estimation via sum-of-squares

Pravesh K. Kothari, David Steurer

1711.11581

Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm

Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford

1602.06929

On Learning Mixtures of Well-Separated Gaussians

Oded Regev, Aravindan Vijayaraghavan

1710.11592

Clustering with Spectral Norm and the k-means Algorithm

Amit Kumar, Ravindran Kannan

1004.1823

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

Jason M. Altschuler, Pablo A. Parrilo

2309.07879

Sketching as a Tool for Numerical Linear Algebra

David P. Woodruff

1411.4357

Approximating $k$-Median via Pseudo-Approximation

Shi Li, Ola Svensson

1211.0243

LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

Zeyuan Allen-Zhu, Yuanzhi Li

1607.03463

Efficient Algorithms and Lower Bounds for Robust Linear Regression

Ilias Diakonikolas, Weihao Kong, Alistair Stewart

1806.00040

A simple SVD algorithm for finding hidden partitions

Van Vu

1404.3918

Stationary signal processing on graphs

Nathanaël Perraudin, Pierre Vandergheynst

1601.02522

Communication-Optimal Distributed Clustering

Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang

1702.00196

Faster Algorithms for Privately Releasing Marginals

Justin Thaler, Jonathan Ullman, Salil Vadhan

1205.1758

An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford

1304.2338

Minimizing Communication in Linear Algebra

Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz

0905.2485

Optimal Private Halfspace Counting via Discrepancy

S. Muthukrishnan, Aleksandar Nikolov

1203.5453

A nearly-mlogn time solver for SDD linear systems

Ioannis Koutis, Gary Miller, Richard Peng

1102.4842

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

Bruce Hajek, Yihong Wu, Jiaming Xu

1412.6156

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

1704.03866

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

Zeyuan Allen-Zhu, Yuanzhi Li

1701.01722

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

Distributed Matrix Completion and Robust Factorization

Lester Mackey, Ameet Talwalkar, Michael I. Jordan

1107.0789

The Frontiers of Fairness in Machine Learning

Alexandra Chouldechova, Aaron Roth

1810.08810

Fast Exact Matrix Completion with Finite Samples

Prateek Jain, Praneeth Netrapalli

1411.1087

Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent

Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, Adam Klivans

2006.12011

Communication lower bounds and optimal algorithms for programs that reference arrays -- Part 1

Michael Christ, James Demmel, Nicholas Knight, Thomas Scanlon, Katherine Yelick

1308.0068

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

Dominik Csiba, Peter Richtárik

1506.02227

Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery

Emmanuel Abbe, Afonso S. Bandeira, Annina Bracher, Amit Singer

1404.4749

Compressive Spectral Clustering

Nicolas Tremblay, Gilles Puy, Remi Gribonval, Pierre Vandergheynst

1602.02018

Exponential Lower Bounds For Policy Iteration

John Fearnley

1003.3418

Algorithms and Hardness for Subspace Approximation

Amit Deshpande, Kasturi Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi

0912.1403

On the Structure, Covering, and Learning of Poisson Multinomial Distributions

Constantinos Daskalakis, Gautam Kamath, Christos Tzamos

1504.08363

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1511.04066

Low Rank Approximation and Regression in Input Sparsity Time

Kenneth L. Clarkson, David P. Woodruff

1207.6365

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan

1304.8087

Graph Expansion and Communication Costs of Fast Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz

1109.1693

$k$-center Clustering under Perturbation Resilience

Maria-Florina Balcan, Nika Haghtalab, Colin White

1505.03924

Random Projections for the Nonnegative Least-Squares Problem

Christos Boutsidis, Petros Drineas

0812.4547

Approximating permanents and hafnians

Alexander Barvinok

1601.07518

Mixture Selection, Mechanism Design, and Signaling

Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng

1508.03679

Estimating operator norms using covering nets

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

1509.05065

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Samir Datta, Raghav Kulkarni, Sambuddha Roy

0802.2850

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

Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, Sujay Sanghavi

1606.03168

Fast matrix completion without the condition number

Moritz Hardt, Mary Wootters

1407.4070

A PTAS for Agnostically Learning Halfspaces

Amit Daniely

1410.7050

Ten Steps of EM Suffice for Mixtures of Two Gaussians

Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis

1609.00368

Approximation Algorithms for Restless Bandit Problems

Sudipto Guha, Kamesh Munagala, Peng Shi

0711.3861

Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics

Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu

1603.09535

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

Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang

2302.11068

Billion-scale similarity search with GPUs

Jeff Johnson, Matthijs Douze, Hervé Jégou

1702.08734

Min-Max Graph Partitioning and Small Set Expansion

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph, Naor, Roy Schwartz

1110.4319

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

Haris Aziz, Simon Mackenzie

1604.03655

Robust Sparse Estimation Tasks in High Dimensions

Jerry Li

1702.05860

Proximal Newton-type methods for minimizing composite functions

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

1206.1623

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak, Ankur Moitra

1501.06521

Faster Kernel Ridge Regression Using Sketching and Preconditioning

Haim Avron, Kenneth L. Clarkson, David P. Woodruff

1611.03220

Scaling Neural Tangent Kernels via Sketching and Random Features

Amir Zandieh, Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, Jinwoo Shin

2106.07880

High-Dimensional Robust Mean Estimation in Nearly-Linear Time

Yu Cheng, Ilias Diakonikolas, Rong Ge

1811.09380

Strongly Refuting Random CSPs Below the Spectral Threshold

Prasad Raghavendra, Satish Rao, Tselil Schramm

1605.00058

On Acceleration with Noise-Corrupted Gradients

Michael B. Cohen, Jelena Diakonikolas, Lorenzo Orecchia

1805.12591

Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models

Jan van den Brand, Zhao Song, Tianyi Zhou

2304.02207

Toward a unified theory of sparse dimensionality reduction in Euclidean space

Jean Bourgain, Sjoerd Dirksen, Jelani Nelson

1311.2542

KDEformer: Accelerating Transformers via Kernel Density Estimation

Amir Zandieh, Insu Han, Majid Daliri, Amin Karbasi

2302.02451

On the Hardness of Signaling

Shaddin Dughmi

1402.4194

Local Search Yields a PTAS for k-Means in Doubling Metrics

Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour

1603.08976

Sample-Optimal Density Estimation in Nearly-Linear Time

Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt

1506.00671

Decentralized Deep Learning with Arbitrary Communication Compression

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

1907.09356

Fast Attention Requires Bounded Entries

Josh Alman, Zhao Song

2302.13214

Privately Releasing Conjunctions and the Statistical Query Barrier

Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan Ullman

1011.1296

Pipage Rounding, Pessimistic Estimators and Matrix Concentration

Nicholas J. A. Harvey, Neil Olver

1307.2274

Learning Topic Models - Going beyond SVD

Sanjeev Arora, Rong Ge, Ankur Moitra

1204.1956

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman

1512.01892

Deterministic Feature Selection for $k$-means Clustering

Christos Boutsidis, Malik Magdon-Ismail

1109.5664

Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta

1811.12469

Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels

Kai Zhong, Zhao Song, Inderjit S. Dhillon

1711.03440

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform

Josh Alman, Zhao Song

2505.11892

Faster Least Squares Approximation

Petros Drineas, Michael W. Mahoney, S. Muthukrishnan, Tamas Sarlos

0710.1435

Transductive Multi-view Zero-Shot Learning

Yanwei Fu, Timothy M. Hospedales, Tao Xiang, Shaogang Gong

1501.04560

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

1911.05416

Approaching optimality for solving SDD systems

Ioannis Koutis, Gary L. Miller, Richard Peng

1003.2958

Stochastic bandits robust to adversarial corruptions

Thodoris Lykouris, Vahab Mirrokni, Renato Paes Leme

1803.09353

Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1209.2184

Nearly Maximum Flows in Nearly Linear Time

Jonah Sherman

1304.2077

Fast unfolding of communities in large networks

Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre

0803.0476

Optimal Testing for Properties of Distributions

Jayadev Acharya, Constantinos Daskalakis, Gautam Kamath

1507.05952

Determinantal Point Processes in Randomized Numerical Linear Algebra

Michał Dereziński, Michael W. Mahoney

2005.03185

Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition

Cameron Musco, Christopher Musco

1504.05477

Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1202.3177

Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra

1610.02704

Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Viresh Patel, Guus Regts

1607.01167

Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics

Zhiyang Xun, Shivam Gupta, Eric Price

2510.26324

Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

Ali Civril, Malik Magdon-Ismail

1006.4349

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

Anshumali Shrivastava, Ping Li

1405.5869

Multi-way spectral partitioning and higher-order Cheeger inequalities

James R. Lee, Shayan Oveis Gharan, Luca Trevisan

1111.1055

Sampling Algorithms and Coresets for Lp Regression

Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney

0707.1714

The Densest k-Subhypergraph Problem

Eden Chlamtáč, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca

1605.04284

Single Pass Spectral Sparsification in Dynamic Streams

Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford

1407.1289

Faster Matrix Multiplication via Asymmetric Hashing

Ran Duan, Hongxun Wu, Renfei Zhou

2210.10173

Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals

Surbhi Goel, Sushrut Karmalkar, Adam Klivans

1911.01462

The CLRS Algorithmic Reasoning Benchmark

Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, Charles Blundell

2205.15659

InstaHide: Instance-hiding Schemes for Private Distributed Learning

Yangsibo Huang, Zhao Song, Kai Li, Sanjeev Arora

2010.02772

Differentially Private Fair Learning

Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, Jonathan Ullman

1812.02696

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan

1305.1681

Vertex Sparsifiers and Abstract Rounding Algorithms

Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra

1006.4536

Provable Submodular Minimization using Wolfe's Algorithm

Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari

1411.0095

Fast Sketching of Polynomial Kernels of Polynomial Degree

Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang

2108.09420

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks

Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis

2006.12476

Testing Shape Restrictions of Discrete Distributions

Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld

1507.03558

Composition of Differential Privacy & Privacy Amplification by Subsampling

Thomas Steinke

2210.00597

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

1508.03261

A Faster Small Treewidth SDP Solver

Yuzhou Gu, Zhao Song

2211.06033

Computational Hardness of the Hylland-Zeckhauser Scheme

Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis

2107.05746

Nearly Tight Low Stretch Spanning Trees

Ittai Abraham, Yair Bartal, Ofer Neiman

0808.2017

Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1202.3173

FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching

Farzin Haddadpour, Belhal Karimi, Ping Li, Xiaoyun Li

2008.04975

On the Complexity of Random Satisfiability Problems with Planted Solutions

Vitaly Feldman, Will Perkins, Santosh Vempala

1311.4821

Frequent Directions : Simple and Deterministic Matrix Sketching

Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff

1501.01711

The Discrete Gaussian for Differential Privacy

Clément L. Canonne, Gautam Kamath, Thomas Steinke

2004.00010

Faster all-pairs shortest paths via circuit complexity

Ryan Williams

1312.6680

Clustering Stable Instances of Euclidean k-means

Abhratanu Dutta, Aravindan Vijayaraghavan, Alex Wang

1712.01241

A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents

Haris Aziz, Simon Mackenzie

1508.05143

On the Local Structure of Stable Clustering Instances

Vincent Cohen-Addad, Chris Schwiegelshohn

1701.08423

Privacy Amplification by Iteration

Vitaly Feldman, Ilya Mironov, Kunal Talwar, Abhradeep Thakurta

1808.06651

Sparse Covers for Sums of Indicators

Constantinos Daskalakis, Christos Papadimitriou

1306.1265

Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)

Anshumali Shrivastava, Ping Li

1410.5410

The solution space geometry of random linear equations

Dimitris Achlioptas, Michael Molloy

1107.5550

Concurrent Composition Theorems for Differential Privacy

Salil Vadhan, Wanrong Zhang

2207.08335

Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling

Vitaly Feldman, Audra McMillan, Kunal Talwar

2012.12803

Stronger Privacy Amplification by Shuffling for Rényi and Approximate Differential Privacy

Vitaly Feldman, Audra McMillan, Kunal Talwar

2208.04591

Clustering under Perturbation Resilience

Maria Florina Balcan, Yingyu Liang

1112.0826

Efficient Frequent Directions Algorithm for Sparse Matrices

Mina Ghashami, Edo Liberty, Jeff M. Phillips

1602.00412

Weisfeiler and Leman go Machine Learning: The Story so far

Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, Karsten Borgwardt

2112.09992

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

A Refined Laser Method and Faster Matrix Multiplication

Josh Alman, Virginia Vassilevska Williams

2010.05846

On a conjecture of Sokal concerning roots of the independence polynomial

Han Peters, Guus Regts

1701.08049

New Frameworks for Offline and Streaming Coreset Constructions

Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, Samson Zhou

1612.00889

Fast Semidifferential-based Submodular Function Optimization

Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes

1308.1006

The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs

Christopher Morris, Matthias Fey, Nils M. Kriege

2105.05911

Private Selection from Private Candidates

Jingcheng Liu, Kunal Talwar

1811.07971

Center-based Clustering under Perturbation Stability

Pranjal Awasthi, Avrim Blum, Or Sheffet

1009.3594

Learning Multi-item Auctions with (or without) Samples

Yang Cai, Constantinos Daskalakis

1709.00228

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration

Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, Ruosong Wang

1706.01081

Learning One Convolutional Layer with Overlapping Patches

Surbhi Goel, Adam Klivans, Raghu Meka

1802.02547

Data Stability in Clustering: A Closer Look

Shalev Ben-David, Lev Reyzin

1107.2379

Does Preprocessing Help Training Over-parameterized Neural Networks?

Zhao Song, Shuo Yang, Ruizhe Zhang

2110.04622

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications

Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong

2004.04250

Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration

Jason Altschuler, Jonathan Weed, Philippe Rigollet

1705.09634

On Symmetric and Asymmetric LSHs for Inner Product Search

Behnam Neyshabur, Nathan Srebro

1410.5518

Graph Neural Networks are Dynamic Programmers

Andrew Dudzik, Petar Veličković

2203.15544

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

Massively scalable Sinkhorn distances via the Nyström method

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

1812.05189

Consistent Weighted Sampling Made Fast, Small, and Easy

Bernhard Haeupler, Mark Manasse, Kunal Talwar

1410.4266

Further limitations of the known approaches for matrix multiplication

Josh Alman, Virginia Vassilevska Williams

1712.07246

Improved Spectral-Norm Bounds for Clustering

Pranjal Awasthi, Or Sheffet

1206.3204

Relax, no need to round: integrality of clustering formulations

Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward

1408.4045

The Structure of Optimal Private Tests for Simple Hypotheses

Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, Jonathan Ullman

1811.11148

Scalable Fair Clustering

Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner

1902.03519

Constant-time filtering using shiftable kernels

Kunal Narayan Chaudhury

1107.4617

RedQueen: An Online Algorithm for Smart Broadcasting in Social Networks

Ali Zarezade, Utkarsh Upadhyay, Hamid Rabiee, Manuel Gomez Rodriguez

1610.05773

Submodular Combinatorial Information Measures with Applications in Machine Learning

Rishabh Iyer, Ninad Khargonkar, Jeff Bilmes, Himanshu Asnani

2006.15412

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering

Shayan Oveis Gharan, Luca Trevisan

1204.2021

Calibrating Noise to Variance in Adaptive Data Analysis

Vitaly Feldman, Thomas Steinke

1712.07196

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Josh Alman, Virginia Vassilevska Williams

1810.08671

Algorithmic Foundations for the Diffraction Limit

Sitan Chen, Ankur Moitra

2004.07659

Composition Theorems for Interactive Differential Privacy

Xin Lyu

2207.09397

Introduction to Multi-Armed Bandits

Aleksandrs Slivkins

1904.07272

Mitigating Bias in Adaptive Data Gathering via Differential Privacy

Seth Neel, Aaron Roth

1806.02329

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

Krishnakumar Balasubramanian, Saeed Ghadimi

1809.06474

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into $\ell_1$

Subhash A. Khot, Nisheeth K. Vishnoi

1305.4581

Faster high-accuracy log-concave sampling via algorithmic warm starts

Jason M. Altschuler, Sinho Chewi

2302.10249

Constructive Algorithms for Discrepancy Minimization

Nikhil Bansal

1002.2259

Neural Algorithmic Reasoning

Petar Veličković, Charles Blundell

2105.02761

Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions

Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes

1311.2110

Algorithms and Hardness for Linear Algebra on Geometric Graphs

Josh Alman, Timothy Chu, Aaron Schild, Zhao Song

2011.02466

Multireference Alignment using Semidefinite Programming

Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu

1308.5256

A Faster Interior Point Method for Semidefinite Programming

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

2009.10217

Private Convex Optimization via Exponential Mechanism

Sivakanth Gopi, Yin Tat Lee, Daogao Liu

2203.00263

Computing the Independence Polynomial: from the Tree Threshold down to the Roots

Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák

1608.02282

Privacy Auditing with One (1) Training Run

Thomas Steinke, Milad Nasr, Matthew Jagielski

2305.08846

The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting

Adam Lechowicz, Nicolas Christianson, Jinhang Zuo, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, Prashant Shenoy

2303.17551

Estimating Renyi Entropy of Discrete Distributions

Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, Himanshu Tyagi

1408.1000

Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints

Rishabh Iyer, Jeff Bilmes

1311.2106

Paper Matching with Local Fairness Constraints

Ari Kobren, Barna Saha, Andrew McCallum

1905.11924

PeerReview4All: Fair and Accurate Reviewer Assignment in Peer Review

Ivan Stelmakh, Nihar B. Shah, Aarti Singh

1806.06237

Planar Graph Perfect Matching is in NC

Nima Anari, Vijay V. Vazirani

1709.07822

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi

1708.02222

Spectral Sparsification of Graphs

Daniel A. Spielman, Shang-Hua Teng

0808.4134

Zero-free regions of partition functions with applications to algorithms and graph limits

Guus Regts

1507.02089

Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

Elad Aigner-Horev, Erel Segal-Halevi

1901.09527

A Convergence Theory for Deep Learning via Over-Parameterization

Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song

1811.03962

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

Arun Jambulapati, Jerry Li, Kevin Tian

2006.06980

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation

Peter Kairouz, Ziyu Liu, Thomas Steinke

2102.06387

Combining geometry and combinatorics: A unified approach to sparse signal recovery

R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff, M. J. Strauss

0804.4666

A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning

Daniel A. Spielman, Shang-Hua Teng

0809.3232

Randomized Extended Kaczmarz for Solving Least-Squares

Anastasios Zouzias, Nikolaos Freris

1205.5770

Tightening LP Relaxations for MAP using Message Passing

David Sontag, Talya Meltzer, Amir Globerson, Tommi S. Jaakkola, Yair Weiss

1206.3288

Iterative Row Sampling

Mu Li, Gary L. Miller, Richard Peng

1211.2713

Sparsity Lower Bounds for Dimensionality Reducing Maps

Jelani Nelson, Huy L. Nguyen

1211.0995

On the optimality of tree-reweighted max-product message-passing

Vladimir Kolmogorov, Martin Wainwright

1207.1395

A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees

Ann Becker, Dan Geiger

1302.3558

A Tutorial on Spectral Clustering

Ulrike von Luxburg

0711.0189

Projection-free Online Learning

Elad Hazan, Satyen Kale

1206.4657

Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing

Bogdan Savchynskyy, Stefan Schmidt, Joerg Kappes, Christoph Schnoerr

1210.4906

CoinPress: Practical Private Mean and Covariance Estimation

Sourav Biswas, Yihe Dong, Gautam Kamath, Jonathan Ullman

2006.06618

A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time

Yeqi Gao, Zhao Song, Weixin Wang, Junze Yin

2309.07418

How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation

Josh Alman, Zhao Song

2310.04064

On Coresets for Logistic Regression

Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff

1805.08571

Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments

Sitan Chen, Jerry Li, Zhao Song

1912.07629

Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng

1010.2921

On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians

Ishaq Aden-Ali, Hassan Ashtiani, Gautam Kamath

2010.09929

Faster Algorithms for High-Dimensional Robust Covariance Estimation

Yu Cheng, Ilias Diakonikolas, Rong Ge, David Woodruff

1906.04661

Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection

Yihe Dong, Samuel B. Hopkins, Jerry Li

1906.11366

An Introduction to Matrix Concentration Inequalities

Joel A. Tropp

1501.01571

Efficiently Searching for Frustrated Cycles in MAP Inference

David Sontag, Do Kook Choe, Yitao Li

1210.4902

Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension

Christian Sohler, David P. Woodruff

1809.02961

Diverse Weighted Bipartite b-Matching

Faez Ahmed, John P. Dickerson, Mark Fuge

1702.07134

Entropy, Optimization and Counting

Mohit Singh, Nisheeth K. Vishnoi

1304.8108

Matching is as Easy as the Decision Problem, in the NC Model

Nima Anari, Vijay V. Vazirani

1901.10387