publications

2025

1. ICML

   Scalable First-order Method for Certifying Optimal k-Sparse GLMs

   Jiachang Liu, Soroosh Shafiee, and Andrea Lodi

   International Conference on Machine Learning (ICML), 2025

   Abs PDF

   This paper investigates the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through an \ell_0 cardinality constraint. While branch-and-bound (BnB) frameworks can certify optimality by pruning nodes using dual bounds, existing methods for computing these bounds are either computationally intensive or exhibit slow convergence, limiting their scalability to large-scale problems. To address this challenge, we propose a first-order proximal gradient algorithm designed to solve the perspective relaxation of the problem within a BnB framework. Specifically, we formulate the relaxed problem as a composite optimization problem and demonstrate that the proximal operator of the non-smooth component can be computed exactly in log-linear time complexity, eliminating the need to solve a computationally expensive second-order cone program. Furthermore, we introduce a simple restart strategy that enhances convergence speed while maintaining low per-iteration complexity. Extensive experiments on synthetic and real-world datasets show that our approach significantly accelerates dual bound computations and is highly effective in providing optimality certificates for large-scale problems.

2024

1. NeurIPS

   FastSurvival: Hidden Computational Blessings in Training Cox Proportional Hazards Models

   Jiachang Liu, Rui Zhang, and Cynthia Rudin

   Advances in Neural Information Processing Systems (NeurIPS), 2024

   Abs PDF

   Survival analysis is an important research topic with applications in healthcare, business, and manufacturing. One essential tool in this area is the Cox proportional hazards (CPH) model, which is widely used for its interpretability, flexibility, and predictive performance. However, for modern data science challenges such as high dimensionality (both n and p) and high feature correlations, current algorithms to train the CPH model have drawbacks, preventing us from using the CPH model at its full potential. The root cause is that the current algorithms, based on the Newton method, have trouble converging due to vanishing second order derivatives when outside the local region of the minimizer. To circumvent this problem, we propose new optimization methods by constructing and minimizing surrogate functions that exploit hidden mathematical structures of the CPH model. Our new methods are easy to implement and ensure monotonic loss decrease and global convergence. Empirically, we verify the computational efficiency of our methods. As a direct application, we show how our optimization methods can be used to solve the cardinality-constrained CPH problem, producing very sparse high-quality models that were not previously practical to construct. We list several extensions that our breakthrough enables, including optimization opportunities, theoretical questions on CPH’s mathematical structure, as well as other CPH-related applications.

2. ICML

   Position: Amazing Things Come From Having Many Good Models

   Cynthia Rudin, Chudi Zhong^*, Lesia Semenova^*, Margo Seltzer^*, Ronald Parr^*, Jiachang Liu^*, Srikar Katta^*, Jon Donnelly^*, Harry Chen^*, and Zachery Boner^*

   Proceedings of the International Conference on Machine Learning (ICML), Spotlight, 2024

   Abs PDF

   The \textitRashomon Effect, coined by Leo Breiman, describes the phenomenon that there exist many equally good predictive models for the same dataset. This phenomenon happens for many real datasets and when it does, it sparks both magic and consternation, but mostly magic. In light of the Rashomon Effect, this perspective piece proposes reshaping the way we think about machine learning, particularly for tabular data problems in the nondeterministic (noisy) setting. We address how the Rashomon Effect impacts (1) the existence of simple-yet-accurate models, (2) flexibility to address user preferences, such as fairness and monotonicity, without losing performance, (3) uncertainty in predictions, fairness, and explanations, (4) reliable variable importance, (5) algorithm choice, specifically, providing advanced knowledge of which algorithms might be suitable for a given problem, and (6) public policy. We also discuss a theory of when the Rashomon Effect occurs and why. Our goal is to illustrate how the Rashomon Effect can have a massive impact on the use of machine learning for complex problems in society.

2023

1. NeurIPS

   OKRidge: Scalable Optimal k-Sparse Ridge Regression for Learning Dynamical Systems

   Jiachang Liu, Sam Rosen, Chudi Zhong, and Cynthia Rudin

   Advances in Neural Information Processing Systems (NeurIPS), Spotlight, 2023

   Abs PDF Code

   We consider an important problem in scientific discovery, identifying sparse governing equations for nonlinear dynamical systems. This involves solving sparse ridge regression problems to provable optimality in order to determine which terms drive the underlying dynamics. We propose a fast algorithm, OKRidge, for sparse ridge regression, using a novel lower bound calculation involving, first, a saddle point formulation, and from there, either solving (i) a linear system or (ii) using an ADMM-based approach, where the proximal operators can be efficiently evaluated by solving another linear system and an isotonic regression problem. We also propose a method to warm-start our solver, which leverages a beam search. Experimentally, our methods attain provable optimality with run times that are orders of magnitude faster than those of the existing MIP formulations solved by the commercial solver Gurobi.

