Projection-Free Bandit Optimization with Privacy Guarantees

02/02/2021

Projection-Free Bandit Optimization with Privacy Guarantees

Alina Ene, Huy L. Nguyen, Adrian Vladu

Keywords:

Abstract Paper Similar Papers

Abstract: We design differentially private algorithms for the bandit convex optimization problem in the projection-free setting. This setting is important whenever the decision set has a complex geometry, and access to it is done efficiently only through a linear optimization oracle, hence Euclidean projections are unavailable (e.g. matroid polytope, submodular base polytope). This is the first differentially-private algorithm for projection-free bandit optimization, and in fact our bound matches the best known non-private projection-free algorithm and the best known private algorithm, even for the weaker setting when projections are available.

The video of this talk cannot be embedded. You can watch it here:

https://slideslive.com/38949219

(Link will open in new window)

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

04/08/2021

Non-Euclidean Differentially Private Stochastic Convex Optimization

Raef Bassily, Cristobal Guzman, Anupama Nandi

Keywords Paper

0

0

0

0

16:40

06/12/2021

Oracle Complexity in Nonsmooth Nonconvex Optimization

Guy Kornowski, Ohad Shamir

Keywords Paper

theory, deep learning, optimization

0

0

0

0

18:30

18/07/2021

Dueling Convex Optimization

Aadirupa Saha, Tomer Koren, Yishay Mansour

Keywords Paper

Algorithms, Multitask and Transfer Learning, Algorithms, Ranking and Preference Learning, Algorithms, Classification

0

0

0

0

6:19

06/12/2020

Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms

Hilal Asi, John Duchi

Keywords Paper

0

0

0

0

3:21

18/07/2021

Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Keywords Paper

Deep Learning, Algorithms, Multitask and Transfer Learning; Algorithms, Online Learning, Social Aspects of Machine Learning, Privacy, Anonymity, and Security

0

0

0

0

17:27

13/04/2021

Private optimization without constraint violations

Andres Munoz, Umar Syed, Sergei Vassilvtiskii, Ellen Vitercik

Keywords Paper

0

0

0

0

2:45

26/08/2020

Integrals over Gaussians under Linear Domain Constraints

Alexandra Gessner, Oindrila Kanjilal, Philipp Hennig

Keywords Paper

0

0

0

0

13:51

18/07/2021

Private Adaptive Gradient Methods for Convex Optimization

Hilal Asi, John Duchi, Alireza Fallah and
Omid Javidbakht, Kunal Talwar

Keywords Paper

Social Aspects of Machine Learning, Privacy, Anonymity, and Security

0

0

0

0

5:24

02/02/2021

Differentially Private Clustering via Maximum Coverage

Matthew Jones, Huy L. Nguyen, Thy D Nguyen

Keywords Paper

0

0

0

0

17:30

26/08/2020

Improved Regret Bounds for Projection-free Bandit Convex Optimization

Dan Garber, Ben Kretzu

Keywords Paper

0

0

0

0

6:03

19/08/2021

Private Stochastic Non-convex Optimization with Improved Utility Rates

Qiuchen Zhang, Jing Ma, Jian Lou, Li Xiong

Keywords Paper

Machine Learning, Learning Theory, Privacy Preserving Data Mining

0

0

0

0

13:17

08/07/2020

Sparse Recovery for Orthogonal Polynomial Transforms

Anna Gilbert, Albert Gu, Christopher Re and
Atri Rudra, Mary Wootters

Keywords Paper

Orthogonal polynomials, Jacobi polynomials, sublinear algorithms, sparse recovery

0

0

0

0

20:29

18/07/2021

Differentially Private Correlation Clustering

Mark Bun, Marek Elias, Janardhan Kulkarni

Keywords Paper

Deep Learning, Embedding Approaches, Algorithms, Representation Learning; Algorithms, Structured Prediction; Applications, Computational Biology and Bioinform, Social Aspects of Machine Learning, Privacy, Anonymity, and Security

0

0

0

0

5:14

12/07/2020

Semismooth Newton Algorithm for Efficient Projections onto $\ell_{1, \infty}$-norm Ball

Dejun Chu, Changshui Zhang, Shiliang Sun, Qing Tao

Keywords Paper

Optimization - Convex

0

0

0

0

13:55

06/12/2020

Simple and Fast Algorithm for Binary Integer and Online Linear Programming

Xiaocheng Li, Chunlin Sun, Yinyu Ye

Keywords Paper

0

0

0

0

3:24

18/07/2021

Learning Online Algorithms with Distributional Advice

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos and
Ali Vakilian, Nikos Zarifis

Keywords Paper

Algorithms

0

0

0

0

5:45

06/12/2020

Synthetic Data Generators -- Sequential and Private

Olivier Bousquet, Roi Livni, Shay Moran

Keywords Paper

Algorithms -> Stochastic Methods; Deep Learning -> Optimization for Deep Networks, Optimization -> Stochastic Optimization

