Convex Relaxation

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 75% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 59

All topics

Match the Distribution, Not the Compute: Post-Training Multi-Token Prediction Heads
Oct 1, 2026Prachi Badarayani, Aidan Jay, Chenghui Zhou +8Multi-Token Prediction Post-Training
Microsoft
A QCQP-Representable IMU Pre-Integration Factor for Certifiable State Estimation
Sep 29, 2026Utkarsh Rai, Zhexin Xu, Bang-Shien Chen +1Inertial Measurement Units State Estimation
Robust Autonomy Lab, Institute for Experiential Robotics, Northeastern University, 360 Huntington Ave, Boston, MA 02115, USA
Structure-Adaptive Tree Field Integrators
Sep 27, 2026Millend Roy, Soham Samal, Ivan Zelich +1Octree Kernel Method
Columbia University New York, NY 10027, USA
Revisiting the Objective of Echo Chamber Detection
Sep 16, 2026Abylaikhan Bexeit, Kushani Perera, Shanika Karunasekera +1Community Detection Network Science
CIS, The University of Melbourne
Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates
Sep 16, 2026Yingquan, Wu, Jason CongMaximum Independent Set Hypergraphs
Cody · MBZUAI Institute of Foundation Models Sunnyvale, CA, USA · University of California, Los Angeles Los Angeles, CA, USA
One Color Preprocessing Improves DSATUR
Sep 15, 2026Adam Nouira, Lucas IsenmannMaximum Independent Set Convex Relaxation
Universit´e de Strasbourg
CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs
Sep 8, 2026Meher Chaitanya, Cameron Musco, Aristides GionisSpectral Preconditioning Singular Value Decomposition
KTH Royal Institute of Technology Stockholm, Sweden · University of Massachusetts Amherst Amherst, Massachusetts, USA
Guide, Not Bind: Why Defeasible Priors Fail in Augmented Lagrangian Causal Discovery
Sep 3, 2026Sairam Sundararaman, Sara Girdhar, Manit Narasimha Murthy +2Causal Discovery Methods Prior Knowledge Integration
Department of Computer Science (AI & ML) PES University · Department of Computer Science2026 PES University · Department of Computer Science PES University
Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration
Sep 2, 2026Connor Holmes, Abhishek Goudar, Timothy D. BarfootCategory-Level Object Pose Estimation Convex Relaxation
University of Toronto Robotics Institute, University of Toronto, Toronto, Ontario, Canada
Fast Length-Squared Sampling for Positive-Semidefinite Matrices
Aug 12, 2026Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco +1Matrix Low-Rank Structure
University of Massachusetts Amherst · University of California Berkeley
Simplex Relaxation for Discrete Diffusion
Aug 11, 2026Jinya Sakurai, Patrick Pynadath, Satoshi Hayakawa +4Diffusion Models Data Generation
1NTU Singapore · 2The University of Tokyo · Institute for Advanced Intelligence and Computing (IAIC), A*STAR +2
Recent advances in weakly supervised learning: New supervision paradigms, assumption relaxations, and practical solutions
Aug 7, 2026Wei Wang, Gang Niu, Masashi SugiyamaSemi-Supervised Learning Label Propagation
RIKEN, Tokyo, Japan · The University of Tokyo, Chiba, Japan
High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption
Jul 29, 2026Loong Kuan Lee, Ragavi Krishnamoorthy, Nico PiatkowskiConditional Independence Markov
Hybrid Intelligence, Fraunhofer IAIS, Sankt Augustin, Germany
Formalizing Flag Algebras in Lean
Jul 26, 2026Gyeongwon Jeong, Seonghun Park, Jihoon Hyun +2Acyclic Graphs Algebraic Structures
School of Computing, KAIST, Daejeon, Korea · School of Computational Sciences, Korea Institute for Advanced Study (KIAS), Seoul, Korea · Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, Korea +1
Random Parameter Noise Does Not Make Exact ReLU Verification Easy
Jul 15, 2026Mojtaba SoltanalianNeural Network Verification Rectified Linear Unit Networks
Department of Electrical and Computer Engineering University of Illinois Chicago
A Near-Linear-Time Solver for Graph $p$ -Laplacian Semi-Supervised Learning via Continuation in $p$
Jul 3, 2026Oren E. LivneGraph Laplacians Solver Iterations
Pine Birch Analytics, Churchville, PA
AI-Assisted Discovery of Convex Relaxations via Dual Agents
Jun 30, 2026Sungyoon Kim, Mert PilanciConvex Relaxation Upper Bounds
Department of Electrical Engineering, Stanford University, CA, USA.
Local-Minima-Preserving Continuous Relaxation of Ising Problems
Jun 29, 2026Debraj Banerjee, Santanu Mahapatra, Kunal N. ChaudhurySpatial Photonic Ising Machines Convex Relaxation
Department of Electrical Engineering, Indian Institute of Science, Bangalore, India · Department of Electronic Systems Engineering, Indian Institute of Science, Bangalore, India
Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
Jun 24, 2026Sam GanzfriedNash Equilibrium Imperfect-Information Games
Ganzfried Research, Cornell University
Sample complexity of unbalanced entropic OT
Jun 23, 2026Francisco Andrade, Gabriel Peyré, Clarice PoonOptimal Transport Approach Optimal Sample Complexity
INRIA (PreMeDICaL & HeKA) · INRIA · CNRS and ENS, PSL Universit´e +1
Training Dynamics of Neural Software Defect Predictors under Coupled Data-Quality Issues
Jun 23, 2026Emmanuel Charleson Dapaah, Philip Makedonski, Jens GrabowskiData Quality Training Data
Institute of Computer Science University of Goettingen Goettingen, Germany
Shifting-based Optimizable Linear Relaxations for General Activation Functions
Jun 18, 2026Philipp Kern, László Antal, Erika Ábráham +1Activation Functions Convex Relaxation
Karlsruhe Institute of Technology · RWTH Aachen University · Karlsruhe University of Applied Sciences
Phase Transition in Convex Relaxations for Graph Alignment
Jun 14, 2026Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux +1Convex Relaxation Full-Rank Correlation Matrices
INRIA, DI/ENS, PSL Research University, Paris, France · Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan, USA. · CNRS, INRIA, Universit´e Paris Dauphine, Paris, France
Semidefinite Relaxations for Collision-Free Motion Planning
Jun 12, 2026Bernhard Paus Graesdal, Alexandre Amice, Pablo A. Parrilo +1Collision-Free Trajectories Convex Relaxation
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA.
Scalable Deep Unfolding of Conic Optimizers
Jun 11, 2026Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. TheodorouDeep Unfolding Networks Convex Relaxation
Georgia Institute of Technology
Reformulate LLM Reinforcement Learning for Efficient Training under Black-box Discrepancy
Jun 7, 2026Jiashun Liu, Runze Liu, Xu Wan +3Large Language Model Reinforcement Learning Training-Inference Mismatch
1Hong Kong University of Science and Technology · 2Zhejiang University · 3Tianjin University
Network Learning with Semi-relaxed Gromov-Wasserstein
Jun 1, 2026Charles Dufour, Ulysse Naepels, Leonardo V. SantoroGromov--Wasserstein Network Science
EPFL, Institute of Mathematics Lausanne, Switzerland
Conditioned free-energy density of proteins using unbalanced solutions to constraint satisfaction problems
May 31, 2026Pratik Worah, Subhash Khot, Srinivasa VaradhanConformational Ensembles Free Energy Principle
Exploiting Chordal Sparsity for Globally Optimal Estimation with Factor Graphs
May 28, 2026Avinash Subramanian, Connor Holmes, Timothy D. Barfoot +2Factor Graphs State Estimation
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA · Robotics Institute, University of Toronto, Toronto, ON, Canada · Department of Mechanical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
Neural Network Verification using Partial Multi-Neuron Relaxation
May 28, 2026Ido Shmuel, Guy KatzNeural Network Verification Convex Relaxation
The Hebrew University of Jerusalem, Jerusalem, Israel
Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective
May 27, 2026Mingjie Hu, Jian-Qiang Hu, Enlu ZhouOffline Reinforcement Learning Convex Relaxation
School of Management, Fudan University · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
May 24, 2026Samuel B. Hopkins, Stefan TiegelSpectral Norm Approximation Algorithms
MIT
Implicit Binarization via Complex Phase Dynamics in Combinatorial Optimization
May 23, 2026Khen Cohen, Mark Glass, Meir Feder +1Quadratic Unconstrained Binary Optimization Convex Relaxation
School of Physics and Astronomy, Tel Aviv University, Tel Aviv, Israel · School of Electrical and Computer Engineering, Tel Aviv University, Tel Aviv, Israel
Decision-Aware Quadratic ReLU Replacement for HE-Friendly Inference
May 21, 2026Rui Li, Wenyuan Wu, Weijie MiaoHomomorphic Encryption Rectified Linear Unit
Chongqing Key Laboratory of Secure Computing for Biology, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, 266 Fangzheng Avenue, Beibei District, Chongqing 400714, China · Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong, China
Targeting Clause Type Distributions: a Picklock for Random Satisfiability Problems
May 19, 2026J. Schwardt, J. C. BudichSatisfiability Large Neighborhood Search
Max Planck Institute for the Physics of Complex Systems, Nöthnitzer Str. 38, 01187 Dresden, Germany · Institute of Theoretical Physics, Technische Universität Dresden and Würzburg-Dresden Cluster of Excellence ctd.qmat, 01062 Dresden, Germany
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
May 18, 2026Tung Quoc Le, Anh Tuan Nguyen, Viet Anh NguyenMixed-Integer Programming Convex Relaxation
Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.
Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting
May 17, 2026Karthik Prakhya, Alp YurtseverConvex Relaxation Deep Network
Ume˚a University, Sweden
Learning Fill-in Reduction Ordering via Graph Policy Optimization for Sparse Matrices
May 17, 2026Ziwei Li, Shuzi Niu, Huiyuan Li +2Tensor Completion Solver Iterations
Institute of Software, Chinese Academy of Sciences, Beijing, China
TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics
May 13, 2026Ishaan Mahajan, Jon Arrizabalaga, Andrea Grillo +4Obstacle Avoidance Model Predictive Control
Columbia University, USA · Massachusetts Institute of Technology, USA · ´Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Switzerland +1
Polyhedral Instability Governs Regret in Online Learning
May 13, 2026Yuetai Li, Fengqing Jiang, Yichen Feng +6\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Submodular Functions
♣University of Washington · ♢Western Washington University · ♠King Abdulaziz City for Science and Technology ♡HUMAIN
Ready from Day 1: Population-Aware Coordination for Large-Scale Constrained Multi-Agent Systems
May 12, 2026Angel Wang, Dominique Perrault-Joncas, Alvaro Maggiar +2Global Coordination Coordination
Amazon
Optimal Policy Learning under Budget and Coverage Constraints
May 12, 2026Giovanni CerulliOptimal Policies Knapsack Constraint
CNR-IRCrES · National Research Council of Italy · Research Institute on Sustainable Economic Growth
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
May 8, 2026Hao Chen, Chendi Qian, Christopher Morris +2Maximum Independent Set Convex Relaxation
1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech
A Differentiable Bayesian Relaxation for Latent Partial-Order Inference
May 7, 2026Dongqing Li, Geoff K. Nicholls, Shiyi Sun +1Bayesian Convex Relaxation
University of Oxford · University College London
Accelerated Relax-and-Round for Concave Coverage Problems
May 7, 2026Matthew Fahrbach, Mehraneh Liaee, Morteza ZadimoghaddamApproximation Algorithms Convex Relaxation
Google Research
Stability of the Monge Map in Semi-Dual Optimal Transport
May 7, 2026Anton Selitskiy, David MillardDifferentiable Optimal Transport Primal-Dual Methods
Dept. of Electrical and Computer Engineering Stony Brook University Stony Brook, NY 11790, USA · Dept. of Electrical and Computer Engineering University of Rochester Rochester, NY 14627, USA
Denoising data using convex relaxations
May 4, 2026Charles Fefferman, Aalok Gangopadhyay, Matti Lassas +2Convex Relaxation Iterative Denoising Methods
Department of Mathematics, Princeton University, Princeton, NJ 08544, USA. · TCS Research · Department of Mathematics and Statistics, University of Helsinki, FI-00014 Helsinki, Finland. +2
On the Expressive Power of GNNs to Solve Linear SDPs
Apr 30, 2026Chendi Qian, Christopher MorrisConvex Relaxation Graph Neural Networks
Faculty of Computer Science, RWTH Aachen University, Germany
Relaxation-Informed Training of Neural Network Surrogate Models
Apr 24, 2026Calvin TsaySurrogate Gradient Rectified Linear Unit Networks
Department of Computing, Imperial College London, South Kensington, SW7 2AZ, United Kingdom.
The Cost of Relaxation: Evaluating the Error in Convex Neural Network Verification
Apr 20, 2026Merkouris Papamichail, Konstantinos Varsos, Giorgos Flouris +1Neural Network Verification Rectified Linear Unit Networks
Foundation for Research and Technology – Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1
Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering
Apr 17, 2026Ibne Farabi Shihab, Sanjeda Akter, Anuj SharmaMaximum Independent Set Convex Relaxation
Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University
Optimal Centered Active Excitation in Linear System Identification
Apr 7, 2026Kaito Ito, Alexandre ProutiereSystem Identification Least Squares
Department of Information Physics and Computing, The University of Tokyo, Tokyo 113-8654, Japan · Division of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Stockholm 114 28, Sweden
A penalised Saito functional for heuristic search of free line arrangements
Apr 3, 2026Tomás S. R. SilvaPermutation Combinations
Instituto de Matem´atica, Estat´ıstica e Computa¸c˜ao Cient´ıfica (IMECC), Universidade Estadual de Campinas (UNICAMP), 13083-859, Campinas, S˜ao Paulo, Brazil.
Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming
Jan 7, 2026Valentine Olanubi, Phineas Agar, Brendan AmesConvex Relaxation Subgraphs
University of Alabama, Department of Mathematics · Department of Mathematics, University of Alabama, Tuscaloosa, AL, USA · University of Southampton, School of Mathematical Sciences +1
Mixtures Closest to a Given Measure: A Semidefinite Programming Approach
Sep 26, 2025Srećko Đurašinović, Jean-Bernard Lasserre, Victor MagronGaussian Mixture Models Convex Relaxation
College of Computing and Data Science, NTU, Singapore · LAAS-CNRS, Toulouse, France · Toulouse School of Economics +1
Learning Latent Graph Geometry via Fixed-Point Schrödinger-Type Activation: A Theoretical Study
Jul 27, 2025Dmitry Pasechnyuk-Vilensky, Martin TakáčDiscriminative Congruence Transform Differentiable Optimization
MBZUAI, UAE
Semidefinite programming relaxations and debiasing for MAXCUT-based clustering
Jan 16, 2024Shuheng ZhouConvex Relaxation Maximum Independent Set
University of California, Riverside, CA 92521
Efficient Cross-Validation for Sparse Linear Regression
Jun 26, 2023Ryan Cory-Wright, Andrés GómezKernel Ridge Regression Sparsity
Department of Analytics, Marketing and Operations, Imperial Business School, London, UK · Department of Industrial and Systems Engineering, Viterbi School of Engineering, University of Southern California, CA
Semidefinite Programming for Quantum Channel Learning
Date pendingMikhail Gennadievich Belov, Victor Victorovich Dubov, Vadim Konstantinovich Ivanov +3Convex Relaxation Channel
Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, GSP-1, Moscow, Vorob’evy Gory, 119991, Russia and Autretech Group, Skolkovo Innovation Center, Nobel Street, Building 7, Moscow, 121205, Russia · Peter the Great St. Petersburg Polytechnic University, 195251, Russia · Ioffe Institute, Politekhnicheskaya 26, St Petersburg, 194021, Russia

