论文检索

Optimization · Non-Convex

Ganzhao Yuan

Nonsmooth composite optimization with orthogonality constraints has a wide range of applications in statistical learning and data science. However, this problem is challenging due to its nonsmooth objective and computationally expensive, non-convex constraints. In this paper, we propose a new approach called \textbf{OBCD}, which leverages Block Coordinate Descent to address these challenges. \textbf{OBCD} is a feasible method with a small computational footprint. In each iteration, it updates $k$ rows of the solution matrix, where $k \geq 2$, by globally solving a small nonsmooth optimization problem under orthogonality constraints. We prove that the limiting points of \textbf{OBCD}, referred to as (global) block-$k$ stationary points, offer stronger optimality than standard critical points. Furthermore, we show that \textbf{OBCD} converges to $\epsilon$-block-$k$ stationary points with an iteration complexity of $\mathcal{O}(1/\epsilon)$. Additionally, under the Kurdyka-Lojasiewicz (KL) inequality, we establish the non-ergodic convergence rate of \textbf{OBCD}. We also demonstrate how novel breakpoint search methods can be used to solve the subproblem in \textbf{OBCD}. Empirical results show that our approach consistently outperforms existing methods.

Reinforcement Learning · Everything Else

Bill Zheng, Vivek Myers, Benjamin Eysenbach, Sergey Levine

The problem of learning how to reach goals in an environment has been a long- standing challenge in for AI researchers. Effective goal-conditioned reinforcement learning (GCRL) methods promise to enable reaching distant goals without task- specific rewards by stitching together past experiences of different complexity. Mathematically, there is a duality between the notion of optimal goal-reaching value functions (the likelihood of success at reaching a goal) and temporal dis- tances (transit times states). Recent works have exploited this property by learning quasimetric distance representations that stitch long-horizon behaviors using the in- ductive bias of their architecture. These methods have shown promise in simulated benchmarks, reducing value learning to a shortest-path problem. But quasimet- ric, and more generally, goal-conditioned RL methods still struggle in complex environments with stochasticity and high-dimensional (visual) observations. There is a fundamental tension between the local dynamic programming (TD backups, temporal distances) that enables optimal shortest-path reasoning in theory and the statistical global MC updates (multistep returns, suboptimal in theory). We show how these approaches can be integrated into a practical GCRL method that fits a quasimetric distance using a multistep Monte-Carlo return. We show our method outperforms existing GCRL methods on long-horizon simulated tasks with up to 4000 steps, even with visual observations. We also demonstrate that our method can enable stitching in the real-world robotic manipulation domain (Bridge setup). Our approach is the first end-to-end GCRL method that enables multistep stitching in this real-world manipulation domain from an unlabeled offline dataset of visual observations.

Deep Learning · Generative Models and Autoencoders

Adnan Oomerjee, Zafeirios Fountas, Haitham Bou Ammar, Jun Wang

Transformer LLMs have been shown to exhibit strong reasoning ability that scales with inference-time compute, most prominently through token-space “thinking” (i.e., chains of thought). A growing line of work pushes this extra computation into the model’s latent space (adjacent to standard decoding) which we term Auxiliary Latent-Space Computation (ALSC). Existing ALSC methods largely fall into three buckets: (i) token-mediated latent or special-token rollouts, (ii) residual/activation steering, and (iii) memory compression via cache pruning, merging, or summarization. An underexplored alternative is memory consolidation and reconsolidation, two processes in the brain that are responsible for stabilising newly formed memory traces, and, upon recall, transiently rendering established traces plastic such they can integrate new contextual information before restabilising. In a Transformer LLM, this can be seen as analogous to performing in-place global rewrites of incoming KV segments, and rewrites of past segments conditioned on newly observed tokens. In this work, we give a theoretical justification as to why memory (re)consolidation via KV cache rewrites is beneficial for improved reasoning. We do this through the lens of Information Bottleneck (IB) theory, which posits that model generalisation emerges from an optimal balance between input information compression and retention of predictive information in latent representations. We prove using IB theory that Vanilla decoder-only Transformers are inherently constrained in their ability to form task-optimal sequence representations. We then introduce the Bottlenecked Transformer, which augments a decoder-only backbone LLM with a lightweight Cache Processor, an auxiliary Transformer that performs periodic, non-causal, in-place KV rewrites at newline-delimited reasoning step boundaries. The processor consolidates recently written KV entries and reconsolidates a small, top-$k$ attention-selected set of prior entries, conditioned on recent context. We evaluate our Bottlenecked Transformer architecture on seven mathematical reasoning benchmarks, with four backbone LLMs. Our model sees consistent performance gains over vanilla Transformers and pause-token augmented Transformer baselines, with gains of up to +6.6pp for selected tasks and backbones.

