Bounding the integrality distance of LP relaxations for structured prediction

By Ben London, Ofer Meshi, Adrian Weller
2016
Download Copy BibTeX
Copy BibTeX
In structured prediction, a predictor optimizes an objective function over a combinatorial search space, such as the set of all image segmentations, or the set of all part-of-speech taggings. Unfortunately, finding the optimal structured labeling—sometimes referred to as maximum a posteriori (MAP) inference—is, in general, NP-hard [12], due to the combinatorial structure of the problem. Many inference approximations have been proposed, some of which are based on linear programming (LP) relaxations [e.g., 5, 1, 15, 16, 4, 13], which “relax” the combinatorial search space to a convex polytope with a polynomial number of constraints. These LP relaxations can be solved efficiently, but may result in fractional solutions, i.e., non-integral labelings. The approximation quality of an LP relaxation is traditionally measured by a quantity known as the integrality gap, defined as the difference in the objective values obtained at the optima of the relaxed and exact problems. When the integrality gap is zero, the solution is said to be tight.
Tags

Latest news

US, MA, North Reading
Working at Amazon Robotics Are you inspired by invention? Is problem solving through teamwork in your DNA? Do you like the idea of seeing how your work impacts the bigger picture? Answer yes to any of these and you’ll fit right in here at Amazon Robotics. We are a smart, collaborative team of doers that work passionately to apply cutting-edge advances in robotics and software to solve real-world challenges that will transform our customers’ experiences in ways we can’t even imagine yet. We invent new improvements every day. We are Amazon Robotics and we will give you the tools and support you need to invent with us in ways that are rewarding, fulfilling and fun. Position Overview The Amazon Robotics (AR) Software Research and Science team builds and runs simulation experiments and delivers analyses that are central to understanding the performance of the entire AR system. This includes operational and software scaling characteristics, bottlenecks, and robustness to “chaos monkey” stresses -- we inform critical engineering and business decisions about Amazon’s approach to robotic fulfillment. We are seeking an enthusiastic Data Scientist to design and implement state-of-the-art solutions for never-before-solved problems. The DS will collaborate closely with other research and robotics experts to design and run experiments, research new algorithms, and find new ways to improve Amazon Robotics analytics to optimize the Customer experience. They will partner with technology and product leaders to solve business problems using scientific approaches. They will build new tools and invent business insights that surprise and delight our customers. They will work to quantify system performance at scale, and to expand the breadth and depth of our analysis to increase the ability of software components and warehouse processes. They will work to evolve our library of key performance indicators and construct experiments that efficiently root cause emergent behaviors. They will engage with software development teams and warehouse design engineers to drive the evolution of the AR system, as well as the simulation engine that supports our work. Inclusive Team Culture Here at Amazon, we embrace our differences. We are committed to furthering our culture of inclusion. We have 12 affinity groups (employee resource groups) with more than 87,000 employees across hundreds of chapters around the world. We have innovative benefit offerings and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences. Amazon’s culture of inclusion is reinforced within our 14 Leadership Principles, which reminds team members to seek diverse perspectives, learn and be curious, and earn trust. Flexibility It isn’t about which hours you spend at home or at work; it’s about the flow you establish that brings energy to both parts of your life. We offer flexibility and encourage you to find your own balance between your work and personal lives. Mentorship & Career Growth We care about your career growth too. Whether your goals are to explore new technologies, take on bigger opportunities, or get to the next level, we'll help you get there. Our business is growing fast and our people will grow with it. A day in the life Amazon offers a full range of benefits that support you and eligible family members, including domestic partners and their children. Benefits can vary by location, the number of regularly scheduled hours you work, length of employment, and job status such as seasonal or temporary employment. The benefits that generally apply to regular, full-time employees include: 1. Medical, Dental, and Vision Coverage 2. Maternity and Parental Leave Options 3. Paid Time Off (PTO) 4. 401(k) Plan If you are not sure that every qualification on the list above describes you exactly, we'd still love to hear from you! At Amazon, we value people with unique backgrounds, experiences, and skillsets. If you’re passionate about this role and want to make an impact on a global scale, please apply! We are open to hiring candidates to work out of one of the following locations: North Reading, MA, USA
US, MA, Boston
The Artificial General Intelligence (AGI) - Automations team is developing AI technologies to automate workflows, processes for browser automation, developers and ops teams. As part of this, we are developing services and inference engine for these automation agents, and techniques for reasoning, planning, and modeling workflows. If you are interested in a startup mode team in Amazon to build the next level of agents then come join us. Scientists in AGI - Automations will develop cutting edge multimodal LLMs to observe, model and derive insights from manual workflows to automate them. You will get to work in a joint scrum with engineers for rapid invention, develop cutting edge automation agent systems, and take them to launch for millions of customers. Key job responsibilities - Build automation agents by developing novel multimodal LLMs. A day in the life An Applied Scientist with the AGI team will support the science solution design, run experiments, research new algorithms, and find new ways of optimizing the customer experience.; while setting examples for the team on good science practice and standards. Besides theoretical analysis and innovation, an Applied Scientist will also work closely with talented engineers and scientists to put algorithms and models into practice. We are open to hiring candidates to work out of one of the following locations: Boston, MA, USA
US, WA, Bellevue
Amazon Fulfillment Planning & Execution (FPX) Science team within Supply Chain Optimization Technologies (SCOT) Fulfilment Optimization group is seeking a Principal Research Scientist with expertise in Machine Learning and a proven record of solving business problems through scalable ML solutions. Network Planning and Fulfillment Execution tackles some of the most mathematically complex challenges in facility and transportation planning to improve Amazon's operational efficiency worldwide. We own Amazon’s global fulfillment center and transportation topology planning and execution. The team also owns the short-term network planning that determines the optimal flow of customer orders through Amazon fulfillment network. This includes developing sophisticated math models and controllers that assign orders to fulfillment centers to be picked and packed and then planning the optimal ship method in terms of cost, speed and carbon impact to deliver to the customer. These plans drive downstream decisions that are in the billions of dollars. The systems we build are entirely in-house, and are on the cutting edge of both academic and applied research in large scale supply chain planning, optimization, machine learning and statistics. These systems operate at various scales, from real-time decision system that completes thousands of transactions per seconds, to large scale distributed system that optimize Amazon’s fulfillment network. As Amazon continues to build and expand the first party delivery network, this role will be critical to realize this vision. Your tech solution will have large impacts to the physical supply chain of Amazon, and play a key role in improving Amazon consumer business’s long-term profitability. If you are interested in diving into a multi-discipline, high impact space this is the team for you. Key job responsibilities As a Principal Research Scientist within FPX Science team, you will propose and deploy solutions that will likely draw from a range of scientific areas such as supervised, semi-supervised and unsupervised learning, reinforcement learning, advanced statistical modeling, and graph models. You will have an opportunity to be on the forefront of supply chain thought leadership by working on some of the most difficult problems in the industry, with some of the best product managers, research scientists, statisticians, and software engineers to integrate scientific work into production systems. You will partner with the senior tech leaders in the organization to define the long-term vision of our Network Planning and Fulfillment Execution systems. You will play a key role in developing long term strategic solutions that have business impact beyond the scope of the organization. You will bring deep technical expertise in the area of Machine Learning, and will play an integral part in building Amazon's Fulfillment Optimization systems. Other responsibilities include: • Research and develop machine learning models to solve diverse business problems faced within Network Planning and Fulfillment Execution team. • Drive and execute machine learning projects/products end-to-end: from ideation, analysis, prototyping, development, metrics, and monitoring. • Review and audit modeling processes and results for other scientists, both junior and senior. • Advocate the right ML solutions to business stakeholders, engineering teams, as well as executive level decision makers • You will ensure senior leaders in the organization are up to speed on important trends, tools and technologies and how they will be used to impact the business. A day in the life In this role, you will be a technical leader in machine learning with significant scope, impact, and high visibility. Your solutions will impact business segments worth many-billions-of-dollars and geographies spanning multiple countries and markets. As a Principal Research Scientist on the team, you will be involved in every aspect of the process - from ideation, business analysis and scientific research, through to development and deployment of advanced models - giving you a real sense of ownership. From day one, you will be working with bar raising scientists, engineers, and designers. You are expected to make decisions about technology, models and methodology choices. You will also collaborate with the broader science community in Amazon to broaden the horizon of your work and mentor engineers and other scientists. We are seeking someone who wants to lead projects that require innovative thinking and deep technical problem-solving skills to create production-ready machine learning solutions. A successful candidate is able to quickly approach large ambiguous problems, turn high-level business requirements into mathematical models, identify the right solution approach, and contribute to the software development for production systems. Successful candidates must thrive in fast-paced environments, which encourage collaborative and creative problem solving, be able to measure and estimate risks, constructively critique peer research, and align research focuses with the Amazon's strategic needs. We look for individuals who know how to deliver results and show a desire to develop themselves, their colleagues, and their career. About the team FPX Science team contains a group of scientists with different technical backgrounds including Machine Learning and Operations Research, who will collaborate closely with you on your projects. Our team directly supports multiple functional areas across Fulfillment Optimization and the research needs of the corresponding product and engineering teams. We tackle some of the most mathematically complex challenges in facility and transportation planning to improve Amazon's operational efficiency worldwide and at a scale that is unique to Amazon. We often seek the opportunity of applying hybrid techniques in the space of Operations Research and Machine Learning to tackle some of our biggest technical challenges. We disambiguate complex supply chain problems and create ML and optimization solutions to solve those problems at scale. We are open to hiring candidates to work out of one of the following locations: Bellevue, WA, USA
US, WA, Bellevue
Have you ever placed an order on Amazon and wondered how it got to you- or how it got to you so fast? Do you get excited thinking about the data and technology that power complex transportation networks and would like to build some of the models enabling their growth? Then, come join Network Engineering, Scheduling and Technology (NEST) Science team within the Amazon Transportation Services and help us innovate the way packages flow to our customers. We are looking for a Data Scientist specializing in the development of simulation and optimization algorithms applied to network planning and transportation labor management. This includes the development, enhancements and implementation of predictive and prescriptive components within the network, and creating analytical tools to improve network planning solutions. The successful candidate will have strong modeling skills and is comfortable owning their own data and working from concept through to execution, including the software implementation in a production environment in collaboration with software development teams. A qualified candidate is a problem-solver and should have demonstrated ability to build methodology and tools that are statistically grounded. The ideal candidate will have curiosity towards developing self-service and/or fully automated optimization and machine learning applications. Key job responsibilities Design and contribute to the components of automated prediction and optimization applications dictating key planning outputs in transportation planning and labor management Developing code (Python, R, Scala, etc.) for analyzing data and building statistical models to solve specific business problems; improving upon existing methodologies by developing new data sources, testing model enhancements, and fine-tuning model parameters. Building science-based applications leveraging discrete event, agent based simulation methods, applications (AnyLogic, Arena, etc.) OR optimization methods, solvers (Gurobi, Xpress, CPLEX, AMPL, etc.) Manipulating/mining data from databases (Redshift, SQL Server, S3) Collaborating with other scientists, product managers and engineering teams to design and implement software solutions for problems within the Amazon Transportation network Communicating verbally and in writing to business customers and leadership team with various levels of technical knowledge, educating them about our systems, as well as sharing insights and recommendations We are open to hiring candidates to work out of one of the following locations: Bellevue, WA, USA
US, WA, Seattle
Amazon Shipping and Delivery Support (SDS) Tech team is seeking a passionate and customer-obsessed Senior Data Scientist to join our science team. You will use scientific research and rigorous analytics to influence our program and product strategies in driver and recipient support, solve complex problems at large scale, and drive intelligence and innovation in decision making. In this role, your main focus is to perform analysis, synthesize information, identify business opportunities, provide project direction, and communicate design and technical requirements within the team and across stakeholder groups. You will assist in defining trade-offs and quantifying opportunities for a variety of projects. You will learn current processes, build metrics, educate diverse stakeholder groups, assist product and tech teams in initial solution design, and audit new process flow implementations. Key job responsibilities * Provide thought leadership and support the development of continuously-evolving business analytics and data models, own the quantitative analysis of project opportunity and ROI. * Translate difficult business problem statements into data science frameworks; build, evaluate, and optimize statistical and machine learning models to solve focused business problems. * Retrieve, analyze, and synthesize critical data into a format that is immediately useful to answering specific questions or informing operational decisions. * Collaborate with product, program, and operations teams to design experiments (A/B Test) and analyze results to support launch decisions. * Conduct written and verbal presentations to share insights to audiences of varying levels of technical sophistication. A day in the life If you are not sure that every qualification on the list above describes you exactly, we'd still love to hear from you! At Amazon, we value people with unique backgrounds, experiences, and skillsets. If you’re passionate about this role and want to make an impact on a global scale, please apply! Amazon offers a full range of benefits that support you and eligible family members, including domestic partners and their children. Benefits can vary by location, the number of regularly scheduled hours you work, length of employment, and job status such as seasonal or temporary employment. The benefits that generally apply to regular, full-time employees include: 1. Medical, Dental, and Vision Coverage 2. Maternity and Parental Leave Options 3. Paid Time Off (PTO) 4. 401(k) Plan We are open to hiring candidates to work out of one of the following locations: Bellevue, WA, USA | Seattle, WA, USA
US, VA, Arlington
We are seeking a Data Scientist to join our analytics team. This person will own the design and implementation of scalable and reliable approaches to support or automate decision making throughout the business. You will do this by analyzing data with a variety of statistical techniques and then building, validating, and implementing models based your analysis. You will not be able to do this alone but by building partnerships across data, engineering, and business teams. Key job responsibilities - Apply a range of data science techniques and tools combined with subject matter expertise to solve difficult customer or business problems and cases in which the solution approach is unclear. - Proactively seek to identify business opportunities and insights and provide solutions to automate and optimize key internal and external products based on a broad and deep knowledge of Amazon data, industry best-practices, and work done by other teams. - Dive deep into the data and other models across the business to identify defects or inefficiencies which materially impact the customer or business, but can be mitigated through corrective actions for the AB Ops use case - Acquire this data by accessing data sources and building the necessary SQL/ETL queries or scripts. - Analyze data for trends and input validity by inspecting univariate distributions, exploring bivariate relationships, constructing appropriate transformations, and tracking down the source and meaning of anomalies. - Build models and automated tools using statistical modeling, mathematical modeling, econometric modeling, network modeling, social network modeling, natural language processing, machine learning algorithms, genetic algorithms, and neural networks. - Validate these models against alternative approaches, expected and observed outcome, and other business defined key performance indicators. - Implement these models in a manner which complies with evaluations of the computational demands, accuracy, and reliability of the relevant ETL processes at various stages of production. - Enable product engineering teams to consume your models through services which can directly power customer-facing experiences. - Inspect the key business metrics/KPIs (even if you did not create them) when your analytics work points to potential gaps or opportunities; providing clear, compelling analyses by leveraging your knowledge across the AWS suite of products to support the broader business. We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA | Bellevue, WA, USA | Seattle, WA, USA
GB, London
Re-imagining the realms of what’s possible in advertising. Amazon is re-imagining advertising. Amazon Ads operates at the intersection of eCommerce and advertising and offering a rich array of advertising solutions and audience insights so businesses and brands can create relevant campaigns that produce measurable results. At Amazon Ads, you can build models that impact millions every day. And we’re passionate about solving real-world problems while using cutting-edge machine learning and artificial intelligence to do this. For example, our applied science teams leverage a variety of advanced machine learning and cloud computing techniques to power Amazon's advertising offerings. This includes building algorithms and cloud services using clustering, deep neural networks, and other ML approaches to make ads more relevant while respecting privacy. They develop machine learning models to predict ad outcomes and select the optimal ad for each shopper, context, and advertiser objective, leveraging techniques like multi-task learning, bandit/reinforcement learning, counterfactual estimation, and low-latency extreme ML. The teams also utilize Spark, EMR, and Elasticsearch to extract insights from big data and deliver recommendations to advertisers at scale, continuously improving through offline analysis and impact evaluation. Additionally, they apply generative AI models for dynamic creative optimization and video experimentation and automation. Underpinning these efforts are unique technical challenges, such as operating at unprecedented scale (hundreds of thousands of requests per second with 40ms latency) while respecting privacy and customer trust guarantees, and solving a wide variety of complex computational advertising problems related to traffic quality, viewability, brand safety, and more. Help us take innovation in advertising to the next level. Our teams are based in our fast-growing tech hubs in London and Edinburgh. Learn more about Amazon Ads, employee stories and available opportunities here: https://www.amazon.jobs/content/en/teams/advertising/applied-science-machine-learning-research?ref_=a20m_us_car_lp_asml Key job responsibilities * Design, prototype and test many possible hypotheses in a high-ambiguity environment, making use of both analysis and business judgment. * Collaborate with software engineering teams to integrate successful experiments into large-scale, highly complex Amazon production systems. * Promote the culture of experimentation and applied science at Amazon. * Demonstrate ability to meet deadlines while managing multiple projects. * Excel communication and presentation skills working with multiple peer groups and different levels of management * Influence and continuously improve a sustainable team culture that exemplifies Amazon’s leadership principles We are open to hiring candidates to work out of one of the following locations: Edinburgh, MLN, GBR | London, GBR
GB, London
Have you ever ordered a product on Amazon and when that box with the smile arrived you wondered how it got to you so fast? Have you wondered where it came from and how much it cost Amazon to deliver it to you? We are looking for a Senior Data Scientist who will be responsible to develop cutting-edge scientific solutions to optimize our Pan-European fulfillment strategy, to maximize our Customer Experience and minimize our cost and carbon footprint. You will partner with the worldwide scientific community to help design the optimal fulfillment strategy for Amazon. You will also collaborate with technical teams to develop optimization tools for network flow planning and execution systems. Finally, you will also work with business and operational stakeholders to influence their strategy and gather inputs to solve problems. To be successful in the role, you will need deep analytical skills and a strong scientific background. The role also requires excellent communication skills, and an ability to influence across business functions at different levels. You will work in a fast-paced environment that requires you to be detail-oriented and comfortable in working with technical, business and technical teams. Key job responsibilities - Design and develop mathematical models to optimize inventory placement and product flows. - Design and develop statistical and optimization models for planning Supply Chain under uncertainty. - Manage several, high impact projects simultaneously. - Consult and collaborate with business and technical stakeholders across multiple teams to define new opportunities to optimize our Supply Chain. - Communicate data-driven insights and recommendations to diverse senior stakeholders through technical and/or business papers. We are open to hiring candidates to work out of one of the following locations: London, GBR
GB, London
Re-imagining the realms of what’s possible in advertising. Amazon is re-imagining advertising. Amazon Ads operates at the intersection of eCommerce and advertising and offering a rich array of advertising solutions and audience insights so businesses and brands can create relevant campaigns that produce measurable results. At Amazon Ads, you can build models that impact millions every day. And we’re passionate about solving real-world problems while using cutting-edge machine learning and artificial intelligence to do this. For example, our applied science teams leverage a variety of advanced machine learning and cloud computing techniques to power Amazon's advertising offerings. This includes building algorithms and cloud services using clustering, deep neural networks, and other ML approaches to make ads more relevant while respecting privacy. They develop machine learning models to predict ad outcomes and select the optimal ad for each shopper, context, and advertiser objective, leveraging techniques like multi-task learning, bandit/reinforcement learning, counterfactual estimation, and low-latency extreme ML. The teams also utilize Spark, EMR, and Elasticsearch to extract insights from big data and deliver recommendations to advertisers at scale, continuously improving through offline analysis and impact evaluation. Additionally, they apply generative AI models for dynamic creative optimization and video experimentation and automation. Underpinning these efforts are unique technical challenges, such as operating at unprecedented scale (hundreds of thousands of requests per second with 40ms latency) while respecting privacy and customer trust guarantees, and solving a wide variety of complex computational advertising problems related to traffic quality, viewability, brand safety, and more. Help us take innovation in advertising to the next level. Our teams are based in our fast-growing tech hubs in London and Edinburgh. Learn more about Amazon Ads, employee stories and available opportunities here: https://www.amazon.jobs/content/en/teams/advertising/applied-science-machine-learning-research?ref_=a20m_us_car_lp_asml Key job responsibilities * Design, prototype and test many possible hypotheses in a high-ambiguity environment, making use of both analysis and business judgment. * Collaborate with software engineering teams to integrate successful experiments into large-scale, highly complex Amazon production systems. * Promote the culture of experimentation and applied science at Amazon. * Demonstrate ability to meet deadlines while managing multiple projects. * Excel communication and presentation skills working with multiple peer groups and different levels of management * Influence and continuously improve a sustainable team culture that exemplifies Amazon’s leadership principles * Develop a deep and wide understanding of large ad tech solutions to which you will contribute, and how they interact with components owned by other teams. * Anticipate obstacles and look around corners, effectively prioritising work, solving trade-offs and influencing the development of advertising products beyond the scope of your immediate team. We are open to hiring candidates to work out of one of the following locations: Edinburgh, MLN, GBR | London, GBR
US, VA, Arlington
Are you looking to work at the forefront of Machine Learning and AI? Would you be excited to apply cutting edge Generative AI algorithms to solve real world problems with significant impact? The Generative AI Innovation Center at AWS is a new strategic team that helps AWS customers implement Generative AI solutions and realize transformational business opportunities. This is a team of strategists, data scientists, engineers, and solution architects working step-by-step with customers to build bespoke solutions that harness the power of generative AI. The team helps customers imagine and scope the use cases that will create the greatest value for their businesses, select and train and fine tune the right models, define paths to navigate technical or business challenges, develop proof-of-concepts, and make plans for launching solutions at scale. The GenAI Innovation Center team provides guidance on best practices for applying generative AI responsibly and cost efficiently. You will work directly with customers and innovate in a fast-paced organization that contributes to game-changing projects and technologies. You will design and run experiments, research new algorithms, and find new ways of optimizing risk, profitability, and customer experience. We’re looking for Data Scientists capable of using GenAI and other techniques to design, evangelize, and implement state-of-the-art solutions for never-before-solved problems. A key focus of this role is GenAI model customization using techniques such as fine-tuning and continued pre-training to help customers build differentiating solutions with their unique data. Key job responsibilities As a Data Scientist, you will: Collaborate with AI/ML scientists and architects to research, design, develop, and evaluate cutting-edge generative AI algorithms to address real-world challenges Interact with customers directly to understand the business problem, help and aid them in implementation of generative AI solutions, deliver briefing and deep dive sessions to customers and guide customer on adoption patterns and paths to production Create and deliver best practice recommendations, tutorials, blog posts, sample code, and presentations adapted to technical, business, and executive stakeholder Provide customer and market feedback to Product and Engineering teams to help define product direction About the team Sales, Marketing and Global Services (SMGS) AWS Sales, Marketing, and Global Services (SMGS) is responsible for driving revenue, adoption, and growth from the largest and fastest-growing small- and mid-market accounts to enterprise-level customers, including the public sector. The AWS Global Support team interacts with leading companies and believes that world-class support is critical to customer success. AWS Support also partners with a global list of customers that are building mission-critical applications on top of AWS services. The Professional Services team is part of Global Services. About AWS Diverse Experiences AWS values diverse experiences. Even if you do not meet all of the qualifications and skills listed in the job description, we encourage candidates to apply. If your career is just starting, hasn’t followed a traditional path, or includes alternative experiences, don’t let it stop you from applying. Why AWS? Amazon Web Services (AWS) is the world’s most comprehensive and broadly adopted cloud platform. We pioneered cloud computing and never stopped innovating — that’s why customers from the most successful startups to Global 500 companies trust our robust suite of products and services to power their businesses. Inclusive Team Culture Here at AWS, it’s in our nature to learn and be curious. Our employee-led affinity groups foster a culture of inclusion that empower us to be proud of our differences. Ongoing events and learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences, inspire us to never stop embracing our uniqueness. Mentorship & Career Growth We’re continuously raising our performance bar as we strive to become Earth’s Best Employer. That’s why you’ll find endless knowledge-sharing, mentorship and other career-advancing resources here to help you develop into a better-rounded professional. Work/Life Balance We value work-life harmony. Achieving success at work should never come at the expense of sacrifices at home, which is why we strive for flexibility as part of our working culture. When we feel supported in the workplace and at home, there’s nothing we can’t achieve in the cloud. We are open to hiring candidates to work out of one of the following locations: Arlington, VA, USA | Denver, CO, USA | Herndon, VA, USA | New York, NY, USA | Santa Clara, CA, USA | Seattle, WA, USA | Washington Dc, DC, USA