Maria-Florina Balcan

research

∙ 07/05/2023

Meta-Learning Adversarial Bandit Algorithms

We study online meta-learning with bandit feedback, with the goal of imp...

0 Mikhail Khodak, et al. ∙

research

∙ 04/06/2023

Reliable Learning for Test-time Attacks and Distribution Shift

Machine learning algorithms are often used in environments which are not...

0 Maria-Florina Balcan, et al. ∙

research

∙ 03/25/2023

Learning with Explanation Constraints

While supervised learning assumes the presence of labeled data, we may h...

0 Rattana Pukdee, et al. ∙

research

∙ 02/28/2023

Bicriteria Multidimensional Mechanism Design with Side Information

We develop a versatile new methodology for multidimensional mechanism de...

0 Maria-Florina Balcan, et al. ∙

research

∙ 02/22/2023

Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs

We study learnability of two important classes of mechanisms, menus of l...

0 Maria-Florina Balcan, et al. ∙

research

∙ 10/07/2022

Label Propagation with Weak Supervision

Semi-supervised learning and weakly supervised learning are important pa...

0 Rattana Pukdee, et al. ∙

research

∙ 07/20/2022

Provably tuning the ElasticNet across instances

An important unresolved challenge in the theory of regularization is to ...

0 Maria-Florina Balcan, et al. ∙

research

∙ 05/27/2022

Meta-Learning Adversarial Bandits

We study online learning with bandit feedback across multiple tasks, wit...

0 Maria-Florina Balcan, et al. ∙

research

∙ 04/15/2022

Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

The incorporation of cutting planes within the branch-and-bound algorith...

0 Maria-Florina Balcan, et al. ∙

research

∙ 04/07/2022

Faster algorithms for learning to link, align sequences, and price two-part tariffs

Data-driven algorithm configuration is a promising, learning-based appro...

0 Maria-Florina Balcan, et al. ∙

research

∙ 03/08/2022

Robustly-reliable learners under poisoning attacks

Data poisoning attacks, in which an adversary corrupts a training set wi...

1 Maria-Florina Balcan, et al. ∙

research

∙ 02/18/2022

Learning Predictions for Algorithms with Predictions

A burgeoning paradigm in algorithm design is the field of algorithms wit...

0 Mikhail Khodak, et al. ∙

research

∙ 11/18/2021

Improved Learning Bounds for Branch-and-Cut

Branch-and-cut is the most widely used algorithm for solving integer pro...

0 Maria-Florina Balcan, et al. ∙

research

∙ 08/19/2021

Learning-to-learn non-convex piecewise-Lipschitz functions

We analyze the meta-learning of the initialization and step-size of lear...

0 Maria-Florina Balcan, et al. ∙

research

∙ 06/08/2021

Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing

Tuning hyperparameters is a crucial but arduous part of the machine lear...

0 Mikhail Khodak, et al. ∙

research

∙ 06/08/2021

Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond

Cutting-plane methods have enabled remarkable successes in integer progr...

0 Maria-Florina Balcan, et al. ∙

research

∙ 03/18/2021

Data driven algorithms for limited labeled data learning

We consider a novel data driven approach for designing learning algorith...

0 Maria-Florina Balcan, et al. ∙

research

∙ 12/24/2020

Generalization in portfolio-based algorithm selection

Portfolio-based algorithm selection has seen tremendous practical succes...

0 Maria-Florina Balcan, et al. ∙

research

∙ 12/19/2020

Scalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning

This paper introduces the first provably accurate algorithms for differe...

0 Kaiwen Wang, et al. ∙

research

∙ 11/14/2020

Data-driven Algorithm Design

Data driven algorithm design is an important aspect of modern data scien...

0 Maria-Florina Balcan, et al. ∙

research

∙ 10/10/2020

Noise in Classification

This chapter considers the computational and statistical aspects of lear...

0 Maria-Florina Balcan, et al. ∙

research

∙ 06/21/2020

Refined bounds for algorithm configuration: The knife-edge of dual class approximability

Automating algorithm configuration is growing increasingly necessary as ...

0 Maria-Florina Balcan, et al. ∙

research

∙ 04/16/2020

Geometry-Aware Gradient Algorithms for Neural Architecture Search

