Borja Balle

ICLR Conference 2025 Conference Paper

DiSK: Differentially Private Optimizer with Simplified Kalman Filter for Noise Reduction

• Xinwei Zhang 0001
• Zhiqi Bu
• Borja Balle
• Mingyi Hong 0001
• Meisam Razaviyayn
• Vahab Mirrokni

Differential privacy (DP) offers a robust framework for safeguarding individual data privacy. To utilize DP in training modern machine learning models, differentially private optimizers have been widely used in recent years. A popular approach to privatize an optimizer is to clip the individual gradients and add sufficiently large noise to the clipped gradient. This approach led to the development of DP optimizers that have comparable performance with their non-private counterparts in fine-tuning tasks or in tasks with a small number of training parameters. However, a significant performance drop is observed when these optimizers are applied to large-scale training. This degradation stems from the substantial noise injection required to maintain DP, which disrupts the optimizer's dynamics. This paper introduces DiSK, a novel framework designed to significantly enhance the performance of DP optimizers. DiSK employs Kalman filtering, a technique drawn from control and signal processing, to effectively denoise privatized gradients and generate progressively refined gradient estimations. To ensure practicality for large-scale training, we simplify the Kalman filtering process, minimizing its memory and computational demands. We establish theoretical privacy-utility trade-off guarantees for DiSK, and demonstrate provable improvements over standard DP optimizers like DPSGD in terms of iteration complexity upper-bound. Extensive experiments across diverse tasks, including vision tasks such as CIFAR-100 and ImageNet-1k and language fine-tuning tasks such as GLUE, E2E, and DART, validate the effectiveness of DiSK. The results showcase its ability to significantly improve the performance of DP optimizers, surpassing state-of-the-art results under the same privacy constraints on several benchmarks.

TMLR Journal 2025 Journal Article

Preserving Expert-Level Privacy in Offline Reinforcement Learning

• Navodita Sharma
• Vishnu Vinod
• Abhradeep Guha Thakurta
• Alekh Agarwal
• Borja Balle
• Christoph Dann
• Aravindan Raghuveer

The offline reinforcement learning (RL) problem aims to learn an optimal policy from historical data collected by one or more behavioural policies (experts) by interacting with an environment. However, the individual experts may be privacy-sensitive in that the learnt policy may retain information about their precise choices. In some domains like personalized retrieval, advertising and healthcare, the expert choices are considered sensitive data. To provably protect the privacy of such experts, we propose a novel consensus-based expert-level differentially private offline RL training approach compatible with any existing offline RL algorithm. We prove rigorous differential privacy guarantees, while maintaining strong empirical performance. Unlike existing work in differentially private RL, we supplement the theory with proof-of-concept experiments on classic RL environments featuring large continuous state spaces, demonstrating substantial improvements over a natural baseline across multiple tasks.

TMLR Journal 2025 Journal Article

Privacy Awareness for Information-Sharing Assistants: A Case-study on Form-filling with Contextual Integrity

• Sahra Ghalebikesabi
• Eugene Bagdasarian
• Ren Yi
• Itay Yona
• Ilia Shumailov
• Aneesh Pappu
• Chongyang Shi
• Laura Weidinger

Advanced AI assistants combine frontier LLMs and tool access to autonomously perform complex tasks on behalf of users. While the helpfulness of such assistants can increase dramatically with access to user information including emails and documents, this raises privacy concerns about assistants sharing inappropriate information with third parties without user supervision. To steer information-sharing assistants to behave in accordance with privacy expectations, we propose to operationalize the design of privacy-conscious assistants that conform with *contextual integrity* (CI), a framework that equates privacy with the appropriate flow of information in a given context. In particular, we design and evaluate a number of strategies to steer assistants' information-sharing actions to be CI compliant. Our evaluation is based on a novel form filling benchmark composed of human annotations of common webform applications, and it reveals that prompting frontier LLMs to perform CI-based reasoning yields strong results.

