
Noise in Classification
This chapter considers the computational and statistical aspects of lear...
read it

Refined bounds for algorithm configuration: The knifeedge of dual class approximability
Automating algorithm configuration is growing increasingly necessary as ...
read it

GeometryAware Gradient Algorithms for Neural Architecture Search
Many recent stateoftheart methods for neural architecture search (NAS...
read it

How much data is sufficient to learn highperforming algorithms?
Algorithms for scientific analysis typically have tunable parameters tha...
read it

Online optimization of piecewise Lipschitz functions in changing environments
In an online optimization problem we are required to choose a sequence o...
read it

Learning to Link
Clustering is an important part of many modern data analysis pipelines, ...
read it

Adaptive GradientBased MetaLearning Methods
We build a theoretical framework for understanding practical metalearni...
read it

Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees
Algorithms typically come with tunable parameters that have a considerab...
read it

Semibandit Optimization in the Dispersed Setting
In this work, we study the problem of online optimization of piecewise L...
read it

Provable Guarantees for GradientBased MetaLearning
We study the problem of metalearning through the lens of online convex ...
read it

Estimating Approximate Incentive Compatibility
In practice, most mechanisms for selling, buying, matching, voting, and ...
read it

Testing Matrix Rank, Optimally
We show that for the problem of testing if a matrix A ∈ F^n × n has rank...
read it

EnvyFree Classification
In classic fair division problems such as cake cutting and rent division...
read it

DataDriven Clustering via Parameterized Lloyd's Families
Algorithms for clustering points in metric spaces is a longstudied area...
read it

Learning to Branch
Tree search algorithms, such as branchandbound, are the most widely us...
read it

Optimal Sample Complexity for Matrix Completion and Related Problems via ℓ_2Regularization
We study the strong duality of nonconvex matrix factorization: we show ...
read it

SConcave Distributions: Towards Broader Distributions for NoiseTolerant and SampleEfficient Learning Algorithms
We provide new results concerning noisetolerant and sampleefficient le...
read it

LearningTheoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
Maxcut, clustering, and many other partitioning problems that are of si...
read it

An Improved GapDependency Analysis of the Noisy Power Method
We consider the noisy power method algorithm, which has wide application...
read it

Active Learning Algorithms for Graphical Model Selection
The problem of learning the structure of a high dimensional graphical mo...
read it

Data Driven Resource Allocation for Distributed Learning
In distributed machine learning, data is dispatched to multiple machines...
read it

Communication Efficient Distributed Agnostic Boosting
We consider the problem of learning from distributed data in the agnosti...
read it

Efficient Clustering with Limited Distance Information
Given a point set S and an unknown metric d on S, we study the problem o...
read it

Scalable Kernel Methods via Doubly Stochastic Gradients
The general perception is that kernel methods are not scalable, and neur...
read it

A Distributed FrankWolfe Algorithm for CommunicationEfficient Sparse Learning
Learning sparse combinations is a frequent theme in machine learning. In...
read it

Budgeted Influence Maximization for Multiple Products
The typical algorithmic problem in viral marketing aims to identify a se...
read it

The Power of Localization for Efficiently Learning Linear Separators with Noise
We introduce a new approach for designing computationally efficient lear...
read it

Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy
We describe a framework for designing efficient active learning algorith...
read it

Distributed kMeans and kMedian Clustering on General Topologies
This paper provides new algorithms for distributed clustering for two po...
read it

Active and passive learning of linear separators under logconcave distributions
We provide new results concerning label efficient, polynomial time, pass...
read it

Learning Valuation Functions
In this paper we study the approximate learnability of valuations common...
read it
MariaFlorina Balcan
is this you? claim profile
Associate Professor, School of Computer Science, Carnegie Mellon University