Oct 1, 2026, cs.LGJ/K move · Enter open · S save

Match the Distribution, Not the Compute: Post-Training Multi-Token Prediction Heads

Prachi Badarayani, Aidan Jay, Chenghui Zhou, Dayquan Julienne+7

Microsoft

Multi-Token Prediction Post-Training Large Language Model Backbones Autoregressive Generation Convex Relaxation

Open paper AskPDF arXiv

Multi-token prediction (MTP) improves the throughput of autoregressive generation by enabling the language model to draft multiple next tokens per forward pass, while a verification step over draft tokens ensures that token distribution of the backbone is preserved. Every open MTP-family release (MiMo-7B, DeepSeek-V3, Qwen3) trains its heads jointly with the backbone over the full pretraining run of tens of trillions of tokens, thus setting the drafter quality at pretraining time. We ask whether a lightweight post-training pass on target-generated chain-of-thought is enough to reach the same expected throughput speedup on a frozen reasoning model, and study how a serving-time system built on such a checkpoint can be optimized. We present three findings. 1) On a frozen Qwen3-8B with

K{=}3

chained MTP heads, we show that a post-training recipe with plain cross-entropy on

\approx\!2.5

B tokens reaches or exceeds the expected speedup of jointly trained MiMo-7B on math, coding and knowledge benchmarks. Our post-training recipe utilizes

10^3

10^4\times

less MTP-training tokens as compared with joint pre-training of MiMO-7B MTP baseline. 2) We propose a chain-aware relaxation of draft token verification rule that allows a bounded drift from backbone language model token distribution. We show that this relaxation lifts expected speedups by

+12

+16\%

per benchmark while preserving task accuracy. 3) We propose an adaptive controller that dynamically chooses the number of MTP heads to be engaged at inference time and demonstrate recovery of upto

11

14\%

loss in speedup using fixed maximum MTP draft length.

Momentum

Related topics

Latest papers 59