ICML Conference 2025 Conference Paper

Scaling Laws for Differentially Private Language Models

• Ryan McKenna
• Yangsibo Huang
• Amer Sinha
• Borja Balle
• Zachary Charles
• Christopher A. Choquette-Choo
• Badih Ghazi
• Georgios Kaissis

Scaling laws have emerged as important components of large language model (LLM) training as they can predict performance gains through scale, and provide guidance on important hyper-parameter choices that would otherwise be expensive. LLMs also rely on large, high-quality training datasets, like those sourced from (sometimes sensitive) user data. Training models on this sensitive user data requires careful privacy protections like differential privacy (DP). However, the dynamics of DP training are significantly different, and consequently their scaling laws are not yet fully understood. In this work, we establish scaling laws that accurately model the intricacies of DP LLM training, providing a complete picture of the compute-privacy-utility and the optimal training configurations in many settings.

ICLR Conference 2025 Conference Paper

The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD

• Milad Nasr
• Thomas Steinke 0002
• Borja Balle
• Christopher A. Choquette-Choo
• Arun Ganesh
• Matthew Jagielski
• Jamie Hayes
• Abhradeep Thakurta

We propose a simple heuristic privacy analysis of noisy clipped stochastic gradient descent (DP-SGD) in the setting where only the last iterate is released and the intermediate iterates remain hidden. Namely, our heuristic assumes a linear structure for the model. We show experimentally that our heuristic is predictive of the outcome of privacy auditing applied to various training procedures. Thus it can be used prior to training as a rough estimate of the final privacy leakage. We also probe the limitations of our heuristic by providing some artificial counterexamples where it underestimates the privacy leakage. The standard composition-based privacy analysis of DP-SGD effectively assumes that the adversary has access to all intermediate iterates, which is often unrealistic. However, this analysis remains the state of the art in practice. While our heuristic does not replace a rigorous privacy analysis, it illustrates the large gap between the best theoretical upper bounds and the privacy auditing lower bounds and sets a target for further work to improve the theoretical privacy analyses.

NeurIPS Conference 2025 Conference Paper

Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy

• Bogdan Kulynych
• Juan Gomez
• Georgios Kaissis
• Jamie Hayes
• Borja Balle
• Flavio Calmon
• Jean Raisaro

Differentially private (DP) mechanisms are difficult to interpret and calibrate because existing methods for mapping standard privacy parameters to concrete privacy risks—re-identification, attribute inference, and data reconstruction—are both overly pessimistic and inconsistent. In this work, we use the hypothesis-testing interpretation of DP ($f$-DP), and determine that bounds on attack success can take the same unified form across re-identification, attribute inference, and data reconstruction risks. Our unified bounds are (1) consistent across a multitude of attack settings, and (2) tunable, enabling practitioners to evaluate risk with respect to arbitrary, including worst-case, levels of baseline risk. Empirically, our results are tighter than prior methods using $\varepsilon$-DP, R\'enyi DP, and concentrated DP. As a result, calibrating noise using our bounds can reduce the required noise by 20% at the same risk level, which yields, e. g. , an accuracy increase from 52% to 70% in a text classification task. Overall, this unifying perspective provides a principled framework for interpreting and calibrating the degree of protection in DP against specific levels of re-identification, attribute inference, or data reconstruction risk.

ICML Conference 2024 Conference Paper

Beyond the Calibration Point: Mechanism Comparison in Differential Privacy

• Georgios Kaissis
• Stefan Kolek
• Borja Balle
• Jamie Hayes
• Daniel Rueckert

