Timezone: »
Integrating logical reasoning within deep learning architectures has been a major goal of modern AI systems. In this paper, we propose a new direction toward this goal by introducing a differentiable (smoothed) maximum satisfiability (MAXSAT) solver that can be integrated into the loop of larger deep learning systems. Our (approximate) solver is based upon a fast coordinate descent approach to solving the semidefinite program (SDP) associated with the MAXSAT problem. We show how to analytically differentiate through the solution to this SDP and efficiently solve the associated backward pass. We demonstrate that by integrating this solver into end-to-end learning systems, we can learn the logical structure of challenging problems in a minimally supervised fashion. In particular, we show that we can learn the parity function using single-bit supervision (a traditionally hard task for deep networks) and learn how to play 9x9 Sudoku solely from examples. We also solve a ``visual Sudoku'' problem that maps images of Sudoku puzzles to their associated logical solutions by combining our MAXSAT solver with a traditional convolutional architecture. Our approach thus shows promise in integrating logical structures within deep learning.
Author Information
Po-Wei Wang (Carnegie Mellon University)
Priya Donti (Carnegie Mellon University)
Bryan Wilder (University of Southern California)
Zico Kolter (Carnegie Mellon University / Bosch Center for AI)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver »
Wed. Jun 12th 01:30 -- 04:00 AM Room Pacific Ballroom #26
More from the Same Authors
-
2021 : Empirical robustification of pre-trained classifiers »
Mohammad Sadegh Norouzzadeh · Wan-Yi Lin · Leonid Boytsov · Leslie Rice · Huan Zhang · Filipe Condessa · Zico Kolter -
2021 : Certified robustness against adversarial patch attacks via randomized cropping »
Wan-Yi Lin · Fatemeh Sheikholeslami · jinghao shi · Leslie Rice · Zico Kolter -
2021 : Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification »
Shiqi Wang · Huan Zhang · Kaidi Xu · Xue Lin · Suman Jana · Cho-Jui Hsieh · Zico Kolter -
2021 : Assessing Generalization of SGD via Disagreement Rates »
YiDing Jiang · Vaishnavh Nagarajan · Zico Kolter -
2022 : Characterizing Datapoints via Second-Split Forgetting »
Pratyush Maini · Saurabh Garg · Zachary Lipton · Zico Kolter -
2022 : Improving adversarial robustness via joint classification and multiple explicit detection classes »
Sina Baharlouei · Fatemeh Sheikholeslami · Meisam Razaviyayn · Zico Kolter -
2022 : Agreement-on-the-Line: Predicting the Performance of Neural Networks under Distribution Shift »
Christina Baek · Yiding Jiang · aditi raghunathan · Zico Kolter -
2023 Workshop: 2nd Workshop on Formal Verification of Machine Learning »
Mark Müller · Brendon G. Anderson · Leslie Rice · Zhouxing Shi · Shubham Ugare · Huan Zhang · Martin Vechev · Zico Kolter · Somayeh Sojoudi · Cho-Jui Hsieh -
2022 Workshop: Workshop on Formal Verification of Machine Learning »
Huan Zhang · Leslie Rice · Kaidi Xu · aditi raghunathan · Wan-Yi Lin · Cho-Jui Hsieh · Clark Barrett · Martin Vechev · Zico Kolter -
2022 Poster: A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks »
Huan Zhang · Shiqi Wang · Kaidi Xu · Yihan Wang · Suman Jana · Cho-Jui Hsieh · Zico Kolter -
2022 Spotlight: A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks »
Huan Zhang · Shiqi Wang · Kaidi Xu · Yihan Wang · Suman Jana · Cho-Jui Hsieh · Zico Kolter -
2022 Poster: Communicating via Markov Decision Processes »
Samuel Sokota · Christian Schroeder · Maximilian Igl · Luisa Zintgraf · Phil Torr · Martin Strohmeier · Zico Kolter · Shimon Whiteson · Jakob Foerster -
2022 Spotlight: Communicating via Markov Decision Processes »
Samuel Sokota · Christian Schroeder · Maximilian Igl · Luisa Zintgraf · Phil Torr · Martin Strohmeier · Zico Kolter · Shimon Whiteson · Jakob Foerster -
2022 : Q&A »
Priya Donti · David Rolnick · Lynn Kaack -
2022 : Considerations for research and deployment »
Priya Donti -
2022 : Q&A »
Priya Donti · David Rolnick · Lynn Kaack -
2022 : Q&A »
Priya Donti · David Rolnick · Lynn Kaack -
2022 : Research challenges: Physics-informed and robust ML »
Priya Donti -
2022 : Q&A »
Priya Donti · David Rolnick · Lynn Kaack -
2022 : Introduction to climate change »
Priya Donti -
2022 Tutorial: Climate Change and Machine Learning: Opportunities, Challenges, and Considerations »
Priya Donti · David Rolnick · Lynn Kaack -
2022 : Opening remarks »
Priya Donti -
2021 Workshop: A Blessing in Disguise: The Prospects and Perils of Adversarial Machine Learning »
Hang Su · Yinpeng Dong · Tianyu Pang · Eric Wong · Zico Kolter · Shuo Feng · Bo Li · Henry Liu · Dan Hendrycks · Francesco Croce · Leslie Rice · Tian Tian -
2021 Poster: DORO: Distributional and Outlier Robust Optimization »
Runtian Zhai · Chen Dan · Zico Kolter · Pradeep Ravikumar -
2021 Poster: RATT: Leveraging Unlabeled Data to Guarantee Generalization »
Saurabh Garg · Sivaraman Balakrishnan · Zico Kolter · Zachary Lipton -
2021 Spotlight: DORO: Distributional and Outlier Robust Optimization »
Runtian Zhai · Chen Dan · Zico Kolter · Pradeep Ravikumar -
2021 Oral: RATT: Leveraging Unlabeled Data to Guarantee Generalization »
Saurabh Garg · Sivaraman Balakrishnan · Zico Kolter · Zachary Lipton -
2021 Poster: On Proximal Policy Optimization's Heavy-tailed Gradients »
Saurabh Garg · Joshua Zhanson · Emilio Parisotto · Adarsh Prasad · Zico Kolter · Zachary Lipton · Sivaraman Balakrishnan · Ruslan Salakhutdinov · Pradeep Ravikumar -
2021 Poster: Stabilizing Equilibrium Models by Jacobian Regularization »
Shaojie Bai · Vladlen Koltun · Zico Kolter -
2021 Spotlight: On Proximal Policy Optimization's Heavy-tailed Gradients »
Saurabh Garg · Joshua Zhanson · Emilio Parisotto · Adarsh Prasad · Zico Kolter · Zachary Lipton · Sivaraman Balakrishnan · Ruslan Salakhutdinov · Pradeep Ravikumar -
2021 Spotlight: Stabilizing Equilibrium Models by Jacobian Regularization »
Shaojie Bai · Vladlen Koltun · Zico Kolter -
2020 : Invited Talk: Zico Kolter (Q&A) »
Zico Kolter -
2020 : Invited Talk: Zico Kolter »
Zico Kolter -
2020 Poster: Adversarial Robustness Against the Union of Multiple Perturbation Models »
Pratyush Maini · Eric Wong · Zico Kolter -
2020 Poster: Combining Differentiable PDE Solvers and Graph Neural Networks for Fluid Flow Prediction »
Filipe de Avila Belbute-Peres · Thomas Economon · Zico Kolter -
2020 Poster: Certified Robustness to Label-Flipping Attacks via Randomized Smoothing »
Elan Rosenfeld · Ezra Winston · Pradeep Ravikumar · Zico Kolter -
2020 Poster: Overfitting in adversarially robust deep learning »
Leslie Rice · Eric Wong · Zico Kolter -
2019 Poster: Certified Adversarial Robustness via Randomized Smoothing »
Jeremy Cohen · Elan Rosenfeld · Zico Kolter -
2019 Poster: Wasserstein Adversarial Examples via Projected Sinkhorn Iterations »
Eric Wong · Frank R Schmidt · Zico Kolter -
2019 Oral: Wasserstein Adversarial Examples via Projected Sinkhorn Iterations »
Eric Wong · Frank R Schmidt · Zico Kolter -
2019 Oral: Certified Adversarial Robustness via Randomized Smoothing »
Jeremy Cohen · Elan Rosenfeld · Zico Kolter -
2019 Poster: Adversarial camera stickers: A physical camera-based attack on deep learning systems »
Juncheng Li · Frank R Schmidt · Zico Kolter -
2019 Oral: Adversarial camera stickers: A physical camera-based attack on deep learning systems »
Juncheng Li · Frank R Schmidt · Zico Kolter -
2018 Poster: Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope »
Eric Wong · Zico Kolter -
2018 Oral: Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope »
Eric Wong · Zico Kolter -
2017 Poster: Input Convex Neural Networks »
Brandon Amos · Lei Xu · Zico Kolter -
2017 Poster: OptNet: Differentiable Optimization as a Layer in Neural Networks »
Brandon Amos · Zico Kolter -
2017 Poster: A Semismooth Newton Method for Fast, Generic Convex Programming »
Alnur Ali · Eric Wong · Zico Kolter -
2017 Talk: OptNet: Differentiable Optimization as a Layer in Neural Networks »
Brandon Amos · Zico Kolter -
2017 Talk: Input Convex Neural Networks »
Brandon Amos · Lei Xu · Zico Kolter -
2017 Talk: A Semismooth Newton Method for Fast, Generic Convex Programming »
Alnur Ali · Eric Wong · Zico Kolter