General Machine Learning · Representation Learning

Guy Ohayon, Pierre-Etienne Fiquet, Florentin Guth, Jona Ballé, Eero Simoncelli

We introduce the Information-Estimation Metric (IEM), a novel form of distance function derived from an underlying continuous probability density over a domain of signals. The IEM is rooted in a fundamental relationship between information theory and estimation theory, which links the log-probability of a signal with the errors of an optimal denoiser, applied to noisy observations of the signal. In particular, the IEM between a pair of signals is obtained by comparing their denoising error vectors over a range of noise amplitudes. Geometrically, this amounts to comparing the score vector fields of the *blurred* density around the signals over a range of blur levels. We prove that the IEM is a valid global distance metric and derive a closed-form expression for its local second-order approximation, which yields a Riemannian metric. For Gaussian-distributed signals, the IEM coincides with the Mahalanobis distance. But for more complex distributions, it adapts, both locally and globally, to the geometry of the distribution. In practice, the IEM can be computed using a learned denoiser (analogous to generative diffusion models) and solving a one-dimensional integral. To demonstrate the value of our framework, we learn an IEM on the ImageNet database. Experiments show that this IEM is competitive with or outperforms state-of-the-art supervised image quality metrics in predicting human perceptual judgments.

Applications · Genetics, Cell Biology, Health, etc

Rohit Dilip, Evan Zhang, Ayush Varshney, David Van Valen

Protein structure tokenizers enable the creation of multimodal models of protein structure, sequence, and function. Current approaches to protein structure tokenization rely on bespoke components that are invariant to spatial symmetries, but that are challenging to optimize and scale. We present Kanzi, a flow-based tokenizer for tokenization and generation of protein structures. Kanzi consists of a diffusion autoencoder trained with a flow matching loss. We show that this approach simplifies several aspects of protein structure tokenizers: frame-based representations can be replaced with global coordinates, complex losses are replaced with a single flow matching loss, and SE(3)-invariant attention operations can be replaced with standard attention. We find that these changes stabilize the training of parameter-efficient models that outperform existing tokenizers on reconstruction metrics at a fraction of the model size and training cost. An autoregressive model trained with Kanzi outperforms similar generative models that operate over tokens, although it does not yet match the performance of state-of-the-art continuous diffusion models.

Theory · Learning Theory

Mahsa Taheri, Fang Xie, Johannes Lederer

Since statistical guarantees for neural networks are usually restricted to global optima of intricate objective functions, it is unclear whether these theories explain the performances of actual outputs of neural network pipelines. The goal of this paper is, therefore, to bring statistical theory closer to practice. We develop statistical guarantees for shallow linear neural networks that coincide up to logarithmic factors with the global optima but apply to stationary points and the points nearby. These results support the common notion that neural networks do not necessarily need to be optimized globally from a mathematical perspective. We then extend our statistical guarantees to shallow ReLU neural networks, assuming the first layer weight matrices are nearly identical for the stationary network and the target. More generally, despite being limited to shallow neural networks for now, our theories make an important step forward in describing the practical properties of neural networks in mathematical terms.