In differentially private (DP) machine learning, the privacy guarantees of DP mechanisms are often reported and compared on the basis of a single $(\varepsilon, \delta)$-pair. This practice overlooks that DP guarantees can vary substantially even between mechanisms sharing a given $(\varepsilon, \delta)$, and potentially introduces privacy vulnerabilities which can remain undetected. This motivates the need for robust, rigorous methods for comparing DP guarantees in such cases. Here, we introduce the $\Delta$-divergence between mechanisms which quantifies the worst-case excess privacy vulnerability of choosing one mechanism over another in terms of $(\varepsilon, \delta)$, $f$-DP and in terms of a newly presented Bayesian interpretation. Moreover, as a generalisation of the Blackwell theorem, it is endowed with strong decision-theoretic foundations. Through application examples, we show that our techniques can facilitate informed decision-making and reveal gaps in the current understanding of privacy risks, as current practices in DP-SGD often result in choosing mechanisms with high excess privacy vulnerabilities.

NeurIPS Conference 2023 Conference Paper

Bounding training data reconstruction in DP-SGD

• Jamie Hayes
• Borja Balle
• Saeed Mahloujifar

Differentially private training offers a protection which is usually interpreted as a guarantee against membership inference attacks. By proxy, this guarantee extends to other threats like reconstruction attacks attempting to extract complete training examples. Recent works provide evidence that if one does not need to protect against membership attacks but instead only wants to protect against a training data reconstruction, then utility of private models can be improved because less noise is required to protect against these more ambitious attacks. We investigate this question further in the context of DP-SGD, a standard algorithm for private deep learning, and provide an upper bound on the success of any reconstruction attack against DP-SGD together with an attack that empirically matches the predictions of our bound. Together, these two results open the door to fine-grained investigations on how to set the privacy parameters of DP-SGD in practice to protect against reconstruction attacks. Finally, we use our methods to demonstrate that different settings of the DP-SGD parameters leading to same DP guarantees can results in significantly different success rates for reconstruction, indicating that the DP guarantee alone might not be a good proxy for controlling the protection against reconstruction attacks.

UAI Conference 2023 Conference Paper

Mnemonist: Locating Model Parameters that Memorize Training Examples

• Ali Shahin Shamsabadi
• Jamie Hayes
• Borja Balle
• Adrian Weller

Recent work has shown that an adversary can reconstruct training examples given access to the parameters of a deep learning image classification model. We show that the quality of reconstruction depends heavily on the type of activation functions used. In particular, we show that ReLU activations lead to much lower quality reconstructions compared to smooth activation functions. We explore if this phenomenon is a fundamental property of models with ReLU activations, or if it is a weakness of current attack strategies. We first study the training dynamics of small MLPs with ReLU activations and identify redundant model parameters that do not memorise training examples. Building on this, we propose our Mnemonist method, which is able to detect redundant model parameters, and then guide current attacks to focus on informative parameters to improve the quality of reconstructions of training examples from ReLU models.

I&C Journal 2022 Journal Article

Approximate minimization of weighted tree automata

• Borja Balle
• Guillaume Rabusseau

This paper studies the following approximate minimization problem: given a minimal weighted tree automaton A with n states recognizing a weighted tree language f, can we construct a smaller automaton A ˆ with n ˆ < n states recognizing a language f ˆ that is a good approximation of f? The corresponding problem for weighted automata on strings was recently studied by Balle et al. [16, 15], where the authors introduced a new canonical form for weighted automata called singular value automata inspired by spectral methods, and showed that truncating such canonical form yields a solution for the problem satisfying a certain approximation criteria. In this paper we take a similar approach and show that in the tree case one can obtain an analogous canonical form that we call singular value tree automata, and use it to study the approximate minimization problem for weighted tree automata. We first establish the existence of this canonical form for weighted tree automata and then provide bounds on the quality of the resulting approximation method based on truncation. We also study the problem of computing the canonical form given a minimal weighted tree automaton and show that in the tree case this task is considerably more complicated than in the string case. In particular, computing the canonical form reduces to solving a system of polynomial equations. By further reducing this problem to the computation of generalized partition functions for weighted tree automata, we propose and analyze two methods for computing the canonical form based on iterative methods: fixed point iteration and Newton's method. Our analysis of Newton's method unveils a connection between iterative methods and sequences of sets of trees satisfying a certain technical condition that might be of independent interest.