0

0

0

0

3:15

04/08/2021

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals

Ilias Diakonikolas, Daniel M Kane, Thanasis Pittas, Nikos Zarifis

Keywords Paper

0

0

0

0

13:19

22/06/2020

Private stochastic convex optimization: Optimal rates in linear time

Vitaly Feldman, Tomer Koren, Kunal Talwar

Keywords Paper

Differential Privacy, Stochastic Convex Optimization, Stochastic Gradient Descent

0

0

0

0

24:28

12/07/2020

Oracle Efficient Private Non-Convex Optimization

Seth Neel, Aaron Roth, Giuseppe Vietri, Steven Wu

Keywords Paper

Privacy-preserving Statistics and Machine Learning

0

0

0

0

13:53

26/08/2020

Black Box Submodular Maximization: Discrete and Continuous Settings

Lin Chen, Mingrui Zhang, Hamed Hassani, Amin Karbasi

Keywords Paper

0

0

0

0

10:16

18/07/2021

Multidimensional Scaling: Approximation and Complexity

Erik Demaine, Adam C Hesterberg, Frederic Koehler and
Jayson Lynch, John C Urschel

Keywords Paper

Theory, Computational Learning Theory

0

0

0

0

5:14

26/04/2020

Sign-OPT: A Query-Efficient Hard-label Adversarial Attack

Minhao Cheng, Simranjit Singh, Patrick H. Chen and
Pin-Yu Chen, Sijia Liu, Cho-Jui Hsieh

Keywords Paper

0

0

0

0

4:56

14/06/2020

Optimal least-squares solution to the hand-eye calibration problem

Amit Dekel, Linus Härenstam-Nielsen, Sergio Caccamo

Keywords Paper

extrinsic, calibration, optimization, hand-eye, camera-model, dual-quaternions, least-squares

0

0

0

0

1:01

09/07/2020

On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems

Dan Garber

Keywords Paper

Convex optimization, Online learning, Stochastic optimization

0

0

0

0

9:38

06/12/2020

Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems

Luo Luo, Haishan Ye, Zhichao Huang, Tong Zhang

Keywords Paper

0

0

0

0

2:00

09/07/2020

Faster Projection-free Online Learning

Elad Hazan, Edgar Minasyan

Keywords Paper

Online learning, Convex optimization

0

0

0

0

15:04

06/12/2020

Escaping the Gravitational Pull of Softmax

Jincheng Mei, Chenjun Xiao, Bo Dai and
Lihong Li, Csaba Szepesvari, Dale Schuurmans

Keywords Paper

0

0

0

0

3:27

26/08/2020

Learning Rate Adaptation for Differentially Private Learning

Antti Koskela, Antti Honkela

Keywords Paper

0

0

0

0

13:08

18/07/2021

Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks

Jiaojiao Fan, Amirhossein Taghvaei, Yongxin Chen

Keywords Paper

Algorithms, Optimal Transport

0

0

0

1

15:56

18/07/2021

Distributionally Robust Optimization with Markovian Data

Mengmeng Li, Tobias Sutter, Daniel Kuhn

Keywords Paper

Optimization

0

0

0

0

5:18

09/07/2020

Information Theoretic Optimal Learning of Gaussian Graphical Models

Sidhant Misra, Marc D Vuffray, Andrey Lokhov

Keywords Paper

High-dimensional statistics, Information theory, Probabilistic graphical models

0

0

0

0

13:39

23/08/2020

A block decomposition algorithm for sparse optimization

Ganzhao Yuan, Li Shen, Wei-Shi Zheng

Keywords Paper

NP-hard, nonconvex optimization, block coordinate descent, sparse optimization, convex optimization

0

0

0

0

18:12

06/12/2020

Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games

Arun Suggala, Praneeth Netrapalli

Keywords Paper

1

1

0

0

3:29

06/12/2020

A novel variational form of the Schatten-$p$ quasi-norm

Paris Giampouras, Rene Vidal, Athanasios Rontogiannis, Benjamin Haeffele

Keywords Paper

0

0

0

0

3:14

08/07/2020

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças and Clara Waldmann

Keywords Paper

Atomic congestion games, existence of equilibria, pure Nash equilibria, approximate equilibria, hardness of equilibria

0

0

0

0

23:42

06/12/2021

Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems

Atara Kaplan, Dan Garber

Keywords Paper

optimization, machine learning

0

0

0

0

15:02

06/12/2021

Optimal Rates for Random Order Online Optimization

Uri Sherman, Tomer Koren, Yishay Mansour

Keywords Paper

optimization, online learning

0

0

0

0

18:43

06/12/2020

One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers

Heng Yang, Luca Carlone

Keywords Paper

0

0

0

0

3:24

18/07/2021

Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations

Angeliki Kamoutsi, Goran Banjac, John Lygeros

Keywords Paper

Theory, RL, Decisions and Control Theory

0

0

0

0

5:29