Haochen Wang, Yuhao Wang, Tao Zhang, Yikang Zhou, Yanwei Li, Jiacong Wang, Jiani zheng, Ye Tian, Jiahao Meng, Zilong Huang 等

While Multimodal Large Language Models (MLLMs) excel at holistic understanding, they struggle with the dense world, i.e., complex scenes requiring fine-grained analysis of intricate details and object inter-relationships. Region-level MLLMs have been a promising step. However, previous attempts are generally optimized to understand given regions in isolation, neglecting crucial global contexts. To address this, we introduce Grasp Any Region (GAR) for comprehensive region-level visual understanding. Empowered by an effective RoI-aligned feature replay technique, GAR supports (1) precise perception by leveraging necessary global contexts, and (2) modeling interactions between multiple prompts. Together, it then naturally achieves (3) advanced compositional reasoning to answer specific free-form questions about any region, shifting the paradigm from passive description to active dialogue. Moreover, we construct GARBench, which not only provides a more accurate evaluation of single-region comprehension, but also, more importantly, measures interactions and complex reasoning across multiple regions. Empirically, GAR-1B not only maintains the state-of-the-art captioning capabilities, e.g., outperforming DAM-3B +4.5 on DLC-Bench, but also excels at modeling relationships between multiple prompts with advanced comprehension capabilities, even surpassing InternVL3-78B on GARBench-VQA. More importantly, our zero-shot GAR-8B even outperforms in-domain VideoRefer-7B on VideoRefer-BenchQ, indicating its strong comprehension capabilities can be easily transferred to videos. Code and data will be released to the community.

Wonjong Jang, Yucheol Jung, Gyeongmin Lee, Seungyong Lee 0001

Self-intersection repair in static 3D surface meshes presents unique challenges due to the absence of temporal motion and penetration depth information—two critical elements typically leveraged in physics-based approaches. We introduce a novel framework that transforms local contact handling into a global repair strategy through a combination of local signed tangent-point energies and their gradient diffusion. At the heart of our method is a key insight: rather than computing expensive global repulsive potentials, we can effectively approximate long-range interactions by diffusing energy gradients from local contacts throughout the mesh surface. In turn, resolving complex self-intersections reduces to simply propagating local repulsive energies through standard diffusion mechanics and iteratively solving tractable local optimizations. We further accelerate convergence through our momentum-based optimizer, which adaptively regulates momentum based on gradient statistics to prevent overshooting while maintaining rapid intersection repair. The resulting algorithm handles a variety of challenging scenarios, from shallow contacts to deep penetrations, while providing computational efficiency suitable for interactive applications.

Xinyu Yi, Shaohua Pan 0002, Feng Xu 0005

By learning human motion priors, motion capture can be achieved by 6 inertial measurement units (IMUs) in recent years with the development of deep learning techniques, even though the sensor inputs are sparse and noisy. However, human global motions are still challenging to be reconstructed by IMUs. This paper aims to solve this problem by involving physics. It proposes a physical optimization scheme based on multiple contacts to enable physically plausible translation estimation in the full 3D space where the z-directional motion is usually challenging for previous works. It also considers gravity in local pose estimation which well constrains human global orientations and refines local pose estimation in a joint estimation manner. Experiments demonstrate that our method achieves more accurate motion capture for both local poses and global motions. Furthermore, by deeply integrating physics, we can also estimate 3D contact, contact forces, joint torques, and interacting proxy surfaces. Code is available at https://xinyu-yi.github.io/GlobalPose/.

Quentin Becker, Oliver Gross 0001, Mark Pauly

Numerous tasks in robotics and character animation involve solving combinations of inverse kinematics and motion planning problems that require the precise design of pose sequences to achieve desired motion objectives. Accounting for the complex interplay between body deformations and resulting motion, especially through interactions with the environment, poses significant challenges for the design of such pose sequences. We propose a computational framework to address these challenges in scenarios where the motion of a deformable body is entirely determined by dynamic changes of its shape. Complementing recent methods on the forward problem—mapping shape sequences to global motion trajectories based on a geometric formulation of locomotion—we address the inverse problem of optimizing shape sequences to achieve user-defined motion objectives. We demonstrate the effectiveness of our method through a diverse set of examples, producing realistic shape sequences that result in desired motion trajectories.