I&C Journal 2022 Journal Article

Bisimulation metrics and norms for real-weighted automata

• Borja Balle
• Pascale Gourdeau
• Prakash Panangaden

We develop a new bisimulation (pseudo)metric for weighted finite automata (WFA) that generalizes Boreale's linear bisimulation relation. Our metrics are induced by seminorms on the state space of WFA. Our development is based on spectral properties of sets of linear operators. In particular, the joint spectral radius of the transition matrices of WFA plays a central role. We also study continuity properties of the bisimulation pseudometric, establish an undecidability result for computing the metric, and give a preliminary account of applications to spectral learning of weighted automata.

ICLR Conference 2020 Conference Paper

A Framework for robustness Certification of Smoothed Classifiers using F-Divergences

• Krishnamurthy Dvijotham
• Jamie Hayes
• Borja Balle
• J. Zico Kolter
• Chongli Qin
• András György 0001
• Kai Xiao
• Sven Gowal

Formal verification techniques that compute provable guarantees on properties of machine learning models, like robustness to norm-bounded adversarial perturbations, have yielded impressive results. Although most techniques developed so far require knowledge of the architecture of the machine learning model and remain hard to scale to complex prediction pipelines, the method of randomized smoothing has been shown to overcome many of these obstacles. By requiring only black-box access to the underlying model, randomized smoothing scales to large architectures and is agnostic to the internals of the network. However, past work on randomized smoothing has focused on restricted classes of smoothing measures or perturbations (like Gaussian or discrete) and has only been able to prove robustness with respect to simple norm bounds. In this paper we introduce a general framework for proving robustness properties of smoothed machine learning models in the black-box setting. Specifically, we extend randomized smoothing procedures to handle arbitrary smoothing measures and prove robustness of the smoothed classifier by using f-divergences. Our methodology improves upon the state of the art in terms of computation time or certified robustness on several image classification tasks and an audio classification task, with respect to several classes of adversarial perturbations.

NeurIPS Conference 2020 Conference Paper

Privacy Amplification via Random Check-Ins

• Borja Balle
• Peter Kairouz
• Brendan McMahan
• Om Thakkar
• Abhradeep Guha Thakurta

Differentially Private Stochastic Gradient Descent (DP-SGD) forms a fundamental building block in many applications for learning over sensitive data. Two standard approaches, privacy amplification by subsampling, and privacy amplification by shuffling, permit adding lower noise in DP-SGD than via na\"{\i}ve schemes. A key assumption in both these approaches is that the elements in the data set can be uniformly sampled, or be uniformly permuted --- constraints that may become prohibitive when the data is processed in a decentralized or distributed fashion. In this paper, we focus on conducting iterative methods like DP-SGD in the setting of federated learning (FL) wherein the data is distributed among many devices (clients). Our main contribution is the \emph{random check-in} distributed protocol, which crucially relies only on randomized participation decisions made locally and independently by each client. It has privacy/accuracy trade-offs similar to privacy amplification by subsampling/shuffling. However, our method does not require server-initiated communication, or even knowledge of the population size. To our knowledge, this is the first privacy amplification tailored for a distributed learning framework, and it may have broader applicability beyond FL. Along the way, we improve the privacy guarantees of amplification by shuffling and show that, in practical regimes, this improvement allows for similar privacy and utility using data from an order of magnitude fewer users.

ICML Conference 2020 Conference Paper

Private Reinforcement Learning with PAC and Regret Guarantees

• Giuseppe Vietri
• Borja Balle
• Akshay Krishnamurthy
• Zhiwei Steven Wu

