While the human eye can perceive an impressive twenty stops of dynamic range, smartphone camera sensors remain limited to about twelve stops despite decades of research. A variety of high dynamic range (HDR) image capture and processing techniques have been proposed, and, in practice, they can extend the dynamic range by 3–5 stops for handheld photography. This paper proposes an approach that robustly captures dynamic range using a handheld smartphone camera and lightweight networks suitable for running on mobile devices. Our method operates indirectly on linear raw pixels in bracketed exposures. Every pixel in the final HDR image is a convex combination of input pixels in the neighborhood, adjusted for exposure, and thus avoids hallucination artifacts typical of recent deep image synthesis networks. We validate our system on both synthetic imagery and unseen real bracketed images — we confirm zero-shot generalization of the method to smartphone camera captures. Our iterative inference architecture is capable of processing an arbitrary number of bracketed input photos, and we show examples from capture stacks containing 3–9 images. Our training process relies only on synthetic captures yet generalizes to unseen real photos from several cameras. Moreover, we show that this training scheme improves other SOTA methods over their pretrained counterparts. Project page: https://lucky-hdr.github.io/.
论文检索
输入标题、作者或关键词，从 1,712 篇学术成果中精准定位
We introduce a high-performance framework for solving nonconvex optimization problems arising in simulation and geometry processing applications. Our framework especially benefits high-dimensional problems whose unknowns are spatial coordinates in ℝd and whose objectives are expressed as a sum of element energies over small stencils. The Hessians of these problems have a block-sparse structure, where the nonzero entries are grouped into dense d × d blocks. Many works have exploited this structure to speed up the Hessian-vector products and nodal smoothers of iterative solvers. In contrast, accelerating direct sparse linear solvers, preferred for applications requiring high accuracy on unstructured grids, has been less explored. Our framework leverages block structure to accelerate all phases of a Newton-type minimization algorithm, from sparsity pattern construction to system assembly, matrix factorization, and solves. A fundamental piece of the framework is BlockCatamari, our highly tuned, block-accelerated multifrontal sparse Cholesky code that achieves significantly faster factorizations than existing direct solvers on shared-memory systems. We combine this solver with our fast parallel Hessian assembly routine, heuristics for conditionally enabling per-element Hessian projections, and strategies for minimizing symbolic factorization re-computations. We show that this leads to dramatic speedups on a large suite of benchmark problems involving injective surface parametrization and elasticity simulation with contact, and we further demonstrate the ease with which new energies can be defined at the different levels of abstraction offered by our framework.
While yarn-level garments offer rich dynamic details and compelling visual realism compared to triangle-based models, their wide adoption is hindered by the immense computational cost due to the presence of a large number of degrees of freedom (DOFs). This paper proposes a novel simulation framework designed to enhance the performance and stability for numerical simulation of nonlinear, non-convex, and high-resolution knitwear. Our method generalizes the Douglas-Rachford Splitting (DRS) scheme to resolve the non-convex coupling between stretching, shearing, bending, twisting, and contacting at each yarn thread. A key contribution is a nested decomposition strategy that decouples the non-convex variational energy into independent and convex sub-problems. Such convexification improves solver robustness and removes the necessity for frequent line searches. We provide a theoretically grounded strategy for metric selection for each sub-problem, derived from an analysis of the convergence guarantee of DRS. Consequently, our method achieves close-to-optimal convergence along the nonlinear iterations rather than relying on ad-hoc parameter tuning. The paper also clarifies a formal connection between our generalized DRS and the ADMM (Alternating Direction Method of Multipliers) framework, extending the applicability of our analysis to a broader set of constrained dynamics problems. Experimental results demonstrate that our method robustly handles complex knitwear simulation scenes with superior efficiency, stability, and physical fidelity compared to existing methods. With a matrix-free GPU parallelization, our method allows an interactive simulation rate of knitwear of multi-million DOFs.
The intricate motion arising from fluid-boundary interactions is visually compelling, yet notoriously difficult and computationally expensive to simulate in the presence of complex boundaries. Accurately resolving boundary geometry requires body-fitted grids constructed via cut-cell methods, which often leads to poorly conditioned linear systems in the pressure projection stage and, consequently, prohibitive computational cost. We present FastVEM, an efficient boundary-conforming fluid simulation framework that enables high-fidelity flow-boundary interaction at substantially reduced cost. Computational efficiency is achieved through a coordinated, top-down design spanning numerical discretization, grid construction, and linear solvers. FastVEM adopts a Virtual Element Method (VEM) discretization to robustly enforce incompressibility and boundary conditions on irregular body-fitted grids, and employs a VEM polynomial-space Particle-in-Cell scheme for advection. Complementing this discretization, a convexity-preserving cut-cell strategy is introduced to construct simulation-friendly body-fitted grids. To accelerate pressure projection, we develop a Galerkin geometric multi-grid solver featuring a diffusion-free prolongation operator that prevents coarse-level matrix densification, along with a nested, boundary-aware grid hierarchy that ensures well-posed placement of coarse-level degrees of freedom. Compared to prior cut-cell-based fluid simulators, FastVEM speeds up the computationally dominant pressure projection stage by up to 100×, while robustly handling even more challenging boundary geometries.
A variety of problems in geometry processing boil down to finding the most parallel field relative to a connection. Instances of this prototypical problem show up in computing direction fields and stripe patterns, quadrilateral meshing, and visualization of fluid flows. When the class of allowed fields includes those with topological defects, a relaxation is required to make the problem well-posed. We observe that these problems can be viewed as synchronization problems, which admit a natural semidefinite relaxation. We propose a unified method of solving all these problems via the efficient Burer-Monteiro factorization method. Geometrically, this amounts to lifting the field values to a higher-dimensional manifold, naturally resolving the singular nature of defects. Practically, we show that our convex relaxation method achieves better and more reliable optima than previous work employing alternative relaxations.
Computing injective, flip-free embeddings of simplicial meshes is a fundamental challenge in geometry processing. While the Total Lifted Content (TLC) energy provides a smooth functional with theoretically guaranteed injective global minima, its non-convex nature presents significant optimization hurdles. In this work, we propose a Nonlinear Multigrid (MG/Opt) framework specifically tailored for efficient TLC energy minimization. Our approach leverages a topology-preserving mesh hierarchy to rapidly eliminate low-frequency errors on coarse scales while maintaining rigorous gradient consistency between hierarchical levels through linear correction terms. To address the persistent challenge of local inversions, we introduce a targeted smoothing strategy and an adaptive parameter scheduling mechanism that balances global convergence speed with local injectivity precision. Experimental evaluations across extensive 2D and 3D benchmark datasets demonstrate the robustness of our approach. Our method achieves a 100% convergence success rate across all tested 2D cases and all but one 3D dataset (the VOLMAP benchmark). Furthermore, our MG/Opt framework delivers substantial performance gains, achieving up to 63 × speedup on high-resolution subdivided datasets compared to traditional solvers. These results confirm that our multigrid strategy provides a scalable and reliable solution for large-scale injective mapping problems. Code and data for this paper are at https://github.com/distmeshM/MGOpt_TLC
Voronoi diagrams, and their more general weighted counterpart, power diagrams, are fundamental geometric constructs with wide-ranging applications in biology, physics simulation, and computer graphics. Recently, they have gained renewed attention in mesh-based neural rendering. Despite being extensively studied, the construction of 3D Voronoi diagrams for large-scale point sets remains computationally expensive, limiting their adoption in large-scale applications. Existing CPU-based approaches typically rely on computing its dual, the Delaunay tetrahedralization, but are prohibitively slow for large diagrams, while GPU-based methods either struggle to scale efficiently to large point sets or assume homogeneous point distributions. The weighted case, power diagrams, is even less explored in this context. Existing approaches are typically tailored to the application at hand, assuming homogeneous point distributions and small weight variations, making them unsuitable for general use in more complex heterogeneous data. In this paper, we present a highly parallelizable GPU algorithm for the fast construction of large-scale 3D Voronoi and power diagrams. Our approach constructs each convex cell from a weighted 3D point by progressively clipping an initial cell volume against bisecting planes induced by candidate neighboring points. To efficiently identify candidate neighbors under arbitrary spatial distributions, we introduce a culling criterion based on directional geometric bounds of the evolving cell, combined with a hierarchical best-first traversal of bounding volumes. We achieve performance on par with state-of-the-art Delaunay tetrahedralization methods on small and moderate problem sizes, while exhibiting robust scalability to large point sets and diverse spatial distributions. Moreover, our method naturally generalizes to power diagrams without additional assumptions. To facilitate reproducibility and future research, we release our source code, see https://research.zenseact.com/publications/paragram.
Data powers almost everything we experience on the web today---from the recommendations and ads we see to the AI systems and online marketplaces that shape our digital interactions. The increasing demand for high-quality data has given rise to platforms that facilitate the buying and selling of data. A key practical challenge in such markets is determining how to price data. Competitive equilibrium (CE), a foundational concept in classical market economics, determines prices for rivalrous goods by matching their supply and demand. In this work, we initiate the study of CE in data markets, explicitly incorporating the role of data in improving predictive performance in buyers' utility functions, and the non-rival nature of data by adapting the standard market-clearing condition to allow the simultaneous allocation of data records to multiple buyers. We analyze the existence, structure, and computation of CE in such data markets. We establish that CE always exists, and almost all instances admit a unique and rational equilibrium price vector. In general, however, there could be a non-convex set of prices, which rules out convex-programming approaches for finding a CE. Despite these challenges, we design an FPTAS for computing approximate equilibria using a Walrasian-style price adjustment algorithm. Our framework opens avenues for studying richer buyer utilities under correlated data sellers, and deeper structural and algorithmic aspects of data markets.
Ranking-dependent DeFi protocols create participation barriers for small-volume stakeholders due to competitive disadvantages based on fund size rankings. Our analysis reveals that brokers with higher fund balances achieve better revenue performance, disadvantaging smaller investors. We introduce LiquidityPool, a fund aggregation protocol that enables collective participation in ranking-dependent DeFi environments by pooling resources from multiple stakeholders. Through game-theoretic analysis of multi-leader multi-follower Stackelberg competition, we establish theoretical results that differ from traditional competition assumptions. Our analysis reveals knife-edge equilibrium properties where symmetric multi-party competition exists only under restrictive initial conditions. When initial asymmetry exceeds a critical threshold, protocols converge to a monopolistic market structure regardless of the starting configuration. We show that monopolistic concentration performs better than fragmented competition in terms of social welfare, contrary to the predictions of classical Bertrand and Cournot competition. This occurs because convex revenue functions create economies of scale that favor fund aggregation over competitive fragmentation. Experimental validation using real Ethereum blockchain data shows monopolization across different market structures. While welfare improvements are modest due to concentrated wealth distribution, LiquidityPool enables 98% of small-volume stakeholders to participate in protocols that were previously inaccessible. These findings suggest that traditional antitrust policies promoting market fragmentation may not be effective in ranking-dependent DeFi networks, where concentration enables rather than restricts efficient resource allocation and stakeholder accessibility.
Recent progress in Large Language Models (LLMs) has transformed text and code generation, yet models still falter on Partial Differential Equations (PDEs) where correctness, constraints, and physical consequences are critical. We explore how formal LLM reasoning can advance symbolic PDE modeling. First, our PDE-Controller formalizes informal PDEs, synthesizes solver-ready code, and plans subgoals to tackle nonconvex control via interactions with external solvers. Second, our Lean Finder accelerates PDE formalization via a semantics-aware search engine for Lean/Mathlib that retrieves relevant theorems, outperforming GPT models and gaining significant traction in the AI-for-math community. Through these efforts, we aim to design a semantics-first LLM that autoformalizes informal PDE problems into machine-checked specifications and synthesizes solver-ready code. This closes the loop between formal analysis and LLM reasoning, ultimately surpassing human heuristics across PDEs.
Fairness auditing aims to assess whether a model is fair, playing a critical role in identifying potential risks in deployed AI systems. In practice, due to limited access, third-party auditors often rely on self-collected datasets (e.g., via sock-puppets), which may differ from real-world deployment scenarios. Such discrepancy can lead to inconsistencies between audit conclusions on the collected data and those in actual deployment, raising concerns about the reliability of third-party audits. This motivates a critical question: When can we trust the fairness audit conclusion derived from third-party datasets? Answering this question is challenging, as the actual deployment distribution is typically inaccessible or unobservable. To tackle this, we introduce the Consistency Radius, a metric that quantifies the maximum distribution shift under which an audit conclusion based on third-party dataset remain consistent. We further propose a convex relaxation optimization-based method to estimate the radius relying solely on model responses over the audit dataset. Leveraging this framework, third-party auditors can provide their datasets to model providers and request the magnitude of distributional discrepancy relative to the deployment distribution, enabling reliable audit conclusions without requiring any direct data access.
Activated PI3Kδ Syndrome (APDS) is a rare genetic immune disorder caused by variants in PIK3CD or PIK3R1, with highly heterogeneous symptoms that often delay diagnosis. Early recognition is hampered by overlapping clinical presentations and limited clinician awareness, motivating systematic, data-driven approaches to detect APDS-associated phenotypic patterns in routine electronic health records. Traditional linear scoring systems cannot capture complex symptom interactions, while deep learning models, though expressive, often lack interpretability. To bridge this gap, we propose Shapley regression, a novel game-theoretic model replacing the linear predictor with a k-additive cooperative game, explicitly modeling co-occurrence of symptoms while maintaining the transparency and convexity of logistic regression. We carry out an empirical study of our lightweight method on eight public biomedical datasets, showing that a 2-additive model with ℓ2 regularization achieves an optimal trade-off between predictive power and noise robustness. We apply it to a real-world cohort of 222 patients, on which Shapley regression accurately distinguished APDS cases from matched controls, confirming and validating phenotypes known to be associated with APDS, and facilitating the exploration of pairwise interactions between symptoms, validated by clinical experts.
Ensuring the safety of probabilistic systems is a central challenge in formal verification. We propose an automated refinement technique for verifying a safety property of posterior distributions in probabilistic programs. Our approach builds on the counterexample-guided abstraction refinement (CEGAR) framework and exploits the duality in convex optimisation and the adequacy of predicate-transformer semantics in probabilistic settings. We implement the technique and evaluate its effectiveness through preliminary experiments.
Convex clustering is a well-regarded clustering method, resembling the similar centroid-based approach of Lloyd's $k$-means, without requiring a predefined cluster count. It starts with each data point as its centroid and iteratively merges them. Despite its advantages, this method can fail when dealing with data exhibiting linearly non-separable or non-convex structures. To mitigate the limitations, we propose a kernelized extension of the convex clustering method. This approach projects the data points into a Reproducing Kernel Hilbert Space (RKHS) using a feature map, enabling convex clustering in this transformed space. This kernelization not only allows for better handling of complex data distributions but also produces an embedding in a finite-dimensional vector space. We provide a comprehensive theoretical underpinning for our kernelized approach, proving algorithmic convergence and establishing finite sample bounds for our estimates. The effectiveness of our method is demonstrated through extensive experiments on both synthetic and real-world datasets, showing superior performance compared to state-of-the-art clustering techniques. This work marks a significant advancement in the field, offering an effective solution for clustering in non-linear and non-convex data scenarios.
The quantal response (QR) model is widely used in Stackelberg security games (SSGs) to capture boundedly rational adversaries. Existing work on SSGs under QR, however, almost exclusively assumes a homogeneous attacker population, ignoring heterogeneity in attacker preferences and rationality. We study SSG with mixed quantal response attackers, where the follower population consists of multiple discrete attacker types, each following a type-specific QR model. The defender allocates limited resources across targets, while an attacker drawn from this heterogeneous population observes the defender’s strategy and attacks a single target. This results in a highly non-convex equilibrium computation problem. We develop a polynomial-time approximation scheme (PTAS) for this setting when the number of attacker types is bounded, based on an exponential cone programming formulation combined with a carefully designed Branch-and-Bound procedure. Experiments demonstrate that our approach outperforms standard gradient-based methods and that explicitly modeling attacker heterogeneity yields significant gains over traditional SSG models with a single QR attacker.
This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a Õ(d √T) regret, where d is the dimension of the action vector and T is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a Õ(d √T) α-regret; for general compact sets lacking strong convexity, we establish a Õ(d T^(2/3)) α-regret, where α pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments.
Privacy concerns in distributed learning often lead clients to return intentionally altered gradient information. We consider the problem of learning convex and L-smooth functions under adversarial gradient perturbation, where a client's gradient reply to a server query can deviate arbitrarily from the true gradient subject to a distance bound. Our study focuses on two fundamental questions: (i) what is the smallest achievable sub-optimality gap (i.e., excess error in optimization) under such responses, and (ii) how many queries are sufficient to guarantee a given sub-optimality gap? We establish tight feasibility thresholds on the sub-optimality gap and provide algorithms that achieve these thresholds with provable query complexity guarantees.
The three-dimensional bin packing problem (3D-BPP) is widely applied in logistics and warehousing. However, existing learning-based approaches often neglect stability constraints and struggle to generalize across diverse bin dimensions. To address this, we propose a novel deep reinforcement learning framework, One4Many-StablePacker (O4M-SP). The primary advantage of O4M-SP lies in its ability to handle variable bin dimensions in a single training process while explicitly enforcing two types of practical stability constraints: support constraints, which ensure an item's bottom center lies within the convex hull of the underlying contact area, and weight constraints, which restrict the total vertical load on an item to its bearing capacity. Our training method introduces two innovative mechanisms. First, a weighted reward function integrates the loading rate with a novel height difference metric for packing layouts, promoting improved bin utilization via flatter packing configurations. Second, clipped policy gradient optimization with tailored policy drifting mitigates entropy collapse, encouraging exploration at critical decision nodes during packing to prevent premature convergence. Extensive experiments demonstrate that O4M-SP generalizes effectively across diverse bin dimensions and significantly outperforms baseline methods. Furthermore, the framework exhibits strong practical applicability by solving complex scenarios under strict stability constraints.
Training a unified language model that adapts between intuitive System 1 and deliberative System 2 remains challenging due to interference between their cognitive modes. Recent studies have thus pursued making System 2 models more efficient. However, these approaches focused on output control, limiting what models produce. We argue that this paradigm is misaligned: output length is merely a symptom of the model's cognitive configuration, not the root cause. In this work, we shift the focus to capability control, which modulates how models think rather than what they produce. To realize this, we leverage existing Instruct and Thinking checkpoints through dynamic parameter interpolation, without additional training. Our pilot study establishes that linear interpolation yields a convex, monotonic Pareto frontier, underpinned by representation continuity and structural connectivity. Building on this, we propose DAMI (DynAmic Model Interpolation), a framework that estimates a query-specific Reasoning Intensity lambda(q) to configure cognitive depth. For training-based estimation, we develop a preference learning method encoding accuracy and efficiency criteria. For zero-shot deployment, we introduce a confidence-based method leveraging inter-model cognitive discrepancy. Experiments on five mathematical reasoning benchmarks demonstrate that DAMI achieves higher accuracy than the Thinking model while remaining efficient, effectively combining the efficiency of System 1 with the reasoning depth of System 2.
Tailored ViT Slimming: Budget-Aware Multi-Dimensional Sparsity Regularization for Vision Transformers Pruning (Student Abstract)
PDF ↗We propose Tailored ViT Slimming (TVS), a budget-aware multi-dimensional pruning framework for Vision Transformers. TVS injects learnable masks into MHSA and MLP modules and applies adaptive non-convex sparsity regularization to achieve maximal utilization of parameters under strict module-wise budgets. In addition, by retaining scaled masks after pruning, TVS avoids abrupt accuracy drops and provides stable initialization for fine-tuning. On ImageNet-1k with DeiT-S and DeiT-B, TVS consistently outperforms prior ViT compression methods. This result empirically shows that the non-convex sparsity regularizer is effective not only in CNNs but also in ViTs.