2. NeurIPS

   Exploring and Interacting with the Set of Good Sparse Generalized Additive Models

   Chudi Zhong^*, Zhi Chen^*, Jiachang Liu, Margo Seltzer, and Cynthia Rudin

   Advances in Neural Information Processing Systems (NeurIPS), 2023

   Abs PDF

   In real applications, interaction between machine learning models and domain experts is critical; however, the classical machine learning paradigm that usually produces only a single model does not facilitate such interaction. Approximating and exploring the Rashomon set, i.e., the set of all near-optimal models, addresses this practical challenge by providing the user with a searchable space containing a diverse set of models from which domain experts can choose. We present algorithms to efficiently and accurately approximate the Rashomon set of sparse, generalized additive models with ellipsoids for fixed support sets and use these ellipsoids to approximate Rashomon sets for many different support sets. The approximated Rashomon set serves as a cornerstone to solve practical challenges such as (1) studying the variable importance for the model class; (2) finding models under user-specified constraints (monotonicity, direct editing); and (3) investigating sudden changes in the shape functions. Experiments demonstrate the fidelity of the approximated Rashomon set and its effectiveness in solving practical challenges.

2022

1. NeurIPS

   FasterRisk: Fast and Accurate Interpretable Risk Scores

   Jiachang Liu^*, Chudi Zhong^*, Boxuan Li, Margo Seltzer, and Cynthia Rudin

   Advances in Neural Information Processing Systems (NeurIPS), 2022

   Abs PDF Code

   Over the last century, risk scores have been the most popular form of predictive model used in healthcare and criminal justice. Risk scores are sparse linear models with integer coefficients; often these models can be memorized or placed on an index card. Typically, risk scores have been created either without data or by rounding logistic regression coefficients, but these methods do not reliably produce high-quality risk scores. Recent work used mathematical programming, which is computationally slow. We introduce an approach for efficiently producing a collection of high-quality risk scores learned from data. Specifically, our approach produces a pool of almost-optimal sparse continuous solutions, each with a different support set, using a beam-search algorithm. Each of these continuous solutions is transformed into a separate risk score through a "star ray" search, where a range of multipliers are considered before rounding the coefficients sequentially to maintain low logistic loss. Our algorithm returns all of these high-quality risk scores for the user to consider. This method completes within minutes and can be valuable in a broad variety of applications.

2. AISTATS

   Fast Sparse Classification for Generalized Linear and Additive Models

   Jiachang Liu, Chudi Zhong, Margo Seltzer, and Cynthia Rudin

   In International Conference on Artificial Intelligence and Statistics, 2022

   Abs PDF Code

   We present fast classification techniques for sparse generalized linear and additive models. These techniques can handle thousands of features and thousands of observations in minutes, even in the presence of many highly correlated features. For fast sparse logistic regression, our computational speed-up over other best-subset search techniques owes to linear and quadratic surrogate cuts for the logistic loss that allow us to efficiently screen features for elimination, as well as use of a priority queue that favors a more uniform exploration of features. As an alternative to the logistic loss, we propose the exponential loss, which permits an analytical solution to the line search at each iteration. Our algorithms are generally 2 to 5 times faster than previous approaches. They produce interpretable models that have accuracy comparable to black box models on challenging datasets.

3. ACL-W

   What Makes Good In-Context Examples for GPT-3?

   Jiachang Liu, Dinghan Shen, Yizhe Zhang, William B Dolan, Lawrence Carin, and Weizhu Chen

   In Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures, Association for Computational Linguistics, 2022

   Abs PDF Code

   GPT-3 has attracted lots of attention due to its superior performance across a wide range of NLP tasks, especially with its powerful and versatile in-context few-shot learning ability. Despite its success, we found that the empirical results of GPT-3 depend heavily on the choice of in-context examples. In this work, we investigate whether there are more effective strategies for judiciously selecting in-context examples (relative to random sampling) that better leverage GPT-3’s few-shot capabilities. Inspired by the recent success of leveraging a retrieval module to augment large-scale neural network models, we propose to retrieve examples that are semantically-similar to a test sample to formulate its corresponding prompt. Intuitively, the in-context examples selected with such a strategy may serve as more informative inputs to unleash GPT-3’s extensive knowledge. We evaluate the proposed approach on several natural language understanding and generation benchmarks, where the retrieval-based prompt selection approach consistently outperforms the random baseline. Moreover, it is observed that the sentence encoders fine-tuned on task-related datasets yield even more helpful retrieval results. Notably, significant gains are observed on tasks such as table-to-text generation (41.9% on the ToTTo dataset) and open-domain question answering (45.5% on the NQ dataset). We hope our investigation could help understand the behaviors of GPT-3 and large-scale pre-trained LMs in general and enhance their few-shot capabilities.

4. TPAMI

   Representing Graphs via Gromov-Wasserstein Factorization

   Hongteng Xu, Jiachang Liu, Dixin Luo, and Lawrence Carin

   IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022

   Abs PDF

   We propose a new nonlinear factorization model for graphs that have topological structures, and optionally, node attributes. This model is based on a pseudo-metric called Gromov-Wasserstein (GW) discrepancy, which compares graphs in a relational way. It estimates observed graphs as the GW barycenters constructed by a set of graph bases with different weights. By minimizing the difference between each observed graph and its GW barycenter-based estimation, we learn the graph bases and their weights associated with the observed graphs. The model achieves a novel and flexible factorization mechanism for graphs, in which both the observed graphs and the learnable graph bases can be unaligned and with different sizes. We design an effective approximate algorithm for learning this Gromov-Wasserstein factorization (GWF) model, unrolling loopy computations as stacked modules and computing gradients with backpropagation. For each observed graph, the weights lead to its permutation-invariant representation. These weights can be parametrized by a graph neural network so that we can extend the proposed transductive GWF model to an inductive version. Compared with state-of-the-art methods, our GWF method can represent graphs with better interpretability and using lower dimensionality, while simultaneously achieving encouraging results in graph clustering and classification task.