Motivated by high-stakes decision-making domains like personalized medicine where user information is inherently sensitive, we design privacy preserving exploration policies for episodic reinforcement learning (RL). We first provide a meaningful privacy formulation using the notion of joint differential privacy (JDP)–a strong variant of differential privacy for settings where each user receives their own sets of output (e. g. , policy recommendations). We then develop a private optimism-based learning algorithm that simultaneously achieves strong PAC and regret bounds, and enjoys a JDP guarantee. Our algorithm only pays for a moderate privacy cost on exploration: in comparison to the non-private bounds, the privacy parameter only appears in lower-order terms. Finally, we present lower bounds on sample complexity and regret for reinforcement learning subject to JDP.

NeurIPS Conference 2019 Conference Paper

Privacy Amplification by Mixing and Diffusion Mechanisms

• Borja Balle
• Gilles Barthe
• Marco Gaboardi
• Joseph Geumlek

A fundamental result in differential privacy states that the privacy guarantees of a mechanism are preserved by any post-processing of its output. In this paper we investigate under what conditions stochastic post-processing can amplify the privacy of a mechanism. By interpreting post-processing as the application of a Markov operator, we first give a series of amplification results in terms of uniform mixing properties of the Markov process defined by said operator. Next we provide amplification bounds in terms of coupling arguments which can be applied in cases where uniform mixing is not available. Finally, we introduce a new family of mechanisms based on diffusion processes which are closed under post-processing, and analyze their privacy via a novel heat flow argument. On the applied side, we generalize the analysis of "privacy amplification by iteration" in Noisy SGD and show it admits an exponential improvement in the strongly convex case, and study a mechanism based on the Ornstein–Uhlenbeck diffusion process which contains the Gaussian mechanism with optimal post-processing on bounded inputs as a special case.

TCS Journal 2018 Journal Article

Generalization bounds for learning weighted automata

• Borja Balle
• Mehryar Mohri

This paper studies the problem of learning weighted automata from a finite sample of strings with real-valued labels. We consider several hypothesis classes of weighted automata defined in terms of three different measures: the norm of an automaton's weights, the norm of the function computed by an automaton, and the norm of the corresponding Hankel matrix. We present new data-dependent generalization guarantees for learning weighted automata expressed in terms of the Rademacher complexity of these classes. We further present upper bounds on these Rademacher complexities, which reveal key new data-dependent terms related to the complexity of learning weighted automata.

ICML Conference 2018 Conference Paper

Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising

• Borja Balle
• Yu-Xiang Wang 0003

The Gaussian mechanism is an essential building block used in multitude of differentially private data analysis algorithms. In this paper we revisit the Gaussian mechanism and show that the original analysis has several important limitations. Our analysis reveals that the variance formula for the original mechanism is far from tight in the high privacy regime ($\varepsilon \to 0$) and it cannot be extended to the low privacy regime ($\varepsilon \to \infty$). We address these limitations by developing an optimal Gaussian mechanism whose variance is calibrated directly using the Gaussian cumulative density function instead of a tail bound approximation. We also propose to equip the Gaussian mechanism with a post-processing step based on adaptive estimation techniques by leveraging that the distribution of the perturbation is known. Our experiments show that analytical calibration removes at least a third of the variance of the noise compared to the classical Gaussian mechanism, and that denoising dramatically improves the accuracy of the Gaussian mechanism in the high-dimensional regime.

AAAI Conference 2018 Conference Paper

Learning Predictive State Representations From Non-Uniform Sampling

• Yuri Grinberg
• Hossein Aboutalebi
• Melanie Lyman-Abramovitch
• Borja Balle
• Doina Precup

Predictive state representations (PSR) have emerged as a powerful method for modelling partially observable environments. PSR learning algorithms can build models for predicting all observable variables, or predicting only some of them conditioned on others (e. g. , actions or exogenous variables). In the latter case, which we call conditional modelling, the accuracy of different estimates of the conditional probabilities for a fixed dataset can vary significantly, due to the limited sampling of certain conditions. This can have negative consequences on the PSR parameter estimation process, which are not taken into account by the current state-of-theart PSR spectral learning algorithms. In this paper, we examine closely conditional modelling within the PSR framework. We first establish a new positive but surprisingly non-trivial result: a conditional model can never be larger than the complete model. Then, we address the core shortcoming of existing PSR spectral learning methods for conditional models by incorporating an additional step in the process, which can be seen as a type of matrix denoising. We further refine this objective by adding penalty terms for violations of the system dynamics matrix structure, which improves the PSR predictive performance. Empirical evaluations on both synthetic and real datasets highlight the advantages of the proposed approach.