Federico Sichetti, Enrico Puppo, Zizhou Huang, Marco Attene, Denis Zorin, Daniele Panozzo

Many problems in computer graphics can be formulated as finding the global minimum of a function subject to a set of non-linear constraints (Minimize), or finding all solutions of a system of non-linear constraints (Solve). We introduce MiSo, a domain-specific language and compiler for generating efficient C++ code for low-dimensional Minimize and Solve problems, that uses interval methods to guarantee conservative results while using floating point arithmetic. We demonstrate that MiSo-generated code shows competitive performance compared to hand-optimized codes for several computer graphics problems, including high-order collision detection with non-linear trajectories, surface-surface intersection, and geometrical validity checks for finite element simulation.

Linjie Lyu, Valentin Deschaintre, Yannick Hold-Geoffroy, Milos Hasan, Jae Shin Yoon, Thomas Leimkühler, Christian Theobalt, Iliyan Georgiev

Generative diffusion models have advanced image editing by delivering high-quality results through intuitive interfaces such as prompts, scribbles, and semantic drawing. However, these interfaces lack precise control, and associated editing methods often specialize in a single task. We introduce a versatile workflow for a range of editing tasks which operates in an intrinsic-image latent space, enabling semantic, local manipulation with pixel precision while automatically handling effects like reflections and shadows. We build on the RGB↔X diffusion framework and address its key deficiencies: the lack of identity preservation and the need to update multiple channels to achieve plausible results. We propose an edit-friendly diffusion inversion and prompt-embedding optimization to enable precise and efficient editing of only the relevant channels. Our method achieves identity preservation and resolves global illumination, without requiring task-specific model fine-tuning. We demonstrate state-of-the-art performance across a variety of tasks on complex images, including material adjustments, object insertion and removal, global relighting, and their combinations.

Zhuodong Li, Fei Hou 0001, Wencheng Wang 0001, Xuequan Lu, Ying He 0001

Orienting point clouds is a fundamental problem in computer graphics and 3D vision, with applications in reconstruction, segmentation, and analysis. While significant progress has been made, existing approaches mainly focus on watertight, object-level 3D models. The orientation of large-scale, non-watertight 3D scenes remains an underexplored challenge. To address this gap, we propose DACPO (Divide-And-Conquer Point Orientation), a novel framework that leverages a divide-and-conquer strategy for scalable and robust point cloud orientation. Rather than attempting to orient an unbounded scene at once, DACPO segments the input point cloud into smaller, manageable blocks, processes each block independently, and integrates the results through a global optimization stage. For each block, we introduce a two-step process: estimating initial normal orientations by a randomized greedy method and refining them by an adapted iterative Poisson surface reconstruction. To achieve consistency across blocks, we model inter-block relationships using an an undirected graph, where nodes represent blocks and edges connect spatially adjacent blocks. To reliably evaluate orientation consistency between adjacent blocks, we introduce the concept of the visible connected region, which defines the region over which visibility-based assessments are performed. The global integration is then formulated as a 0-1 integer-constrained optimization problem, with block flip states as binary variables. Despite the combinatorial nature of the problem, DACPO remains scalable by limiting the number of blocks (typically a few hundred for 3D scenes) involved in the optimization. Experiments on benchmark datasets demonstrate DACPO's strong performance, particularly in challenging large-scale, non-watertight scenarios where existing methods often fail. The source code is available at https://github.com/zd-lee/DACPO.

Lei Lan, Zixuan Lu, Chun Yuan 0001, Weiwei Xu 0003, Hao Su 0001, Huamin Wang 0001, Chenfanfu Jiang, Yin Yang 0002