2020

1. ICML

   CLUB: A Contrastive Log-ratio Upper Bound of Mutual Information

   Pengyu Cheng, Weituo Hao, Shuyang Dai, Jiachang Liu, Zhe Gan, and Lawrence Carin

   In International Conference on Machine Learning, 2020

   Abs PDF Code

   Mutual information (MI) minimization has gained considerable interests in various machine learning tasks. However, estimating and minimizing MI in high-dimensional spaces remains a challenging problem, especially when only samples, rather than distribution forms, are accessible. Previous works mainly focus on MI lower bound approximation, which is not applicable to MI minimization problems. In this paper, we propose a novel Contrastive Log-ratio Upper Bound (CLUB) of mutual information. We provide a theoretical analysis of the properties of CLUB and its variational approximation. Based on this upper bound, we introduce a MI minimization training scheme and further accelerate it with a negative sampling strategy. Simulation studies on Gaussian distributions show the reliable estimation ability of CLUB. Real-world MI minimization experiments, including domain adaptation and information bottleneck, demonstrate the effectiveness of the proposed method. The code is at https://github.com/Linear95/CLUB.

1967

1. Vision

   

   Letters on wave mechanics

   Albert Einstein, Erwin Schrödinger, Max Planck, Hendrik Antoon Lorentz, and Karl Przibram

   1967

   Bib

   @book{przibram1967letters,
     title = {Letters on wave mechanics},
     author = {Einstein, Albert and Schrödinger, Erwin and Planck, Max and Lorentz, Hendrik Antoon and Przibram, Karl},
     year = {1967},
     publisher = {Vision},
   }

1956

1. 

   Investigations on the Theory of the Brownian Movement

   Albert Einstein

   1956

   Bib

   @book{einstein1956investigations,
     title = {Investigations on the Theory of the Brownian Movement},
     author = {Einstein, Albert},
     year = {1956},
     publisher = {Courier Corporation},
   }

1950

1. AJP

   The meaning of relativity

   Albert Einstein and AH Taub

   American Journal of Physics, 1950

   Bib

   @article{einstein1950meaning,
     title = {The meaning of relativity},
     author = {Einstein, Albert and Taub, AH},
     journal = {American Journal of Physics},
     volume = {18},
     number = {6},
     pages = {403--404},
     year = {1950},
     publisher = {American Association of Physics Teachers}
   }

1935

1. PhysRev

   Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?

   A. Einstein^*†, B. Podolsky^*, and N. Rosen^*

   Phys. Rev., New Jersey. More Information can be found here , May 1935

   Abs DOI HTML PDF Video

   

   In a complete theory there is an element corresponding to each element of reality. A sufficient condition for the reality of a physical quantity is the possibility of predicting it with certainty, without disturbing the system. In quantum mechanics in the case of two physical quantities described by non-commuting operators, the knowledge of one precludes the knowledge of the other. Then either (1) the description of reality given by the wave function in quantum mechanics is not complete or (2) these two quantities cannot have simultaneous reality. Consideration of the problem of making predictions concerning a system on the basis of measurements made on another system that had previously interacted with it leads to the result that if (1) is false then (2) is also false. One is thus led to conclude that the description of reality as given by a wave function is not complete.

1920

1. Relativity: the Special and General Theory

   Albert Einstein

   May 1920

   HTML

1905

1. Über die von der molekularkinetischen Theorie der Wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen

   A. Einstein

   Annalen der physik, May 1905
2. Ann. Phys.

   Un the movement of small particles suspended in statiunary liquids required by the molecular-kinetic theory 0f heat

   A. Einstein

   Ann. Phys., May 1905
3. On the electrodynamics of moving bodies

   A. Einstein

   May 1905
4. Ann. Phys.

   Über einen die Erzeugung und Verwandlung des Lichtes betreffenden heuristischen Gesichtspunkt

   Albert Einstein

   Ann. Phys., May 1905

   Nobel Prize Abs DOI Bib

   Albert Einstein receveid the Nobel Prize in Physics 1921 for his services to Theoretical Physics, and especially for his discovery of the law of the photoelectric effect

   This is the abstract text.

   @article{einstein1905photoelectriceffect,
     title = {{{\"U}ber einen die Erzeugung und Verwandlung des Lichtes betreffenden heuristischen Gesichtspunkt}},
     author = {Einstein, Albert},
     journal = {Ann. Phys.},
     volume = {322},
     number = {6},
     pages = {132--148},
     year = {1905},
     doi = {10.1002/andp.19053220607},
   }