NeurIPS Conference 2018 Conference Paper

Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences

• Borja Balle
• Gilles Barthe
• Marco Gaboardi

Differential privacy comes equipped with multiple analytical tools for the design of private data analyses. One important tool is the so-called "privacy amplification by subsampling" principle, which ensures that a differentially private mechanism run on a random subsample of a population provides higher privacy guarantees than when run on the entire population. Several instances of this principle have been studied for different random subsampling methods, each with an ad-hoc analysis. In this paper we present a general method that recovers and improves prior analyses, yields lower bounds and derives new instances of privacy amplification by subsampling. Our method leverages a characterization of differential privacy as a divergence which emerged in the program verification community. Furthermore, it introduces new tools, including advanced joint convexity and privacy profiles, which might be of independent interest.

NeurIPS Conference 2017 Conference Paper

Hierarchical Methods of Moments

• Matteo Ruffini
• Guillaume Rabusseau
• Borja Balle

Spectral methods of moments provide a powerful tool for learning the parameters of latent variable models. Despite their theoretical appeal, the applicability of these methods to real data is still limited due to a lack of robustness to model misspecification. In this paper we present a hierarchical approach to methods of moments to circumvent such limitations. Our method is based on replacing the tensor decomposition step used in previous algorithms with approximate joint diagonalization. Experiments on topic modeling show that our method outperforms previous tensor decomposition methods in terms of speed and model quality.

Highlights Conference 2017 Conference Abstract

Learning Automata with Hankel Matrices

• Borja Balle

The Hankel matrix is a fundamental tool in the theory of weighted automata. In this talk we will describe a general framework for learning automata with Hankel matrices. Our framework provides a unified view of many classical and recent algorithms for learning automata under different learning paradigms, including query learning algorithms, spectral learning algorithms, and Hankel matrix completion algorithms.

NeurIPS Conference 2017 Conference Paper

Multitask Spectral Learning of Weighted Automata

• Guillaume Rabusseau
• Borja Balle
• Joelle Pineau

We consider the problem of estimating multiple related functions computed by weighted automata~(WFA). We first present a natural notion of relatedness between WFAs by considering to which extent several WFAs can share a common underlying representation. We then introduce the model of vector-valued WFA which conveniently helps us formalize this notion of relatedness. Finally, we propose a spectral learning algorithm for vector-valued WFAs to tackle the multitask learning problem. By jointly learning multiple tasks in the form of a vector-valued WFA, our algorithm enforces the discovery of a representation space shared between tasks. The benefits of the proposed multitask approach are theoretically motivated and showcased through experiments on both synthetic and real world datasets.

ICML Conference 2017 Conference Paper

Spectral Learning from a Single Trajectory under Finite-State Policies

• Borja Balle
• Odalric-Ambrym Maillard

We present spectral methods of moments for learning sequential models from a single trajectory, in stark contrast with the classical literature that assumes the availability of multiple i. i. d. trajectories. Our approach leverages an efficient SVD-based learning algorithm for weighted automata and provides the first rigorous analysis for learning many important models using dependent data. We state and analyze the algorithm under three increasingly difficult scenarios: probabilistic automata, stochastic weighted automata, and reactive predictive state representations controlled by a finite-state policy. Our proofs include novel tools for studying mixing properties of stochastic weighted automata.

ICML Conference 2016 Conference Paper

Differentially Private Policy Evaluation

• Borja Balle
• Maziar Gomrokchi
• Doina Precup