Many recent state-of-the-art methods for neural architecture search (NAS...

23 Liam Li, et al. ∙

research

∙ 08/08/2019

How much data is sufficient to learn high-performing algorithms?

Algorithms for scientific analysis typically have tunable parameters tha...

0 Maria-Florina Balcan, et al. ∙

research

∙ 07/22/2019

Online optimization of piecewise Lipschitz functions in changing environments

In an online optimization problem we are required to choose a sequence o...

0 Maria-Florina Balcan, et al. ∙

research

∙ 07/01/2019

Learning to Link

Clustering is an important part of many modern data analysis pipelines, ...

0 Maria-Florina Balcan, et al. ∙

research

∙ 06/06/2019

Adaptive Gradient-Based Meta-Learning Methods

We build a theoretical framework for understanding practical meta-learni...

0 Mikhail Khodak, et al. ∙

research

∙ 05/26/2019

Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees

Algorithms typically come with tunable parameters that have a considerab...

0 Maria-Florina Balcan, et al. ∙

research

∙ 04/18/2019

Semi-bandit Optimization in the Dispersed Setting

In this work, we study the problem of online optimization of piecewise L...

0 Maria-Florina Balcan, et al. ∙

research

∙ 02/27/2019

Provable Guarantees for Gradient-Based Meta-Learning

We study the problem of meta-learning through the lens of online convex ...

14 Mikhail Khodak, et al. ∙

research

∙ 02/25/2019

Estimating Approximate Incentive Compatibility

In practice, most mechanisms for selling, buying, matching, voting, and ...

0 Maria-Florina Balcan, et al. ∙

research

∙ 10/18/2018

Testing Matrix Rank, Optimally

We show that for the problem of testing if a matrix A ∈ F^n × n has rank...

0 Maria-Florina Balcan, et al. ∙

research

∙ 09/23/2018

Envy-Free Classification

In classic fair division problems such as cake cutting and rent division...

0 Maria-Florina Balcan, et al. ∙

research

∙ 09/19/2018

Data-Driven Clustering via Parameterized Lloyd's Families

Algorithms for clustering points in metric spaces is a long-studied area...

0 Maria-Florina Balcan, et al. ∙

research

∙ 03/27/2018

Learning to Branch

Tree search algorithms, such as branch-and-bound, are the most widely us...

0 Maria-Florina Balcan, et al. ∙

research

∙ 04/27/2017

Optimal Sample Complexity for Matrix Completion and Related Problems via ℓ_2-Regularization

We study the strong duality of non-convex matrix factorization: we show ...

0 Maria-Florina Balcan, et al. ∙

research

∙ 03/22/2017

S-Concave Distributions: Towards Broader Distributions for Noise-Tolerant and Sample-Efficient Learning Algorithms

We provide new results concerning noise-tolerant and sample-efficient le...

0 Maria-Florina Balcan, et al. ∙

research

∙ 11/14/2016

Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems

Max-cut, clustering, and many other partitioning problems that are of si...

0 Maria-Florina Balcan, et al. ∙

research

∙ 02/23/2016

An Improved Gap-Dependency Analysis of the Noisy Power Method

We consider the noisy power method algorithm, which has wide application...

0 Maria-Florina Balcan, et al. ∙

research

∙ 02/01/2016

Active Learning Algorithms for Graphical Model Selection

The problem of learning the structure of a high dimensional graphical mo...

0 Gautam Dasarathy, et al. ∙

research

∙ 12/15/2015

Data Driven Resource Allocation for Distributed Learning

In distributed machine learning, data is dispatched to multiple machines...

0 Travis Dick, et al. ∙

research

∙ 06/21/2015

Communication Efficient Distributed Agnostic Boosting

We consider the problem of learning from distributed data in the agnosti...

0 Shang-Tse Chen, et al. ∙

research

∙ 08/09/2014

Efficient Clustering with Limited Distance Information

Given a point set S and an unknown metric d on S, we study the problem o...

0 Konstantin Voevodski, et al. ∙

research

∙ 07/21/2014

Scalable Kernel Methods via Doubly Stochastic Gradients

The general perception is that kernel methods are not scalable, and neur...

0 Bo Dai, et al. ∙

research

∙ 04/09/2014

A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning

Learning sparse combinations is a frequent theme in machine learning. In...

0 Aurélien Bellet, et al. ∙

research

∙ 12/08/2013

Budgeted Influence Maximization for Multiple Products

The typical algorithmic problem in viral marketing aims to identify a se...

0 Nan Du, et al. ∙

research

∙ 07/31/2013

The Power of Localization for Efficiently Learning Linear Separators with Noise

We introduce a new approach for designing computationally efficient lear...

0 Pranjal Awasthi, et al. ∙

research

∙ 07/11/2013

Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy

We describe a framework for designing efficient active learning algorith...

0 Maria-Florina Balcan, et al. ∙

research

∙ 06/03/2013

Distributed k-Means and k-Median Clustering on General Topologies

This paper provides new algorithms for distributed clustering for two po...

0 Maria-Florina Balcan, et al. ∙

research

∙ 11/06/2012

Active and passive learning of linear separators under log-concave distributions

We provide new results concerning label efficient, polynomial time, pass...

0 Maria-Florina Balcan, et al. ∙

Maria-Florina Balcan

Featured Co-authors