In parallel simulation, convergence and parallelism are often seen as inherently conflicting objectives. Improved parallelism typically entails lighter local computation and weaker coupling, which unavoidably slow the global convergence. This paper presents a novel GPU algorithm that achieves convergence rates comparable to fullspace Newton's method while maintaining good parallelizability just like the Jacobi method. Our approach is built on a key insight into the phenomenon of overshoot. Overshoot occurs when a local solver aggressively minimizes its local energy without accounting for the global context, resulting in a local update that undermines global convergence. To address this, we derive a theoretically second-order optimal solution to mitigate overshoot. Furthermore, we adapt this solution into a pre-computable form. Leveraging Cubature sampling, our runtime cost is only marginally higher than the Jacobi method, yet our algorithm converges nearly quadratically as Newton's method. We also introduce a novel full-coordinate formulation for more efficient pre-computation. Our method integrates seamlessly with the incremental potential contact method and achieves second-order convergence for both stiff and soft materials. Experimental results demonstrate that our approach delivers high-quality simulations and outperforms state-of-the-art GPU methods with 50× to 100× better convergence.

Rahul Mitra, Mattéo Couplet, Tongtong Wang, Megan Hofmann, Kui Wu 0003, Edward Chien

We develop a method for automatic placement of knit singularities based on curl quantization, extending the knit-planning frameworks of Mitra et al. [2024; 2023]. Stripe patterns are generated that closely follow the isolines of an underlying knitting time function, and has course and wale singularities in regions of high curl for the normalized time function gradient and its 90° rotated field, respectively. Singularities are placed in an iterative fashion, and we show that this strategy allows us to easily maintain the structural constraints necessary for machine-knitting, e.g., the helix-free constraint, and to satisfy user constraints such as stripe alignment and singularity placement. Our more performant approach obviates the need for a mixed-integer solve [Mitra et al. 2023], manual fixing of singularity positions, or the running of a singularity matching procedure in post-processing [Mitra et al. 2024]. Our global optimization also produces smooth knit graphs that provide quick simulation-free previews of rendered knits without the surface artifacts of competing methods. Furthermore, we extend our method to the popular cut-and-sew garment design paradigm. We validate our method by machine-knitting and rendering yarn-based visualizations of prototypical models in the 3D and cut-and-sew settings.

Songyin Wu, Zhaoyang Lv, Yufeng Zhu, Duncan P. Frost, Zhengqin Li, Ling-Qi Yan 0001, Carl Yuheng Ren, Richard A. Newcombe, Zhao Dong 0001

We propose an online 3D Gaussian-based dense mapping framework for photorealistic details reconstruction from a monocular image stream. Our approach addresses two key challenges in monocular online reconstruction: distributing Gaussians without relying on depth maps and ensuring both local and global consistency in the reconstructed maps. To achieve this, we introduce two key modules: the Hierarchical Gaussian Management Module for effective Gaussian distribution and the Global Consistency Optimization Module for maintaining alignment and coherence at all scales. In addition, we present the Multi-level Occupancy Hash Voxels (MOHV), a structure that regularizes Gaussians for capturing details across multiple levels of granularity. MOHV ensures accurate reconstruction of both fine and coarse geometries and textures, preserving intricate details while maintaining overall structural integrity. Compared to state-of-the-art RGB-only and even RGB-D methods, our framework achieves superior reconstruction quality with high computational efficiency. Moreover, it integrates seamlessly with various tracking systems, ensuring generality and scalability. Project page: https://poiw.github.io/MODP/.

Lei Lan, Tianjia Shao, Zixuan Lu, Yu Zhang 0090, Chenfanfu Jiang, Yin Yang 0002