We present the first differentially private algorithms for reinforcement learning, which apply to the task of evaluating a fixed policy. We establish two approaches for achieving differential privacy, provide a theoretical analysis of the privacy and utility of the two algorithms, and show promising results on simple empirical examples.

IJCAI Conference 2016 Conference Paper

Learning Multi-Step Predictive State Representations

• Lucas Langer
• Borja Balle
• Doina Precup

Recent years have seen the development of efficient and provably correct spectral algorithms for learning models of partially observable environments arising in many applications. But despite the high hopes raised by this new class of algorithms, their practical impact is still below expectations. One reason for this is the difficulty in adapting spectral methods to exploit structural constraints about different target environments which can be known beforehand. A natural structure intrinsic to many dynamical systems is a multi-resolution behaviour where interesting phenomena occur at different time scales during the evolution of the system. In this paper we introduce the multi-step predictive state representation (M-PSR) and an associated learning algorithm that finds and leverages frequent patterns of observations at multiple scales in dynamical systems with discrete observations. We perform experiments on robot exploration tasks in a wide variety of environments and conclude that the use of M-PSRs improves over the classical PSR for varying amounts of data, environment sizes, and number of observations symbols.

ICRA Conference 2016 Conference Paper

Learning time series models for pedestrian motion prediction

• Chenghui Zhou
• Borja Balle
• Joelle Pineau

Robot systems deployed in real-world environments often need to interact with other dynamic objects, such as pedestrians, cars, bicycles or other vehicles. In such cases, it is useful to have a good predictive model of the object's motion to factor in when optimizing the robot's own behaviour. In this paper we consider motion models cast in the Predictive Linear Gaussian (PLG) model, and propose two learning approaches for this framework: one based on the method of moments and the other on a least-squares criteria. We evaluate the approaches on several synthetic datasets, and deploy the system on a wheelchair robot, to improve its ability to follow a walking companion.

AAAI Conference 2016 Conference Paper

Multitask Generalized Eigenvalue Program

• Boyu Wang
• Joelle Pineau
• Borja Balle

We present a novel multitask learning framework called multitask generalized eigenvalue program (MTGEP), which jointly solves multiple related generalized eigenvalue problems (GEPs). This framework is quite general and can be applied to many eigenvalue problems in machine learning and pattern recognition, ranging from supervised learning to unsupervised learning, such as principal component analysis (PCA), Fisher discriminant analysis (FDA), common spatial pattern (CSP), and so on. The core assumption of our approach is that the leading eigenvectors of related GEPs lie in some subspace that can be approximated by a sparse linear combination of basis vectors. As a result, these GEPs can be jointly solved by a sparse coding approach. Empirical evaluation with both synthetic and benchmark real world datasets validates the efficacy and efficiency of the proposed techniques, especially for grouped multitask GEPs.

RLDM Conference 2015 Conference Abstract

Learning and Planning with Timing Information in Markov Decision Processes

• Pierre-Luc Bacon
• Borja Balle
• Doina Precup

We consider the problem of learning and planning in Markov decision processes with temporally extended actions rep-resented in the options framework. We propose to use predictions about the duration of extended actions to represent the state and show that this leads to a compact predictive state representation model independent of the set of primitive actions. Then we develop a consistent and efficient spectral learning algorithm for such models. Using just the timing information to represent states allows for faster improvement in the planning performance. We illustrate our approach with experiments in both synthetic and robot navigation domains.

UAI Conference 2015 Conference Paper

Learning and Planning with Timing Information in Markov Decision Processes

• Pierre-Luc Bacon
• Borja Balle
• Doina Precup

We consider the problem of learning and planning in Markov decision processes with temporally extended actions represented in the options framework. We propose to use predictions about the duration of extended actions to represent the state and show that this leads to a compact predictive state representation model independent of the set of primitive actions. Then we develop a consistent and efficient spectral learning algorithm for such models. Using just the timing information to represent states allows for faster improvement in the planning performance. We illustrate our approach with experiments in both synthetic and robot navigation domains.

