Satyen Kale
Google Research
Publications
Filter by type:
Sort by year:
Stochastic Negative Mining for Learning with Large Output Spaces
ConferenceProceedings of 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019
Escaping Saddle Points with Adaptive Gradient Methods
ConferenceProceedings of 36th International Conference on Machine Learning (ICML), 2019
Online Learning of Quantum States
ConferenceProceedings of 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), 2018
On the convergence of Adam and Beyond
ConferenceProceedings of 6th International Conference on Learning Representations (ICLR), 2018
Loss Decomposition for Fast Learning in Large Output Spaces
ConferenceProceedings of 35th International Conference on Machine Learning (ICML), 2018
Logistic Regression: The Importance of Being Improper
ConferenceProceedings of 31st Conference on Learning Theory (COLT), 2018
Adaptive Methods for Nonconvex Optimization
ConferenceProceedings of 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), 2018
Parameter-Free Online Learning via Model Selection
ConferenceProceedings of 31st Annual Conference on Neural Information Processing Systems (NeurIPS), 2017
Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP
ConferenceProceedings of 34th International Conference on Machine Learning (ICML), 2017
Online Sparse Linear Regression
ConferenceProceedings of 29th Conference on Learning Theory (COLT), 2016
Online Semidefinite Programming
ConferenceProceedings of 43rd International Colloquium on Automata, Languages and Programming (ICALP), 2016
Hardness of Online Sleeping Combinatorial Optimization Problems.
ConferenceProceedings of 30th Annual Conference on Neural Information Processing Systems (NeurIPS), 2016
Optimal and Adaptive Algorithms for Online Boosting
ConferenceProceedings of 32nd International Conference on Machine Learning (ICML), 2015
Online Gradient Boosting
ConferenceProceedings of 29th Annual Conference on Neural Information Processing Systems (NeurIPS), 2015
Budgeted Prediction With Expert Advice
ConferenceProceedings of 29th AAAI Conference on Artificial Intelligence (AAAI), 2015
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
ConferenceProceedings of 31st International Conference on Machine Learning (ICML), 2014
Multiarmed Bandits With Limited Expert Advice
ConferenceProceedings of 27th Conference on Learning Theory (COLT), 2014
The Approximability of the Binary Paintshop Problem
ConferenceProceedings of 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2013
Bargaining for Revenue Shares on Tree Trading Networks
ConferenceProceedings of 23rd International Conference on Artificial Intelligence (IJCAI), 2013
Adaptive Market Making via Online Learning
ConferenceProceedings of 27th Annual Conference on Neural Information Processing Systems (NeurIPS), 2013
The Multiplicative Weights Update Method: A Meta-Algorithm and Applications
JournalIn Theory of Computing , 2012
Projection-free Online Learning
ConferenceProceedings of 29th International Conference on Machine Learning (ICML), 2012
Near-Optimal Algorithms for Online Matrix Prediction
ConferenceJournalIn SIAM Journal on Computing (SICOMP), 2017. Proceedings of 25th Conference on Learning Theory (COLT), 2012
Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
ConferenceProceedings of 29th International Conference on Machine Learning (ICML), 2012
Contextual Bandit Learning with Predictable Rewards
ConferenceProceedings of 15th International Conference on Artificial Intelligence and Statistics (AISTATS), 2012
Who Moderates the Moderators? Crowdsourcing Abuse Detection in User-generated Content
ConferenceProceedings of 12th ACM Conference on Electronic Commerce (EC), 2011
Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction
ConferenceProceedings of 27th Annual Conference on Neural Information Processing Systems (NeurIPS), 2011
Efficient optimal learning for contextual bandits
ConferenceProceedings of 27th Conference on Uncertainty in Artificial Intelligence (UAI), 2011
Cross-Validation and Mean-Square Stability
ConferenceProceedings of 2nd Symposium on Innovations in Computer Science (ICS), 2011
Combinatorial Approximation Algorithms for MaxCut using Random Walks
ConferenceProceedings of 2nd Symposium on Innovations in Computer Science (ICS), 2011
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization
ConferenceJournalIn Journal of Machine Learning Research (JMLR), 2014. Also in proceedings of 24th Conference on Learning Theory (COLT), 2011
Non-Stochastic Bandit Slate Problems
ConferenceProceedings of 24th Annual Conference on Neural Information Processing Systems (NeurIPS), 2010
Learning rotations with little regret
ConferenceJournalIn Machine Learning Journal (MLJ), (2016). Also in proceedings of 23rd Conference on Learning Theory (COLT), 2010. Corrigendum to conference version, 2010
The Uniform Hardcore Lemma via Approximate Bregman Projections
ConferenceTech ReportAppeared as ECCC Report TR07-131 and in proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009
Online Submodular Minimization
ConferenceJournalIn Journal of Machine Learning Research (JMLR), 2012. Also in proceedings of 23rd Annual Conference on Neural Information Processing Systems (NeurIPS), 2009
Better Algorithms for Benign Bandits
ConferenceJournalIn Journal of Machine Learning Research (JMLR), 2011. Also in proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009
An online portfolio selection algorithm with regret logarithmic in price variation
ConferenceJournalIn Mathematical Finance, 2012. Originally appeared as "On Stochastic and Worst-case Models for Investing" in proceedings of 23rd Annual Conference on Neural Information Processing Systems (NeurIPS), 2009
Noise Tolerance of Expanders and Sublinear Expander Reconstruction
ConferenceJournalIn SIAM Journal on Computing (SICOMP), 2014. Also in proceedings of 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008
Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs
ConferenceJournalIn Machine Learning Journal (MLJ), 2010. Also in proceedings of 21st Conference on Learning Theory (COLT), 2008
An Expansion Tester for Bounded Degree Graphs
ConferenceJournalTech ReportIn SIAM Journal on Computing (SICOMP), 2011. Also appeared as ECCC Report TR07-131 and in proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP), 2008
Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release
ConferenceProceedings of 26th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2007
Efficient Algorithms using the Multiplicative Weights Update Method
Tech ReportPh.D. thesis. Princeton Tech Report TR-804-07, 2007
Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria
ConferenceProceedings of 21st Annual Conference on Neural Information Processing Systems (NeurIPS), 2007
A Combinatorial, Primal-Dual approach to Semidefinite Programs
ConferenceJournalIn Journal of the ACM, 2016. Also in proceedings of 39th ACM Symposium on Theory of Computing (STOC), 2007
Logarithmic Regret Algorithms for Online Convex Optimization
ConferenceJournalIn Machine Learning Journal (MLJ), 2007. An earlier version with Adam Kalai appeared in proceedings of 19th Conference on Learning Theory (COLT), 2006
Efficient Aggregation Algorithms for Probabilistic Data
ConferenceProceedings of 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006
Algorithms for Portfolio Management based on the Newton Method
ConferenceProceedings of 23rd International Conference on Machine Learning (ICML), 2006
A Variation on SVD Based Image Compression
ConferenceJournalIn Image and Vision Computing, 2007. In proceedings of 3rd Workshop on Computer Vision, Graphics, and Image Processing (WCVGIP), 2006
A Fast Random Sampling Algorithm for Sparsifying Matrices
ConferenceProceedings of 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2006
Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update method
ConferenceProceedings of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005
Analysis and Algorithms for Content-based Event Matching
ConferenceProceedings of 4th International Workshop on Distributed Event-Based Systems (DEBS), 2005
Approximating Quadratic Programs with Positive Semidefinite Constraints
Tech ReportPrinceton Tech Report TR-746-06, 2004
\(O(\sqrt{\log n})\) approximation to SPARSEST CUT in \(\tilde{O}(n^2)\) time
ConferenceJournalIn SIAM Journal on Computing (SICOMP), 2010. Also in proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004