mtybilly/Instruct2DS huggingface dataset:
Hindsight Learning for MDPs with Exogenous Inputs
Authors: Sinclair, Sean R. and Vieira Frujeri, Felipe and Cheng, Ching-An and Marshall, Luke and Barbalho, Hugo De Oliveira and Li, Jingling and Neville, Jennifer and Menache, Ishai and Swaminathan, Adith
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Many resource management problems require sequential decision-making under uncertainty, where the only uncertainty affecting the decision outcomes are exogenous variables outside the control of the decision-maker. We model these problems as Exo-MDPs (Markov Decision Processes with Exogenous Inputs) and design a class of data-efficient algorithms for them termed Hindsight Learning (HL). Our HL algorithms achieve data efficiency by leveraging a key insight: having samples of the exogenous variables, past decisions can be revisited in hindsight to infer counterfactual consequences that can accelerate policy improvements. We compare HL against classic baselines in the multi-secretary and airline revenue management problems. We also scale our algorithms to a business-critical cloud resource management problem – allocating Virtual Machines (VMs) to physical machines, and simulate their performance with real datasets from a large public cloud provider. We find that HL algorithms outperform domain-specific heuristics, as well as state-of-the-art reinforcement learning methods.
Text-To-4D Dynamic Scene Generation
Authors: Singer, Uriel and Sheynin, Shelly and Polyak, Adam and Ashual, Oron and Makarov, Iurii and Kokkinos, Filippos and Goyal, Naman and Vedaldi, Andrea and Parikh, Devi and Johnson, Justin and Taigman, Yaniv
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: We present MAV3D (Make-A-Video3D), a method for generating three-dimensional dynamic scenes from text descriptions. Our approach uses a 4D dynamic Neural Radiance Field (NeRF), which is optimized for scene appearance, density, and motion consistency by querying a Text-to-Video (T2V) diffusion-based model. The dynamic video output generated from the provided text can be viewed from any camera location and angle, and can be composited into any 3D environment. MAV3D does not require any 3D or 4D data and the T2V model is trained only on Text-Image pairs and unlabeled videos. We demonstrate the effectiveness of our approach using comprehensive quantitative and qualitative experiments and show an improvement over previously established internal baselines. To the best of our knowledge, our method is the first to generate 3D dynamic scenes given a text description. Generated samples can be viewed at make-a-video3d.github.io
The Hessian perspective into the Nature of Convolutional Neural Networks
Authors: Singh, Sidak Pal and Hofmann, Thomas and Schölkopf, Bernhard
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: While Convolutional Neural Networks (CNNs) have long been investigated and applied, as well as theorized, we aim to provide a slightly different perspective into their nature — through the perspective of their Hessian maps. The reason is that the loss Hessian captures the pairwise interaction of parameters and therefore forms a natural ground to probe how the architectural aspects of CNNs get manifested in their structure and properties. We develop a framework relying on Toeplitz representation of CNNs, and then utilize it to reveal the Hessian structure and, in particular, its rank. We prove tight upper bounds (with linear activations), which closely follow the empirical trend of the Hessian rank and in practice also hold for more general settings. Overall, our work generalizes and further establishes the key insight that the Hessian rank grows as the square root of the number of parameters, even in CNNs.
When do Minimax-fair Learning and Empirical Risk Minimization Coincide?
Authors: Singh, Harvineet and Kleindessner, Matthäus and Cevher, Volkan and Chunara, Rumi and Russell, Chris
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Minimax-fair machine learning minimizes the error for the worst-off group. However, empirical evidence suggests that when sophisticated models are trained with standard empirical risk minimization (ERM), they often have the same performance on the worst-off group as a minimax-trained model. Our work makes this counter-intuitive observation concrete. We prove that if the hypothesis class is sufficiently expressive and the group information is recoverable from the features, ERM and minimax-fairness learning formulations indeed have the same performance on the worst-off group. We provide additional empirical evidence of how this observation holds on a wide range of datasets and hypothesis classes. Since ERM is fundamentally easier than minimax optimization, our findings have implications on the practice of fair machine learning.
Differentiable Simulations for Enhanced Sampling of Rare Events
Authors: Sipka, Martin and Dietschreit, Johannes C. B. and Grajciar, Lukáš and Gomez-Bombarelli, Rafael
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Simulating rare events, such as the transformation of a reactant into a product in a chemical reaction typically requires enhanced sampling techniques that rely on heuristically chosen collective variables (CVs). We propose using differentiable simulations (DiffSim) for the discovery and enhanced sampling of chemical transformations without a need to resort to preselected CVs, using only a distance metric. Reaction path discovery and estimation of the biasing potential that enhances the sampling are merged into a single end-to-end problem that is solved by path-integral optimization. This is achieved by introducing multiple improvements over standard DiffSim such as partial backpropagation and graph mini-batching making DiffSim training stable and efficient. The potential of DiffSim is demonstrated in the successful discovery of transition paths for the Muller-Brown model potential as well as a benchmark chemical system - alanine dipeptide.
Preprocessors Matter! Realistic Decision-Based Attacks on Machine Learning Systems
Authors: Sitawarin, Chawin and Tramèr, Florian and Carlini, Nicholas
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Decision-based attacks construct adversarial examples against a machine learning (ML) model by making only hard-label queries. These attacks have mainly been applied directly to standalone neural networks. However, in practice, ML models are just one component of a larger learning system. We find that by adding a single preprocessor in front of a classifier, state-of-the-art query-based attacks are up to seven× less effective at attacking a prediction pipeline than at attacking the model alone. We explain this discrepancy by the fact that most preprocessors introduce some notion of invariance to the input space. Hence, attacks that are unaware of this invariance inevitably waste a large number of queries to re-discover or overcome it. We, therefore, develop techniques to (i) reverse-engineer the preprocessor and then (ii) use this extracted information to attack the end-to-end system. Our preprocessors extraction method requires only a few hundred queries, and our preprocessor-aware attacks recover the same efficacy as when attacking the model alone. The code can be found at https://github.com/google-research/preprocessor-aware-black-box-attack.
Invariance in Policy Optimisation and Partial Identifiability in Reward Learning
Authors: Skalse, Joar Max Viktor and Farrugia-Roberts, Matthew and Russell, Stuart and Abate, Alessandro and Gleave, Adam
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: It is often very challenging to manually design reward functions for complex, real-world tasks. To solve this, one can instead use reward learning to infer a reward function from data. However, there are often multiple reward functions that fit the data equally well, even in the infinite-data limit. This means that the reward function is only partially identifiable. In this work, we formally characterise the partial identifiability of the reward function given several popular reward learning data sources, including expert demonstrations and trajectory comparisons. We also analyse the impact of this partial identifiability for several downstream tasks, such as policy optimisation. We unify our results in a framework for comparing data sources and downstream tasks by their invariances, with implications for the design and selection of data sources for reward learning.
A Game-Theoretic Framework for Managing Risk in Multi-Agent Systems
Authors: Slumbers, Oliver and Mguni, David Henry and Blumberg, Stefano B and Mcaleer, Stephen Marcus and Yang, Yaodong and Wang, Jun
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: In order for agents in multi-agent systems (MAS) to be safe, they need to take into account the risks posed by the actions of other agents. However, the dominant paradigm in game theory (GT) assumes that agents are not affected by risk from other agents and only strive to maximise their expected utility. For example, in hybrid human-AI driving systems, it is necessary to limit large deviations in reward resulting from car crashes. Although there are equilibrium concepts in game theory that take into account risk aversion, they either assume that agents are risk-neutral with respect to the uncertainty caused by the actions of other agents, or they are not guaranteed to exist. We introduce a new GT-based Risk-Averse Equilibrium (RAE) that always produces a solution that minimises the potential variance in reward accounting for the strategy of other agents. Theoretically and empirically, we show RAE shares many properties with a Nash Equilibrium (NE), establishing convergence properties and generalising to risk-dominant NE in certain cases. To tackle large-scale problems, we extend RAE to the PSRO multi-agent reinforcement learning (MARL) framework. We empirically demonstrate the minimum reward variance benefits of RAE in matrix games with high-risk outcomes. Results on MARL experiments show RAE generalises to risk-dominant NE in a trust dilemma game and that it reduces instances of crashing by 7x in an autonomous driving setting versus the best performing baseline.
On the Effectiveness of Offline RL for Dialogue Response Generation
Authors: Sodhi, Paloma and Wu, Felix and Elenberg, Ethan R. and Weinberger, Kilian Q and Mcdonald, Ryan
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: A common training technique for language models is teacher forcing (TF). TF attempts to match human language exactly, even though identical meanings can be expressed in different ways. This motivates use of sequence-level objectives for dialogue response generation. In this paper, we study the efficacy of various offline reinforcement learning (RL) methods to maximize such objectives. We present a comprehensive evaluation across multiple datasets, models, and metrics. Offline RL shows a clear performance improvement over teacher forcing while not inducing training instability or sacrificing practical training budgets.
Fair Densities via Boosting the Sufficient Statistics of Exponential Families
Authors: Soen, Alexander and Husain, Hisham and Nock, Richard
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: We introduce a boosting algorithm to pre-process data for fairness. Starting from an initial fair but inaccurate distribution, our approach shifts towards better data fitting while still ensuring a minimal fairness guarantee. To do so, it learns the sufficient statistics of an exponential family with boosting-compliant convergence. Importantly, we are able to theoretically prove that the learned distribution will have a representation rate and statistical rate data fairness guarantee. Unlike recent optimization based pre-processing methods, our approach can be easily adapted for continuous domain features. Furthermore, when the weak learners are specified to be decision trees, the sufficient statistics of the learned distribution can be examined to provide clues on sources of (un)fairness. Empirical results are present to display the quality of result on real-world data.
The Dormant Neuron Phenomenon in Deep Reinforcement Learning
Authors: Sokar, Ghada and Agarwal, Rishabh and Castro, Pablo Samuel and Evci, Utku
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: In this work we identify the dormant neuron phenomenon in deep reinforcement learning, where an agent’s network suffers from an increasing number of inactive neurons, thereby affecting network expressivity. We demonstrate the presence of this phenomenon across a variety of algorithms and environments, and highlight its effect on learning. To address this issue, we propose a simple and effective method (ReDo) that Recycles Dormant neurons throughout training. Our experiments demonstrate that ReDo maintains the expressive power of networks by reducing the number of dormant neurons and results in improved performance.
Abstracting Imperfect Information Away from Two-Player Zero-Sum Games
Authors: Sokota, Samuel and D'Orazio, Ryan and Ling, Chun Kai and Wu, David J and Kolter, J Zico and Brown, Noam
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: In their seminal work, Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This insight underpins sound solvers and decision-time planning algorithms for common-payoff games. Unfortunately, a naive application of the same insight to two-player zero-sum games fails because Nash equilibria of the game with public policy announcements may not correspond to Nash equilibria of the original game. As a consequence, existing sound decision-time planning algorithms require complicated additional mechanisms that have unappealing properties. The main contribution of this work is showing that certain regularized equilibria do not possess the aforementioned non-correspondence problem—thus, computing them can be treated as perfect-information problems. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games and yields a simplified framework for decision-time planning in two-player zero-sum games, void of the unappealing properties that plague existing decision-time planning approaches.
Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization
Authors: Son, Jiwoo and Kim, Minsu and Kim, Hyeonah and Park, Jinkyoo
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: This paper proposes Meta-SAGE, a novel approach for improving the scalability of deep reinforcement learning models for combinatorial optimization (CO) tasks. Our method adapts pre-trained models to larger-scale problems in test time by suggesting two components: a scale meta-learner (SML) and scheduled adaptation with guided exploration (SAGE). First, SML transforms the context embedding for subsequent adaptation of SAGE based on scale information. Then, SAGE adjusts the model parameters dedicated to the context embedding for a specific instance. SAGE introduces locality bias, which encourages selecting nearby locations to determine the next location. The locality bias gradually decays as the model is adapted to the target instance. Results show that Meta-SAGE outperforms previous adaptation methods and significantly improves scalability in representative CO tasks. Our source code is available at https://github.com/kaist-silab/meta-sage.
Consistency Models
Authors: Song, Yang and Dhariwal, Prafulla and Chen, Mark and Sutskever, Ilya
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Diffusion models have significantly advanced the fields of image, audio, and video generation, but they depend on an iterative sampling process that causes slow generation. To overcome this limitation, we propose consistency models, a new family of models that generate high quality samples by directly mapping noise to data. They support fast one-step generation by design, while still allowing multistep sampling to trade compute for sample quality. They also support zero-shot data editing, such as image inpainting, colorization, and super-resolution, without requiring explicit training on these tasks. Consistency models can be trained either by distilling pre-trained diffusion models, or as standalone generative models altogether. Through extensive experiments, we demonstrate that they outperform existing distillation techniques for diffusion models in one- and few-step sampling, achieving the new state-of-the-art FID of 3.55 on CIFAR-10 and 6.20 on ImageNet 64x64 for one-step generation. When trained in isolation, consistency models become a new family of generative models that can outperform existing one-step, non-adversarial generative models on standard benchmarks such as CIFAR-10, ImageNet 64x64 and LSUN 256x256.
LipsNet: A Smooth and Robust Neural Network with Adaptive Lipschitz Constant for High Accuracy Optimal Control
Authors: Song, Xujie and Duan, Jingliang and Wang, Wenxuan and Li, Shengbo Eben and Chen, Chen and Cheng, Bo and Zhang, Bo and Wei, Junqing and Wang, Xiaoming Simon
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Deep reinforcement learning (RL) is a powerful approach for solving optimal control problems. However, RL-trained policies often suffer from the action fluctuation problem, where the consecutive actions significantly differ despite only slight state variations. This problem results in mechanical components’ wear and tear and poses safety hazards. The action fluctuation is caused by the high Lipschitz constant of actor networks. To address this problem, we propose a neural network named LipsNet. We propose the Multi-dimensional Gradient Normalization (MGN) method, to constrain the Lipschitz constant of networks with multi-dimensional input and output. Benefiting from MGN, LipsNet achieves Lipschitz continuity, allowing smooth actions while preserving control performance by adjusting Lipschitz constant. LipsNet addresses the action fluctuation problem at network level rather than algorithm level, which can serve as actor networks in most RL algorithms, making it more flexible and user-friendly than previous works. Experiments demonstrate that LipsNet has good landscape smoothness and noise robustness, resulting in significantly smoother action compared to the Multilayer Perceptron.
Deep Perturbation Learning: Enhancing the Network Performance via Image Perturbations
Authors: Song, Zifan and Gong, Xiao and Hu, Guosheng and Zhao, Cairong
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Image perturbation technique is widely used to generate adversarial examples to attack networks, greatly decreasing the performance of networks. Unlike the existing works, in this paper, we introduce a novel framework Deep Perturbation Learning (DPL), the new insights into understanding image perturbations, to enhance the performance of networks rather than decrease the performance. Specifically, we learn image perturbations to amend the data distribution of training set to improve the performance of networks. This optimization w.r.t data distribution is non-trivial. To approach this, we tactfully construct a differentiable optimization target w.r.t. image perturbations via minimizing the empirical risk. Then we propose an alternating optimization of the network weights and perturbations. DPL can easily be adapted to a wide spectrum of downstream tasks and backbone networks. Extensive experiments demonstrate the effectiveness of our DPL on 6 datasets (CIFAR-10, CIFAR100, ImageNet, MS-COCO, PASCAL VOC, and SBD) over 3 popular vision tasks (image classification, object detection, and semantic segmentation) with different backbone architectures (e.g., ResNet, MobileNet, and ViT).
Latent Traversals in Generative Models as Potential Flows
Authors: Song, Yue and Keller, T. Anderson and Sebe, Nicu and Welling, Max
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Despite the significant recent progress in deep generative models, the underlying structure of their latent spaces is still poorly understood, thereby making the task of performing semantically meaningful latent traversals an open research challenge. Most prior work has aimed to solve this challenge by modeling latent structures linearly, and finding corresponding linear directions which result in ‘disentangled’ generations. In this work, we instead propose to model latent structures with a learned dynamic potential landscape, thereby performing latent traversals as the flow of samples down the landscape’s gradient. Inspired by physics, optimal transport, and neuroscience, these potential landscapes are learned as physically realistic partial differential equations, thereby allowing them to flexibly vary over both space and time. To achieve disentanglement, multiple potentials are learned simultaneously, and are constrained by a classifier to be distinct and semantically self-consistent. Experimentally, we demonstrate that our method achieves both more qualitatively and quantitatively disentangled trajectories than state-of-the-art baselines. Further, we demonstrate that our method can be integrated as a regularization term during training, thereby acting as an inductive bias towards the learning of structured representations, ultimately improving model likelihood on similarly structured data. Code is available at https://github.com/KingJamesSong/PDETraversal.
FedAvg Converges to Zero Training Loss Linearly for Overparameterized Multi-Layer Neural Networks
Authors: Song, Bingqing and Khanduri, Prashant and Zhang, Xinwei and Yi, Jinfeng and Hong, Mingyi
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Federated Learning (FL) is a distributed learning paradigm that allows multiple clients to learn a joint model by utilizing privately held data at each client. Significant research efforts have been devoted to develop advanced algorithms that deal with the situation where the data at individual clients have heterogeneous distributions. In this work, we show that data heterogeneity can be dealt from a different perspective. That is, by utilizing a certain overparameterized multi-layer neural network at each client, even the vanilla FedAvg (a.k.a. the Local SGD) algorithm can accurately optimize the training problem: When each client has a neural network with one wide layer of size $N$ (where $N$ is the number of total training samples), followed by layers of smaller widths, FedAvg converges linearly to a solution that achieves (almost) zero training loss, without requiring any assumptions on the clients’ data distributions. To our knowledge, this is the first work that demonstrates such resilience to data heterogeneity for FedAvg when trained on multi-layer neural networks. Our experiments also confirm that, neural networks of large size can achieve better and more stable performance for FL problems.
RGE: A Repulsive Graph Rectification for Node Classification via Influence
Authors: Song, Jaeyun and Kim, Sungyub and Yang, Eunho
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: In real-world graphs, noisy connections are inevitable, which makes it difficult to obtain unbiased node representations. Among various attempts to resolve this problem, a method of estimating the counterfactual effects of these connectivities has recently attracted attention, which mainly uses influence functions for single graph elements (i.e., node and edge). However, in this paper, we argue that there is a strongly interacting group effect between the influences of graph elements due to their connectivity. In the same vein, we observe that edge groups connecting to the same train node exhibit significant differences in their influences, hence no matter how negative each is, removing them at once may have a rather negative effect as a group. Based on this motivation, we propose a new edge-removing strategy, Repulsive edge Group Elimination (RGE), that preferentially removes edges with no interference in groups. Empirically, we demonstrate that RGE consistently outperforms existing methods on the various benchmark datasets.
Importance Weighted Expectation-Maximization for Protein Sequence Design
Authors: Song, Zhenqiao and Li, Lei
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Designing protein sequences with desired biological function is crucial in biology and chemistry. Recent machine learning methods use a surrogate sequence-function model to replace the expensive wet-lab validation. How can we efficiently generate diverse and novel protein sequences with high fitness? In this paper, we propose IsEM-Pro, an approach to generate protein sequences towards a given fitness criterion. At its core, IsEM-Pro is a latent generative model, augmented by combinatorial structure features from a separately learned Markov random fields (MRFs). We develop an Monte Carlo Expectation-Maximization method (MCEM) to learn the model. During inference, sampling from its latent space enhances diversity while its MRFs features guide the exploration in high fitness regions. Experiments on eight protein sequence design tasks show that our IsEM-Pro outperforms the previous best methods by at least 55% on average fitness score and generates more diverse and novel protein sequences.
Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability
Authors: Song, Zhao and Wang, Yitan and Yu, Zheng and Zhang, Lichen
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Sketching is one of the most fundamental tools in large-scale machine learning. It enables runtime and memory saving via randomly compressing the original large problem into lower dimensions. In this paper, we propose a novel sketching scheme for the first order method in large-scale distributed learning setting, such that the communication costs between distributed agents are saved while the convergence of the algorithms is still guaranteed. Given gradient information in a high dimension $d$, the agent passes the compressed information processed by a sketching matrix $Rın ℝ^s\times d$ with $słl d$, and the receiver de-compressed via the de-sketching matrix $R^⊤$ to “recover” the information in original dimension. Using such a framework, we develop algorithms for federated learning with lower communication costs. However, such random sketching does not protect the privacy of local data directly. We show that the gradient leakage problem still exists after applying the sketching technique by presenting a specific gradient attack method. As a remedy, we prove rigorously that the algorithm will be differentially private by adding additional random noises in gradient information, which results in a both communication-efficient and differentially private first order approach for federated learning tasks. Our sketching scheme can be further generalized to other learning settings and might be of independent interest itself.
Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
Authors: Song, Zhao and Yang, Xin and Yang, Yuanyuan and Zhang, Lichen
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Projection maintenance is one of the core data structure tasks. Efficient data structures for projection maintenance have led to recent breakthroughs in many convex programming algorithms. In this work, we further extend this framework to the Kronecker product structure. Given a constraint matrix $\sf A$ and a positive semi-definite matrix $Wın ℝ^n\times n$ with a sparse eigenbasis, we consider the task of maintaining the projection in the form of $\sf B^⊤(\sf B\sf B^⊤)^-1\sf B$, where $\sf B=\sf A(Wøtimes I)$ or $\sf B=\sf A(W^1/2øtimes W^1/2)$. At each iteration, the weight matrix $W$ receives a low rank change and we receive a new vector $h$. The goal is to maintain the projection matrix and answer the query $\sf B^⊤(\sf B\sf B^⊤)^-1\sf Bh$ with good approximation guarantees. We design a fast dynamic data structure for this task and it is robust against an adaptive adversary. Following the beautiful and pioneering work of [Beimel, Kaplan, Mansour, Nissim, Saranurak and Stemmer, STOC’22], we use tools from differential privacy to reduce the randomness required by the data structure and further improve the running time.
A Nearly-Optimal Bound for Fast Regression with $\ell_∞$ Guarantee
Authors: Song, Zhao and Ye, Mingquan and Yin, Junze and Zhang, Lichen
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Given a matrix $Aın ℝ^n\times d$ and a vector $bın ℝ^n$, we consider the regression problem with $\ell_ınfty$ guarantees: finding a vector $x’ın ℝ^d$ such that $||x’-x^* ||_ınfty łeq \fracε\sqrtd· ||Ax^*-b||_2· ||A^\dagger||$ with $x^*$ being the optimal solution to the regression $||Ax-b||_2$. One popular approach for solving $\ell_2$ regression problem is via sketching: picking a structured random matrix $Sın ℝ^m\times n$ with $młl n$ and $SA$ can be quickly computed, solve the “sketched” regression problem $x’=\mathrmargmin ||SAx-Sb||_2$. In this paper, we show that in order to obtain such $\ell_ınfty$ guarantee for $\ell_2$ regression, one has to use sketching matrices that are <em>dense</em>. To the best of our knowledge, this is the first user case in which dense sketching matrices are necessary. On the algorithmic side, we prove that, there exists a distribution of dense sketching matrices with $m=ε^-2dłog^3(n/δ)$ such that solving the sketched regression problem gives the $\ell_ınfty$ guarantee, with probability at least $1-δ$. Moreover, the matrix $SA$ can be computed in time $O(ndłog n)$. Our row count is nearly-optimal up to logarithmic factors, and significantly improves the result in [Price, Song and Woodruff, ICALP’17], in which $m=Ømega(ε^-2d^1+γ)$ for $γın (0, 1)$ is required. Moreover, we develop a novel analytical framework for $\ell_ınfty$ guarantee regression that utilizes the <em>Oblivious Coordinate-wise Embedding</em> (OCE) property introduced in [Song and Yu, ICML’21]. Our analysis is much simpler and more general than that of [Price, Song and Woodruff, ICALP’17]. Leveraging this framework, we extend the $\ell_ınfty$ guarantee regression result to dense sketching matrices for computing fast tensor product of vectors.
Loss-Guided Diffusion Models for Plug-and-Play Controllable Generation
Authors: Song, Jiaming and Zhang, Qinsheng and Yin, Hongxu and Mardani, Morteza and Liu, Ming-Yu and Kautz, Jan and Chen, Yongxin and Vahdat, Arash
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: We consider guiding denoising diffusion models with general differentiable loss functions in a plug-and-play fashion, enabling controllable generation without additional training. This paradigm, termed Loss-Guided Diffusion (LGD), can easily be integrated into all diffusion models and leverage various efficient samplers. Despite the benefits, the resulting guidance term is, unfortunately, an intractable integral and needs to be approximated. Existing methods compute the guidance term based on a point estimate. However, we show that such approaches have significant errors over the scale of the approximations. To address this issue, we propose a Monte Carlo method that uses multiple samples from a suitable distribution to reduce bias. Our method is effective in various synthetic and real-world settings, including image super-resolution, text or label-conditional image generation, and controllable motion synthesis. Notably, we show how our method can be applied to control a pretrained motion diffusion model to follow certain paths and avoid obstacles that are proven challenging to prior methods.
Differentiable Tree Operations Promote Compositional Generalization
Authors: Soulos, Paul and Hu, Edward J and Mccurdy, Kate and Chen, Yunmo and Fernandez, Roland and Smolensky, Paul and Gao, Jianfeng
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: In the context of structure-to-structure transformation tasks, learning sequences of discrete symbolic operations poses significant challenges due to their non-differentiability. To facilitate the learning of these symbolic sequences, we introduce a differentiable tree interpreter that compiles high-level symbolic tree operations into subsymbolic matrix operations on tensors. We present a novel Differentiable Tree Machine (DTM) architecture that integrates our interpreter with an external memory and an agent that learns to sequentially select tree operations to execute the target transformation in an end-to-end manner. With respect to out-of-distribution compositional generalization on synthetic semantic parsing and language generation tasks, DTM achieves 100% while existing baselines such as Transformer, Tree Transformer, LSTM, and Tree2Tree LSTM achieve less than 30%. DTM remains highly interpretable in addition to its perfect performance.
Are labels informative in semi-supervised learning? Estimating and leveraging the missing-data mechanism.
Authors: Sportisse, Aude and Schmutz, Hugo and Humbert, Olivier and Bouveyron, Charles and Mattei, Pierre-Alexandre
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Semi-supervised learning is a powerful technique for leveraging unlabeled data to improve machine learning models, but it can be affected by the presence of “informative" labels, which occur when some classes are more likely to be labeled than others. In the missing data literature, such labels are called missing not at random. In this paper, we propose a novel approach to address this issue by estimating the missing-data mechanism and using inverse propensity weighting to debias any SSL algorithm, including those using data augmentation. We also propose a likelihood ratio test to assess whether or not labels are indeed informative. Finally, we demonstrate the performance of the proposed methods on different datasets, in particular on two medical datasets for which we design pseudo-realistic missing data scenarios.
Linear Causal Disentanglement via Interventions
Authors: Squires, Chandler and Seigal, Anna and Bhate, Salil S and Uhler, Caroline
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Causal disentanglement seeks a representation of data involving latent variables that are related via a causal model. A representation is identifiable if both the latent model and the transformation from latent to observed variables are unique. In this paper, we study observed variables that are a linear transformation of a linear latent causal model. Data from interventions are necessary for identifiability: if one latent variable is missing an intervention, we show that there exist distinct models that cannot be distinguished. Conversely, we show that a single intervention on each latent variable is sufficient for identifiability. Our proof uses a generalization of the RQ decomposition of a matrix that replaces the usual orthogonal and upper triangular conditions with analogues depending on a partial order on the rows of the matrix, with partial order determined by a latent causal model. We corroborate our theoretical results with a method for causal disentanglement. We show that the method accurately recovers a latent causal model on synthetic and semi-synthetic data and we illustrate a use case on a dataset of single-cell RNA sequencing measurements.
Generating Language Corrections for Teaching Physical Control Tasks
Authors: Srivastava, Megha and Goodman, Noah and Sadigh, Dorsa
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: AI assistance continues to help advance applications in education, from language learning to intelligent tutoring systems, yet current methods for providing students feedback are still quite limited. Most automatic feedback systems either provide binary correctness feedback, which may not help a student understand how to improve, or require hand-coding feedback templates, which may not generalize to new domains. This can be particularly challenging for physical control tasks, where the rich diversity in student behavior and specialized domains make it challenging to leverage general-purpose assistive tools for providing feedback. We design and build CORGI, a model trained to generate language corrections for physical control tasks, such as learning to ride a bike. CORGI takes in as input a pair of student and expert trajectories, and then generates natural language corrections to help the student improve. We collect and train CORGI over data from three diverse physical control tasks (drawing, steering, and joint movement). Through both automatic and human evaluations, we show that CORGI can (i) generate valid feedback for novel student trajectories, (ii) outperform baselines on domains with novel control dynamics, and (iii) improve student learning in an interactive drawing task.
FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels
Authors: Staerman, Guillaume and Allain, Cédric and Gramfort, Alexandre and Moreau, Thomas
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Temporal point processes (TPP) are a natural tool for modeling event-based data. Among all TPP models, Hawkes processes have proven to be the most widely used, mainly due to their adequate modeling for various applications, particularly when considering exponential or non-parametric kernels. Although non-parametric kernels are an option, such models require large datasets. While exponential kernels are more data efficient and relevant for specific applications where events immediately trigger more events, they are ill-suited for applications where latencies need to be estimated, such as in neuroscience. This work aims to offer an efficient solution to TPP inference using general parametric kernels with finite support. The developed solution consists of a fast $\ell_2$ gradient-based solver leveraging a discretized version of the events. After theoretically supporting the use of discretization, the statistical and computational efficiency of the novel approach is demonstrated through various numerical experiments. Finally, the method’s effectiveness is evaluated by modeling the occurrence of stimuli-induced patterns from brain signals recorded with magnetoencephalography (MEG). Given the use of general parametric kernels, results show that the proposed approach leads to an improved estimation of pattern latency than the state-of-the-art.
Partial Optimality in Cubic Correlation Clustering
Authors: Stein, David and Di Gregorio, Silvia and Andres, Bjoern
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.
MODeL: Memory Optimizations for Deep Learning
Authors: Steiner, Benoit and Elhoushi, Mostafa and Kahn, Jacob and Hegarty, James
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: The size of deep neural networks has grown exponentially in recent years. Unfortunately, hardware devices have not kept pace with the rapidly increasing memory requirements. To cope with this, researchers have proposed various techniques including spilling, rematerialization, reduced precision training, model pruning, and so on. However, these approaches suffer from various limitations, such as increasing training time, affecting model accuracy, or requiring extensive manual modifications to the neural networks. We present MODeL, an algorithm that optimizes the lifetime and memory location of the tensors used to train neural networks. Our method automatically reduces the memory usage of existing neural networks without any of the drawbacks of other techniques. We formulate the problem as a joint integer linear program (ILP). We present several techniques to simplify the encoding of the problem, and enable our approach to scale to the size of state-of-the-art neural networks using an off-the-shelf ILP solver. We experimentally demonstrate that MODeL only takes seconds to allow the training of neural networks using 30% less memory on average.
Improving Expert Predictions with Conformal Prediction
Authors: Straitouri, Eleni and Wang, Lequn and Okati, Nastaran and Gomez Rodriguez, Manuel
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Automated decision support systems promise to help human experts solve multiclass classification tasks more efficiently and accurately. However, existing systems typically require experts to understand when to cede agency to the system or when to exercise their own agency. Otherwise, the experts may be better off solving the classification tasks on their own. In this work, we develop an automated decision support system that, by design, does not require experts to understand when to trust the system to improve performance. Rather than providing (single) label predictions and letting experts decide when to trust these predictions, our system provides sets of label predictions constructed using conformal prediction—prediction sets—and forcefully asks experts to predict labels from these sets. By using conformal prediction, our system can precisely trade-off the probability that the true label is not in the prediction set, which determines how frequently our system will mislead the experts, and the size of the prediction set, which determines the difficulty of the classification task the experts need to solve using our system. In addition, we develop an efficient and near-optimal search method to find the conformal predictor under which the experts benefit the most from using our system. Simulation experiments using synthetic and real expert predictions demonstrate that our system may help experts make more accurate predictions and is robust to the accuracy of the classifier the conformal predictor relies on.
Lookahead When It Matters: Adaptive Non-causal Transformers for Streaming Neural Transducers
Authors: Strimel, Grant and Xie, Yi and King, Brian John and Radfar, Martin and Rastrow, Ariya and Mouchtaris, Athanasios
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: Streaming speech recognition architectures are employed for low-latency, real-time applications. Such architectures are often characterized by their causality. Causal architectures emit tokens at each frame, relying only on current and past signal, while non-causal models are exposed to a window of future frames at each step to increase predictive accuracy. This dichotomy amounts to a trade-off for real-time Automatic Speech Recognition (ASR) system design: profit from the low-latency benefit of strictly-causal architectures while accepting predictive performance limitations, or realize the modeling benefits of future-context models accompanied by their higher latency penalty. In this work, we relax the constraints of this choice and present the Adaptive Non-Causal Attention Transducer (ANCAT). Our architecture is non-causal in the traditional sense, but executes in a low-latency, streaming manner by dynamically choosing when to rely on future context and to what degree within the audio stream. The resulting mechanism, when coupled with our novel regularization algorithms, delivers comparable accuracy to non-causal configurations while improving significantly upon latency, closing the gap with their causal counterparts. We showcase our design experimentally by reporting comparative ASR task results with measures of accuracy and latency on both publicly accessible and production-scale, voice-assistant datasets.
Kernel QuantTree
Authors: Stucchi, Diego and Rizzo, Paolo and Folloni, Nicolò and Boracchi, Giacomo
Published in: Proceedings of the 40th International Conference on Machine Learning (Main Conference Track), 2023

Abstract: We present Kernel QuantTree (KQT), a non-parametric change detection algorithm that monitors multivariate data through a histogram. KQT constructs a nonlinear partition of the input space that matches pre-defined target probabilities and specifically promotes compact bins adhering to the data distribution, resulting in a powerful detection algorithm. We prove two key theoretical advantages of KQT: <em>i</em>) statistics defined over the KQT histogram do not depend on the stationary data distribution $ϕ_0$, so detection thresholds can be set a priori to control false positive rate, and <em>ii</em>) thanks to the kernel functions adopted, the KQT monitoring scheme is invariant to the roto-translation of the input data. Consequently, KQT does not require any preprocessing step like PCA. Our experiments show that KQT achieves superior detection power than non-parametric state-of-the-art change detection methods, and can reliably control the false positive rate.