ICML Conference 2014 Conference Paper

Methods of Moments for Learning Stochastic Languages: Unified Presentation and Empirical Comparison

• Borja Balle
• William L. Hamilton
• Joelle Pineau

Probabilistic latent-variable models are a powerful tool for modelling structured data. However, traditional expectation-maximization methods of learning such models are both computationally expensive and prone to local-minima. In contrast to these traditional methods, recently developed learning algorithms based upon the method of moments are both computationally efficient and provide strong statistical guarantees. In this work, we provide a unified presentation and empirical comparison of three general moment-based methods in the context of modelling stochastic languages. By rephrasing these methods upon a common theoretical ground, introducing novel theoretical results where necessary, we provide a clear comparison, making explicit the statistical assumptions upon which each method relies. With this theoretical grounding, we then provide an in-depth empirical analysis of the methods on both real and synthetic data with the goal of elucidating performance trends and highlighting important implementation details.

ICML Conference 2014 Conference Paper

Spectral Regularization for Max-Margin Sequence Tagging

• Ariadna Quattoni
• Borja Balle
• Xavier Carreras
• Amir Globerson

We frame max-margin learning of latent variable structured prediction models as a convex optimization problem, making use of scoring functions computed by input-output observable operator models. This learning problem can be expressed as an optimization involving a low-rank Hankel matrix that represents the input-output operator model. The direct outcome of our work is a new spectral regularization method for max-margin structured prediction. Our experiments confirm that our proposed regularization framework leads to an effective way of controlling the capacity of structured prediction models.

TCS Journal 2013 Journal Article

Learning probabilistic automata: A study in state distinguishability

• Borja Balle
• Jorge Castro
• Ricard Gavaldà

Known algorithms for learning PDFA can only be shown to run in time polynomial in the so-called distinguishability μ of the target machine, besides the number of states and the usual accuracy and confidence parameters. We show that the dependence on μ is necessary in the worst case for every algorithm whose structure resembles existing ones. As a technical tool, a new variant of Statistical Queries termed L ∞ -queries is defined. We show how to simulate L ∞ -queries using classical Statistical Queries and show that known PAC algorithms for learning PDFA are in fact statistical query algorithms. Our results include a lower bound: every algorithm to learn PDFA with queries using a reasonable tolerance must make Ω ( 1 / μ 1 − c ) queries for every c > 0. Finally, an adaptive algorithm that PAC-learns w. r. t. another measure of complexity is described. This yields better efficiency in many cases, while retaining the same inevitable worst-case behavior. Our algorithm requires fewer input parameters than previously existing ones, and has a better sample bound.

ICML Conference 2012 Conference Paper

Local Loss Optimization in Operator Models: A New Insight into Spectral Learning

• Borja Balle
• Ariadna Quattoni
• Xavier Carreras

NeurIPS Conference 2012 Conference Paper

Spectral Learning of General Weighted Automata via Constrained Matrix Completion

• Borja Balle
• Mehryar Mohri

Many tasks in text and speech processing and computational biology require es- timating functions mapping strings to real numbers. A broad class of such func- tions can be defined by weighted automata. Spectral methods based on the sin- gular value decomposition of a Hankel matrix have been recently proposed for learning a probability distribution represented by a weighted automaton from a training sample drawn according to this same target distribution. In this paper, we show how spectral methods can be extended to the problem of learning a general weighted automaton from a sample generated by an arbitrary distribution. The main obstruction to this approach is that, in general, some entries of the Hankel matrix may be missing. We present a solution to this problem based on solving a constrained matrix completion problem. Combining these two ingredients, matrix completion and spectral method, a whole new family of algorithms for learning general weighted automata is obtained. We present generalization bounds for a particular algorithm in this family. The proofs rely on a joint stability analysis of matrix completion and spectral learning.