3D Gaussian Splatting (3DGS) has emerged as a mainstream solution for novel view synthesis and 3D reconstruction. By explicitly encoding a 3D scene using a collection of Gaussian kernels, 3DGS achieves high-quality rendering with superior efficiency. As a learning-based approach, 3DGS training has been dealt with the standard stochastic gradient descent (SGD) method, which offers at most linear convergence. Consequently, training often requires tens of minutes, even with GPU acceleration. This paper introduces a (near) second-order convergent training algorithm for 3DGS, leveraging its unique properties. Our approach is inspired by two key observations. First, the attributes of a Gaussian kernel contribute independently to the image-space loss, which endorses isolated and local optimization algorithms. We exploit this by splitting the optimization at the level of individual kernel attributes, analytically constructing small-size Newton systems for each parameter group, and efficiently solving these systems on GPU threads. This achieves Newton-like convergence per training image without relying on the global Hessian. Second, kernels exhibit sparse and structured coupling across input images. This property allows us to effectively utilize spatial information to mitigate overshoot during stochastic training. Our method converges an order faster than standard GPU-based 3DGS training, requiring over 10 × fewer iterations while maintaining or surpassing the quality of the compared with the SGD-based 3DGS reconstructions.

Ellie Arar, Yarden Frenkel, Daniel Cohen-Or, Ariel Shamir, Yael Vinker

Recent advancements in large vision-language models have enabled highly expressive and diverse vector sketch generation. However, state-of-the-art methods rely on a time-consuming optimization process involving repeated feedback from a pretrained model to determine stroke placement. Consequently, despite producing impressive sketches, these methods are limited in practical applications. In this work, we introduce SwiftSketch, a diffusion model for image-conditioned vector sketch generation that can produce high-quality sketches in less than a second. SwiftSketch operates by progressively denoising stroke control points sampled from a Gaussian distribution. Its transformer-decoder architecture is designed to effectively handle the discrete nature of vector representation and capture the inherent global dependencies between strokes. To train SwiftSketch, we construct a synthetic dataset of image-sketch pairs, addressing the limitations of existing sketch datasets, which are often created by non-artists and lack professional quality. For generating these synthetic sketches, we introduce ControlSketch, a method that enhances SDS-based techniques by incorporating precise spatial control through a depth-aware ControlNet. We demonstrate that SwiftSketch generalizes across diverse concepts, efficiently producing sketches that combine high fidelity with a natural and visually appealing style.

Jerry Hsu, Tongtong Wang, Kui Wu 0003, Cem Yuksel

Cosserat rods have become an increasingly popular framework for simulating complex bending and twisting in thin elastic rods, used for hair, tree, and yarn-level cloth models. However, traditional approaches often encounter significant challenges in robustly and efficiently solving for valid quaternion orientations, even when employing small time steps or computationally expensive global solvers. We introduce stable Cosserat rods, a new solver that can achieve high accuracy with high stiffness levels and maintain stability under large time steps. It is also inherently suitable for parallelization. Our key contribution is a split position and rotation optimization scheme with a closed-form Gauss-Seidel quasi-static orientation update. This solver significantly improves the numerical stability with Cosserat rods, allowing faster computation and larger time steps. We validate our method across a wide range of applications, including simulations of hair, trees, yarn-level cloth, slingshots, and bridges, demonstrating its ability to handle diverse material behaviors and complex geometries. Furthermore, we show that our method is orders of magnitude faster and more stable than alternative rod solvers, such as extended position-based dynamics and discrete elastic rods.

Jianqi Chen, Biao Zhang, Xiangjun Tang, Peter Wonka

We present V2M4, a novel 4D reconstruction method that directly generates a usable 4D mesh animation asset from a single monocular video. Unlike existing approaches that rely on priors from multi-view image and video generation models, our method is based on native 3D mesh generation models. Naively applying 3D mesh generation models to generate a mesh for each frame in a 4D task can lead to issues such as incorrect mesh poses, misalignment of mesh appearance, and inconsistencies in mesh geometry and texture maps. To address these problems, we propose a structured workflow that includes camera search and mesh reposing, condition embedding optimization for mesh appearance refinement, pairwise mesh registration for topology consistency, and global texture map optimization for texture consistency. Our method outputs high-quality 4D animated assets that are compatible with mainstream graphics and game software. Experimental results across a variety of animation types and motion amplitudes demonstrate the generalization and effectiveness of our method.