Timezone: »
Poster
Online Linear Optimization with Many Hints
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit
We study an online linear optimization (OLO) problem in which the learner is provided access to $K$ ``hint'' vectors in each round prior to making a decision. In this setting, we devise an algorithm that obtains logarithmic regret whenever there exists a convex combination of the $K$ hints that has positive correlation with the cost vectors. This significantly extends prior work that considered only the case $K=1$. To accomplish this, we develop a way to combine many arbitrary OLO algorithms to obtain regret only a logarithmically worse factor than the minimum regret of the original algorithms in hindsight; this result is of independent interest.
Author Information
Aditya Bhaskara (University of Utah)
Ashok Cutkosky (Boston University)
Ravi Kumar (Google)
Manish Purohit (Google)
More from the Same Authors
-
2021 Spotlight: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2023 Poster: Mechanic: A Learning Rate Tuner »
Ashok Cutkosky · Aaron Defazio · Harsh Mehta -
2023 Poster: Sparsity-Preserving Differentially Private Training of Large Embedding Models »
Badih Ghazi · Yangsibo Huang · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Amer Sinha · Chiyuan Zhang -
2023 Poster: Unconstrained Dynamic Regret via Sparse Coding »
Zhiyu Zhang · Ashok Cutkosky · Yannis Paschalidis -
2023 Poster: Tight Bounds for Volumetric Spanners and Applications »
Aditya Bhaskara · Sepideh Mahabadi · Ali Vakilian -
2023 Poster: Optimal Unbiased Randomizers for Regression with Label Differential Privacy »
Ashwinkumar Badanidiyuru Varadaraja · Badih Ghazi · Pritish Kamath · Ravi Kumar · Ethan Leeman · Pasin Manurangsi · Avinash V Varadarajan · Chiyuan Zhang -
2023 Poster: Alternation makes the adversary weaker in two-player games »
Volkan Cevher · Ashok Cutkosky · Ali Kavis · Georgios Piliouras · Stratis Skoulakis · Luca Viano -
2023 Poster: On Differentially Private Sampling from Gaussian and Product Distributions »
Badih Ghazi · Xiao Hu · Ravi Kumar · Pasin Manurangsi -
2023 Poster: User-Level Differential Privacy With Few Examples Per User »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
2023 Poster: On Computing Pairwise Statistics with Local Differential Privacy »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Adam Sealfon -
2023 Oral: User-Level Differential Privacy With Few Examples Per User »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
2022 Poster: Optimal Comparator Adaptive Online Learning with Switching Cost »
Zhiyu Zhang · Ashok Cutkosky · Yannis Paschalidis -
2022 Poster: Better SGD using Second-order Momentum »
Hoang Tran · Ashok Cutkosky -
2022 Poster: Momentum Aggregation for Private Non-convex ERM »
Hoang Tran · Ashok Cutkosky -
2022 Poster: Private Isotonic Regression »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Poster: Parameter-free Regret in High Probability with Heavy Tails »
Jiujia Zhang · Ashok Cutkosky -
2022 Poster: Anonymized Histograms in Intermediate Privacy Models »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Poster: Differentially Private Online-to-batch for Smooth Losses »
Qinzi Zhang · Hoang Tran · Ashok Cutkosky -
2021 Oral: High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails »
Ashok Cutkosky · Harsh Mehta -
2021 Poster: High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails »
Ashok Cutkosky · Harsh Mehta -
2021 Poster: Online Selective Classification with Limited Feedback »
Aditya Gangrade · Anil Kag · Ashok Cutkosky · Venkatesh Saligrama -
2021 Poster: User-Level Differentially Private Learning via Correlated Sampling »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2021 Poster: Logarithmic Regret from Sublinear Hints »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2021 Poster: Deep Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang -
2021 Poster: Online Knapsack with Frequency Predictions »
Sungjin Im · Ravi Kumar · Mahshid Montazer Qaem · Manish Purohit -
2020 Poster: Adaptive Probing Policies for Shortest Path Routing »
Aditya Bhaskara · Sreenivas Gollapudi · Kostas Kollias · Kamesh Munagala -
2020 Poster: Better Full-Matrix Regret via Parameter-Free Online Learning »
Ashok Cutkosky -
2020 Poster: Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Ben Moseley · Philip Pham · Sergei Vassilvitskii · Yuyan Wang -
2020 Poster: Online MAP Inference of Determinantal Point Processes »
Aditya Bhaskara · Amin Karbasi · Silvio Lattanzi · Morteza Zadimoghaddam -
2020 Poster: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2020 Poster: Comparator-Adaptive Convex Bandits »
Dirk van der Hoeven · Ashok Cutkosky · Haipeng Luo -
2020 Oral: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2019 : Coffee Break & Poster Session 2 »
Juho Lee · Yoonho Lee · Yee Whye Teh · Raymond A. Yeh · Yuan-Ting Hu · Alex Schwing · Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Christian Bueno · Aditya Sanghi · Pradeep Kumar Jayaraman · Ignacio Arroyo-Fernández · Andrew Hryniowski · Vinayak Mathur · Sanjay Singh · Shahrzad Haddadan · Vasco Portilheiro · Luna Zhang · Mert Yuksekgonul · Jhosimar Arias Figueroa · Deepak Maurya · Balaraman Ravindran · Frank NIELSEN · Philip Pham · Justin Payan · Andrew McCallum · Jinesh Mehta · Ke SUN -
2019 : Contributed Talk - Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Philip Pham -
2019 Poster: On Distributed Averaging for Stochastic k-PCA »
Aditya Bhaskara · Pruthuvi Maheshakya Wijewardena -
2019 Poster: Efficient Rematerialization for Deep Networks »
Ravi Kumar · Manish Purohit · Zoya Svitkina · Erik Vee · Joshua Wang -
2019 Poster: Momentum-Based Variance Reduction in Non-Convex SGD »
Ashok Cutkosky · Francesco Orabona -
2019 Poster: Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration »
Kwang-Sung Jun · Ashok Cutkosky · Francesco Orabona -
2019 Poster: Greedy Sampling for Approximate Clustering in the Presence of Outliers »
Aditya Bhaskara · Sharvaree Vadgama · Hong Xu -
2018 Poster: Mallows Models for Top-k Lists »
Flavio Chierichetti · Anirban Dasgupta · Shahrzad Haddadan · Ravi Kumar · Silvio Lattanzi -
2018 Poster: Distributed Stochastic Optimization via Adaptive SGD »
Ashok Cutkosky · Róbert Busa-Fekete -
2018 Poster: Improving Online Algorithms via ML Predictions »
Manish Purohit · Zoya Svitkina · Ravi Kumar -
2017 Poster: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii -
2017 Poster: Stochastic and Adversarial Online Learning without Hyperparameters »
Ashok Cutkosky · Kwabena A Boahen -
2017 Spotlight: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii -
2016 Poster: Online Convex Optimization with Unconstrained Domains and Losses »
Ashok Cutkosky · Kwabena A Boahen -
2016 Poster: Linear Relaxations for Finding Diverse Elements in Metric Spaces »
Aditya Bhaskara · Mehrdad Ghadiri · Vahab Mirrokni · Ola Svensson -
2014 Poster: Distributed Balanced Clustering via Mapping Coresets »
Mohammadhossein Bateni · Aditya Bhaskara · Silvio Lattanzi · Vahab Mirrokni